[FOM] Another easy solution does not work

Harvey Friedman friedman at math.ohio-state.edu
Wed Sep 11 03:25:19 EDT 2002


>
>Another example worth noting here is one due to Steve Yablo that 
>purports to be, and I think is, an example of a semantic paradox in 
>which no self-reference is involved. Here's the example. Consider an 
>infinitely long line of people. Each person in the line is to utter 
>one sentence. As it happens, each person in the line says: 
>Everything the people behind me will say will be false. No one's 
>remark includes his own remark in its intended scope. And yet, we 
>get a paradox. I'll leave the informal argument as an exercise, as 
>well as the formalization of the example, which is actually a nice 
>exercise in diagonalization.
>
>Richard Heck


Perhaps this should be looked at as recursive definition along a non 
well founded ordering. E.g., we can "define" f:N into N at any n in 
terms of not the values at 0,1,...,n-1, but in terms of the values at 
n+1,..., or even in terms of the value at n+1. This is impossible for 
even defintions of f:N into {0,1}.

E.g., f(n) = 1 if for some m > n, f(m) = 0; 0 otherwise.

For definitions of f(n) in terms of f(n+1), we cannot define 
functions f:N into N. E.g., f(n) = n+1.

AMUSING THEOREM. Let h: {1,...,k} into {1,...,k}. There exists a 
function f:N into {1,...,k} such that for all n >= 0, f(n) = h(n+1).

What is the most general form of such amusements??

Because the mathematical properties of inductive definitions along 
non well foounded orderings is so mathematically well understood, or 
at least can be so mathematically well understood, I would hesitate 
to throw it in the same category as the liar paradox and other 
paradoxes. I.e., I would hesitate to call it a semantic paradox.

******************************

I am only slightly familiar with the philosophical literature on 
liar's paradox and self reference. I appreciate very much this thread 
that is being conducted by Heck, Hodges, and others, who are very 
familiar with this literature, and hope that it continues. Thank to 
Hodges for creating some misunderstandings of mine about the 
literature.

Let me mention an approach that may well be explicitly in the 
literature, and/or may have been proved to be equivalent to an 
existing approach.

Let me start with the context of PA (Peano Arithmetic) with a truth 
predicate T. There is a trouble free notion of L(T) = the language of 
PA with the unary predicate symbol T, where some but not all natural 
numbers are godel numbers of sentences of L(T).

DIGRESSION. There is perhaps a more honest version of this in the 
theory of hereditarily finite sets, where instead of relying on some 
ad hoc godel numbering setup, one can at least attempt to talk of 
"honest" names for sentences of L(T) - i.e., the sentences 
themselves(?!). However here little blemishes also come up. I don't 
know if this has been straightened out, can be straightened out, or 
what, and I don't know just how important a matter this should or 
should not be. END OF DIGRESSION.

The problem facing us is to make sense of the sentences of L(T) 
semantically. Self reference is the heart of the issue, of course. 
One must always bear in mind the well known metatheorem:

THEOREM. Let phi(n) be a formula of L(T) with the one free variable 
shown. There is a closed term t such that the sentence phi(t) has 
godel number |t| = the correct value of t.

In particular, there is a closed term t such that notT(t) has godel number |t|.

The approach I was thinking of is to take seriously the well known, 
but not particularly satisfying fact, that a sentence in L = language 
of PA is true if and only if it has an infinitary proof. As a 
Corollary, every sentence in L is provable or refutable infinitarily. 
This is in a standard formulation of infinitary logic for this 
purpose.

There is an obvious form of infinitary logic for L(T), only here it 
is by no means the case that every sentence is provable or refutable. 
In fact, this infinitary logic can be set up to handle infinitary 
L(T), where (countably) infinite conjunctions and disjunctions are 
allowed in the formulas.

Now let us be given a sentence phi in L(T). The expansion of phi, 
written exp(phi), is obtained by replacing every subformula of the 
form T(s) by the infinite conjunction

if s = 0 then phi_0
if s = 1 then phi_1
if s = 2 then phi_2
...

where phi_n is the sentence of L(T) with godel number n if there is 
one; 0 = 0 otherwise.

One could attempt to take a hard line, that asserting the validity of 
a sentence in L(T) is simply asserting that among the sequence of 
iterated expansions of phi,

phi, exp(phi), exp(exp(phi)), ...

one of them has an infinitary proof. It seems clear that if one of 
them has an infinitary proof, then all the later ones do also.

*****************************

I think there is a more focused situation worth studying (and 
probably is being studied).

We don't try to handle an unrestricted notion of truth like the 
above, but rather, at least in a first version, just the construct 
"this sentence".

This seems to make perfectly good sense even in the context of 
propositional calculus. Let me explain.

Let PROP be the usual syntax of ordinary propositional calculus, with 
infinitely many atoms, and the usual connectives.

We introduce a new special atom to PROP called TS. (TS stands for 
"this sentence"). Call this new language PROP(TS).

Here is a familiar formula of PROP(TS) which does not even mention 
the original atoms:

not(TS).

We want to use the expansion idea. Let phi be a formula of PROP(TS). 
The expansion is simply obtained by replacing TS by phi.

We attempt to take the hard line that asserting the validity of a 
formula of PROP(TS) is simply asserting that among the sequence of 
iterated expansions, one of them is valid by truth tables.

The plan is to gather information about which formulas of PROP(TS), 
with and without the original atoms, are valid in this sense.

Let us take this a step further. We consider PROP*, which is more 
elaborate and meant to handle multiple assertions, referring to each 
other.

We have the original atoms, p_1,p_2,... . We have the special atoms 
S[1], S[2], ... . Formulas are defined as usual.

A compound assertion is a list of one or more formulas 
phi_1,phi_2,...,phi_n, such that every S[r] that appears somewhere in 
this list has 1 <= r <= n.

The expansion of a compound assertion is also a list of formulas of 
the same length, but where each instance of S[i] is replaced by the 
formula phi_i.

We say that phi_i is valid in the context of phi_1,phi_2,...,phi_n if 
and only if in some iterated expansion, the i-th formula is valid by 
truth tables.

Work up information about which lists of formulas of PROP*, which 
items in the list are valid in this sense.





























More information about the FOM mailing list