- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Infinite chains and antichains in computable partial orderings
Journal of Symbolic Logic 66 (2):923-934 (2001)
Abstract
We show that every infinite computable partial ordering has either an infinite Δ 0 2 chain or an infinite Π 0 2 antichain. Our main result is that this cannot be improved: We construct an infinite computable partial ordering that has neither an infinite Δ 0 2 chain nor an infinite Δ 0 2 antichainOther Versions
No versions found
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Chains and antichains in partial orderings.Valentina S. Harizanov, Carl G. Jockusch & Julia F. Knight - 2009 - Archive for Mathematical Logic 48 (1):39-53.
Stability and Posets.Carl G. Jockusch, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693-711.
Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
Interpreting true arithmetic in the Δ 0 2 -enumeration degrees.Thomas F. Kent - 2010 - Journal of Symbolic Logic 75 (2):522-550.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
Degree spectra of relations on computable structures in the presence of Δ 2 0 isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697-720.
A note on partial numberings.Serikzhan Badaev & Dieter Spreen - 2005 - Mathematical Logic Quarterly 51 (2):129-136.
On Ramsey choice and partial choice for infinite families of n -element sets.Lorenz Halbeisen & Eleftherios Tachtsis - 2020 - Archive for Mathematical Logic 59 (5-6):583-606.
Effective powers of Ω over δ 2 cohesive sets and infinite π 1 sets without δ 2 cohesive subsets.Paul Shafer - forthcoming - Journal of Symbolic Logic:1-26.
(Extra)Ordinary Equivalences with the Ascending/Descending Sequence Principle.Marta Fiori-Carones, Alberto Marcone, Paul Shafer & Giovanni Soldà - 2024 - Journal of Symbolic Logic 89 (1):262-307.
Analytics
Added to PP
2009-01-28
Downloads
133 (#335,368)
6 months
36 (#234,303)
2009-01-28
Downloads
133 (#335,368)
6 months
36 (#234,303)
Historical graph of downloads
Citations of this work
Reverse mathematics and the equivalence of definitions for well and better quasi-orders.Peter Cholak, Alberto Marcone & Reed Solomon - 2004 - Journal of Symbolic Logic 69 (3):683-712.
Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
THE REVERSE MATHEMATICS OF ${\mathsf {CAC\ FOR\ TREES}}$.Julien Cervelle, William Gaudelier & Ludovic Patey - 2024 - Journal of Symbolic Logic 89 (3):1189-1211.
Chains and antichains in partial orderings.Valentina S. Harizanov, Carl G. Jockusch & Julia F. Knight - 2009 - Archive for Mathematical Logic 48 (1):39-53.
Preface.Douglas Cenzer, Valentina Harizanov, David Marker & Carol Wood - 2009 - Archive for Mathematical Logic 48 (1):1-6.
Try MATCHA Writer if you're interested in citing directly from PhilPapers and certifying your authorship.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation