TOPICS
Search

Kreisel Conjecture


The Kreisel conjecture is a conjecture in proof theory that postulates that, if phi(x) is a formula in the language of arithmetic for which there exists a nonnegative integer k such that, for every nonnegative integer n, Peano arithmetic proves phi(n) in at most k steps, then Peano arithmetic proves its universal closure,  forall xphi(x).

A special case of the conjecture was proven true by M. Baaz in 1988 (Baaz and Pudlák 1993).


See also

Decidable

Portions of this entry contributed by Lorenzo Sauras-Altuzarra

Explore with Wolfram|Alpha

References

Baaz, M. and Pudlák P. "Kreisel's Conjecture for L exists _1." In Arithmetic, Proof Theory, and Computational Complexity, Papers from the Conference Held in Prague, July 2-5, 1991 (Ed. P. Clote and J. Krajiček). New York: Oxford University Press, pp. 30-60, 1993.Dawson, J. "The Gödel Incompleteness Theorem from a Length of Proof Perspective." Amer. Math. Monthly 86, 740-747, 1979.Kreisel, G. "On the Interpretation of Nonfinitistic Proofs, II." J. Sym. Logic 17, 43-58, 1952.Santos, P. G. and Kahle, R. "Variants of Kreisel's Conjecture on a New Notion of Provability." Bull. Sym. Logic 24, 337-350, 2021.

Referenced on Wolfram|Alpha

Kreisel Conjecture

Cite this as:

Sauras-Altuzarra, Lorenzo and Weisstein, Eric W. "Kreisel Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KreiselConjecture.html

Subject classifications