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?
Hyper-Extensionality and One-Node Elimination on Membership Graphs
PIAZZA, Carla;POLICRITI, Alberto;
2014-01-01
Abstract
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?I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
