Infinite chains and antichains in computable partial orderings (Q2747728)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Infinite chains and antichains in computable partial orderings |
scientific article; zbMATH DE number 1658184
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Infinite chains and antichains in computable partial orderings |
scientific article; zbMATH DE number 1658184 |
Statements
5 September 2003
0 references
computable partial order
0 references
chain
0 references
antichain
0 references
arithmetic hierarchy
0 references
Infinite chains and antichains in computable partial orderings (English)
0 references
It is shown that any computable partial order on \(\mathbb N\) contains either an infinite chain that is a \(\Delta_2^0\) set or an infinite antichain that is a \(\Pi_2^0\) set. This result is proved to be optimal because an infinite computable order is constructed that has no infinite \(\Delta_2^0\) chain and no infinite \(\Delta_2^0\) antichain.
0 references
