Is Hyper-extensionality Preservable Under Deletions of Graph Elements?
Alberto Casagrande, Carla Piazza, Alberto Policriti · Electronic Notes in Theoretical Computer Science · 2016
Any hereditarily finite set S can be represented as a finite pointed graph –dubbed membership graph– whose nodes denote elements of the transitive closure of { S } and whose edges model the membership relation. Membership graphs must be hyper-extensional, that is pairwise distinct nodes are not bisimilar and (uniquely) represent hereditarily finite sets. We will see that the removal of even a single node or edge from a membership graph can cause “collapses” of different nodes and, therefore, the loss of hyper-extensionality of the graph itself. With the intent of gaining a deeper understanding on the class of hyper-extensional hereditarily finite sets, this paper investigates whether pointed hyper-extensional graphs always contain either a node or an edge whose removal does not disrupt the hyper-extensionality property.