Chains and antichains in partial orderings

Archive for Mathematical Logic 48 (1):39-53 (2009)

Authors
Valentina Harizanov
George Washington University
Abstract
We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering ${\mathcal{A}}$ has the feature that for every ${\mathcal{B} \cong \mathcal{A}}$ , there is an infinite chain or antichain that is ${\Delta _{2}^{0}}$ relative to ${\mathcal{B}}$ , then we have uniform dichotomy: either for all copies ${\mathcal{B}}$ of ${\mathcal{A}}$ , there is an infinite chain that is ${\Delta _{2}^{0}}$ relative to ${\mathcal{B}}$ , or for all copies ${\mathcal{B}}$ of ${\mathcal{A}}$ , there is an infinite antichain that is ${\Delta _{2}^{0}}$ relative to ${\mathcal{B}}$
Keywords Mathematics   Algebra   Mathematics, general   Mathematical Logic and Foundations
Categories (categorize this paper)
DOI 10.1007/s00153-008-0114-2
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,164
Through your library

References found in this work BETA

Ramsey's Theorem and Recursion Theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
Infinite Chains and Antichains in Computable Partial Orderings.E. Herrmann - 2001 - Journal of Symbolic Logic 66 (2):923-934.

Add more references

Citations of this work BETA

Stability and Posets.Carl Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693 - 711.

Add more citations

Similar books and articles

Infinite Chains and Antichains in Computable Partial Orderings.E. Herrmann - 2001 - Journal of Symbolic Logic 66 (2):923-934.
Stability and Posets.Carl Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693 - 711.
Computing Maximal Chains.Alberto Marcone, Antonio Montalbán & Richard A. Shore - 2012 - Archive for Mathematical Logic 51 (5-6):651-660.
An Example Related to Gregory’s Theorem.J. Johnson, J. F. Knight, V. Ocasio & S. VanDenDriessche - 2013 - Archive for Mathematical Logic 52 (3-4):419-434.
Partitions of Large Rado Graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
Goodness in the Enumeration and Singleton Degrees.Charles M. Harris - 2010 - Archive for Mathematical Logic 49 (6):673-691.
Infinite Time Extensions of Kleene’s $${\Mathcal{O}}$$.Ansten Mørch Klev - 2009 - Archive for Mathematical Logic 48 (7):691-703.
Covering Properties of Ideals.Marek Balcerzak, Barnabás Farkas & Szymon Gła̧b - 2013 - Archive for Mathematical Logic 52 (3-4):279-294.
Additivity of the Two-Dimensional Miller Ideal.Otmar Spinas & Sonja Thiele - 2010 - Archive for Mathematical Logic 49 (6):617-658.
Embedding FD(Ω) Into {Mathcal{P}_s} Densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.

Analytics

Added to PP index
2013-11-23

Total views
36 ( #219,205 of 2,237,278 )

Recent downloads (6 months)
8 ( #193,109 of 2,237,278 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature