Hyper-Extensionality and One-Node Elimination on Membership Graphs


A (hereditarily finite) set/hyperset S can be completely depicted by a (finite pointed) graph GS—dubbed its membership graph— in which every node represents an element of the transitive closure of S and every arc represents a membership relation holding between its source and its target. In a membership graph different nodes must have different sets of successors and, more generally, if the graph is cyclic no bisimilar nodes are admitted. We call such graphs hyper-extensional. Therefore, the elimination of even a single node in a membership graph can cause different nodes to “collapse” (becoming representatives of the same set/hyperset) and the graph to loose hyper-extensionality and its original membership character. In this note we discuss the following problem: given S is it always possible to find a node s in GS whose deletion does not cause any collapse?

Proceedings of the 29th Italian Conference on Computational Logic