Hostname: page-component-8448b6f56d-cfpbc Total loading time: 0 Render date: 2024-04-16T22:25:05.274Z Has data issue: false hasContentIssue false
  • English
  • Français

Infinite chains and antichains in computable partial Orderings

Published online by Cambridge University Press:  12 March 2014

E. Herrmann
E. Herrmann*
Affiliation:
Institut für Mathematik, Humboldt University, Unter Den Linden 6, 10099 Berlin, Germany, E-mail: herrmann@mathematik.hu-berlin.de
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that every infinite computable partial ordering has either an infinite chain or an infinite antichain. Our main result is that this cannot be improved: We construct an infinite computable partial ordering that has neither an infinite chain nor an infinite antichain.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 66 , Issue 2 , June 2001 , pp. 923 - 934
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Herrmann, E., Recursively enumerable sets (the lattice structure and general properties of the recursively enumerable sets), to appear.Google Scholar
[2]Jockusch, C. G., Ramsey's theorem in recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[3]Slaman, T. A., Questions in recursion theory, London Mathematical Society Lecture Note Series, (1996), no. 224, pp. 333–346.Google Scholar
[4]Soare, R. I., Recursively enumerable sets and degrees, Perspectives in mathematical logic (Heidelberg), Springer Verlag, 1987.Google Scholar