Yablo paradox in partial semantics and potentially innite domains

Yablo paradox in partial semantics and potentially infinite domains Michal Tomasz Godziszewski April 22, 2015 Abstract The paper describes properties of Yablo sequences over growing domains of finite arithmetical models and over partial models of Kripke truth theory. We show that 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 equivalently: the truth-value of all Yablo sentences Y (n) in fixed-point partial models under any of the above valuation scheme, is indeterminate. Furthermore, we show that under the logic of sufficiently large finite models (logic of potential infinity) all the Yablo sentences are false in the limit. The main philosophical conclusion is that a finitist, not accepting the notion of actual infinity may adopt the sl-theory of 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 a given arithmetical model) all the Yablo sentences are false.

1

Preliminaries

In 1993, Stephen Yablo gave in [27] an example of a semantic paradox that, according to the author, does not involve self-reference. He began his seminal paper with a question: Why are some sentences paradoxical while others are not? Since Russell the universal answer has been: circularity, and more especially self-reference. It is clear that the appearance of self-reference in a sentence is not a sufficient condition for the sentence to be paradoxical. However, it has been widely believed among philosophers that self-reference or circularity is a necessary feature of a sentence or a set of sentences that we claim to be paradoxical or antinomial. We will now present the paradox and define formally the sequence of sentences that generates the paradox within the framework of arithmetic. Let us consider the following infinite sequence of sentences: Y0 = ∀k > 0 ¬ T r(Yk ) Y1 = ∀k > 1 ¬ T r(Yk ) 1

