Saturday, 9 April 2011

Yablo's Paradox

A topic that Hannes Leitgeb, Roy Cook and I have written about is Yablo's paradox, which has an interesting subliterature associated with it; about 2 or 3 articles/year.

Instead of the usual liar paradox (a single sentence saying of itself that it is untrue), one can obtain semantic paradoxes by introducing (finite or even infinite) "loops". Yablo's idea (see Yablo 1993) is this: what if one replaces the loop by an infinite list? Yablo's paradox concerns a denumerable set of sentences $\{Y_0, Y_1, ...\}$, such that each $Y_n$ is equivalent to "for all $k > n$, $Y_k$ is not true". It's easy to see that one cannot assign truth values consistently to the $Y_n$. (As Roy mentions in the comments below, a related idea is mooted in Kripke 1975).

Two major issues arise in connection with Yablo's paradox: the question of self-reference and the phenomenon of $\omega$-inconsistency.

(A) Self-Referentiality
Is this semantic paradox self-referential? Some say "no" (Yablo); some say "yes" (Priest); some say, "it depends". The argument for "no" is that $Y_n$ is, roughly, equivalent to $\neg Y_{n+1} \wedge \neg Y_{n+2} \wedge ...$. So, the truth value of $Y_n$ doesn't "depend" on itself. Rather it "depends" on the truth values of $Y_{n+1}, Y_{n+2}$, etc. But what does "depends" mean? There is a sense in which this can be made more precise (see Leitgeb 2005), and one can formally show that each $Y_n$ is not self-referential. On the other hand, the construction of the sentences $Y_n$ requires a uniform fixed point result, saying that the predicate $Y(x)$ is equivalent (for variable $x$) to "for all $y > x$, $Y(y)$ is not true". This makes it look like the predicate $Y(x)$ is self-referential, although its instances aren't. (See Cook 2006 for more on this sort of thing.)

