45
Views
2
CrossRef citations to date
0
Altmetric
Section A

Well-quasi-ordering hereditarily finite sets

&
Pages 1278-1291 | Received 04 Sep 2011, Accepted 26 Nov 2012, Published online: 07 Mar 2013
 

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.

2010 AMS Subject Classifications:

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’.

Log in via your institution

Log in to Taylor & Francis Online

PDF download + Online access

  • 48 hours access to article PDF & online version
  • Article PDF can be downloaded
  • Article PDF can be printed
USD 61.00 Add to cart

Issue Purchase

  • 30 days online access to complete issue
  • Article PDFs can be downloaded
  • Article PDFs can be printed
USD 1,129.00 Add to cart

* Local tax will be added as applicable

Related Research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.