[FOM] The liar and the semantics of set theory

[Rupert McCallum]

--- Roger Bishop Jones <rbj at rbjones.com> wrote:
> The liar "paradox" was used by Tarski to show that
> arithmetic truth is not definable in arithmetic.
> 
> It is natural to suppose that a similar result obtains in
> relation to set theory, viz. that set theoretic truth is not
> definable in set theory.
> However, I am not aware of any argument (using the
> liar or otherwise) which conclusively demonjstrates
> this conjecture.
> 

Tarski's argument may be generalized as follows. 

Theorem. (Undefinability of truth).

Suppose we have an interpreted first-order language, with respect to
which, to each expression (i.e. formula or term) phi there exists a
closed term G(phi) whose referent in the model we call g(phi) or the
Goedel code for phi, and g is a one-to-one function from the set of
expressions into a subset of the model called the set of natural
numbers, and that every natural number has a numeral which is a closed
term in our language. Suppose further we have a three-place function
Sub, definable in our language, such that the referent of Sub(X,Y,Z)
under the interpretation X=x, Y=y, Z=z - when x is the Goedel code of
the formula phi, y is the Goedel code of the variable v, v is free in
phi, and z is a natural number - is the Goedel code for the result of
substituting the numeral for z for v in phi. Then there does not exist
a one-place predicate Tr, definable in our language, such that for all
sentences phi, Tr(X) holds under the interpretation X=g(phi) if and
only if phi is true in the model. 

Corollary. Consider the first-order language of set theory with
abstraction terms {x|phi}, interpreted by the model V. We may define in
this language a mapping G from the set of sentences to the set of
closed terms whose referents are natural numbers, and a three-place
function Sub, with respect to which the hypotheses of the theorem are
satisfied. Consequently there does not exist a one-place predicate Tr
in this language which is a "truth predicate" in the sense discussed.
As an easy consequence, on any reasonable definition of "truth
predicate" the first-order language of set theory doesn't have one
(with respect to the model V).

Proof of the Theorem. 

I follow Drake, "Set Theory: An Introduction to Large Cardinals",
North-Holland 1974, p. 97.

Suppose that such a predicate Tr did exist. Consider the predicate
phi(v)=~Tr(Sub(v,0,v)). Let u be the Goedel code of phi, then if s
equals Sub(u,0,u) (i.e. is the referent of Sub(X,Y,Z) under the
interpretation X=u, Y=0, Z=u) then s equals the Goedel code of phi(u),
the result of substituting the numeral for u for the free variable of
phi. It may be seen that this yields a version of the liar paradox,
that we have Tr(s) holds (i.e. Tr(X) holds under the interpretation
X=s) if and only if it doesn't. Roughly because we have phi(g(psi)) iff
~psi(g(psi)), and s=g(phi(g(phi))), and we have phi(g(phi)) iff
~phi(g(phi)) by the foregoing. 

> The situaltion is made a little more complicated by
> there being some degree of uncertainty about exactly
> what is the semantics of set theory.
> The liar can be used to show that for a
> large class of possible definitions of truth for set
> theory, that definition cannot be carried through in
> the set theory which has that semantics.
> 
> If truth of a sentence of first order set theory is defined
> as truth in any single interpretation of that language,
> the definability of this version of set theoretic truth in
> the set theory with this semantics would allow the
> construction of a sentence denying its own truth.
> 
> However, we might want to interpret first order
> set theory as talking about all the "standard" models
> of ZFC (i.e. V(alpha) for inaccessible alpha).
> 
> if truth of a sentence of first order set theory
> is defined as truth in more than one "intended"
> interpretation (and falsity as falsity in all of them),
> then some sentences may lack a truth value
> (even though they all have a truth value in every
> interpretation).
> In that case both the liar sentence and its denial
> might lack a truth value and the proof that in such
> a set theory its own set theoretic truth is not
> definable would not go through.
> 
> Does anyone know of a conclusive argument
> showing that set theoretic truth is not
> definable in set theory?
> 
> Roger Jones
> (with apologies if this question has already been covered)
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom


__________________________________________________
Do you Yahoo!?
New DSL Internet Access from SBC & Yahoo!
http://sbc.yahoo.com