Metalogical Properties of Yablo Sequences

Uniwersytet Warszawski Wydział Filozofii i Socjologii Michał Tomasz Godziszewski Nr albumu: 276868

Metalogical properties of Yablo sequences Metalogiczne własności ciągów Yablo

Praca magisterska na kierunku Filozofia w zakresie Logika

Praca wykonana pod kierunkiem dr hab. Cezarego Cieślińskiego Instytut Filozofii, Uniwersytet Warszawski

Warszawa, lipiec 2013

1

Oświadczenie kierującego pracą Oświadczam, że niniejsza praca została przygotowana pod moim kierunkiem i stwierdzam, że spełnia ona warunki do przedstawienia jej w postępowaniu o nadanie tytułu zawodowego.

Data

Podpis kierującego pracą

Oświadczenie autora pracy Świadom odpowiedzialności prawnej oświadczam, że niniejsza praca dyplomowa została napisana przez mnie samodzielnie i nie zawiera treści uzyskanych w sposób niezgodny z obowiązującymi przepisami. Oświadczam również, że przedstawiona praca nie była wcześniej przedmiotem procedur związanych z uzyskaniem tytułu zawodowego w wyższej uczelni. Oświadczam ponadto, że niniejsza wersja pracy jest identyczna z załączoną wersją elektroniczną.

Data

Podpis autora pracy

3

Abstract The thesis discusses metalogical properties of Yablo sequences introduced by S. Yablo in [75]. In natural language, Yablo sequence, taken together with certain truth principles, leads to a paradox. By the result of G. Priest from [62] Yablo sentences provably exist in sufficiently rich formal theories. J. Ketland showed in [46] that the theory P AT − (Peano Arithmetic in the language extended with a truth predicate T r and induction scheme restricted to arithmetical formulae) with adjoined local disquotation principles for arithmetical sentences (AD) and Yablo sentences (Y D), is consistent, yet ω-inconsistent. We prove that the theory P AT + AD + Y D (with induction scheme for all formulae of the extended language) is also consistent. L.M. Picollo showed in [60] that rewriting of Yablo sequence to second-order language gives an unsatisfiable, yet still not inconsistent theory. We prove that there is a subsystem of second-order arithmetic (ACA0 ) which has a model satisfying Y D. We prove that for any partial fixed-point model in the meaning defined by S. Kripke in [48], the truth-value of every Yablo sentence Y (n) is indeterminate under Strong Kleene, Weak Kleene and Supervaluation valuation schema. We prove that under the logic Lsl of sufficiently large finite models, defined by M. Mostowski in [58], for any class K of finite models, if K |=sl Y D, then K |=sl ¬Y (n) for any n ∈ ω. We show the construction of such a class, basing on the notion of F M -domain, introduced by M. Mostowski in [55]. We also give the results of C. Cieślinski from [18] on Yablo sentences in axiomatic truth theories. As corollaries, we propose new possible solutions to Yablo paradox. Streszczenie Praca omawia metalogiczne własności ciągów Yablo wprwadzonych przez S. Yablo w [75]. W języku naturalnym, ciąg Yablo wraz z pewnymi zasadami prawdziwościowymi prowadzi do paradoksu. Na mocy wyniku G. Priesta z [62], zdania Yablo dowodliwie istnieją w dostatecznie bogatych teoriach formalnych. J. Ketland wykazał w [46], że teoria P AT − (Arytmetyka Peano w języku rozszerzonym o predykat prawdy T r i ze schematem indukcji ograniczonym do formuł arytmetycznych) wraz z lokalnymi zasadami dyskwotacyjnymi dla zdań arytmetycznych (AD) oraz zdań Yablo (Y D), jest niesprzeczna, lecz ω-sprzeczna. Dowodzimy, że P AT +AD +Y D (ze schematem indukcji dla wszystkich formuł rozszerzonego języka) także jest niesprzeczna. L.M. Picollo wykazała w [60], że przepisanie ciągu Yablo do języka drugiego rzędu daje niesprzeczną, lecz niespełnialną teorię. Dowodzimy, że istnieje podsystem arytmetyki drugiego rzędu (ACA0 ), ktory ˙ ma model spełniający Y D. Dowodzimy, że dla dowolnego częściowego modelu punktu stałego w sensie zdefiniowanym przez S. Kripkego w [48], wartość logiczna każdego zdania Yablo Y (n) jest nieokreślona przy schematach: silny Kleene, słaby Kleene, superwaluacje. Dowodzimy, że w logice Lsl dostatecznie dużych modeli skończonych, zdefiniowanej przez M. Mostowskiego w [58], dla każdej klasy K modeli, jeśli K |=sl Y D, to K |=sl ¬Y (n) dla każdego n ∈ ω. Pokazujemy konstrukcję takiej klasy, opierając się na pojęciu F M -dziedziny, wprowadzonym przez M. Mostowskiego w [55]. Podajemy wyniki C. Cieślinskiego z [18] na temat zdań Yablo w aksjomatycznych teoriach prawdy. Jako wnioski, podajemy propozycje nowych możliwych rozwiązań paradoksu Yablo. Keywords Yablo sequences, Yablo paradox, nonstandard models of arithmetic, ω-inconsistency, second-order arithmetic, many-valued logic, partial models, finite structures, F M -domains, axiomatic theories of truth.

Dziedzina pracy (kody wg programu Socrates-Erasmus) 08100 5

Doctor Emmett Brown: Great Scott! Your other self will miss the lightning bolt at the clocktower, you won’t get back to the future and we’ll have a major paradox! Marty McFly: Wait, wait, a paradox? You mean one of those things that could destroy the universe? Doctor Emmett Brown: Precisely! Back to the Future − Part II R. Zemeckis, 1989. 7

Contents 1 Introduction 1.1 Definitions of paradox and antinomy . 1.2 Examples of paradoxes and antinomies 1.2.1 Logical paradoxes . . . . . . . 1.2.2 Semantic antinomies . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

10 10 11 11 12

2 Truth and Arithmetic 2.1 Representability, arithmetization and diagonalization 2.1.1 Language and axioms . . . . . . . . . . . . . 2.1.2 Representability . . . . . . . . . . . . . . . . 2.1.3 Arithmetization and diagonal lemma . . . . . 2.2 Limitations of the notion of truth . . . . . . . . . . . 2.2.1 Definability of truth . . . . . . . . . . . . . . 2.3 Kripke’s theory of truth . . . . . . . . . . . . . . . . 2.4 Nonstandard models of arithmetic . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

15 15 15 16 20 22 22 29 33

. . . . . . . . . . . . .

40 40 40 41 42 47 49 49 54 57 59 61 63 64

. . . .

69 69 69 71 72

. . . .

. . . .

. . . .

3 Yablo Sequences 3.1 Yablo paradox and arithmetization of Yablo 3.1.1 Infinite liar . . . . . . . . . . . . . . 3.1.2 Existence of Yablo sequences . . . . 3.2 Consistency of Yablo sequences . . . . . . . 3.3 Yablo sequences in second-order languages . 3.4 Yablo paradox in axiomatic truth theories . 3.4.1 Friedman-Sheard Theory . . . . . . 3.4.2 Kripke-Feferman Theory . . . . . . . 3.5 Yablo paradox in partial semantics . . . . . 3.5.1 Weak Kleene . . . . . . . . . . . . . 3.5.2 Strong Kleene . . . . . . . . . . . . . 3.5.3 Supervaluations . . . . . . . . . . . . 3.6 Yablo sequences in Lsl . . . . . . . . . . . . 4 Summary 4.1 Summary of results . . . . . . . . . . . . . . 4.2 Sources of the properties of Yablo sequences 4.3 Possible solutions to Yablo paradox . . . . . 4.4 Other questions concerning Yablo sequences

9

. . . .

. . . .

. . . .

. . . .

sentences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

. . . . . . . . . . . . .

. . . .

1

Introduction

This thesis is devoted to analysis of the metalogical properties of the so-called Yablo sequences. These are infinite sequences of a certain type of sentences, that are a formalisation of the sentences introduced by S. Yablo in [75], such that taken together they lead to a paradoxical conclusion that none of them can be true or false. What is this sequence exactly? Let us imagine an infinite, countable, numbered list of sentences such that for every natural number n the nth sentence says: For each number k bigger than n, the k th sentence is not true. So, the first sentence on the list says that all of the sentences, beginning with the second one, are not true. The second one says that all of the sentences, beginning with the third one, are not true. And so on - to infinity. Obviously, any sentence has to be either true or false. Can any sentence from our list be true? Let us assume that there is a natural number m such that, the mth sentence is true. For a sentence to be true plausibly seems to mean that the things are just as the sentence states them to be. So, from our assumption we get that for any number k bigger than m, the k th sentence is not true. What does it mean? In particular, it means that the (m + 1)th sentence is false and that for any number k bigger than m + 1 the k th sentence is not true. But the proposition that for any number k bigger than m + 1 the k th sentence is not true is precisely what the (m + 1)th sentence says. So it must be true. But we have just derived that the (m + 1)th sentence is false. So, from the premise that for some m the mth sentence is true we got to contradiction. This means than all of the sentences on the list have to be false. In particular, the 23rd sentence is false. It means that what it says, does not hold. So it is not the case that for any number k bigger than 23, the k th sentence is false. Therefore, the negation of this sentence holds: at least one of the sentences on the list subsequent to the 23rd sentence is true. But we have just established that each sentence on the list has to be false. This is a contradiction. This semantic paradox was introduced as a positive answer to a question if a phenomenon of self-reference could be avoided in deriving semantic paradoxes, and whether there are genuine contradictions that arise from ungroundedness. Let us notice that at least prima facie there is no self-reference anywhere in the sentences we just derived the paradox from. Each of those sentences referred only to the subsequent sentences and not explicitly to itself. So, apart from the general question how to solve the paradox, one might also ask what is the source of this paradox, if not self-reference. Before we proceed to the detailed analysis of the properties of Yablo sentences and Yablo paradox, let us give some general, introductory remarks.

1.1

Definitions of paradox and antinomy

What is a paradox? Typically, we use the word to name either a seemingly sound or valid reasoning that leads to an unacceptable conclusion or an unacceptable conclusion of a seemingly sound or valid reasoning. In both meanings, it is a situation in which we are dealing with a certain type of argument. In particular, as e.g. R.T. Cook explains in ([22], p. 9) it is an argument that: (a) Begins with premises that seem uncontroversially true. (b) Proceeds via reasoning that seems uncontroversially valid.

10

(c) Arrives at a conclusion that is a contradiction, is false or is otherwise absurd, inappropriate, or unacceptable.1 A concept related to the notion of paradox, is antinomy. As again R.T. Cook puts it in ([22], p. 14) an antinomy is a pair of arguments such that: (a) Each argument begins with premises that seem uncontroversially true. (b) Each argument proceeds via reasoning that seems uncontroversially valid. (c) The conclusions of the arguments are incompatible with each other. For the purpose of our considerations, it is not necessary to keep a strict distinction between paradoxes and antinomies, therefore we will not treat them as separate categories.

1.2

Examples of paradoxes and antinomies

We will here consider some famous examples of modern paradoxes. Before turning to that, let us declare that we follow Frank Ramsey’s distinction between semantic antinomies - such that their formulation requires semantic notions like meaning, naming or truth and logical ones the formulation of which does not demand the use of the notions above. 1.2.1

Logical paradoxes

1. Russell’s paradox. Russell’s paradox is the most famous of the logical or set-theoretical paradoxes. The paradox arises within naive set theory - let us consider the set of all such sets that are not elements of themselves. Namely let: ∆ = {x : x ∈ / x}. By the law of excluded middle, the set ∆ is a member of itself or it is not a member of itself. So: (a) ∆ ∈ ∆ or (b) ∆ ∈ / ∆. Assume (a). Then, by the definition of ∆, ∆ does not belong to ∆, which is a contradiction. Therefore (b) has to hold. So ∆ ∈ / ∆. This means that ¬(∆ ∈ ∆) which by the definition gives that: ¬(∆ ∈ / ∆), hence: ∆ ∈ ∆. Hence we obtain a paradox.2 1