(B) $\omega$-Inconsistency
The paradox leads to an interesting form of $\omega$-inconsistency (first noted, I believe, by Hardy 1995), which itself is related to the non-wellfoundedness of the dependence relation (see also Forster 1996). One can reconstruct the paradox using the language of arithmetic with a primitive truth predicate $T(x)$ added. First, define a fixed-point predicate $Y(x)$ by uniform diagonalization so that $PA$ proves (with a little use/mention abuse):
  • $\forall x [Y(x) \leftrightarrow \forall y > x \neg T(\ulcorner Y(\dot{y}\urcorner)]$
Define the $n$-th Yablo sentence $Y_n$ to be $Y(x/\underline{n})$. Then add local disquotational T-sentences for each arithmetic sentence:
  • $T(\ulcorner A \urcorner) \leftrightarrow A$ (where $A$ is an arithmetic sentence)
And add the local disquotational scheme for each Yablo sentence:
  • $T(\ulcorner Y_n \urcorner) \leftrightarrow Y_n$
Call the resulting theory $PA_Y$. Compactness tells us that $PA_Y$ is consistent. Furthermore, one can prove that $PA_Y$ is an $\omega$-inconsistent conservative extension of PA. This means that $PA_Y$ has no standard model: the natural number structure $\mathcal{N}$ cannot be expanded to a model $(\mathcal{N}, E) \models PA_Y$. Still, each non-standard $\mathcal{M} \models PA$ can be expanded to a model $(\mathcal{M}, E) \models PA_Y$, by choosing $E$ (the denotation of the truth predicate) carefully. However, the $\omega$-inconsistency is "localized" entirely within the part of the language containing the truth predicate, for every arithmetic theorem of $PA_Y$ is true in $\mathcal{N}$. This relates Yablo's paradox to the phenomenon of truth theories with no standard model (see Leitgeb 2001, Ketland 2004, 2005, Barrio 2010, Picollo 2011).

Here is a temporally-ordered bibliography (which I'll update) with links:

[0] Kripke, S. 1975: "Outline of a Theory of Truth", Journal of Philosophy 72.
[1] Yablo, S. 1985: "Truth and reflection". Journal of Philosophical Logic 14.
[2] Yablo, S. 1993: "Paradox without self-reference". Analysis 53.
[3] Goldstein, L. 1994: "A Yabloesque paradox in set theory". Analysis 54.
[4] Hardy, J. 1995: "Is Yablo's paradox liar-like?". Analysis 55.
[5] Tennant, N. 1995: "On paradox without self-reference". Analysis 55.
[6] Forster, T. 1996: "The significance of Yablo's paradox without self-reference". (Unpublished: PS).
[7] Priest, G. 1997: "Yablo's paradox without self-reference". Analysis 57. (PDF)
[8] Sorensen, R. 1998: "Yablo's paradox and kindred infinite liars". Mind 107.
[9] Beall, J.C. 1999: "Completing Sorensen's menu: a non-modal Yabloesque Curry". Mind 108.
[10] Beall, J.C. 2001: "Is Yablo's paradox non-circular?". Analysis 61.
[11] Leitgeb, H. 2001: "Theories of truth which have no standard models". Studia Logica 68.
[12] Leitgeb, H. 2002: "What is a self-referential sentence? Critical remarks on the alleged (non)-circularity of Yablo's paradox". Logique et Analyse 177-8 (no online link).
[13] Bueno, O. & Colyvan, M. 2003: "Yablo's paradox and referring to infinite objects". Australasian Journal of Philosophy 81. (PDF)
[14] Bringsjord, S & van Heuveln, B. 2003: "The 'mental-eye' defence of an infinitized version of Yablo's paradox". Analysis 63.
[15] Bueno, O. & Colyvan, M. 2003: "Paradox without satisfaction". Analysis 63.
[16] Ketland, J. 2004: "Bueno and Colyvan on Yablo's paradox". Analysis 64.
[17] Cook, R.T. 2004: "Patterns of paradox". Journal of Symbolic Logic 69.
[18] Yablo, S. 2004: "Circularity and self-reference". In T. Bolander, V. Hendricks & S. Petersen (eds.) 2004, Self-Reference. (PDF)
[19] Uzquiano, G. 2004: "An infinitary paradox of denotation". Analysis 64.
[20] Ketland, J. 2005: "Yablo's paradox and $\omega$-inconsistency". Synthese 145.
[21] Leitgeb, H. 2005: "What truth depends on". Journal of Philosophical Logic 34.
[22] Leitgeb, H. 2005: "Paradox by (non-wellfounded) definition". Analysis 65.
[23] Shackel, N. 2005: "The Form of the Benardete Dichotomy". British Journal for the Philosophy of Science 56.
[24] Goldstein, L. 2006: "Fibonacci, Yablo, and the cassationist approach to paradox". Mind 115.
[25] Cook, R.T. 2006: "There are non-circular paradoxes (but Yablo's isn't one them!)". The Monist 89.
[26] Schlenker, P. 2007: "The elimination of self-reference: generalized Yablo-series and the theory of truth ". Journal of Philosophical Logic 36.
[27] Schlenker, P. 2007: "How to eliminate self-reference: a precis". Synthese 158.
[28] Bolander, T. 2008: "Self-Reference". SEP.
[29] Landini, G. 2008: "Yablo's paradox and Russellian propositions". Russell: Journal of Bertrand Russell Studies 28.
[30] Bernadi, C. 2009: "A topological approach to Yablo's paradox". Notre Dame J of Formal Logic 50.
[31] Luna, L. 2009: "Yablo's paradox and beginningless time". Disputatio 3.
[32] Cook, R.T. 2009: "Curry, Yablo and Duality". Analysis 69.
[33] Urbaniak, R. 2009: "Leitgeb, "About," Yablo". Logique et Analyse 207. (PDF).
[34] Barrio, E. 2010: "Theories of truth without standard models and Yablo's sequences". Studia Logica 96.
[35] Picollo, L. 2011: "La paradojicidad de la paradoja de Yablo". University of Buenos Aires, Undergraduate dissertation (PDF in Spanish).

[to be updated!]

9 comments:

  1. You forgot the earliest: Kripke's classic [1975], where he writes:

    One surprise to me was the fact that the orthodox approach by no means obviously guarantees groundedness… Even if unrestricted truth definitions are in question, standard theorems easily allow us to construct a descending chain of first-order languages L0, L1, L2,…, such that Li contains a truth predicate for Li+1. I don’t know whether such a chain can engender ungrounded sentences, or even quite how to state the problem here; some substantial technical questions in this area are yet to be resolved. ([1975]: 698)

    ReplyDelete
  2. Hi Roy, yes - good point! I knew Kripke had briefly mentioned something in the area, but I'd forgotten when making the list. (Both Gabriel Uzquiano 2004 in Analysis, and Hannes's 2005 Analysis paper have similar ideas.)

    I'll update the post and, since you're here on the blog too, I'll change the intro bit too.

    ReplyDelete
  3. Hi Jeff, thanks for the mention.:) I think you forgot the Bueno&Colyvan response to your paper. It's "Yablo's paradox rides again" (I think it's unpublished, but available online at

    http://homepage.mac.com/mcolyvan/papers/yra.pdf )

    Although, I don't think their case is too strong, just sketched a few remarks at Entia et Nomina:

    http://entiaetnomina.blogspot.com/2011/08/yablos-paradox-bueno-colyvan-vs-ketland.html

    If you think I misunderstood your position somehow in those comments, please let me know.

    ReplyDelete
  4. Hi Rafal, yes, that's pretty much right.
    You write,

    "Ketland was probably a bit hasty when he said the existence of Yablo sequence is a theorem of logic: for it is conditional upon PA extended with a truth predicate. (Although, this of course hinges on what you mean by mathematical logic)."

    Right - but I did not say that it is a theorem of "logic"!!
    I said it is a "theorem of mathematical logic". Mathematical logic is branch of *mathematics*, covered in books such as Enderton, Shoenfield, and other textbooks.

    You quote B&C saying,
    "Still, if the list is a theorem of Peano arithmetic suppelemented with a truth predicate, isn't that enough? Not really."

    The list is *not* a theorem of PA + truth predicate. How can a list be a theorem? The existence of the list is a theorem of mathematical logic. The universally quantified biconditional is a theorem of PA + truth predicate. The *existence* of this list is a theorem of mathematical logic (if one wanted to be really fussy, I'm pretty sure provable in $I \Sigma_1$, and not even using a truth predicate!). And the existence of its instances then follows.

    The original paper by B&C claimed that one could, pace Priest, deduce a contradiction using just the *local T-scheme*. The uniform one amounts to using a satisfaction predicate - Priest's point. But I'd noticed that only an omega-inconsistency follows with the local T-scheme (i.e., disquotation applied to Yablo sentences one-by-one), since I'd written some notes for myself on the problem in 2000, I think, and discussed it with Stephen Yablo. So, one needs the stronger uniform scheme - which is equivalent to using satisfaction. (At the time, I didn't know the papers by Hardy 1995 and Leitgeb 2001. Note that B&C are also objecting to Hardy and Leitgeb.)

    You quote B&C as saying:

    "While it is true that each finite subset of Yablo sentences is not paradoxical, it is not true that each subset is satisfiable."

    This confuses finite subsets of Yablo *biconditionals* with finite subsets of Yablo sentences. The consistency proof concerns the former. Each finite subset of Yablo *biconditionals* is satisfiable.

    So, I didn't mention the unpublished B&C reply in this bibliography because of these apparent mathematical errors.

    Cheers,

    Jeff

    ReplyDelete
  5. Hi Rafal, (by the way, many thanks for writing the post on this), here's another comment on your comment ...

    "Well, Ketland's response is slightly misleading, for it doesn't emphasize the (possible) difference between being on the Yablo list, and being a Yablo sentence. On one interpretation (interpretation A) the Yablo list is the list of Yablo sentences obtained for natural numbers as indices. In another (B) the Yablo list is just the set of all Yablo sentences, ordered by the less-then relation, no matter whether the numbers involved are standard or not."

    Right - but I don't think there is a difference between Yablo sentences and the list of Yablo sentences.
    There is a difference between
    - the Yablo sentences (indexed by $n \in \omega$)
    - what a non-standard model *thinks* is a Yablo sentence.

    So, on interpretation (A), this simply is the definition of the Yablo sentences (= the Yablo list), which is:

    $Y_n$ is the result of substituting the numeral of $n$ for all free occurrences of $x$ in $Y(x)$.

    And the numeral of $n$ is defined by:

    The numeral of $0$ is $\underline{0}$.
    The numeral of $n+1$ is $s\underline{n}$.

    Let $\mathcal{A} \models PA$ be non-standard. Let $a \in dom(\mathcal{A})$ be a non-standard element. What then is its numeral? More or less by definition, non-standard elements do not have numerals. The concept "numeral of $n$" is defined in the metalanguage. Unless one accepts this, one cannot even define "non-standard"! For "$\mathcal{A} \models PA$ is non-standard" means "$\mathcal{A}$ is not isomorphic to $(\mathbb{N}, 0, S, +, \times)$".

    Without these distinctions, I don't see how one can distinguish between local and uniform schemes. This seems to be the central mistake of B&C (original and reply). The local scheme gives the $\omega$-inconsistency, while the uniform one gives a genuine inconsistency. Quantification of $\phi(x)$ with respect to a variable $x$ is not always the same as infinitary conjunction of its instances with numerals, for there are non-standard models.

    Cheers,

    Jeff

    ReplyDelete
  6. Hi Jeff,
    Hi Jeff,

    Many thanks for your comments, a few further remarks.
    —-
    QUOTE
    "Ketland was probably a bit hasty when he said the existence of Yablo sequence is a theorem of logic: for it is conditional upon PA extended with a truth predicate. (Although, this of course hinges on what you mean by mathematical logic)."

    Right - but I did not say that it is a theorem of "logic"!!
    I said it is a "theorem of mathematical logic". Mathematical logic is branch of *mathematics*, covered in books such as Enderton, Shoenfield, and other textbooks.
    —-
    COMMENT
    I thought you had that in mind, hence the remark "(Although, this of course hinges on what you mean by mathematical logic.)" Still, the use of term "logic" might have caused some confusion, as witnessed by the case in question.
    —-

    —-
    QUOTE
    You quote B&C saying,
    "Still, if the list is a theorem of Peano arithmetic suppelemented with a truth predicate, isn't that enough? Not really."

    The list is *not* a theorem of PA + truth predicate. How can a list be a theorem? The existence of the list is a theorem of mathematical logic. The universally quantified biconditional is a theorem of PA + truth predicate. The *existence* of this list is a theorem of mathematical logic [...] And the existence of its instances then follows.
    —-
    COMMENT
    Yup, B&C's phrasing struck me as unfortunate, but I charitably assumed they had the existence of the list in mind.
    —-

    —-
    QUOTE
    You quote B&C as saying:
    "While it is true that each finite subset of Yablo sentences is not paradoxical, it is not true that each subset is satisfiable."

    This confuses finite subsets of Yablo *biconditionals* with finite subsets of Yablo sentences. The consistency proof concerns the former. Each finite subset of Yablo *biconditionals* is satisfiable.
    —-
    COMMENT
    Good point, I didn't make this distinction. But still, even if you look at the sentences not biconditionals, their argument that s_1+s_2 is not satisfiable because s_2 is vacuously true fails.
    —-

    —-
    QUOTE
    Right - but I don't think there is a difference between Yablo sentences and the list of Yablo sentences.
    There is a difference between
    - the Yablo sentences (indexed by n∈ω)
    - what a non-standard model *thinks* is a Yablo sentence.
    [...]

    Without these distinctions, I don't see how one can distinguish between local and uniform schemes. This seems to be the central mistake of B&C (original and reply). The local scheme gives the ω-inconsistency, while the uniform one gives a genuine inconsistency.
    —-
    COMMENT
    I completely agree. My point was that by including whatever the non-standard model thinks is a Yablo sentence on the list of Yablo sentences (to which the local disquotation scheme applies) B&C in effect tacitly replaced the local scheme (applying to sentences indexed with natural numbers) with the uniform one.
    —-

    cheers,
    Rafal

    ReplyDelete
  7. Hi Rafal, many thanks!
    The main confusion of Bueno & Colyvan 2004 (and their mistaken reply) is to confuse variables with numerals, i.e., confusing a universally quantified formula $\forall x \phi(x)$ with the set $\{\phi(\underline{n}): n \in \omega\}$.
    In this particular case, the set of instances,

    $\{\mathbf{True}(\ulcorner Y_n \urcorner) \leftrightarrow Y_n: n \in \omega\}$

    is confused the universal generalization, the uniform sentence,

    $\forall x(\mathbf{True}(\ulcorner Y(\dot{x}) \urcorner) \leftrightarrow Y(x))$

    Cheers,

    Jeff

    ReplyDelete
  8. - BUTLER, Jesse (2005) «Circularity and infinite liar-like paradoxes», Master of Arts Thesis, University of Florida.
    - KENNEDY, Niel (2007) «The definite story on Yablo's paradox», In : Institute for Language Logic and Computation. Paris-Amsterdam Logic Meeting of Young Researchers - 6, Amsterdam, 14-15 Décembre, 2007.
    - LUNA, Laureano (2009) «Yablo’s paradox and beginningless time», Disputatio 26(3).
    - ANDRÁS, Ferenc (2010) «The new clothes of paradox». (Available online)
    - HASSMAN, Benjamin John (2011) «Semantic objects and paradox. A study of Yablo’s omega-liar», PhD Dissertation, University of Iowa.
    - LEACH-KROUSE, Graham (2011) «Yablo’s paradox and arithmetical incompleteness», arXiv.
    - FORSTER, Thomas (2012) «Yablo’s paradox and the omitting types theorem for propositional languages». (Available online)


    http://ferenc.andrasek.hu/index.php?page=/right9.php

    ReplyDelete