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 the normal view instead:
scientific article; zbMATH DE number 1658184
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.9268029928207396
0 references
0.8030240535736084
0 references
0.7927588820457458
0 references
0.7728304862976074
0 references
0.7700842618942261
0 references
