[FOM] Diagonalization and Self-Reference

[Sandy Hodges]

I think it may be possible to meet Heck's challenge.

Heck:  the most obvious way of trying to do it  fails, that being to
consider something like:
        (Ey)(rhs(x,y) & T(y)) <--> (Ey)(lhs(x,y) & ~T(y))
where 'rhs(x,y)' represents 'y is the rhs of the biconditional x', etc.,
and then diagonalize. When we do so, what we get is a sentence P such
that:
(3)    PA |- P <--> [(Ey)(rhs(*P*,y) & T(y)) <--> (Ey)(lhs(*P*,y) &
~T(y))]
But P itself is not the sentence on the rhs side here. Rather, P is
itself an existential formula. Hence, P has no rhs, and no lhs, either;
---

S.H. We're looking for something like:

  (1) The following predicate, applied to its own quotation, yields a
formula whose Lxyz is not true iff its Rxyz is true: "the following
predicate, applied to its own quotation, yields a formula whose Lxyz is
not true iff its Rxyz is true".

where Lxyz and Rxyz are operations, yet to be specified, which when
applied to (1), will find phrases and put them together to get what we
need for the proof.      That cut and paste operation, though complex,
should be just arithmetical.

Consider
  (2) (E f) (Lxyz(*m(*m*)*,f) & ~ T(f)) <--> (E r) (Rxyz(*m(*m*)*,r) &
T(f))

we want some G which, when applied to *m*, yields (2).   *G* contains
somewhere within it, *Lxyz* and *Rxyz*   Let *Q*(a) be the number that
results from replacing *Lxyz* with a in *G(*G*)*.

Then we want Lxyz to be such that

Lxyz(*Q*(a),z)  <--> z = *(E f) (a(*Q*(a),f) & ~T(f))*

Lxyz is arithmetic - it just has to fish around in its first argument,
put the bits together in a certain way, and compare the result to the
second argument.     Define Rxyz similarly.   We have in particular:

(3) Lxyz(*G(*G*)*,z)  <-->   z = *(E f) (Lxyz(*G(*G*)*,f) & ~T(f))*

Then assume G(*G*) is true.   There follows from the definition of G:

(E f) (Lxyz(*G(*G*)*,f) & ~ T(f)) <--> (E r) (Rxyz(G(*G*),r) & T(r))

assume both sides of this biconditional are true.   Find z = *(E f)
(Lxyz(*G(*G*)*,f) & ~ T(f))*.   z is thus the Gn. of the left hand side
of the biconditional, so by our assumption T(z).    By (3),
Lzyz(*G(*G*)*,z).

Now we're assuming that the left side of the biconditional is true, that
is

(E f) (Lxyz(*G(*G*)*,f) & ~ T(f))

If this is true of some f, then

(\/ f) (Lxyz(*G(*G*)*,f) --> ~ T(f))

since there will be in fact only one f which makes Lxyz(*G(*G*)*,f)
true.   Putting z for f, we get

Lxyz(*G(*G*)*,z) --> ~ T(z)

We have already established Lzyz(*G(*G*)*,z), so we have  ~ T(z).    But
we already had T(z), a contradiction.   So our assumption that both
sides of the biconditional are true, fails.    Similar arguments apply
to the other possible assumptions.
-----
I'm not sure Richard will accept the existence of a G which, when
applied to *m*, yields (2).    But that part seemed like ordinary
diagonalization so I hope it's all right.   The special problems posed
by lhs and rhs seemed to require only that we use relations that probe
more complicatedly inside of formulas than rhs and lhs do.

------- -- ---- - --- -- --------- -----
Sandy Hodges / Alameda,  California,   USA
mail to SandyHodges at attbi.com will reach me.