Y2 = ∀k > 2 ¬ T r(Yk ) ... Yn = ∀k > n ¬ T r(Yk ) ... We may notice that every sentence of the sequence (Yn )n∈ω refers only to the subsequent sentences and no sentence refers to itself explicitly. Therefore we have an infinite, noncircular (and with no loops) sequence of non-self-referential sentences. Moreover, we can ask a question whether any of the sentences in the sequence is true. We then reason as follows: 1. We fix n and we assume Yn to be true. 2. Then for any j > n Yj is false. 3. In particular Yn+1 is false. 4. Then also for any j > n + 1 Yj is false. 5. But the above is exactly what Yn+1 states, so Yn+1 is true. 6. This is a contradiction between (3) and (5). Therefore Yn cannot be true, hence it is false. 7. However, we can conduct the above reasoning for any n, so no Yn is true − each Yn must be false. 8. In particular, for any j > 17 Yj is false. 9. But this is exactly what Y17 states , hence it is true. 10. This gives us the contradiction between (7) and (9). Hence we get a paradox. We may now observe an interesting property of the reasoning presented above. In order to derive the contradiction we have to use strong assumptions concerning the notion of truth - namely we have to assume that ∀n (Yn ≡ T r(Yn )). With a weaker assumption about the truth predicate, a derivation of a contradiction would be possible if we used some infinitary inference rule like the ω-rule (which will be defined below). Using only finitary inference rules and simultaneously adopting some weaker assumptions about the notion of truth does not lead to a contradiction. Further sections are devoted to a detailed analysis of those interesting properties of Yablo sequences. One might ask how we actually know that Yablo sequences exist in formal theories. This is a decent question since what we did before were just some vague operations on natural language sentences that were not properly defined. It is possible to construct the Yablo sequence within a given theory, but in order to do so, we need to use a general version of the diagonal lemma (for formulae with two free variables in the language containing the truth predicate). Diagonal Lemma 1. Let T be a first-order theory in the language LT r (a language of arithmetic extended by a truth predicate), containing Robinson’s arithmetic Q. Then, for any LT r -formula ϕ(x, y) there is a LT r -formula ψ(x) such that: T ` ψ(x) ≡ ϕ(x, pψ(x)q)

2

Proof. Let ϕ(x, y) be a fixed first-order formula of the language LT r . We will construct a diagonal formula ψ(x), introducing auxiliary definitions: (1) ζ(x, y) := ϕ(x, sub(y, pyq, name(y))) (2) m := pζ(x, y)q (3) ψ(x) := ζ(x, m). With these definitions we get a sequence of equivalences. First of all, we notice that the definition of ψ(x) in (3) simply gives: T ` ψ(x) ≡ ζ(x, m) From this and by the definition of ζ(x) in (1) we have: T ` ψ(x) ≡ ϕ(x, sub(m, pyq, name(m))) Applying the definition of m from (2), we obtain: T ` ψ(x) ≡ ϕ(x, sub(pζ(x, y)q, pyq, name(m))) By the fact that sub and name represent appropriate functions, we get: T ` ψ(x) ≡ ϕ(x, pζ(x, m)q) Using the definition of ψ(x) again, we finally find out: T ` ψ(x) ≡ ϕ(x, pψ(x)q) The expression Qx T r(pϕ(x)q), ˙ where Q ∈ {∀, ∃} is to be read as follows: for all natural numbers x (there exists a natural number x such that), the result of substituting a numeral denoting x for a variable free in ϕ is true. Definition 1. (Yablo Formula) Y (x) is a Yablo formula in a theory T iff it satisfies the Yablo condition, i.e.: ˙ T ` ∀x(Y (x) ≡ ∀w > x¬T r(pY (w)q)). This also gives rise to a natural way of defining the sentences from the sequence - we obtain them via the following definition: Definition 2. (Yablo Sentence) ϕ is a Yablo sentence in a theory T iff it is obtained by substituting a numeral for x in Yablo formula Y (x) This enables us to prove that we are not dealing with fictitious entities, but with properly defined, formal objects. Next, we prove: Theorem 1. (Existence of Yablo Formula) (G. Priest [23]) Let T be a theory in a language LT r containing Robinson arithmetic Q. Then there exists a Yablo formula in T . 3

Proof. Let ϕ(x, y) = ∀w > x ¬T r(sub(y, pyq, name(w))). By the Diagonal Lemma 2, there is a formula Y (x) such that: T ` Y (x) ≡ ∀w > x ¬T r(sub(pY (x)q, pyq, name(w))). Therefore by the fact that sub represents appropriate function, we have: T ` Y (x) ≡ ∀w > x ¬T r(pY (w)q).Thus ˙ we may conclude that Y (x) is a Yablo formula. Hence Yablo sentences exist. An interesting question one might ask about the Yablo sequences is about their consistency. Despite the fact that on the level of natural language it is not difficult to derive contradiction from the definition of Yablo sequence, its formalization lets us prove that any infinite Yablo sequence is consistent, even though it is ω-inconsistent. We show that a Yablo sequence with a certain class of T -equivalences gives a consistent yet ω-inconsistent theory. Up to the Theorem 3, results from this section were originally obtained by J. Ketland in [14]. Definition 3. (ω-consistency) Let T be a first-order theory in the arithmetical language L. T is ω-consistent if there is no ϕ(x) ∈ F rmL such that simultaneously: ∀n ∈ ω T ` ¬ϕ(n) T ` ∃xϕ(x)

(1) (2)

If there is such a formula ϕ, then we say that T is ω-inconsistent theory. Definition 4. (P AF ) Let LF be a language of arithmetic extended by one monadic predicate F . P AF := P A ∪ {F (n) ≡ ∀x > n ¬F (x) : n ∈ ω} Lemma 1. P AF is ω-inconsistent Proof. Let us consider T = P AF ∪ {F (n)} for a fixed n ∈ ω. By the definition of T , we have (∗) T ` ∀x > 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 5. (Local Arithmetical Disquotation) AD = {T r(pϕq) ≡ ϕ : ϕ ∈ SentL (T r does not occur in ϕ)}. Definition 6. (Local Yablo Disquotation) YD = {T r(pY (n)q) ≡ Y (n) : Y (n) belongs to the Yablo sequence}. 4

Definition 7. (P AD ) Let P AT be a theory obtained from P A by extending the language of arithmetic with a truth predicate T r1 . 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 2. P AD is ω-inconsistent Proof. By formal definition of Yablo formulae we obtain: ˙ By the fact that P AD contains Y D we get: ∀n ∈ ω P AD ` Y (n) ≡ ∀x > n ¬T r(pY (x)q). ∀n ∈ ω P AD ` T r(pY (n)q) ≡ ∀x > n ¬T r(pY (x)q). ˙ ˙ With this definition we get: Let us denote F (x) := T r(p(x)q). ∀n ∈ ω P AD ` F (n) ≡ ∀x > n¬F (x). Applying the preceding lemma to this fact ends the proof. Lemma 2. 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. P A− D is consistent. 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), ˙

(3)

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. 1

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

5

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).

(4)

Therefore we may conclude that (M, S) |= Y D which ends the proof. Theorem 4. 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), (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). 6

(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 1. 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 [?]. Definition 8. (Uniform Yablo Disquotation) ˙ ≡ Y (x)) (UYD) ∀x(T r(pY (x)q) Fact 1. T = P AT + U Y D is inconsistent.

7

Proof. We are working in T . By the definition of Yablo formula and existence theorem, ˙ From (U Y D) we then derive we have ∀x (Y (x) ≡ ∀w > x¬T r(pY (w)q)). (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∃yx < 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 9. (ω-rule) An ω-rule is a following infinitary inference rule defined for arithmetical formulae ϕ: ϕ(0), ϕ(1), ϕ(2), ..., ϕ(n), ... ∀x ϕ(x) Definition 10. 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 5. 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). In particular: (∗) P AωD ` ¬Y (23). 8

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.

