Formal Theories of Truth and Nonstandard Models of Arithmetic

W załączniku

In this dissertation we study certain model-theoretic properties of formal theories of truth in the context of the debate on the so-called de ationism about truth and some computability-theoretic properties of nonstandard models of arithmetic and their presentations in the context of the debate on the distinguishability of the intended model of arithmetic. Further, we investigate the relation between the arithmetical and the truth-theoretic structures of models of su ciently strong theories. Finally, we examine certain nitistic solutions to Yablo's antinomy under the modal interpretation of quanti ers. The main mathematical results of the thesis are that: The axiomatic theory TB of local disquotational truth is not semantically conservative over any complete extension of PA. Any model Mj= PA has an elementary (nonstandard) extension K which is expandable to a model of TB, but not recursively saturated. No nonstandard model of PA has a computable quotient presentation by a computably enu- merable equivalence relation, even in the restricted (but fully expressive) language f+; g with only addition and multiplication: there is no computable structure (N; ; ) and a computably enumerable equivalence relation E, which is a congruence with respect to this structure, such that the quotient (N; ; )=E is a nonstandard model of PA. No nonstandard model of arithmetic in the language f+; ; g has a computably enumerable quotient presentation by any equivalence relation, of any complexity. That is, there is no com- putably enumerable structure hN; ; ;Ei, where and are computable binary operations and E is a computably enumerable relation, and an equivalence relation E that is a congru- ence with respect to that structure, such that the quotient hN; ; ;Ei=E is a nonstandard model of arithmetic in the language f+; ; g. There is no computable structure hN; ; i and a co-computably enumerable equivalence relation E, which is a congruence with respect to this structure, such that the quotient hN; ; i=E is a nonstandard model of true arithmetic. There is no computable structure hN; ; i and a co-computably enumerable equivalence relation E, which is a congruence with respect to this structure, such that the quotient hN; ; i=E is a 1-sound nonstandard model of arithmetic, or even merely a nonstandard model of arithmetic with 00 in the Standard System of the model. A corollary of this is actually a strengthening of the form: no nonstandard model of arithmetic in the language f+; ; 0; 1;<g and with 00 in its Standard System has a computably enumerable quotient presentation by any equivalence relation, of any complexity. No model of ZFC has a computable quotient presentation. That is, there is no computable relation and equivalence relation E, a congruence with respect to , for which the quotient hN; i=E is a model of ZFC or even considerably weaker set theories. There is no computably enumerable relation with a co-computably enumerable equivalence relation E respecting it for which hN; i=E is a model of set theory. 1 There is no computable relation and equivalence relation E, a congruence with respect to , of any complexity, such that the quotient hN; i=E is a nonstandard model of nite set theory ZF:1. There is no computably enumerable relation with a co-computably enumerable equivalence relation E respecting it for which hN; i=E is a nonstandard model of nite set theory ZF:1. There exists a nonstandard model M j= PA such that M = hN; ; ; S; 0; 1i=E; where hN; ; ; S; 0; 1i is computable and E is 01 , i.e., it is a complement of a computably enumerable set (co-c.e.). For any theory T interpreting PA and de ning arithmetical truth TA and for any !-nonstandard model M j= T with countable NM there is a model M0 such that: 1. M = M0 2. NM = NM0 (the natural numbers of the models agree), 3. TAM 6= TAM0 i.e. the models disagree on their theories of arithmetical truth. Let msl(FM(N)) denote the msl theory (i.e. the sl-theory of the FM-domain of natural numbers with the modal interpretation of quanti ers). Then we have: msl(FM(N)) = Th(N). There is no FM(N)Y -domain such that YD msl(FM(N)Y ). For any second-order arithmetical formula the following are equivalent: 1. 2 msl(FM((N2))), 2. (N;Pfin(N)) j= , where Pfin(N) denotes the family of all nite subsets of natural numbers. The main philosophical consequences of these results are that: Under the assumption that semantic conservativitity is an acceptable criterion for a de a- tionary axiomatic theory of truth, the inductive theory of local disquotation is excluded as a de ationary theory over any completion of arithmetic. Distinguishing the standard model of arithmetic by an argument from Tennenbaum's Theorem cannot be achieved and that not only the argument-from-Tennenbaum's-theorem does not work due to conceptual issues, but that in the context of computable quotient presentations of rst-order structures the theorem itself simply does not hold. The determinateness of the arithmetical structure is not a su cient condition for determi- nateness of the arithmetical truth. Formalizing the foundations of arithmetic in a nonstandard nitistic manner does not save us from some semantic antinomies, if the formalization is performed in a way preserving the true arithmetic.