It is worth noting that other definitions of the notion of paradox have also been offered. For example, R. Sorensen in [69] gives the following wide definition of the concept of paradox: I take paradoxes to be riddles. The oldest philosophical questions evolved from folklore and show vestiges of the verbal games that generated them. ([69], p. 3) The riddle theory of paradox allows for the possibility of meaningless paradoxes. Riddles need only appear to be genuine questions; they can instead be meaningless utterances that look like questions. Pseudoquestions need only appear to have good answers and so need only appear to have an overabundance of good answers. ([69], p. 36) What is important here is that Sorensen implies that some paradoxes may not have any sound solution. For more detailed observations on the wide sense, see ([22], p. 10). 2 This paradox has some particularly nice natural-language interpretations. Two of them are the following: (a) Barber’s paradox: consider a village and a barber such that he shaves all and only those men who do not shave themselves. Does the barber shave himself? (b) Catalogue paradox: consider a library which compiles a bibliographic catalogue of all and only those catalogues which do not list themselves. Then does the library’s catalogue list itself?

11

2. Cantor’s paradox. Let us consider the set Σ of all sets. So there can be no sets that are not in Σ. However, by Cantor’s theorem, Σ has more subsets than it has elements, so there must be some sets that are not in Σ. Hence a paradox. 3. Burali-Forti’s paradox. An ordinal number is the order-type of a well-ordered set. For the purposes of this section, it may be understood in the following way: ∅ is an ordinal number and for any ordinal number α, the successor of α - i.e. the set α ∪ {α} is also an ordinal number. A limit ordinal is an ordinal number which is neither an empty set nor a successor ordinal, i.e. λ is a limit ordinal if and only if there is an ordinal less than λ and whenever β is an ordinal less than λ, then there exists an ordinal γ such that β < γ < λ. Now, it can be proved in set theory that every well-ordered set has a unique ordinal number, that every initial segment of ordinals (i.e., any set of ordinals arranged in natural order which contains all the predecessors of each of its elements) has an ordinal number which is greater than any ordinal in the segment, the set of all ordinal numbers is an ordinal number itself. S Let us consider a set Ω of all ordinal numbers. Therefore β = Ω is an ordinal number. However, S β ∪ {β} is also an ordinal number. So β ∪ {β} ∈ Ω and β ∈ β ∪ {β}. So β ∈ Ω = β, which is impossible. Actually, all of the three above-mentioned paradoxes have been resolved by modern mathematics - the answer to Russell’s paradox has been an axiomatisation of set theory and restricting the comprehension axiom scheme. An answer to Cantor’s paradox is that there is no set of all sets. The answer to Burali-Forti’s paradox is similar: there is no set of all ordinals. Both of the abovementioned are the so-called proper classes, i.e. such collection of sets that are not sets themselves (it is worth noting, that in Zermelo-Fraenkel set theory the notion of class is informal). 1.2.2

Semantic antinomies

As it was already mentioned, semantic antinomies are antinomies such that their formulation requires the use of semantic notions. The most famous semantic antinomy is: 1. Liar paradox. Let λ denote a sentence that says of itself: λ is not true. It has to be either true or false. If it is true, then things are as it says. So it holds that λ is not true. This is a contradiction. Therefore, λ must be false. Then it is not the case that λ is not true. This means that λ is true. Hence a paradox. For further, detailed discussion of the liar paradox, see e.g. Barwise [3] and Beall [7]. 2. Grelling’s paradox. We say that a word is autological if it has the property it designates, or as to denote it: the word pwq is autological if it has the property w. For example the word pEnglishq is an English word. So it is autological. If a word is not autological, we say it is heterological. Let us consider the word: pheterologicalq. There are two exclusive possibilities: either pheterologicalq is heterological or it is autological. Let us assume that pheterologicalq is heterological. Then, by definition it is autological, so it is not heterological. Therefore, pheterologicalq has to be autological. Then, by definition it is heterological, and hence it is not autological. This gives a paradox. For more information on heterologicality and interesting discussion of its applications, see Cieślinski [14]. 3. Richard’s paradox. Let Γ be the set of all infinite decimal expansions of real numbers that can be designated in a finite 12

√ number of words (e.g. 2, having an infinite decimal expansion can be designated as a number that is the ratio between the diagonal and the side of the square). Since these designations are made up of a finite number of words, they form an enumerable set. Let us fix their enumeration: x0 = x00 .x01 x02 x03 x04 ...x0k ... x1 = x10 .x11 x12 x13 x14 ...x1k ... x2 = x20 .x21 x22 x23 x24 ...x2k ... x3 = x30 .x31 x32 x33 x34 ...x3k ... ... xk = xk0 .xk1 xk2 xk3 xk4 ...xkk ... ... Now, basing on this enumeration let us define a real number with the following decimal expansion: y = y0 .y1 y2 y3 y4 ...ym ... where for all n we have: yn =

 x

nn

+1

0

ifxnn 6= 9 ifxnn = 9.

Consider number y. It has just been designated in a finite number of words, hence there exist a number m such that y = xm . But by the definition of y: ym 6= xmm , so y is not on the list. But we assumed the list contained all the real numbers designated by a finite number of words, so it is a paradox. 4. Berry’s paradox. Berry’s paradox is a simplified version of Richard’s paradox. Let us consider a set of natural numbers that cannot be named in less than 28 syllables, namely let Φ = {n ∈ ω : n cannot be named in less than 28 syllables}. By the least number principle there exists a least number x such that x ∈ Φ. Since x ∈ Φ, it cannot be named in less then 28 syllables. But p the least number which cannot be named in less then 28 syllablesq is the name of this number and it is shorter then 28 syllables. This constitutes a paradox. 5. Curry’s paradox. Curry’s paradox, introduced in [24] is an antinomy that allows the derivation of an arbitrary sentence from a self-referential sentence. Let us consider the following sentence: (ψ) If this sentence (ψ) is true, then Vladimir Putin is a Tsar of Russia. We then have the following equivalence: ψ ≡ (ψ ⇒ ξ), where ξ is the sentence pVladimir Putin is a Tsar of Russiaq. By propositional calculus we also trivially have ψ ⇒ ψ. By substituting (ψ ⇒ ξ) for the subsequent of this implication, we get: ψ ⇒ (ψ ⇒ ξ). Now, by contraction we get that: (ψ ⇒ ξ). By the equivalence again we also have: 13

ψ. Now, by Modus Ponens we obtain: ξ. Hence we proved a sentence that, however doubtful it may seem, is false. The sentence ξ may be arbitrary - it can also be a contradiction, e.g. pEvery sentence is true.q, which gives a paradox. For detailed analysis of some interesting questions concerning Curry’s paradox and the problem of self-reference, see: [64] Let us now answer an obvious, introductory question: what are these uncontroversial premises which are employed in semantic antinomies (specifically the ones about truth)? The answer is that the claims about the notion of truth we (naturally) invoke and that are meaningful to the derivation of contradiction in semantic paradoxes are: (1) (2) (3) i.e.

The law of bivalence: every sentence ϕ is either true or false. The law of non-contradiction: no sentence ϕ is both true and false. The T -scheme: for any sentence ϕ, ϕ is true if and only if what it says is the case, True(ϕ) iff ϕ.

It is then clear that in order to perform a detailed analysis of Yablo sequences and Yablo paradox, we need to make our considerations precise - therefore we have to prepare some formal tools that will enable us to clarify how different aspects of the theories in which one can formulate the Yablo sentences may influence their properties and status. For general monographs on the phenomena of non-wellfoundedness and circularity, see Barwise [4] and Field [28].

14

2

Truth and Arithmetic

We will be dealing with the notion of truth over some arithmetical theory as base theory or in some arithmetical structure as a model for our truth theory. The choice of arithmetic as a base theory for speaking of truth is justified by its foundational character and fundamental meaning for mathematics and science.

2.1

Representability, arithmetization and diagonalization

In order to meaningfully express the existence of Yablo formulae and Yablo sentences within our theory, we will need a certain form of diagonal lemma. For the diagonal lemma we need arithmetization of syntax and representability theorem. This chapter is devoted to proving necessary theorems and establishing necessary tools. 2.1.1

Language and axioms