2

Yablo paradox in partial semantics

we are going to consider the properties of Yablo sequences in partial models. Here we explain why the partial models are worth of interest. In 1975, Saul Kripke presented in [16] a semantical theory of self-referential truth that was a critical development of Tarski’s conception and has become very influential - since then it was broadly discussed and became a rich source of inspiration for proof-theoretical approaches to truth (see e.g.: [12]). Kripke’s purpose was to construct models of the language LT r (Let L be the language of arithmetic and LT r be L extended with the truth predicate T r) such that they would be adequate to self-referential character of the concept of truth. This means that some sentences (like the liar sentence λ) are left without any truth-value actually the intuition that the liar-sentences cannot have a determinate truth value is the basic motivation for developing a theory of truth in which T r is treated as a partial predicate. Kripke’s construction relies on the notion of partial model in which it is possible for some sentences that neither they nor their negations hold in the model. This is what discerns this theory from classical Tarskian approaches. The truth predicate T r is partially interpreted in the following sense: beginning with the standard model of arithmetic, we construct the model by transfinite induction in such a way that at each ordinal stage the truth predicate receives an extension E and an anti-extension A. The extension is the set of the codes of sentences that are determinately true at the given stage. The antiextension is the set of codes of sentences that are determinately false at the given stage. The sum A ∪ E is always a proper subset of the domain N, since otherwise T r would be a total predicate. We also demand that A ∩ E = ∅, since we do not want to allow the possibility that some sentence is both true and false. We will now present Kripke’s construction in more detail, following Kripke’s original paper as well as [13] and [12]. We begin with defining the Strong Kleene scheme which is an evaluation scheme used in the Kripke semantic construction. Strong Kleene models (or SK-models) are triples (M, S1 , S2 ), where M is an L-model and S1 and S2 are subsets of the universe of M. We 9

will limit our attention to the structures for which M = N. The definition of satisfaction will be given inductively with respect to the positive complexity of the formula. Definition 11. Positive Complexity (P C) of the formula is a function F rmLT r → N such that: For atomic formulae ϕ we put: P C(ϕ) = P C(¬ϕ) := 0 For ψ of the form: ¬¬ϕ, ∀xϕ, ∃cϕ, ¬∀xϕ or ¬∃xϕ we put: P C(ψ) := P C(ϕ) + 1. For γ of the form: ϕ ∧ ψ, ¬(ϕ ∧ ψ), ϕ ∨ ψ or ¬(ϕ ∨ ψ) we put: P C(γ) := max{P C(ϕ), P C(ψ)} + 1

We will now define the Strong Kleene scheme. Definition 12. For sets S1 , S2 ⊆ ω Strong Kleene scheme (N, S1 , S2 ) |=sk is a relation such that: For any constant terms s, t: 1. (N, S1 , S2 ) |=sk s = t iff val(s) = val(t). 2. (N, S1 , S2 ) |=sk s 6= t iff val(s) 6= val(t) . 3. (N, S1 , S2 ) |=sk T r(t) iff t is a constant term s.t. val(t) = pϕq, where ϕ ∈ SentLT r and pϕq ∈ S1 . 4. (N, S1 , S2 ) |=sk ¬T r(t) iff t is a constant term s.t. val(t) = pϕq, where ϕ ∈ SentLT r and pϕq ∈ S2 or for any ϕ ∈ SentLT r val(t) 6= pϕq . For any LT r -sentences ϕ, ψ: 5. (N, S1 , S2 ) |=sk ¬¬ϕ iff (N, S1 , S2 ) |=sk ϕ. 6. (N, S1 , S2 ) |=sk ϕ ∧ ψ iff (N, S1 , S2 ) |=sk ϕ and (N, S1 , S2 ) |=sk ψ. 7. (N, S1 , S2 ) |=sk ¬(ϕ ∧ ψ) iff (N, S1 , S2 ) |=sk ¬ϕ or (N, S1 , S2 ) |=sk ¬ψ. 8. (N, S1 , S2 ) |=sk ϕ ∨ ψ iff (N, S1 , S2 ) |=sk ϕ or (N, S1 , S2 ) |=sk ψ. 9. (N, S1 , S2 ) |=sk ¬(ϕ ∨ ψ) iff (N, S1 , S2 ) |=sk ¬ϕ and (N, S1 , S2 ) |=sk ¬ψ. For 10. 11. 12. 13.

