An Ordering of the set of Sentences of Peano Arithmetic
Arithmetical classification of the set of all provably recursive functions
The set of all indices of all functions provably recursive in any reasonable theory is shown to be recursively isomorphic to , where is -complete set.
Arithmetical transfinite induction and hierarchies of functions
We generalize to the case of arithmetical transfinite induction the following three theorems for PA: the Wainer Theorem, the Paris-Harrington Theorem, and a version of the Solovay-Ketonen Theorem. We give uniform proofs using combinatorial constructions.
Automorphisms of models of bounded arithmetic
We establish the following model-theoretic characterization of the fragment IΔ₀ + Exp + BΣ₁ of Peano arithmetic in terms of fixed points of automorphisms of models of bounded arithmetic (the fragment IΔ₀ of Peano arithmetic with induction limited to Δ₀-formulae). Theorem A. The following two conditions are equivalent for a countable model of the language of arithmetic: (a) satisfies IΔ₀ + BΣ₁ + Exp; (b) for some nontrivial automorphism j of an end extension of that satisfies IΔ₀. Here is the...
Axiomatization of the forcing relation with an application to Peano Arithmetic
Binumerability in a sequence of theories
Combinatorial principles concerning approximations of functions.
Completion closed algebras and models of Peano arithmetic
Consistency proof without transfinite induction for a formal system for turing machines.
Constructing Kripke models of certain fragments of Heyting's arithmetic.
Counting sets
Definability within structures related to Pascal’s triangle modulo an integer
Let Sq denote the set of squares, and let be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let . For every integer n ≥ 2 addition and multiplication are definable in the structures ⟨ℕ; Bn,⊥⟩ and ⟨ℕ; Bn,Sq⟩; thus their elementary theories are undecidable. On the other hand, for every prime p the elementary theory of ⟨ℕ; Bp,SQp⟩ is decidable.
Diagonal reasonings in mathematical logic
First we show a few well known mathematical diagonal reasonings. Then we concentrate on diagonal reasonings typical for mathematical logic.
Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen.
Equivalence relations induced by extensional formulae: classification by means of a new fixed point property
Finite sets and Gödel's incompleteness theorems [Book]
Fragments of complete extensions of PA and McDowell-Specker's theorem.
Gödel et la thèse de Turing
Cet article porte sur la discussion par Gödel de la thèse de Turing. Pour l’essentiel, nous présentons des notes inédites conservées dans les Archives Gödel, qui apportent des éléments nouveaux sur la relation ambiguë de Gödel à Turing. La première section examine la position qu’avait Gödel avant 1937 sur la possibilité d’une définition de la calculabilité. La deuxième concerne directement l’interprétation par Gödel de la thèse de Turing. Dans plusieurs passages, antérieurs à 1937, Gödel qualifie...
Goodstein's function.
Herbrand consistency and bounded arithmetic
We prove that the Gödel incompleteness theorem holds for a weak arithmetic Tₘ = IΔ₀ + Ωₘ, for m ≥ 2, in the form Tₘ ⊬ HCons(Tₘ), where HCons(Tₘ) is an arithmetic formula expressing the consistency of Tₘ with respect to the Herbrand notion of provability. Moreover, we prove , where is HCons relativised to the definable cut Iₘ of (m-2)-times iterated logarithms. The proof is model-theoretic. We also prove a certain non-conservation result for Tₘ.