Switch to: Citations

Add references

You must login to add references.
  1. Über eine bisher noch nicht benützte erweiterung Des finiten standpunktes.Von Kurt Gödel - 1958 - Dialectica 12 (3‐4):280-287.
    ZusammenfassungP. Bernays hat darauf hingewiesen, dass man, um die Widerspruchs freiheit der klassischen Zahlentheorie zu beweisen, den Hilbertschen flniter Standpunkt dadurch erweitern muss, dass man neben den auf Symbole sich beziehenden kombinatorischen Begriffen gewisse abstrakte Begriffe zulässt, Die abstrakten Begriffe, die bisher für diesen Zweck verwendet wurden, sinc die der konstruktiven Ordinalzahltheorie und die der intuitionistischer. Logik. Es wird gezeigt, dass man statt deesen den Begriff einer berechenbaren Funktion endlichen einfachen Typs über den natürlichen Zahler benutzen kann, wobei keine anderen (...)
    Download  
     
    Export citation  
     
    Bookmark   163 citations  
  • On the strength of Ramsey's theorem for pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
    We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...)
    Download  
     
    Export citation  
     
    Bookmark   56 citations  
  • On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
    We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for recursive formulas. (...)
    Download  
     
    Export citation  
     
    Bookmark   49 citations  
  • Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
    Download  
     
    Export citation  
     
    Bookmark   46 citations  
  • Combinatorial principles weaker than Ramsey's Theorem for pairs.Denis R. Hirschfeldt & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (1):171-206.
    We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for pairs (...)
    Download  
     
    Export citation  
     
    Bookmark   34 citations  
  • (1 other version)Mathematically strong subsystems of analysis with low rate of growth of provably recursive functionals.Ulrich Kohlenbach - 1996 - Archive for Mathematical Logic 36 (1):31-71.
    Download  
     
    Export citation  
     
    Bookmark   28 citations  
  • Note on the Fan theorem.A. S. Troelstra - 1974 - Journal of Symbolic Logic 39 (3):584-596.
    Download  
     
    Export citation  
     
    Bookmark   16 citations  
  • Elimination of Skolem functions for monotone formulas in analysis.Ulrich Kohlenbach - 1998 - Archive for Mathematical Logic 37 (5-6):363-390.
    In this paper a new method, elimination of Skolem functions for monotone formulas, is developed which makes it possible to determine precisely the arithmetical strength of instances of various non-constructive function existence principles. This is achieved by reducing the use of such instances in a given proof to instances of certain arithmetical principles. Our framework are systems ${\cal T}^{\omega} :={\rm G}_n{\rm A}^{\omega} +{\rm AC}$ -qf $+\Delta$ , where (G $_n$ A $^{\omega})_{n \in {\Bbb N}}$ is a hierarchy of (weak) subsystems (...)
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • (1 other version)On the arithmetical content of restricted forms of comprehension, choice and general uniform boundedness.Ulrich Kohlenbach - 1998 - Annals of Pure and Applied Logic 95 (1-3):257-285.
    In this paper the numerical strength of fragments of arithmetical comprehension, choice and general uniform boundedness is studied systematically. These principles are investigated relative to base systems Tnω in all finite types which are suited to formalize substantial parts of analysis but nevertheless have provably recursive functions of low growth. We reduce the use of instances of these principles in Tnω-proofs of a large class of formulas to the use of instances of certain arithmetical principles thereby determining faithfully the arithmetical (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations