Is Hyper-extensionality Preservable under Deletions of Graph Elements?


© 2016 The Authors. Published by Elsevier B.V.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.

Electronic Notes in Theoretical Computer Science