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?
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1032553
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact