Computability-theoretic and proof-theoretic aspects of partial and linear orderings (Q1425651): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Set OpenAlex properties.
 
(5 intermediate revisions by 4 users not shown)
Property / author
 
Property / author: D. Reed Solomon / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Jeffry L. Hirst / rank
Normal 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 / namelinks / 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
    0 references
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references