any LT r -formula ϕ(x) with x as the only free variable: (N, S1 , S2 ) |=sk ∀xϕ(x) iff for every n ∈ ω (N, S1 , S2 ) |=sk ϕ(n). (N, S1 , S2 ) |=sk ¬∀xϕ(x) iff for some n ∈ ω (N, S1 , S2 ) |=sk ¬ϕ(n). (N, S1 , S2 ) |=sk ∃xϕ(x) iff for some n ∈ ω (N, S1 , S2 ) |=sk ϕ(n). (N, S1 , S2 ) |=sk ¬∃xϕ(x) iff for every n ∈ ω (N, S1 , S2 ) |=sk ¬ϕ(n).

Moreover, we have the following: 14. (N, S1 , S2 ) 6|=sk n for any n s.t. for any ϕ ∈ SentLT r n 6= pϕq. 10

Definition 13. For any ordinal α a partial model Mα is a triple (N, Eα , Aα ) such that: M0 = (N, ∅, ∅) and Eα+1 = {ϕ ∈ SentLT r : Mα |=sk ϕ} and Aα+1 = {ϕ ∈ SentLT r : Mα |=sk ¬ϕ}. For limit stages λ we set: Eλ =

[

Eα ,

α n) = f and v(¬T r(Y (a))) = f or (ii) v(a > n) = f and v(¬T r(Y (a))) = t or 16

(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). 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.

2.2

Strong Kleene

Kleene’s strong logic 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 18. 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. 17

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 f t u u t f

u t t t u t u t

Conjunction under SK-scheme ∧ f u t

f f f f

u t f f u u u t

Disjunction under SK-scheme ∨ f u t

f u t f u t u u t t t t

Negation under SK-scheme ϕ f u t

¬ϕ t u f

Quantifiers under SK-scheme   t v(∀xϕ(x)) = f   u   t v(∃xϕ(x)) = f   u

if ∀a ∈ |M| v(ϕ(a)) = t if ∃a ∈ |M| v(ϕ(a)) = f otherwise if ∃a ∈ |M| v(ϕ(a)) = t if ∀a ∈ |M| v(ϕ(a)) = f otherwise 18

Theorem 11. 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 ∈ |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.

2.3

Supervaluations

Supervaluationism is a semantics that was originally invented for dealing with irreferential singular terms and vagueness (see e.g. van Fraassen [9]). 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 supervaluation-true in a partial model if ϕ comes out true in

19

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 19. (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 12. For each Yablo sentence Y(n) (i) (|M|, E, A) 6|=SV Y (n), (ii) (|M|, E, A) 6|=SV ¬Y (n). 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 > 20

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 4. 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

Yablo sequences in potentially infinite domains

In this section we consider the so-called sl-semantics of F M -domains. This framework has been developed by M. Mostowski in [17], [18] 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: F M (A) = (n) (n) {An : n = 1, 2, ...}, where An = ({0, 1, ..., n − 1}, R1 , ..., Rk ). For the purposes of this 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 ∈ K8 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 previous theorem is not empty. Definition 24. 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 ϕ}. 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 |. 8

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

23

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 [20], 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 14. ∀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). Indeed, let us fix n and take m such that pY (n + 1)q ∈ |NmY | and for any x < n + 1 and any k > m 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. It is also easy to notice that: Theorem 15. For any class K, if K |=sl Y D, then for sufficiently large M ∈ K, there is exactly one n ∈ ω s.t. pY (n)q ∈ TM . 24

Theorem 16. For sufficiently large models M ∈ K, if pY (n)q ∈ TM , then pY (n)q ∈ |M| and pY (n + 1)q ∈ / |M|, Corollary 6. 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 ). The results above mean that 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). The main philosophical conclusion is that a non-strict finitist, not accepting the notion of actual infinity may adopt the sl-theory of 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

