[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