## Friday, 29 July 2011

### Roy's Fortnightly Puzzle: Volume 7

A bit late - apologies. Traveling again.

Anyway, most of you will be familiar with the Yablo paradox. To refresh (and suppressing some of the more tedious details): Add a truth predicate to first-order arithmetic, and then apply the diagonal lemma to obtain a theorem of the form:

(x)(Y(x) <--> (z)(z > x <--> ~ T(Fz)))

The the Yablo paradox is the sequence Y(1), Y(2), Y(3)...

There is no 'acceptable' assignment of truth values to each of Y(1), Y(2), Y(3)... such that the usual axioms for the truth (and satisfaction) predicate(s) come out true (technically: This sequence of statements is omega-inconsistent and thus has no standard model). The question is this: Which Yabloesque variants on this construction are paradoxical and which are not?

This question has been studied (in, e.g. Cook (2004)) and continues to be studied from a graph theoretic standpoint (formalizing Yabloesque paradoxes in terms of infinitary conjunction and then studying the characteristics of the associated directed graphs). Here I would like to suggest another route: Looking at variations that can be constructed within Peano arithmetic.

To give the problem a definite form, consider omega-sequences of formulas F(1), F(2), F(3)... where, for all z:

F(z) <--> (x)((x > z & H(z, x)) --> ~ T(F(x)))

is a theorem (where H is any predicate of Peano arithmetic - not including any instances of the the truth predicate - with at most x and z free). In other words, each sentence F(z) in the Yabloesque sequence is equivalent to the claim that, for any number x greater than z such that H holds of z and x, F(x) is false.

In order to guarantee that each sentence in the list refers to at least one other sentence, we assume that:

(z)(Ex)(x > z & H(z, x))

Here are some simple results to get you started (with some notes on where they come from):

Theorem 1: If H does not contain variable z free, then the resulting Yabloesque sequence is paradoxical.

[Notes: Observed by Lavinia Picollo, Universidad de Beunos Aires].

Theorem 2: If (z)(Ew)(x)(x > w --> H(z, x)) then the resulting Yabloesque sequence is paradoxical.

[Notes: In other words, for each z, the collection of x > z such that H(z, x) is cofinite. This result is, in essence, in Yablo (2006)].

Theorem 3: Given any H(z, x) as above, if the Yabloesque sequence in question is paradoxical, then the Dual version consisting of instances of:

F(z) <--> (Ex)(x > z & H(z, x) & ~ T(F(x)))

[Notes: A standard sort of 'duality' result for Yabloesque constructions.]

What other conditions are necessary or sufficient for paradox?

[Notation: F is the Goedel code of F, (x) is the universal quantifier, and (Ex) is the existential quantifier.]

Cook, R. [2004], “Patterns of Paradox”, Journal of Symbolic Logic 69, [2004]: 767 – 774.

Yablo, S. [2006], “Circularity and Paradox”, in Bolander, Hendricks, & Pedersen, Self-Reference.