Sources of the properties of Yablo sequences

We have addressed the question of the ways in which different aspects 9 of our formal theories affect the metalogical properties of Yablo sequences. We may typologize these aspects and divide them into two main groups: (1) logic behind the theory, (2) arithmetical content of the theory. 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 be noticed 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 9

independent of the notion of truth employed in our theory - the latter aspects are analysed within the subject of axiomatic truth theories that are beyond the scope of this paper, see e.g. Cieslinski [6]

25

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) for 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 (see Picollo [21]). 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. (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 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 26

one believes that the standard model of arithmetic is the only ontologically acceptable model and he is working in a particular truth theory, then it is a fact that Yablo paradox is a problem for him. If for example one believes that finitary first-order logic is the only acceptable logic, then 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.

5

Possible solutions to Yablo paradox

We may develop three possible answers to Yablo paradox that can be held by somebody committed to a theory of arithmetical truth (again - independent of the axiomatic properties of the notion of truth that we employ). 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 since 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. 3. A non-strict finitist, not accepting the notion of actual infinity may adopt the sl-theory of 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 schemes that were discussed earlier and simply respond that Yablo sentences are ungrounded. 27

References [1] 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. [2] J.P. Burgess, The truth is never simple, Journal of Symbolic Logic 51 (1986), 663-681. [3] J. Cain and Z. Damnjanovic, A fixed point theorem for the Weak Kleene valuation scheme, Journal of Symbolic Logic 56 (1991), 1452-1468. [4] A. Cantini, Notes on formal theories of truth, Zeitschrift f¨ ur Mathematische Logik und Grundlagen der Mathematik 35 (1989), 97-130. [5] A. Church and S. C. Kleene, Formal definitions in the theory of ordinal numbers, Fundamenta mathematicae 28 (1937), 11-21. [6] C. Cie´slinski, 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. [7] S. Feferman, Degrees of unsolvability associated with classes of formalized theories, Journal of Symbolic Logic 22 (1957), 161-175. [8] S. Feferman, Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae 49 (1960), 35-92. [9] B. van Fraassen, Singular Terms, Truth-Value Gaps and Free Logic, Journal of Philosophy 63 (1966), 481-495. [10] A. Gupta and R. L. Martin, A fixed point theorem for the Weak Kleene valuation scheme, Journal of Philosophical Logic 13 (1984), 131-135. [11] V. Halbach and L. Horsten, Axiomatizing Kripke’s theory of truth, Journal of Symbolic Logic 71 (2006), 677-712. [12] V. Halbach, Axiomatic theories of truth, Cambridge University Press, Cambridge, 2011. [13] L. Horsten, Tarskian turn. Deflationism and axiomatic truth, MIT Press, Cambridge MA, 2011. [14] J. Ketland, Yablo’s paradox and ω-inconsistency, Synthese 145 (2005), 295-302. [15] R. Kossak and J. Schmerl, The structure of models of Peano Arithmetic, Clarendon Press, Oxford, 2006. [16] S. Kripke, Outline of a theory of truth, Journal of Philosophy 72 (1975), 690-716. [17] M. Mostowski, On representing concepts in finite models, Mathematical Logic Quarterly 47 (2001), 513-523.

28

[18] 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. [19] M. Mostowski and K. Zdanowski, FM-representability and beyond, in: S. B. Cooper and B. L¨owe, and L. Torenvliet (eds.) Archive for Mathematical Logic, Springer-Verlag, Berlin, 2005, pp. 358-367. [20] M. Mostowski Truth in the limit, 2012, in manuscript. [21] L.M. Picollo, Yablo’s paradox in second-order languages: consistency and unsatisfiability, Studia Logica 101 (2013), 601-617. [22] G. Priest, The structure of the paradoxes of self reference, Mind 103 (2002), 25-34. [23] G. Priest, Yablo’s paradox, Analysis 57 (1997), 236-242. [24] W.N. Reinhardt, Some remarks on extending and interpreting theories with a partial predicate for truth, Journal of Philosophical Logic 15 (1986), 219-251. [25] 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. 617706. [26] S. Yablo, Truth and reflection, Journal of Philosophical Logic 14 (1985), 297-349. [27] S. Yablo, Paradox without self-reference, Analysis 52 (1993), 251-252. [28] 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.

29