Definition 2.1.1. Let σ = (0, s, +, ×, 0. Hence nM n ¬F (x).

In particular, T ` ∀x > n + 1 ¬F (x). This sentence is however equivalent to F (n + 1). But from (∗) T ` ¬F (n + 1). Since the choice of n was arbitrary, this means that: ∀n ∈ ω P AF ` ¬F (n). But by the definition of F we have then: ∀n ∈ ω P AF ` ∃x > n F (x). In particular: P AF ` ∃x F (x).

Definition 3.2.4. (Local Arithmetical Disquotation) AD = {T r(pϕq) ≡ ϕ : ϕ ∈ SentL (T r does not occur in ϕ)}. Definition 3.2.5. (Local Yablo Disquotation) YD = {T r(pY (n)q) ≡ Y (n) : Y (n) belongs to the Yablo sequence}. Definition 3.2.6. (P AD ) Let P AT be a theory obtained from P A by extending the language of arithmetic with a truth predicate T r18 . Let P AD = P AT ∪ AD ∪ Y D and let P A− D be P AD with the induction axiom scheme restricted to formulae without the truth predicate Theorem 3.2.7. P AD is ω-inconsistent Proof. By formal definition of Yablo formulae we obtain: ∀n ∈ ω P AD ` Y (n) ≡ ∀x > n ¬T r(pY (x)q). ˙ By the fact that P AD contains Y D we get: ∀n ∈ ω P AD ` T r(pY (n)q) ≡ ∀x > n ¬T r(pY (x)q). ˙ Let us denote F (x) := T r(p(x)q). ˙ With this definition we get: ∀n ∈ ω P AD ` F (n) ≡ ∀x > n¬F (x). Applying the preceding lemma to this fact ends the proof. Lemma 3.2.8. P AF is consistent. Proof. Consider any M, such that M |= P A and M is nonstandard. We pick a nonstandard element a ∈ |M| and let A = {a}. We extend the language of P A with the monadic predicate F and put (M, F M ) = (M, A). Since a is nonstandard, we get: ∀n ∈ ω (M, A) |= ¬F (n). But since A is non-empty, (M, A) |= ∃x F (x). Moreover, because the only element of the set of witnesses for the formula F (x) is nonstandard, we have: ∀n ∈ ω (M, A) |= ∃x > n F (x). Hence we obtain: ∀n ∈ ω (M, A) |= F (n) ≡ ∀x > n ¬F (x). But because M is already a model of P A, the last statement lets us conclude that: (M, A) |= P AF which by completeness theorem means that P AF is a consistent theory. Theorem 3.2.9. P A− D is consistent. 18

P AT is then not really a theory of truth, with T r being just a new predicate, without any substance to it.

43

Proof. Consider any M, such that M |= P A and M being nonstandard. Let S0 = {pϕq : M |= ϕ and ϕ ∈ SentL }. Further, let us denote t(x) := pY (x)q ˙ (which means that the value of t depends on the value of x which occurs as a free variable in the formula Y (x)). Then there are nonstandard numbers b and c such that tM (b) = c, i.e. c = pY (b)q. Let S = S0 ∪ {c}. We extend the language of P A with the truth predicate T r and put (M, T rM ) = (M, S). We then have ∀n ∈ ω (M, S) |= ∃x > n T r(pY (x)q), ˙

(9)

since we have (M, S) |= T r(c) and hence ∀n ∈ ω (M, S) |= x > n ∧ T r(pY (x)q) ˙ [b]. S contains the codes of the true purely arithmetical sentences (without the truth predicate), therefore (M, S) |= AD. The codes of sentences Y (n) do not belong to S - they are neither arithmetical nor identical to c. Thus we conclude that ∀n ∈ ω (M, S) |= ¬T r(pY (n)q). Additionally, by the definition of Yablo sentences we have: ∀n ∈ ω P AT ` Y (n) ≡ ∀x > n ¬T r(pY (x)q). ˙ Since M is a model of P A, we obtain: ∀n ∈ ω (M, S) |= Y (n) ≡ ∀x > n ¬T r(pY (x)q). ˙ But from this it follows that ∀n ∈ ω (M, S) |= ¬Y (n).

(10)

Therefore we may conclude that (M, S) |= Y D which ends the proof. Theorem 3.2.10. P AD is consistent. Proof. Let us consider any finite subset ∆ of P AD . We will show that ∆ is finitely satisfiable. Indeed, there is only finite number of T -equivalences for Yablo sentences in ∆. Hence, there is the greatest m such that there is a T -equivalence for Y (m) in ∆. Without loss of generality, we may assume that for all n ≤ m we have T -equivalences for sentences Y (n). Let us now take a model (M, S) such that M |= P A and S := T rM = {pY (m)q} ∪ {pϕq : ϕ ∈ SentL ∩ ∆ and M |= ϕ}. By the definition of S that we have: (1) (M, S) |= T r(pY (m)q), (2) ∀k < m (M, S) |= ¬T r(pY (k)q), 44

(3) ∀k > m (M, S) |= ¬T r(pY (k)q), and for all true arithmetical ϕ ∈ ∆: (4) (M, S) |= T r(pϕq). From (1) we easily get that: ∀k < m (M, S) |= ∃x > k T r(pY (x)q), ˙ and hence: (5) ∀k < m (M, S) |= ¬Y (k). By (3) we obtain: (M, S) |= ∀x > m ¬T r(pY (x)q), ˙ and hence: (6) (M, S) |= Y (m). (1) and (6) give us then: (M, S) |= Y (m) ≡ T r(pY (m)q), whereas by (2) and (5) we have: ∀k < m (M, S) |= Y (k) ≡ T r(pY (k)q). These two statements are obviously equivalent to: ∀n ≤ m (M, S) |= Y (n) ≡ T r(pY (n)q), and it follows that: (∗) (M, S) |= ∆ ∩ Y D. From (4) and definition of S we immediately obtain: (M, S) |= ϕ ≡ T r(pϕq) for all arithmetical ϕ ∈ ∆, which means that: (∗∗) (M, S) |= ∆ ∩ AD. Since S is finite, we also obviously have that for all ψ ∈ SentLT r (∗ ∗ ∗) (M, S) |= Ind(ψ), where Ind(ψ) denotes an instance of the induction axiom scheme for the formula ψ. It follows from (∗), (∗∗) and (∗ ∗ ∗) that (M, S) |= ∆. By compactness, this means that P AD is satisfiable and therefore consistent. Corollary 3.2.11. P AD is a conservative extension of P A. Proof. Let us consider an arithmetical sentence ϕ such that P A 0 ϕ. This entails that P A ∪ {¬ϕ} is consistent. Then there is a nonstandard model M of P A such that M |= ¬ϕ. By the theorem above, we may expand M to (M, S) such that (M, S) |= P AD . Obviously, since by the definition: ¬ϕ ∈ S, we have (M, S) 6|= ϕ, therefore P AD 0 ϕ. It is however still possible to derive the contradiction from the Yablo sequence, but in order to achieve this we would have to use a generalized version of the truth principle governing Yablo sequence - it would have to be necessary to add to our arithmetical theory principles that would be strong enough to prove a version of T -schema uniform for all Yablo sentences. If one wishes to find out more information on theories of truth without standard model, she shall see [49]. 45

Definition 3.2.12. (Uniform Yablo Disquotation) (UYD) ∀x(T r(pY (x)q) ˙ ≡ Y (x)) Fact 3.2.13. T = P AT + U Y D is inconsistent. Proof. We are working in T . By the definition of Yablo formula and existence theorem, we have ∀x (Y (x) ≡ ∀w > x¬T r(pY (w)q)). ˙ From (U Y D) we then derive (1) ∀x (Y (x) ≡ ∀w > x ¬Y (w)). From this we infer ∀x (Y (x) ≡ ∀w > x∃z > w T r(pY (z)q)). ˙ By (U Y D) again we get (2) ∀x (Y (x) ≡ ∀w > x ∃z > w Y (z)). We will now use some auxiliary axioms of order that are provable in T , namely: ∀x∃y x < y and ∀x∀y∀z ((x < y ∧ y < z) → x < z). By (2) and by the order axioms above, we get: (3) ∀x (Y (x) ≡ ∃z > x Y (z)). By (1), (3) we have: ∀x ((∀w > x¬Y (w)) ≡ (∃w > xY (w))) and hence a contradiction since for a certain LT r -formula ϕ we have obtained that: ∀x (ϕ(x) ≡ ¬ϕ(x)). Definition 3.2.14. (ω-rule) An ω-rule is a following infinitary inference rule defined for arithmetical formulae ϕ: ϕ(0), ϕ(1), ϕ(2), ..., ϕ(n), ... ∀x ϕ(x) Definition 3.2.15. T ω Let T be an axiomatizable first-order theory in the language LT r . If α is an ordinal, a sequence (ϕ0 , ..., ϕα ) of formulae is a derivation in ω-logic from T if and only if, for each ordinal β ≤ α: (1) ϕβ is an axiom of T or (2) there are γ < β and δ < β, such that ϕδ = (ϕγ ⇒ ϕβ ) or (3) ϕβ = ∀xψ(x) for some ψ(x) ∈ F rmL with exactly one free variable and there is an injective function f : ω → β such that ∀n ∈ ω ϕf (n) = ψ(n). We say that ϕ is a theorem of T in ω-logic if there is an ω-derivation of ϕ from T . We also call such ϕ an ω-consequence of T and denote it as follows: T ω ` ϕ. T ω is a set of sentences that are theorems of T in ω-logic. Theorem 3.2.16. A theory P AωD = (P A ∪ AD ∪ Y D)ω is inconsistent Proof. Since P AωD is an extension of P AT , by the diagonal lemma we may assume that Yablo sentences exist in this theory. Let us now fix n ∈ ω. We are working in P AωD . Suppose Y (n). By the definition of Yablo sentence, we therefore have ∀x (x > n ⇒ ¬T r(pY (x)q)). ˙ Hence, ¬T r(pY (n + 1)q) as well as ∀x (x > n + 1 ⇒ ¬T r(pY (x)q)). ˙ But the last sentence is equivalent to Y (n + 1). By the appropriate T -equivalence we therefore get T r(pY (n + 1)q) which is impossible. Since the choice of n was arbitrary, we have: ∀n ∈ ω P AωD ` ¬Y (n).

46

In particular: (∗) P AωD ` ¬Y (23). By the fact that we have a T -equivalence for every Yablo sentence in our theory we also have: ∀n ∈ ω P AωD ` ¬T r(pY (n)q). It is worth noting that up to this moment, P AD was sufficient to justify everything we argued for in this proof. Now, we will essentially use the means of P AωD . By applying the ω-rule we therefore obtain: P AωD ` ∀x ¬T r(pY (x)q). ˙ In particular we have ˙ P AωD ` ∀x (x > 23 ⇒ ¬T r(pY (x)q). But this means we have: (∗∗) P AωD ` Y (23). It immediately follows from (∗) and (∗∗) that P AωD is inconsistent.

3.3

Yablo sequences in second-order languages

The results from this section - except for those concerning ACA0 - are also formulated in Picollo [60]. Definition 3.3.1. (i) Let P A2 be a second-order theory that is obtained from P A by adjoining to it the comprehension scheme and replacing all the instances of the induction axiom scheme (IND) of P A by the second-order induction axiom and let then P AT2 denote a theory obtained from P A2 just by adjoining a first-order truth predicate T r to its language. (ii) Let Z denote here an extension of P A2 formulated in second-order language L2 . (iii) Let N2 denote the standard (intended) model of arithmetic for the language L2 , namely let N2 = (ω, P(ω), +, ×, s, 0, k ∧ T r(pY (x)q), ˙ M |= ∀x 6= n ¬T r(pY (x)q) ˙ and thus, by the definition of Yablo sentence, M |= Y (n) and M 6|= Y (k). By (i) and (ii) it is also obvious that P AT does not prove the negation of 0 Y (n) ⇒ Y (k) for n > k. From now on within this section, for convenience and transparency, we omit the corner and overline notation. 3.4.1

Friedman-Sheard Theory

Definition 3.4.2. (Stratified Compositional Truth Theory ) Stratified Compositional Truth Theory (CT − ) is an axiomatic theory obtained from P A by adjoining to it the following axioms: 21

Note that ACA0 is a theory of second-order arithmetic - a theory in many-sorted arithmetical language. This is very different from second-order logic.

49

(CT1) ∀s, t ∈ T rm[T r(s = t) ≡ val(s) = val(t)], (CT2) ∀x[SentL (x) ⇒ (T r(¬x) ≡ ¬T r(x))], (CT3) ∀x, y[(SentL (x ∧ y)) ⇒ (T r(x ∧ y) ≡ T r(x) ∧ T r(y))], (CT4) ∀x, y[(SentL (x ∨ y)) ⇒ (T r(x ∨ y) ≡ T r(x) ∨ T r(y))], (CT5) ∀v, x[SentL (∀vx) ⇒ (T r(∀vx) ≡ ∀tT r(x(t/v)))], (CT6) ∀v, x[SentL (∃vx) ⇒ (T r(∃vx) ≡ ∃tT r(x(t/v)))], where by SentL (x) we mean that x is the Gödel number of an arithmetical (without any occurence of the truth predicate) sentence of the language L. Let us note that there are no instances of the induction axiom scheme for formulae of the extended language LT r other then those for formulae of the original language of P A among the axioms of CT − . A sentence (Ind)

(ϕ(0) ∧ ∀x(ϕ(x) ⇒ ϕ(s(x)))) ⇒ ∀xϕ(x)

is an axiom of CT − only if ϕ ∈ F rmL , i.e. the truth predicate T r does not occur in ϕ, i.e. (Ind) is an instance of induction axiom in P A.22 The system CT − is called stratified since in the axioms (CT 2) − (CT 6) all the sentences being in the scope of the quantifiers are the sentences of the language L. The axiom (CT 1) speaks only of L-sentences because equational theorems are all sentences of L. Definition 3.4.3. (Friedman-Sheard Theory (FS)) Friedman-Sheard Theory (F S) is an axiomatic theory obtained from P AT by adjoning to it the following axioms and inference rules: (FS1) ∀s, t ∈ T rm[T r(s = t) ≡ val(s) = val(t)], (FS2) ∀x[Sent(x) ⇒ (T r(¬x) ≡ ¬T r(x))], (FS3) ∀x, y[(Sent(x ∧ y)) ⇒ (T r(x ∧ y) ≡ T r(x) ∧ T r(y))], (FS4) ∀x, y[(Sent(x ∨ y)) ⇒ (T r(x ∨ y) ≡ T r(x) ∨ T r(y))], (FS5) ∀v, x[Sent(∀vx) ⇒ (T r(∀vx) ≡ ∀tT r(x(t/v)))], (FS6) ∀v, x[Sent(∃vx) ⇒ (T r(∃vx) ≡ ∃tT r(x(t/v)))], ϕ N EC T r(ϕ) , CON EC

T r(ϕ) ϕ .

Any truth theory (extending P A) that is closed under both N EC and CON EC is called symmetric. What is worth noting, no such theory proves or disproves the liar sentence λ, i.e. for any consistent, symmetrical theory S it holds that S 0 λ and S 0 ¬λ. The argument for this is straightforward: for the sake of contradiction suppose S ` λ. By N EC we get: S ` T r(λ). But by the definition of λ we also get: S ` ¬T r(λ) which is inconsistent with our general assumption. Now suppose S ` ¬λ. By its definition then: S ` T r(λ). But by applying CON EC: S ` λ which again is inconsistent with our general assumption and hence ends the proof. What is interesting is that if we replace one of the discussed rules with an appropriate axiom scheme, the resulting theory S ∗ will be inconsistent. For example, let us replace CON EC with an axiom scheme: T r(ϕ) ⇒ ϕ. Hence we have S ∗ ` T r(λ) ⇒ λ. Now, working in S ∗ take the definition of λ and we have: T r(λ) ⇒ ¬λ, so (1) ¬T r(λ) and again, by the definition of λ we then get: λ itself. By N EC we obtain: (2) T r(λ) A system that is obtained from CT − by adjoining to it all the instances of induction formulated in the ful language LT r is called CT . 22

50

which is in contradiction with (1). Let us add one more piece of information on symmetric theories. For a given formal theory T in the language LT r let IS = {ϕ : S ` T r(pϕq)} denote the so-called inner theory (logic) of the theory S and let OS = {ϕ : T ` ϕ} be an outer theory (logic) (namely, the set of theorems of S). A thing to mention here is that symmetric theories like F S have one more advantage: their inner and outer logic coincide. This fact follows immediately from N EC and CON EC and means that for any ϕ S ` ϕ iff S ` T r(pϕq), which can be read as a weak form of Tarski scheme. It is worth noting that for theories whose inner and outer logic do not coincide it is often a problem to find some natural axiomatisation of IS other than the entire set itself. Another interesting fact about truth theories closed under the N EC rule is the following: Theorem 3.4.4. (Löb’s theorem) Let S be an axiomatic theory extending P A such that it has the following properties: (i) S is closed under N EC, (ii) S ` T r(ϕ ⇒ ψ) ⇒ (T r(ϕ) ⇒ T r(ψ)), (iii) S ` T r(ϕ) ⇒ T r(T r(ϕ)). Then S ` T r(T r(ϕ) ⇒ ϕ) ⇒ T r(ϕ). Proof. (of Löb’s theorem) Let us fix ϕ and assume we are working in S. By the Diagonal lemma there is a sentence ϑ such that we have: ϑ ≡ (T r(ϑ) ⇒ ϕ). By applying N EC we get: T r(ϑ ≡ (T r(ϑ) ⇒ ϕ)). Now, by (ii) and Modus Ponens we have: T r(ϑ) ⇒ (T r(T r(ϑ)) ⇒ T r(ϕ)). By (iii) then: (1) T r(ϑ) ⇒ T r(ϕ), and hence by propositional calculus (T r(ϕ) ⇒ ϕ) ⇒ (T r(ϑ) ⇒ ϕ) and by the diagonal sentence: (T r(ϕ) ⇒ ϕ) ⇒ ϑ. We apply N EC and obtain: T r((T r(ϕ) ⇒ ϕ) ⇒ ϑ). By (ii) and Modus Ponens again: T r(T r(ϕ) ⇒ ϕ) ⇒ T r(ϑ) and by (1): T r(T r(ϕ) ⇒ ϕ) ⇒ T r(ϕ), which is the desired conclusion. For the analysis of Löb’s theorem in a set-theoretical setting, see Cieślinski [15]. Let now F S − denote a theory obtained from F S by restricting the induction axiom scheme to arithmetical formulae. We may see that F S − is an extension of CT − obtained by adjoining two new inference rules to it23 and by letting the compositional axioms (F S2) − (F S6) be no longer restricted to the arithmetical sentences of the language L - the truth predicate may occur in the formulae governed by our axioms of compositionality. Let us now turn to stating an interesting theorem about F S − . Theorem 3.4.5. (McGee’s theorem [52]) Let S be an axiomatic theory extending P A such that it has the following properties: (i) S is closed under N EC, (ii) S ` ∀x[SentL (x) ⇒ (T r(¬x) ⇒ ¬T r(x))], (iii) ∀x, y[(Sent(x ∨ y)) ⇒ (T r(x ∨ y) ⇒ T r(x) ∨ T r(y))], (iv) ∀v, x[Sent(∀vx) ⇒ (T r(∀vx) ⇒ ∀tT r(x(t/v)))]. Then S is ω-inconsistent Proof. We define a binary, primitive recursive function f such that f (n, pϕq) = pT r(pT r(...pT r(pϕq)q...)q)q. |

{z

n times

}

The function is clearly primitive recursive, since f (0, pϕq) = pϕq is primitive recursive and f (s(n), pϕq) = pT r(f (n, pϕq))q is an instance of the simple recursion scheme. Since f is primitive recursive, by 23

In the same sense F S is an extension of CT .

51

Representability it is represented in P AT by some formula ψ(n, pϕq, y). For convenience and transparence however, we will use a symbol f throughout the proof24 . We are working in S. By Diagonal lemma there is a sentence ϑ such that (∗) ϑ ≡ (¬∀xT r(f (x, pϑq))). Then we may reason as follows: ¬ϑ ∨ ¬∀xT r(f (x, pϑq))

prop. calc.

T r(¬ϑ ∨ ¬∀xT r(f (x, pϑq)))

N EC

T r(¬ϑ) ∨ T r(¬∀xT r(f (x, pϑq)))

(ii)

¬T r(ϑ) ∨ T r(¬∀xT r(f (x, pϑq)))

(i)

T r(ϑ) ⇒ T r(¬∀xT r(f (x, pϑq)))

prop. calc.

T r(ϑ) ⇒ ¬T r(∀xT r(f (x, pϑq)))

(i)

T r(ϑ) ⇒ ¬∀xT r(f (s(x), pϑq))

(iii), df. of f

T r(ϑ) ⇒ ¬∀xT r(f (x, pϑq))

weakening

and by (∗) we get (∗∗) T r(ϑ) ⇒ ϑ. However, we also have: ¬ϑ ⇒ ∀xT r(f (x, pϑq))

by (∗)

¬ϑ ⇒ T r(f (0, pϑq))

dictum de omni

which, by the definition of f gives us : (∗ ∗ ∗) ¬ϑ ⇒ T r(ϑ). From (∗∗) and (∗ ∗ ∗) it follows that ϑ, hence by (∗) we obtain: (1) ∃x ¬T r(f (x, pϑq)). Now, outside of S we can see that since we proved ϑ, by applying N EC to it any finite number of times we may observe that: (2) ∀n ∈ ω S ` T r(f (n, pϑq)). (1) and (2) obviously give ω-inconsistency.25 Corollary 3.4.6. F S − is ω-inconsistent. Proof. Immediate, by the observation that F S − is closed under N EC and the conditions from the statement of the theorem above are weak (in a sense that we take implication instead of equivalence) versions of the axioms: (CT 2), (F S4), (F S5) For more detailed information on the F S theory itself, see the original paper of H. Friedman and M. Sheard [32] or for its proof-theoretical stregth see V. Halbach [38]. We will now show, that all Yablo sentences are provably equivalent in F S − . Theorem 3.4.7. F S − ` ∀x∀w(Y (x) ≡ Y (w)) Proof. We are working in F S − . Let us fix x and w and assume x < w. By the definition of Yablo sentences we have that Y (x) ⇒ Y (w). Let us now assume Y (w) and for the sake of contradiction, assume also ¬Y (x), i.e. ∃z(z > x ∧ T r(Y (z))). 24 25

Actually, we may simply extend the standard language of arithmetic with a new function symbol for f . McGee’s theorem may be proved in a different way - V. Halbach et. al. in [39] reduce it to the Löb’s theorem.

52

By Y (w) we have of course ∀z(z > w ⇒ ¬T r(Y (z)). Those two statements give us that: ∃z(z > x ∧ z ≤ w ∧ T r(Y (z)). Let us fix such z. But by the assumption Y (w), we also have : ¬T r(Y (w + 1)). From the first part of the proof again, by axioms of F S and by applying N EC we get: ∀x∀y(x < y ⇒ (T r(Y (x)) ⇒ T r(Y (y)))). Since z < w + 1 and T r(Y (z)), we get T r(Y (w + 1)) which is a contradiction and ends the proof. Corollary 3.4.8. F S − ` ∀x∀w(T r(Y (x)) ≡ T r(Y (w))). Proof. Immediate, by applying N EC and compositional axioms to the previous theorem. Corollary 3.4.9. F S − ` ∀x(Y (x) ≡ ¬T r(Y (x))). Proof. (=⇒) By Y (x), we get ¬T r(Y (x + 1)), thus ¬T r(Y (x)) by the corollary above. (⇐=) By ¬T r(Y (x)) we get that ∀w¬T r(Y (w)), and in particular ∀w > x ¬T r(Y (w)) which is equivalent to Y (x). So, provably in F S − , all (uniform general statement) Yablo sentences are liars. Morevoer we have: Fact 3.4.10. If F S is consistent, then: (i) F S 0 ∃x Y (x), (ii) F S 0 ∃x ¬Y (x) Proof. For (i), assume for the sake of contradiction, F S ` ∃x Y (x). By the theorem above, we have then F S ` ∀x Y (x). Applying N EC and axiom of F S for general quantifier, we obtain: F S ` ∀x T r(Y (x)).In particular we get: F S ` T r(Y (1)). But from F S ` ∀x Y (x) we also have F S ` Y (0) and further F S ` ¬T r(Y (1)) which is a contradiction. For (ii), assume for the sake of contradiction, F S ` ∃x ¬Y (x). By the theorem above, we have then F S ` ∀x¬Y (x). Applying N EC and axioms of F S for general quantifier and negation, we obtain: F S ` ∀x ¬T r(Y (x)). But then, by previous corollary F S ` ∀x Y (x). Therefore contrary to our general assumption F S is inconsistent. This contradiction ends the proof.

53

3.4.2

Kripke-Feferman Theory

Kripke-Feferman is a system that was established to axiomatize Kripke’s semantical theory of truth with the Strong Kleene valuation scheme. As such, it is formulated in classical logic, but it describes a partial notion of truth. It corresponds to Kripke’s conception in such a way that its axioms are just formalised Kripke’s truth conditions (with SK-scheme) and the fixed points of the construction are possible extensions of the truth predicate in the standard model. If we fix the standard model N of arithmetic as a base model for the language L of our arithmetical theory, then KF fully characterizes the fixed points with Strong Kleene scheme (see the lemma below). Definition 3.4.11. (Kripke-Feferman Theory (KF) Kripke-Feferman Theory (KF ) is an axiomatic theory obtained from P AT by adjoning to it the following axioms: (KF1) ∀s, t ∈ T rm[T r(s = t) ≡ val(s) = val(t)], (KF2) ∀s, t ∈ T rm[T r(¬(s = t)) ≡ val(s) 6= val(t)], (KF3) ∀x[Sent(x) ⇒ (T r(¬¬x) ≡ T r(x))], (KF4) ∀x, y[(Sent(x ∧ y)) ⇒ (T r(x ∧ y) ≡ T r(x) ∧ T r(y))], (KF5) ∀x, y[(Sent(x ∧ y)) ⇒ (T r(¬(x ∧ y)) ≡ T r(¬x) ∨ T r(¬y))], (KF6) ∀x, y[(Sent(x ∨ y)) ⇒ (T r(x ∨ y) ≡ T r(x) ∨ T r(y))], (KF7) ∀x, y[(Sent(x ∨ y)) ⇒ (T r(¬(x ∨ y)) ≡ T r(¬x) ∧ T r(¬y))], (KF8) ∀v, x[Sent(∀vx) ⇒ (T r(∀vx) ≡ ∀tT r(x(t/v)))], (KF9) ∀v, x[Sent(∀vx) ⇒ (T r(¬∀vx) ≡ ∃tT r(¬x(t/v)))], (KF10) ∀v, x[Sent(∃vx) ⇒ (T r(∃vx) ≡ ∃tT r(x(t/v)))], (KF11) ∀v, x[Sent(∃vx) ⇒ (T r(¬∃vx) ≡ ∀tT r(¬x(t/v)))], (KF12) ∀t ∈ T rm[T r(T r(t)) ≡ T r(val(t))], (KF13) ∀t ∈ T rm[T r(¬T r(t)) ≡ (T r(¬val(t)) ∨ ¬Sent(val(t)))]. Lemma 3.4.12. For any model M = (N, E, A) the following equivalence holds: M |=SK KF if and only if M is a fixed-point model. Proof. (sketch) If M is a fixed-point model, then it is clear that all the axioms of KF are true in M. On the other hand, by assuming M to satisfy KF and comparing the axioms to the Kripke’s conditions we easily see that the extension of the truth predicate in M has to be fixed point. Definition 3.4.13. CONS and COMPL (CONS) ∀x[Sent(x) ⇒ ¬(T r(x) ∧ T r(¬x))], (COMPL) ∀x[Sent(x) ⇒ (T r(x) ∨ T r(¬x))]. Adjoining CON S or COM P L to KF results in a theory that is truth-theoretically stronger than KF , while maintaining the same arithmetical strength. We will now show that KF taken together with either CON S or COM P L, proves one of the directions of the uniform T -schema: ∀x1 ...∀xn [T r(ϕ(x1 , ..., xn )) ≡ ϕ(x1 , ..., xn )] Fact 3.4.14. For every LT r -formula ϕ(x1 , ..., xn ) the following hold: (i) KF + CON S ` ∀x1 ...∀xn [T r(ϕ(x1 , ..., xn )) ⇒ ϕ(x1 , ..., xn )] (ii) KF + COM P L ` ∀x1 ...∀xn [ϕ(x1 , ..., xn ) ⇒ T r(ϕ(x1 , ..., xn ))] 54

Proof. (Sketch) The proof is by induction on the positive complexity of LT r -formula ϕ(x1 , ..., xn ). We will show the steps in which CON S and COM P L are used. This is the case for ϕ(x) = ¬T r(x): (i) We are working in KF + CON S. Assume T r(¬T r(x)) and for the sake of contradiction assume also T r(x). By (KF 12) this gives us T r(T r(x)) which is inconsistent with CON S. (ii) We are working in KF + COM P L. Assume ¬T r(x) and for the sake of contradiction assume also ¬T r(¬T r(x)). By COM P L we have then T r(T r(x)), and further by (KF 12) we get T r(x) which is a contradiction and ends the sketch of the proof. Definition 3.4.15. Let E and A denote the extension and the antiextension of the truth predicate e := (Sent − A) , (ii) in a given model M. Then, for M= (|M|, E, A) |= KF we put: (i) E f := (M, E) e M Theorem 3.4.16. Let Y (x) be a Yablo formula provably in KF +COM P L (i.e. KF +COM P L ` Y (x) ≡ ∀w(w > x ⇒ ¬T r(Y (w))). Then: KF + COM P L ` ∀x ¬Y (x). Proof. We are working in KF + COM P L. For the sake of contradiction let us assume Y (x). It means that ∀w(w > x ⇒ ¬T r(Y (w))) and thus ¬T r(Y (x + 1)). We also have ∀w(w > x + 1 ⇒ ¬T r(Y (w))), which is equivalent to Y (x + 1). Hence T r(Y (x + 1)), by the fact that KF + COM P L proves this direction of uniform T -scheme. This is a contradiction. Theorem 3.4.17. For every natural number n there exist formulae Y0 (x) and Y1 (x), such that (i) Y0 (x) and Y1 (x) are Yablo formulae in KF + CON S, (ii) KF + CON S ` Y0 (n), (iii) KF + CON S ` ¬Y1 (n) Proof. Let us fix n. Let λ denote the liar sentence. We define: (a) Y0 (x) := (x = n) ∨ (x > n ∧ λ) (b) Y1 (x) := (x = n + 1) ∨ (x > n ∧ λ). With those definitions, we see that (ii) and (iii) are trivially satisfied. For (i) let us first show that Y0 (x) is a Yablo formula in KF + CON S. We are working in KF + CON S. Let us fix x and let us divide the proof into two cases: x < n and x ≥ n. Assuming x < n we have ¬Y0 (x) and because we have T r(Y0 (n)) and therefore: ∃w (w > x ∧ T r(w = n ∨ (v > n ∧ λ))). This makes the Yablo condition true for Y0 (x). In the second case, since by proving the appropriate direction of uniform T -scheme, KF + CON S ` λ, we easily get Y0 (x). Now let us fix w > x and for the sake of contradiction let us assume that T r(Y0 (w)). By the axioms of KF for disjunction, we then obtain: T r(w = n) ∨ (T r(w > n) ∧ T r(λ))). However, we assumed that w > n, hence T r(λ) which is equivalent to ¬λ and this gives us a contradiction. 55

Theorem 3.4.18. Let Y (x) be a Yablo formula in KF . Then KF + CON S ` ∀xY (x) . f |= (KF +COM P L): Proof. Let M be such that M |= (KF +CON S). Let us observe that then M f we will limit our attention to arguing that M |= COM P L. For this, let us fix a sentence ϕ. Let us e This means that ϕ ∈ A and hence, ¬ϕ ∈ E. Then, using CON S, we obtain: assume that ϕ ∈ / E. e and shows that COM P L is satisfied in M. f ¬ϕ ∈ / A which entails ¬ϕ ∈ E Now, for the sake of contradiction assume that for some a ∈ |M| M |= ¬Y (a). This means that ∃b ∈ |M| such that b > a and M |= T r(Y (a)). This means that Y (b) ∈ E and ¬Y (b) ∈ A, so e We will show that ¬Y (b) ∈ / E. (∗) ∀c > b Y (c) ∈ A

. Let us fix c such that c > b and assume for the sake of contradiction that Y (c) ∈ / A. Then, by e f definition: Y (c) ∈ E and by the fact that c > b we also have M |= ¬Y (b). Now, from the fact that f and because it proves the appropriate direction of uniform T -scheme, COM P L is satisfied in M f |= T r(¬Y (b)) which means that ¬Y (b) ∈ E e which is impossible. we get: M e e which by definition of Yablo sentence By definition of E, from (∗) we get that: ∀c > b Y (c) ∈ /E f |= Y (b) and immediately gives us: M f |= ¬T r(Y (b + 1)) M f |= Y (b + 1), so by COM P L and M f |= T r(Y (b + 1)) M

which is a contradiction. Lemma 3.4.19. Let Y2 (x) be the following formula: (x = 0 ∧ ∀w¬T r(Y (w))) ∨ (x 6= 0 ∧ Y (x − 1))]. Then Y2 (x) is a Yablo formula in KF . Proof. (=⇒) Let us fix x, assume Y2 (x) and fix w > x. Suppose for the sake of contradiction that we have T r(Y2 (w)). Then by definition of Y2 (x) and by the fact that w > 0 we get: T r(Y (w − 1)) . Then x 6= 0 (suppose x = 0 - then we would have ∀w ¬T r(Y (w))). From this we get: Y (x − 1). But obviously x − 1 < w − 1, so we have ¬T r(Y (w − 1)) which is a contradiction. (⇐=) Let us assume: ∀w > x ¬T r(Y2 (w)). For the sake of contradiction suppose ¬(Y2 (x)). This means that we assume: ((x 6= 0) ∨ ∃w T r(Y (w))) ∧ ((x = 0) ∨ ¬Y (x − 1)). There are now two cases to consider: Case 1: x = 0. Then ∃w T r(Y (w)). Let us fix such w and let us put a := w + 1. We get T r((a 6= 0) ∧ Y (a − 1)) which is sufficient for T r(Y2 (a)). This contradicts our general assumption. Case 2: x 6= 0. Then ∃w ≥ x T r(Y (w)), since we have ¬Y (x − 1). Let us fix such w and put a := z + 1. Again, we get: r((a 6= 0) ∧ Y (a − 1)). This contradicts our general assumption as well and thus, ends the proof. 56

Theorem 3.4.20. Let Y (x) be a Yablo formula in KF . Then KF + CON S ` ∀x¬T r(Y (x)) Proof. It immediately follows from the previous theorem, that KF + CON S ` ∀x > 0 ¬T r(Y (x)). We need to show that KF + CON S ` ¬T r(Y (0)). This is an easy corollary of the above lemma, since by the previous theorem KF + CON S ` ∀x Y2 (x). In particular KF + CON S ` Y2 (0), therefore by the definition of Y2 (x) we have: KF + CON S ` ∀x ¬T r(Y (x)) which ends the proof.

From the two above theorems, we immediately get: Corollary 3.4.21. Let Y (x) be a Yablo formula in KF . Then KF + CON S ` ∀x (Y (x) ≡ ¬T r(Y (x))) We also have that KF itself does not decide any Yablo sentence: Corollary 3.4.22. Let Y (x) be a Yablo formula in KF . Then: (i) KF 0 ∃x Y (x), (ii) KF 0 ∃x ¬Y (x). Proof. (i) is immediate from the theorem that KF + COM P L ` ∀x¬Y (x), so in an arbitrary model of KF + COM P L ∃x Y (x) does not hold. (ii) is also immediate from the theorem that KF + CON S ` ∀xY (x), so in an arbitrary model of KF + CON S ∃x ¬Y (x) does not hold. For more information of KF , see the papers of H. Reinhardt [63], A. Cantini [12] and S. Fefereman [27] - the latter particularly for the analysis of the proof-theoretical strength of KF . For axiomatisation of KF in partial logic, see [40].

3.5

Yablo paradox in partial semantics

We will be working with a model (M, E, A) such that it is a fixed-point model in the meaning defined in the section 2.3. We will consider the behaviour of Yablo sentences in this model under different types of partial-logic semantics as evaluation schemas - we will analyse certain, seemingly the most relevant for truth-theoretical considerations, 26 types of many-valued logic. Generally, many-valued logics resemble classical logic because they accept the principle of truth-functionality, i.e. that the truth of a complex sentence is determined by the truth values of its component sentences but they differ from classical logic by the fundamental fact that they do not restrict the number of truth values to only two: they allow for a larger set of truth degrees. Three-valued logic is a system in which there are three truth values indicating true, false and an intermediate value - for our purposes this indeterminate third value may be interpreted simply as unknown. We will provide some basic definitions and properties, but for detailed information on partial logics, see e.g. [9]. 26

E.g. we do not consider the so-called Łukasiewicz logic Ł3, as it has has the same tables for ∧, ∨ and ¬ as the Strong Kleene logic and it differs form it in the table for implication only when both the truth-values of precedent and antecedent of ⇒ have the value unknown which is not an interesting case for analysis of Yablo sentences, as we shall see below.

57

Definition 3.5.1. (i) The set V = {t, f, u} is called a set of values. (ii) A valuation v is any function from the set of atomic sentences AtomLT r to the set V of values. In accordance with this definition, for convenience and transparency we will omit overlines and corners and denote the value of a formula just by v(ϕ). By the assumption that (M, S) is a fixed-point model, for any LT r -sentence we have v(ϕ) = v(T r(pϕq)) We begin our analysis with the description of the Strong and Weak Kleene schemas. As it is shown by J. Cain and Z. Damnjanovic in [11] there are some significat differences between performing Kripke’s construction of fixed-point models under Strong and Weak Kleene schemas. We state them for full information. See the cited article for futher details. If we use Strong Kleene scheme, then regardless of the way language is Gödel-numbered, we have: 1. There are 2ℵ0 fixed-point models. 2. In the minimal fixed-point model, the weakly definable sets, i.e. sets of the form: {n : ϕ(n) is true in the minimal fixed-point model and ϕ(x) ∈ F rmLT r } are precisely the Π11 sets.27 3. In the minimal fixed-point model, the totally defined sets (i.e. sets weakly defined by formulae all of whose instances are either true or false) are precisely the ∆11 sets. 4. The ordinal of the minimal fixed-point model is ω1CK . If we use Weak Kleene scheme, then depending on the way language is Gödel-numbered, we have: 1. There are finitely many, ℵ0 or 2ℵ0 fixed-point models. 2. In the minimal fixed-point model, the weakly definable sets may range from a subclass of the sets one-to-one-reducible28 to T h(N) to the Π11 sets (including intermediate classes). 3. In the minimal fixed-point model, the totally defined sets may range from a subclass of the sets one-to-one-reducible to T h(N) to the ∆11 sets (including intermediate classes). 4. The ordinal of the minimal fixed-point model may be ω, ω1CK or any intermediate limit ordinal.29 27

A set of natural numbers is in the class Σ1n iff it is definable by a Σ1n formula. A set of natural numbers is in the class Π1n iff it is definable by a Π1n formula. If the set is both Σ1n and Π1n , then it is ∆1n (the class ∆11 is said to be a class of hyperarithmetical sets). Hierarchy of formulae goes as follows: Σ10 = Π10 = ∆10 is the class of formulae in the language of second-order arithmetic with no set quantifiers. A formula is Σ1n+1 iff it is logically equivalent to a formula of the form ∃X1 ...∃Xk ψ(X1 , ..., Xk ), where ψ(X1 , ..., Xk ) is Π1n . A formula is Π1n+1 iff it is logically equivalent to a formula of the form ∀X1 ...∀Xk ψ(X1 , ..., Xk ), where ψ(X1 , ..., Xk ) is Σ1n . As an example, a formula ϕ(T ) saying that a tree T ⊆ ω n ⇒ ¬T r(Y (x))) By the definition of the W Kscheme for the general quantifier we have: ∀a ∈ |M| v(a > n ⇒ ¬T r(Y (a))) = t. By the definition of W K-scheme for implication there are three possibilities: (i) v(a > n) = f and v(¬T r(Y (a))) = f or (ii) v(a > n) = f and v(¬T r(Y (a))) = t or (iii) v(a > n) = t and v(¬T r(Y (a))) = t. We want to know what happens when a > n. We can see that (iii) is the only case to be considered then. Let us fix any a > n. We then have v(a > n) = t and v(¬T r(Y (a))) = t. This entails v(T rY (a)) = f , and thus by the T -schema we obtain: v(Y (a)) = f. Since the choice of a was arbitrary, we have: (1) ∀a ∈ |M| (a > n ⇒ v(Y (a)) = f ) Let m > n. Then v(Y (m)) = f . By the definition of Yablo sentence v(Y (m)) = v(∀x(x > m ⇒ ¬T r(Y (x))) = f . By the definition of W K-scheme for general quantifier: ∃b ∈ |M| v(b > m ⇒ ¬T r(Y (b))) 6= t and ∀b ∈ |M| v(b > m ⇒ ¬T r(Y (b))) 6= u. Therefore ∃b ∈ |M| v(b > m ⇒ ¬T r(Y (b))) = f . By the definition of W K-scheme for implication v(b > m) = t and v(¬T r(Y (b))) = f , which means that v(T r(Y (b))) = t and by the T -schema v(Y (b)) = t. This means that ∃b ∈ |M| b > m > n ∧ v(Y (b)) = t. In particular: (2) ∃b ∈ |M| (b > n ∧ v(Y (b)) = t). 60

This gives us a contradiction between (1) and (2). Let us suppose that ∃n ∈ |M| v(Y (n)) = f . Let us fix n and assume v(Y (n)) = f . By the definition of Yablo sentence we get that: v(∀x(x > n ⇒ ¬T r(Y (x)))) = f . By the definition of W K-scheme for general quantifier: ∃b ∈ |M| v(b > n ⇒ ¬T r(Y (b))) 6= t and ∀b ∈ |M| v(b > n ⇒ ¬T r(Y (b))) 6= u. This means that ∃b ∈ |M| v(b > m ⇒ ¬T r(Y (b))) = f . By the definition of W K-scheme for implication v(b > n) = t and v(¬T r(Y (b))) = f which means that v(T r(Y (b))) = t and by the T -schema we have: v(Y (b)) = t. So ∃b ∈ |M| v(Y (b)) = t. But we already proved that this is impossible. Finally we have that ∀n ∈ |M| v(Y (n)) = u, i.e. we assign values u to all of the Yablo sentences. 3.5.2

Strong Kleene

Kleene’s strong logic, already mentioned in the section 2.3 devoted to Kripke’s theory of truth, is a logic of indeterminacy. Its intended interpration is that some sentences are underdetermined. We recall the definition in the style of truth-tables. Definition 3.5.4. For any fixed-point model M = (|M|, E, A) and for any LT r -sentence ϕ, we say that ϕ is true in M under the SK-scheme, denoted by: M |=SK ϕ if and only if v(ϕ) = t. The valuation v is defined for atomic sentences. The following truth-tables for propositional connectives and truth-rules for quantifiers define the values of v(ϕ) for complex sentences:

Implication under SK-scheme ⇒ f u t

f t u f

u t u u

t t t t

Conjunction under SK-scheme ∧ f u t

f f f f

u f u u

61

t f u t

Disjunction under SK-scheme ∨ f u t

f f u t

u u u t

t t t t

Negation under SK-scheme ¬ϕ t u f

ϕ f u t

Quantifiers under SK-scheme

v(∀xϕ(x)) =

v(∃xϕ(x)) =

   t  

if ∀a ∈ |M| v(ϕ(a)) = t

   u

otherwise

   t  

if ∃a ∈ |M| v(ϕ(a)) = t

   u

otherwise

f

f

if ∃a ∈ |M| v(ϕ(a)) = f

if ∀a ∈ |M| v(ϕ(a)) = f

Theorem 3.5.5. For each Yablo sentence Y(n) (i) (|M|, E, A) 6|=SK Y (n), (ii) (|M|, E, A) 6|=SK ¬Y (n). Proof. We will show that for each Yablo sentence Y (n), the value of Y (n) is unknown, i.e. ∀n ∈ |M| v(Y (n)) = u. Let us fix n and suppose that v(Y (n)) = t. By the definition of Yablo sentence we have: v(Y (n)) = v(∀x(x > n ⇒ ¬T r(Y (x))). By the definition of the SK-scheme for the general quantifier we have: ∀a ∈ |M| v(a > n ⇒ ¬T r(Y (a))) = t. By the definition of SK-scheme for implication there are two possibilities: (i) v(a > n) = f or (ii) v(¬T r(Y (a))) = t Now fix any m > n. We have: v(¬T r(Y (m))) = t which means that v(T r(Y (m))) = f and by T -schema v(Y (m)) = f . Since the choice of m was arbitrary, we have: (1) ∀m ∈ |M| (m > n ⇒ v(Y (a)) = f ). So let us take m again. We have v(Y (m)) = f . By the definition of Yablo sentence: v(∀xx > m ⇒ ¬T r(Y (x))) = f . By the definition of SK-scheme for general quantifier we get that: ∃b ∈ 62

|M| v(b > m ⇒ ¬T r(Y (b))) = f . Let us consider b > m. Then v(b > m) = t, which entails that: v(¬T r(Y (b))) = f , further: v(T r(Y (b))) = t, and by T -schema again: v(Y (b)) = t So we showed that ∃b ∈ |M| (b > m > n ∧ v(Y (b)) = t). In particular (2) ∃b ∈ |M| (b > n ∧ v(Y (b)) = t). This gives us a contradiction between (1) and (2). Let us fix n and suppose that v(Y (n)) = f . By the definition of Yablo sentence: v(∀xx > n ⇒ ¬T r(Y (x))) = f . By the definition of SK-scheme for general quantifier: ∃a ∈ |M| v(a > n ⇒ ¬T r(Y (a))) = f By the definition of SK-scheme for implication we have: v(a > n) = t and v(¬T r(Y (a))) = f . Let us fix a such that a > n. We have: v(T r(Y (a))) = t and by T -scheme: v(Y (a)) = t Thus, ∃a ∈ |M| v(Y (a)) = t. But we already proved that this is impossible. Finally we have that ∀n ∈ |M| v(Y (n)) = u, i.e. we assign values u to all of the Yablo sentences.

3.5.3

Supervaluations

Supervaluationism is a semantics that was originally invented for dealing with irreferential singular terms and vagueness (see e.g. van Fraassen [31]). According to it, some sentences lack truth-value and are imprecise. However, they may be precisified by an interpretation in a way extending the original one. A sentence is supervaluation-true if it is true under all precisifications. In the so-called supervaluation approach to partial models we say that sentence ϕ is regarded as supervaluationtrue in a partial model if ϕ comes out true in every way of extending this partial model to a total, classical model. We understand the notion of supervaluation-false in an analogous way. To make things precise: For any partial model M = (|M|, E, A) (satisfying E ∩ A = ∅), we say that M1 = (|M1 |, E1 , A1 ) is a classical extension of M if and only if: (i) |M| = |M1 |, E ⊆ E1 and A ⊆ A1 (i.e. M1 is an extension of M) and (ii) E1 ∪ A1 = |M1 | and E1 ∩ A1 = ∅ (i.e. truth predicate is classical in M1 ) Definition 3.5.6. (Supervaluation scheme) For any fixed-point model M = (|M|, E, A) and for any LT r -sentence ϕ, we say that ϕ is true in M under the SV -scheme, denoted by: M |=SV ϕ if and only if for any M1 being a classical extension of M we have M1 |= ϕ. So we see that the definition of supervaluation scheme leaves a possibility for a sentence to be neither supervaluation-true nor supervaluation-false. However, every classical tautology is supervaluation-true in all partial models. This makes supervaluation logic in a sense closer to classical logic than (Strong) Kleene logic. Now we turn to analysis of the properties of Yablo sequences in partial models with supervaluation as an evaluation scheme. Theorem 3.5.7. For each Yablo sentence Y(n) (i) (|M|, E, A) 6|=SV Y (n), (ii) (|M|, E, A) 6|=SV ¬Y (n).

63

Proof. Let us fix n and suppose that M |=SV Y (n). By the definition of the SV -scheme we have that for any classical extension M1 of M the following holds: M1 |= Y (n). By the definition of Yablo sentence this means that M1 |= ∀x (x > n ⇒ ¬T r(pY (x)q). ˙ By the definition of classical semantics we have that ∀a > n M1 |= a > n ⇒ ¬T r(pY (a)q). From this we get: (1) M1 |= ¬T r(pY (n + 1)q) and (2) M1 |= a > n + 1 ⇒ ¬T r(pY (a)q). Since ¬T r(pY (n + 1)q) holds in any M1 extending M, we have that pY (n + 1)q has to be in the set A. Therefore p¬Y (n + 1)q is in E. Thus, for any M1 extending M we have: M1 |= T r(p¬Y (n + 1)q). Hence, M |=SV T r(p¬Y (n + 1)q). By the fact that M is a fixed-point model we have M |=SV ¬Y (n + 1). Therefore ¬Y (n + 1) has to be satisfied in extensions of M, so M1 |= ¬Y (n + 1). But from the definition of Yablo sentence, by (2) we have: M1 |= Y (n + 1)). Since M1 is classical, this is a contradiction. Let us fix n and suppose that M |=SV ¬Y (n). By the definition of the SV -scheme we have that for any classical extension M1 of M the following holds: M1 |= ¬Y (n). By the definition of Yablo sentence this means that M1 |= ∃x (x > n ∧ T r(pY (x)q). ˙ By the definition of classical semantics we have that there is a ∈ |M1 | such that M1 |= a > n ∧ T r(pY (a)q). Let us fix such an a > n. We have then: M1 |= T r(pY (a)q). For any M1 extending M we have M1 |= T r(pY (a)q). Hence, M |=SV T r(pY (a)q). By the fact that M is a fixed-point model we have M |=SV Y (a). Therefore Y (a) has to be satisfied in extensions of M, so M1 |= Y (a), so there is a ∈ |M1 | such that M1 |= Y (a). But since the choice of M1 was arbitrary, we have then M |=SV Y (a), which as we have just shown is impossible. Corollary 3.5.8. For any partial fixed-point model M = (|M|, E, A) and for the Strong Kleene, Weak Kleene and Supervaluation valuation schema, all Yablo sentences Y (n) are neither true nor false under these schemas in M, or as to put it: the truth-value of all Yablo sentences Y (n) in fixed-point partial models under any of the above valuation schema, is indeterminate.

3.6

Yablo sequences in Lsl

In this section we consider the so-called sl-semantics of F M -domains. This framework has been developed by M. Mostowski in [55], [56] and was motivated by computational foundations of mathematics and the search for the semantics under which first-order sentences would be interpreted in potentially infnite domains. The latter are understood within this framework as growing sequences of finite models. We begin with limiting our attention to such finite models over a purely relational vocabulary such that the initial segments of natural numbers are the domains of those models. Let R ⊆ ω r be an arithmetical relation. Then by R(n) we denote R ∩ {0, 1, ..., n − 1}. For any model A over the signature σ = (R1 , ..., Rk ) we define the F M -domain of A as follows: (n) (n) F M (A) = {An : n = 1, 2, ...}, where An = ({0, 1, ..., n − 1}, R1 , ..., Rk ). For the purposes of this 64

section, by N we denote the standard model of arithmetic (ω, +, ×, 0, s, k ∧ M |= Y (n)). Let us take take such n. Let us fix k and take M ∈ K30 with card(M) > k such that pY (n + 1)q ∈ |M| and: (i) M |= Y (n). (ii) M |= Y (n + 1) ≡ ∀x(x > n + 1 ⇒ ¬T r(pY (x)q)). ˙ (iii) M |= Y (n + 1) ≡ T r(pY (n + 1)q). From (i) we obtain: (1) M |= ¬T r(pY (n + 1)q), as well as: (2) M |= ∀x(x > n + 1 ⇒ ¬T r(pY (x)q)). ˙ Now, from (1), by (iii) we have that: M |= ¬Y (n + 1), and from (2), by (ii) we have that: M |= Y (n + 1), which gives a contradiction that ends the proof. We will now show a construction of a class K such that K |=sl Y D + AD, which means that the satisfaction of the premise of the theorem 3.6.7 is not empty. Definition 3.6.8. F M (N )Y and sl(F M (N )Y ) We fix the formula Y (x) defined in the corollary 3.6.6. A family of models F M (N )Y is an F M (N )T domain {NkY : k ∈ ω} such that NkY = (Nk , Tk ), where Tk = T Ak ∪ T Yk , and: T Ak = {pϕq : ϕ ∈ SentL and Nk |= ϕ} ∩ |Nk | T Yk = {pY (m)q : pY (m)q ∈ |Nk | ∧ pY (m + 1)q ∈ / |Nk |}. Naturally, sl(F M (N )Y ) = {ϕ : F M (N )Y |=sl ϕ}. 30

Without loss of generality we could assume that M = NkT for some natural k.

66

The construction is well-defined, because for every n there is m such that for all k > m and for all j ≤ n: NkY |= Y (j) ≡ ∀x > j ¬T r(pY (x)q). ˙ Moreover, for every n there is m such that for all k > m and for all j ≤ n: pY (j)q ∈ |NkY |, and there is m such that for every k > m there is n such that for all j ≤ n: pY (j)q ∈ |NkY |. We also have that for every n there is k such that: pY (n)q ∈ |NkY | and pY (n + 1)q ∈ / |NkY |, and there is m such that for every k > m there is exactly one n such that: pY (n)q ∈ |NkY | and pY (n + 1)q ∈ / |NkY |. It is also clear that we have: F M (N )Y |=sl ϕ ≡ T r(pϕq), F M (N )Y |=sl Y (n) ≡ T r(pY (n)q), for all n ∈ ω and for all ϕ ∈ SentL . It is worth noting that the family F M (N )Y is not a proper potentially-infinite domain in the sense defined in Mostowski [58], i.e. for any natural numbers r < s NrY is not a submodel of NsY , since the interpretation of the truth predicate T r varies between subsequent models from the domain. Theorem 3.6.9. ∀n ∈ ω F M (N )Y |=sl ¬Y (n) Proof. We claim that for any n there exists m such that for any k > m: NkY |= ¬Y (n). Y | and for any x < n + 1 and any k > m Indeed, let us fix n and take m such that pY (n + 1)q ∈ |Nm we have: NkY |= Y (x) ≡ ∀w > x ¬T r(pY (w)q). ˙

Let k > m. Then obviously pY (n + 1)q ∈ |NkY |. Let j be the greatest number such that pY (j)q ∈ |NkY |. Such a number exists since our F M -domain is infinite and every model in it is finite. Obviously, n < j. From the definition of the class F M (N )Y and by the choice of j we obtain: NkY |= T r(pY (j)q), and for any x < j we get: NkY |= ∃w(w > x T r(pY (w)q)). ˙ hence for any x < j, by the definition of Yablo sentence Y (x) the following holds: NkY |= ¬Y (x). Thus, since n < j, we obtain: NkY |= ¬Y (n), which ends the proof. 67

Corollary 3.6.10. sl(F M (N )Y ) is ω-inconsistent. Proof. We have just shown that ∀n ∈ ω (¬Y (n) ∈ sl(F M (N )Y )). We obviously also have that there is m such that for all k > m there is j such that NkY |= Y (j), so by existential generalization we obtain that there is m such that for all k > m NkY |= ∃xY (x) and thus: ∃xY (x) ∈ sl(F M (N )Y ).

68

4 4.1

Summary Summary of results

In this thesis we have shown that: 1. By the diagonal lemma for formulae with two free variables Yablo sentences exist provably in a sufficiently rich theory. 2. By compactness (and hence by the existence of nonstandard models of arithmetic) Yablo sequences taken together with a certain class of local disquotational principles are consistent yet ω-inconsistent (and they are simply inconsistent only if taken together with a uniform disquotation principle for Yablo sentences. 3. The rewriting of Yablo sequence to second-order language gives an unsatisfiable, yet still not inconsistent theory. 4. There is a subsystem of second-order arithmetic which has a model satisfying Yablo disquotation. 5. Concerning Yablo sentences in axiomatic theories of truth: (a) Yablo sentences are independent of KF and assuming that the theory F S is consistent, they are independent of F S - these theories neither prove nor disprove Yablo sentences. (b) F S proves that all Yablo sentences are equivalent to the liar sentence. (c) KF + COM P L uniformly disproves all Yablo sentences. (d) KF + CON S may prove, refute or leave Yablo sentences undecided, depending on the choice of the formula satisfying the Yablo condition. But if a sentence Y (x) satisfies this condition in KF itself, then KF + CON S uniformly proves all Yablo sentences. (e) If a sentence Y (x) satisfies Yablo condition in KF , then KF + CON S proves that all Yablo sentences are equivalent to the liar sentence. 6. For any partial fixed-point model and for the Strong Kleene, Weak Kleene and Supervaluation valuation schema, all Yablo sentences Y (n) are neither true nor false under these schema or as to put it: the truth-value of all Yablo sentences Y (n) in fixed-point partial models under any of the above valuation scheme, is indeterminate. 7. Under the logic Lsl of sufficiently large finite models (i.e. logic of potential infinity) Y D entails ¬Y (n) for any natural n (or, as to put it: Y D entails that all the Yablo sentences are false in the limit). (4), (6) and (7) are original results.

4.2

Sources of the properties of Yablo sequences

We have addressed the question of the ways in which different aspects of our formal theories affect the metalogical properties of Yablo sequences. We may typologize these aspects and divide them into three main groups: (1) logic behind the theory, (2) arithmetical content of the theory, (3) the notion of truth employed in the theory .

69

Ad. (1) What we mean here is that depending on the logic we adopt - in terms of its semantics, language and inference rules, the Yablo sentences may obtain different properties. The main oppositions or lines of potential conflict that are to notice here are: (a) semantics: classical (two-valued) logic vs. partial (many-valued) logic - as we have shown, under any reasonable valuation scheme, the truth-value of all Yablo sentences Y (n) in any fixed-point partial model is indeterminate. This taken together with the fact that the theory with Yablo sequence is consistent shall be interpreted as a testimony to ungroundedness of Yablo formulae (in the sense of Kripke’s concept of truth). On the other hand, while maintaining classical logic, we have to agree that there are models of arithmetic (extended with the interpretation of the truth predicate) in which some Yablo sentences are interpreted as true and the rest of them are false, where the Yablo sentence interpreted in a model as a true one is nonstandard. In the standard model, there is no consistent interpretation of the truth predicate for Yablo disquotation principle. Under many-valued logic, on the other hand, the fixed-point model in which we prove that the truth value of Yablo sentence is indeterminate, is arbitrary. Therefore in a fixed-point model build from the standard model it will also hold under partial semantics that Yablo sentences are of unknown truth value. This seems to be an argument in favor of adopting partial logic in theory of truth. (b) language: first-order logic vs. second-order logic - a first-order arithmetical theory in the language extended with the truth predicate and with adjoined disquotation principles for Yablo sentences is satisfiable, hence consistent. However, the second-order rewriting of such theory (formalized in a sufficiently strong theory) is unsatisfiable, yet consistent. The source of this is the fact that full semantics for second-order logic cannot be complete and that second-order induction axiom makes arithmetic categorical, hence the only model of such a rewriting is the standard one in which as we know, a Yablo sequence with T -biconditionals (Yablo theory) for the members of Yablo sequence is unsatisfiable. Yet it is still impossible to derive contradiction in a finite number of steps from the second-order rewriting of Yablo theory. The interpretation of this result shall then depend on the philosophical stance concernig models of arithmetic. Everything indicates that the question of language (in the sense presented here) reduces to the question about ontology (arithmetic) behind our theory. (c) inference rules: finitary rules vs. infinitary rules - if we agree to reason on the basis of infinite number of premises - i.e. agree to some infinitary rule of inference, like the ω-rule, we will derive the contradiction from Yablo sentences. If we decide for any reason to stay on the ground of any finitary proof system, irrespective of the language we will employ to reasoning, there is no possiblity for us to derive inconsistency from Yablo sentences. This gives another strong reason not to consider Yablo paradox, a proper paradox, but rather an ω-paradox. Ad. (2) Another factor having strong influence on the behaviour of Yablo sequences is the ontology that underlies our theoretical considerations and is given by the arithmetical model we are developing our truth theory on: (a) finite models (potentially infinite) vs. (actually) infinite ones - there might be philosophical reasons independent of truth theories for someone to stand on one of those 70

two positions. A finitist will have an easy way to solve the paradox, while an infinitist must answer a question about the approach to arithmetic he adopts (see below). (b) standard model vs. nonstandard models - if for some philosophical reasons one believes that the standard model of arithmetic is the only ontologically acceptable model and is working in some truth theory, then it is a fact that Yablo paradox is a problem for him. If for some reasons (e.g. believing that finitary first-order logic is the only legal logic) one sees no reason to discard nonstandard models and accepts them as good description of possible structures of arithmetics, then there are obviously questions he needs to answer (e.g. any truth theory containg the T -biconditionals for Yablo sentences will be a theory of truth without standard model) but in terms of Yablo paradox he may consistently state that it is not a genuine paradox, but again: an ω-paradox. Ad. (3) It seems that various axiomatic truth theories give good insight into differences between the properties of the notions of truth we want to adopt. The main lines of opposition we saw are: (a) independence vs. decidability - as we saw the theories KF and F S do not decide Yablo sentences, whereas in some situations, both KF + COM P L and KF + CON S do respectively disprove or prove Yablo sentences. (b) consistency vs. completeness - if we take upon the completeness axioms that says that for any sentence if it is not true, then its negation must be true, then we obtain that all Yablo sentences are provably false, whereas if we take upon the consistency axiom that states that it is not possible for a sentence and its negation to be simultaneously true, the theory proves all Yablo sentences

4.3

Possible solutions to Yablo paradox

As far as the analysis in this thesis has gone, we may develop three possible answers to Yablo paradox that can be held by somebody committed to a theory of arithmetical truth. 1. There are two principal ways of looking at arithmetic. Adopting the first one, we take the standard model of natural numbers N as a start, and being focused on this structure, we are mainly interested in T h(N). But there is a second approach, according to which we are mainly interested in what we can prove about natural numbers within some formal, axiomatized arithmetical first-order theory (this theory may be thought of as an approximation of T h(N)) satisfying some intuitive conditions. A proponent of the first approach has to deal with Yablo sentences if he wants to commit himself to any, even very weak, notion of truth since then Yablo sentences cannot be consistently evaluated in the model. However, it seems that if one conceives arithmetics simply as T h(N), then he will also commit to ω-rule within his reasoning, so it would be possible for him to prove the inconsistency of Yablo sequence and hence consider it as a phenomenon equivalent to the liar sentence. 2. A representant of the second approach, however, may decide that as the derivation of consistency requires means that are illegal from the point of view of first-order, finitary logic, Yablo paradox is only an ω-paradox and as such is not a contradiction but at most an interesting formal phenomenon. Within this approach, the only way to ascribe any further, stronger properties to Yablo sentences is by analyzing them in axiomatic truth theories - such as KF or F S. 3. A non-strict finitist, not accepting the notion of actual infinity may adopt the sl-theory of 71

arithmetics as an adequate explication of the concept of potential infinity and simply give an answer to the Yablo paradox that in the limit (i.e. under the sl-semantics on the FM-domain of given arithmetical model) all the Yablo sentences are false and there is no reason to be worried. 4. Finally, one may simply discard two-valued logic (maybe for some philosophical reasons different from the ones stemming from theories of truth) and within truth theory adopt one of the valuation scheme that were discussed in the previous chapter and simply respond that Yablo sentences are ungrounded. It is worth noting that the solutions proposed above do not have to exclude each other, e.g. one may simultaneously be in favour of the second approach to arithmetic and to many-valued semantics.

4.4

Other questions concerning Yablo sequences

First of all, we did not cover the entire topic of Yablo sequences and Yablo paradox in this thesis. There are two main groups of problems and questions that we did not approach as they seem a subject for a separate, independent analysis: (a) question of self-reference: are Yablo sentences self-referential or not? Is self-reference the source of the paradox? For discussion on this topic, see first of all Sorensen [68] and also: [5], [6], [19], [20], [21], [42], [50], [61], [62], [66], [70], [72] and [76]. (b) mathematical interpretations of Yablo sequences in provability theory, topology and set theory - what are the ways in which Yablo sequences can be re-read in different mathematical contexts and what does these re-readings tell about those contexts? For the discussion, see: [8], [17], [29], [30], [34], [35]

72

References [1] Z. Adamowicz and P. Zbierski, Logic of mathematics, John Wiley & Sons, New York, 1997. [2] J. Barwise and J. Schlipf, An introduction to recursively saturated and resplendent models, Journal of Symbolic Logic 41 (1976), 531-536. [3] J. Barwise and J. Etchemendy, The liar, Oxford University Press, New York, 1984. [4] J. Barwise and L. Moss, Vicious circles. On the mathematics of non-wellwounded phenomena, CSLI Publications, Stanford, 1996. [5] J.C. Beall, Completing Sorensen’s menu: A non-modal yabloesque Curry, Mind 108 (1999), 737-739. [6] J.C. Beall, Is Yablo’s paradox non-circular?, Analysis 61 (2001), 176-187. [7] J.C. Beall (ed.), Revenge of the liar. New essays on the paradox, Oxford University Press, Oxford, 2007. [8] C. Bernardi, Topological approach to Yablo’s paradox, Notre Dame Journal of Formal Logic 50 (2009), 331-338. [9] S. Blamey, Partial logic, in D. M. Gabbay and F. Guenthner (eds.), Handbook of Philosophical Logic, vol. IV, Kluwer Academic Publishers, Dordrecht, 1986, pp. 1-70. [10] J.P. Burgess, The truth is never simple, Journal of Symbolic Logic 51 (1986), 663-681. [11] J. Cain and Z. Damnjanovic, A fixed point theorem for the Weak Kleene valuation scheme, Journal of Symbolic Logic 56 (1991), 1452-1468. [12] A. Cantini, Notes on formal theories of truth, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 35 (1989), 97-130. [13] A. Church and S. C. Kleene, Formal definitions in the theory of ordinal numbers, Fundamenta mathematicae 28 (1937), 11-21. [14] C. Cieślinski, Heterologicality and incompleteness, Mathematical Logic Quarterly 48 (2002), 105-110. [15] C. Cieślinski, Löb’s theorem in a set-theoretical setting, Studia Logica 75 (2003), 319-326. [16] C. Cieślinski, Deflacyjna koncepcja prawdy. Wybrane zagadnienia logiczne, Semper, Warszawa, 2009. [17] C. Cieślinski and R. Urbaniak, Gödelizing the Yablo sequence, forthcoming in: Journal of Philosophical Logic, DOI 10.1007/s10992-012-9244-4 (access: June 12, 2013). [18] C. Cieślinski, Yablo sequences in truth theories, in: K. Lodaya (ed.), Logic and its applications (Lecture Notes in Computer Science LNCS 7750), Springer-Verlag, Berlin Heidelberg, 2013, pp. 127-138. 73

[19] R. Cook Curry, Yablo and duality, Analysis 69 (2002), 612-620. [20] R. Cook, Patterns of paradox, Journal of Symbolic Logic 69 (2004), 767-774. [21] R. Cook, There are non-circular paradoxes (but Yablo’s isn’t one of them), The Monist 89 (2006), 118-149. [22] R. Cook, Paradoxes, Polity, Cambridge, 2013. [23] W. Craig, On axiomatisability within a system, Journal of Symbolic Logic 18 (1953), 30-32. [24] H. Curry, The inconsistency of certain formal logics, Journal of Symbolic Logic 7 (1942), 115-117. [25] S. Feferman, Degrees of unsolvability associated with classes of formalized theories, Journal of Symbolic Logic 22 (1957), 161-175. [26] S. Feferman, Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae 49 (1960), 35-92. [27] S. Feferman, Reflecting on Incompleteness, Journal of Symbolic Logic 56 (1991), 1-49. [28] H. Field, Saving truth from paradox, Oxford University Press, Oxford, 2008. [29] T. Forster, The significance of Yablo’s paradox without self-reference, 1996, in manuscript: https://www.dpmms.cam.ac.uk/˜tf/yablo.ps (access: June 12, 2013). [30] T. Forster, Yablo’s paradox and the omitting types theorem for propositional languages, 2012, in manuscript: https://www.dpmms.cam.ac.uk/˜tf/yabloomittingtypes.pdf (access: June 12, 2013). [31] B. van Fraassen, Singular Terms, Truth-Value Gaps and Free Logic, Journal of Philosophy 63 (1966), 481-495. [32] H. Friedman and M. Sheard, Axiomatic theories of self-referential truth, Annals of Pure and Applied Logic 33 (1987), 1-21. [33] K. Gödel, On formally undecidable propositions of Principia Mathematica and related systems I, in: J. van Heijenoort (ed.), From Frege to Gödel. A source book in mathematical logic 1879-1931, Harvard University Press, Cambridge MA, 1967, pp. 596-616. [34] L. Goldstein, A yabloesque paradox in set theory, Analysis 54 (1994), 223-227. [35] L. Goldstein, Fibonacci, Yablo, and the cassationist approach to paradox, Mind 115 (2006), 867-890. [36] A. Gupta and R. L. Martin, A fixed point theorem for the Weak Kleene valuation scheme, Journal of Philosophical Logic 13 (1984), 131-135. [37] P. Hajek and P. Pudlak, Metamathematics of first-order arithmetic, Springer Verlag, Berlin, 1993. 74

[38] V. Halbach, A system of complete and consistent truth, Notre Dame Journal of Formal Logic 35 (1994), 311-327. [39] V. Halbach and H. Leitgeb and P. Welch, Possible world semantics for modal notions conceived as predicates, Journal of Philosophical Logic 32 (2003), 179-223. [40] V. Halbach and L. Horsten, Axiomatizing Kripke’s theory of truth, Journal of Symbolic Logic 71 (2006), 677-712. [41] V. Halbach, Axiomatic theories of truth, Cambridge University Press, Cambridge, 2011. [42] J. Hardy, Is Yablo’s paradox liar-like?, Analysis 55 (1995), 197-198. [43] J. van Heijenoort (ed.), From Frege to Gödel. A source book in mathematical logic 1879-1931, Harvard University Press, Cambridge MA, 1967. [44] L. Horsten, Tarskian turn. Deflationism and axiomatic truth, MIT Press, Cambridge MA, 2011. [45] R. Kaye, Models of Peano Arithmetic, Oxford University Press, Oxford, 1991. [46] J. Ketland, Yablo’s paradox and ω-inconsistency, Synthese 145 (2005), 295-302. [47] R. Kossak and J. Schmerl, The structure of models of Peano Arithmetic, Clarendon Press, Oxford, 2006. [48] S. Kripke, Outline of a theory of truth, Journal of Philosophy 72 (1975), 690-716. [49] H. Leitgeb, Theories of truth which have no standard models, Studia Logica 68 (2001), 69-87. [50] H. Leitgeb, What is a self-referential sentence? Critical remarks on the alleged (non)circularity of Yablo’s paradox, Logique et Analyse 207 (2002), 177-178. [51] D. Marker, Model theory. An introduction, Springer Verlag, New York, 2002. [52] V. McGee, How truth-like can a predicate be? A negative result, Journal of Philosphical Logic 14 (1985), 399-410. [53] V. McGee, Maximally consistent sets of instances of Tarski schema (T), Journal of Philosophical Logic 21 (1992), 235-241. [54] E. Mendelson, Introduction to mathematical logic, Wadsworth Inc., Belmont, 1987. [55] M. Mostowski, On representing concepts in finite models, Mathematical Logic Quarterly 47 (2001), 513-523. [56] M. Mostowski, On representing semantics in finite models, in: A. Rojszczak and J. Cachro and G. Kurczewski (eds.) Philosophical Dimensions of Logic and Science, Kluwer Academic Publishers, Dordrecht, 2001, pp. 15-28.

75

[57] M. Mostowski and K. Zdanowski, FM-representability and beyond, in: S. B. Cooper and B. Löwe, and L. Torenvliet (eds.) Archive for Mathematical Logic, Springer-Verlag, Berlin, 2005, pp. 358-367. [58] M. Mostowski Truth in the limit, 2012, in manuscript. [59] R. Murawski Recursive functions and metamathematics, Kluwer Academic Publishers, Dordrecht, 1999. [60] L.M. Picollo, Yablo’s paradox in second-order languages: consistency and unsatisfiability, Studia Logica 101 (2013), 601-617. [61] G. Priest, The structure of the paradoxes of self reference, Mind 103 (2002), 25-34. [62] G. Priest, Yablo’s paradox, Analysis 57 (1997), 236-242. [63] W.N. Reinhardt, Some remarks on extending and interpreting theories with a partial predicate for truth, Journal of Philosophical Logic 15 (1986), 219-251. [64] G. Restall, Curry’s Revenge: the costs of non-classical solutions to the paradoxes of selfreference, in: J.C. Beall (ed.), Revenge of the liar. New essays on the paradox, Oxford University Press, Oxford, 2007, pp. 262-271. [65] P. Smith, Introduction to Gödel’s theorems, Cambridge University Press, Cambridge, 2007. [66] P. Schlenker, The elimination of self-reference. Generalized Yablo-series and the theory of truth, Journal of Philosophical Logic 36 (2007), 251-307. [67] S. Simpson, Subsystems of second-order arithmetic, Cambridge University Press, Cambridge, 2009. [68] R. Sorensen, Yablo’s paradox and kindred infinite liars, Mind 107 (1998), 137-155. [69] R. Sorensen, A brief history of the paradox. Philosophy and the labirynths of mind, Oxford University Press, Oxford, 2005. [70] N. Tennant, On paradox without self-reference, Analysis 55 (1995), 199-207. [71] S. Tennenbaum, Non-archimedean models for arithmetic, Notices of American Mathematical Society 6 (1959), 270. [72] R. Urbaniak, Leitgeb about Yablo, Logique et Analyse 207 (2009), 239-254. [73] A. Visser, Semantics and the liar paradox, in: D. Gabbay, F. Guenthner (eds.), Handbook of Philosophical Logic, vol. IV, Kluwer Academic Publishers, Dordrecht, 1989, pp. 617-706. [74] S. Yablo, Truth and reflection, Journal of Philosophical Logic 14 (1985), 297-349. [75] S. Yablo, Paradox without self-reference, Analysis 52 (1993), 251-252. [76] S. Yablo, Circularity and self-reference, in: T. Bolander and V. Hendricks and S. Petersen (eds.), Self-reference, CSLI Publications, Stanford, 2004, pp. 165-183.

76