This paper contains detailed description of two consistency proofs, which state that in the system called Peano arithmetic no contradiction can be obtained. The proofs were first published in 1936 and 1938 by the German mathematician Gerhard Gentzen. For the purpose of this paper, the proofs were read and studied from the original articles called "Die Widerspruchsfreiheit der reinen Zahlentheorie" and "Neue Fassung des Widerspruchsfreiheitsbeweises für die reine Zahlentheorie". The first mentioned proof is interesting from the historical point of view. Gentzen used a natural deduction sequent calculus and ordinal numbers in an unusual form he invented. The second proof is similar to the consistency proof, which is commonly known as a consistency proof for Peano arithmetic nowadays.

The aim of this thesis is Russell's analysis of Peano arithmetic. This analysis was presented by Russell and A. N. Whitehead in the book Prin- cipia Mathematica and then in Russell's book Introduction to Mathema- tical Philosophy which provided this approach in a more accessible form. The thesis focuses on Russell's critique of original Peano axioms and his effort to use only logical definitions instead of axioms. Another goal of the thesis is Russell's theory of classes and substitution of classes by propositional functions. Furthermore, the type theory for propositional functions is introduced and explained. All is converted into present-day logical notation. Moreover, the non-standard models of Russell's Peano arithmetic are studied. Finally, there are two particular arithmetic exam- ples illustrating the purposes of the thesis. Key words Bertrand Russell, Peano Arithmetic, classes, propositional funkction

This thesis examines the method of forcing in set theory and focuses on aspects that are set aside in the usual presentations or applications of forcing. It is shown that forcing can be formalized in Peano arithmetic (PA) and that consis- tency results obtained by forcing are provable in PA. Two ways are presented of overcoming the assumption of the existence of a countable transitive model. The thesis also studies forcing as a method giving rise to interpretations between theories. A notion of bi-interpretability is defined and a method of forcing over a non-standard model of ZFC is developed in order to argue that ZFC and ZF are not bi-interpretable. 1

of doctoral thesis Study of Arithmetical Structures and Theories with Regard to Representative and Descriptive Analysis Petr Glivický We are motivated by a problem of understanding relations between local and global properties of an operation o in a structure of the form B, o , with regard to an application for the study of models B, · of Peano arithmetic, where B is a model of Presburger arithmetic. We are particularly interested in a dependency problem, which we formulate as the problem of describing the dependency closure iclO (E) = {d ∈ Bn ; (∀o, o ∈ O)(o E = o E ⇒ o(d) = o (d))}, where B is a structure, O a set of n-ary operations on B, and E ⊆ Bn. We show, that this problem can be reduced to a definability question in certain expansion of B. In particular, if B is a saturated model of Presburger arithmetic, and O is the set of all (saturated) Peano products on B, we prove that, for a ∈ B, iclO ({a}×B) is the smallest possible, i.e. it contains just those pairs (d0, d1) ∈ B2 for which at least one of di equals p(a), for some polynomial p ∈ Q[x]. We show that the presented problematics is closely connected to the descriptive analysis of linear theories. That are theories, models of which are - up to a change of the language - certain discretely ordered modules over specific discretely ordered...

The thesis consists of two parts. The first one deals with Gentzen's consistency proof of 1935, especially with the impact of his cut elimination strategy on the complexity of the proof. Our analysis of Gentzen's cut elimi- nation strategy, which eliminates uppermost cuts regardless of their comple- xity, yields that, in his proof, Gentzen implicitly applies transfinite induction up to Φω(0) where Φω is the ω-th Veblen function. This is an upper bound and Φω(0) represents an upper bound on heights of cut-free infinitary deriva- tions that Gentzen constructs for sequents derivable in Peano arithmetic (PA). We currently do not know whether this is a lower bound too. The first part also contains a formalization of Gentzen's proof of 1935. Based on the formalization, we see that the transfinite induction mentioned above is the only principle used in the proof that exceeds PA. The second part compares the performance of Gentzen's and Tait's cut elimi- nation strategy in classical propositional logic. Tait's strategy reduces the cut-rank of the derivation. Since the propositional logic does not use inference rules with eigenvariables, we managed to organize the cut elimination in the way that both strategies yield identical cut-free derivations in classical propositional logic.

Cette thèse étudie deux modèles de réalisabilité pour la logique classique construits sur la sémantique des jeux HO, interprétant la logique, l'arithmétique et l'analyse classiques directement par des programmes manipulant un espace de stockage d'ordre supérieur.La non-innocence en jeux HO autorise les références d'ordre supérieur, et le non parenthésage révèle la CPS des jeux HO et fournit une catégorie de continuations dans laquelle interpréter le lambda-mu calcul de Parigot. Deux modèles de réalisabilité sont construits sur cette interprétation calculatoire directe des preuves classiques.Le premier repose sur l'orthogonalité, comme celui de Krivine, mais il est simplement typé et au premier ordre. En l'absence de codage de l'absurdité au second ordre, une mu-variable libre dans les réaliseurs permet l'extraction. Nous définissons un bar-récurseur et prouvons qu'il réalise l'axiome du choix dépendant, utilisant deux conséquences de la structure de CPO du modèle de jeux: toute fonction sur les entiers (même non calculable) existe dans le modèle, et toute fonctionnelle sur des séquences est Scott-continue. La bar-récursion est habituellement utilisée pour réaliser intuitionnistiquement le « double negation shift » et en déduire la traduction négative de l'axiome du choix. Ici, nous réalisons directement l'axiome du choix dans un cadre classique.Le second, très spécifique au modèle de jeux, repose sur des conditions de gain: des ensembles de positions d'un jeu munis de propriétés de cohérence. Un réaliseur est alors une stratégie dont les positions sont toutes gagnantes. / This thesis investigates two realizability models for classical logic built on HO game semantics. The main motivation is to have a direct computational interpretation of classical logic, arithmetic and analysis with programs manipulating a higher-order store.Relaxing the innocence condition in HO games provides higher-order references, and dropping the well-bracketing of strategies reveals the CPS of HO games and gives a category of continuations in which we can interpret Parigot's lambda-mu calculus. This permits a direct computational interpretation of classical proofs from which we build two realizability models.The first model is orthogonality-based, as the one of Krivine. However, it is simply-typed and first-order. This means that we do not use a second-order coding of falsity, and extraction is handled by considering realizers with a free mu-variable. We provide a bar-recursor in this model and prove that it realizes the axiom of dependent choice, relying on two consequences of the CPO structure of the games model: every function on natural numbers (possibly non computable) exists in the model, and every functional on sequences is Scott-continuous. Usually, bar-recursion is used to intuitionistically realize the double negation shift and consequently the negative translation of the axiom of choice. Here, we directly realize the axiom of choice in a classical setting.The second model relies on winning conditions and is very specific to the games model. A winning condition is a set of positions in a game which satisfies some coherence properties, and a realizer of a formula is then a strategy which positions are all winning.