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.

Publication
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Related