Well-quasi-ordering hereditarily finite sets

Abstract

Hereditarily finite sets can be viewed as digraphs, when one interprets sets as vertices, and the membership relation among sets as the adjacency relation among vertices. We study three digraph containment relation (weak and strong immersion, subdivision) between such membership digraphs and subclasses of them, well-quasi-ordered by these three relations. More specifically, we strengthen and generalize our previous result concerning hereditarily finite well-founded sets. We show that only two conditions of the ones previously considered (slimness, requiring that every membership be necessary, and bounded cardinality) are enough for guaranteeing the well-quasi-ordering property. This is best possible, in the sense that neither of them can be dropped without losing the well-quasi-order property. Our proofs are given in a very general context requiring minimal set-theoretic assumptions, and in which slimness is translated as a graph-theoretic property. This allows us to conclude the well-quasi-ordering of an analogous class of non-well-founded sets, or hypersets.

Keywords:

• well-quasi-order
• hereditarily finite set
• subdivision
• extensional digraph
• hyperset

2010 AMS Subject Classifications:

• 05C20
• 97E60
• 05C83
• 03E05

Acknowledgements

We thank Giovanna D'Agostino for useful comments and suggestions. We are very grateful to one referee for suggesting that we can strengthen the claim of the main theorem present in the initial version of this paper. The second author acknowledges partial support from the European Science Foundation, activity ‘Games for Design and Verification’.