Computability-theoretic and proof-theoretic aspects of partial and linear orderings (Q1425651): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: D. Reed Solomon / rank | |||
Property / reviewed by | |||
Property / reviewed by: Jeffry L. Hirst / rank | |||
Property / author | |||
Property / author: D. Reed Solomon / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jeffry L. Hirst / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5606574 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5581652 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3964625 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4249724 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4249355 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4111536 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3773882 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Countable algebra and set existence axioms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective procedures in field theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ramsey's theorem and recursion theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ∏ 0 1 Classes and Degrees of Theories / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Effective content of field theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable Algebra, General Theory and Theory of Computable Fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5573961 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3949052 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3216704 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4220572 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extending partial orders to dense linear orders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4040892 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ordered Groups: A Case Study in Reverse Mathematics / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02783429 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2028592975 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:10, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Computability-theoretic and proof-theoretic aspects of partial and linear orderings |
scientific article |
Statements
Computability-theoretic and proof-theoretic aspects of partial and linear orderings (English)
0 references
17 March 2004
0 references
The authors examine the reverse mathematics and effective content of several variations of Szpilrajn's Theorem [\textit{E. Szpilrajn}, Fundam. Math. 16, 386--389 (1930; JFM 56.0843.02)]. A linear order type \(\tau\) is called {extendible} if every partial order containing no subchains of type \(\tau\) can be extended to a linear ordering containing no subchains of type \(\tau\). The main results of the paper are: (1) ``\(\omega ^*\) is extendible'' is provable in ACA\(_0\) and strictly stronger than WKL\(_0\); (2) ``\(\eta\) is extendible'' is provable in \(\Pi^1_1\)-CA\(_0\), but not in WKL\(_0\); and (3) ``\(\zeta\) is extendible'' is equivalent to ATR\(_0\). Here \(\omega^*\) is \(\omega\) with the reverse order, \(\eta\) is the order type of the rationals, and \(\zeta\) is the order type of the integers. For a survey of linear extensions of partial orderings, see \textit{R. Bonnet} and \textit{M. Pouzet}'s paper ``Linear extensions of ordered sets'' [in: I. Rival (ed.), Ordered sets, Proc. NATO Adv. Study Inst., Banff/Can. 1981, 125--170 (1982; Zbl 0499.06002)]. For background on computability-theoretic aspects of linear orderings, see \textit{R. G. Downey}'s paper ``Computability theory and linear orderings'' [in: Yu. L. Ershov et al. (eds.), Handbook of recursive mathematics. Vol. 2. Recursive algebra, analysis and combinatorics. Amsterdam: Elsevier. Stud. Logic Found. Math. 139, 823--976 (1998; Zbl 0941.03045)].
0 references
reverse mathematics
0 references
proof theory
0 references
effective content
0 references
Szpilrajn's theorem
0 references
linear ordering
0 references
partial ordering
0 references
combinatorics
0 references