3
$\begingroup$

Suppose that I work in Zermelo-Fraenkel set theory with the axioms of choice (ZFC). Using the recursion theorem, I can define the truth value of formulas in the language $\mathcal{L}$ of set theory (one predicate symbol $\in$), $Val_\mathcal{M}(\varphi)$, for structures $\mathcal{M}$ whose universe is a set.

Hence, for any set $A$, I can define the relation $\left( A, \in\upharpoonright_A \right)\models\varphi$ in the language of set theory. Since $\left( A, \in\upharpoonright_A \right)$ interprets $\mathcal{L}$, it seems that this relation can define the set of all true formulas (with respect to the model $A$). This contradicts Tarski's theorem. What am I missing?

My second question is why this definition for $Val_\mathcal{M}(\varphi)$ fails when $\mathcal{M}$ is a proper class, and why the existence of such a definition of truth over a proper class would contradict Tarski's theorem (whereas the same definition over a set exists and does not contradict it).

$\endgroup$
2
  • $\begingroup$ @Ioannis Filippidis: please do not make minor edits to old questions and answers. The practice is usually discouraged on this site. It bumps questions onto the active list. We generally accept minor typos or phrasing issues, as long as the mathematics is clear. $\endgroup$ Commented Dec 10, 2016 at 13:38
  • $\begingroup$ OK, thanks for letting me know. $\endgroup$
    – 0 _
    Commented Dec 10, 2016 at 20:01

2 Answers 2

6
$\begingroup$

Short version: the Skolem functions on a proper class are too big.

Long version: the way we define the predicate "$A\models\varphi$" is via Skolem functions: $A\models \varphi$ if there is a Skolem function witnessing that $\varphi$ is true in $A$. For instance, if $\varphi$ is the sentence "$\forall x\exists y(x\in y)$," then a Skolem function for "$\varphi$ holds in $A$" should be a function $f: A\rightarrow A$ such that $$\forall x\in A[ x\in_A f(x)].$$ So "$A\models\varphi$" will in general have the form "$\exists f: A\rightarrow A [. . .]$."

The problem is that if we try to similarly define truth for a proper class structure - say, all of $V$ - then we're left with a formula of the form $$"\exists f: V\rightarrow V[. . .]"$$ Such an $f$ is a class function - basically, a proper class. But we can't quantify over classes, so this formula isn't actually something we can express.

So this explains why the standard construction of a truth predicate breaks down for proper class-sized structures. But how do we know such a definition can't exist at all? Maybe there's some other way to get one.

Well, this is exactly what is ruled out by Tarski's theorem on the undefinability of truth! The proof of Tarski's theorem is the following: such a definition would let us define, via a formula $\varphi$, the set of (Godel numbers of) sentences which are true in $V$. We can now use the Diagonal Lemma to write a sentence expressing, roughly, "I am not true" which clearly isn't something we can do.

Which brings us to your final question: why doesn't our ability to define truth predicates for set-sized structures contradict Tarski's theorem? The answer is that we can happily build a truth predicate for a structure $A$, as long as we're content to do so outside the structure $A$. For instance, if we expand $V$ to have a constant naming the set of Gödel numbers of sentences true in $V$, the resulting structure $V^*$ clearly defines a truth predicate for $V$. However, since the sentence defining "truth in $V$" in $V^*$ is not a sentence in the language $\{\in\}$, we can't use the Diagonal Lemma to get a contradiction. Set-sized structures are "far from" $V$, so $V$ can build truth predicates for them.

$\endgroup$
6
  • $\begingroup$ Thanks for your answer! I have a few questions, the recursive definition i had in mind was something like $\left(A, \in_A \right)\models \exists x\varphi $ iff $\exists a\in A: (A,\in_A)\models \varphi[x\rightarrow a]$.I may quantify over the existence of a member in a proper class, which is fine since if $\psi_A$ defines the proper class $A$ then $\exists x\in A$ turns into $\exists x\psi_A(x)$. Whats wrong with this definition? using skolem functions causes a problem since you quantify over a class (and not membership). $\endgroup$
    – Ariel
    Commented Aug 19, 2015 at 19:02
  • $\begingroup$ That works for defining a truth predicate for a small class of formulas - say, those of a fixed quantifier complexity. The problem is when you try to pass to a single truth predicate capturing everything at once - try doing this explicitly and you'll see what I mean. $\endgroup$ Commented Aug 19, 2015 at 19:10
  • $\begingroup$ is this the sort of thing you meant by capturing everything at once? $(A,\in _A)\models \exists x\varphi$ iff $\exists f:A\rightarrow A: (A,\in _A)\models\varphi[x\rightarrow f(\ulcorner\varphi\urcorner)]$ (assuming i can code the formulas in $A$, $f$ tells me the witness for any formula starting with an existential quantifier). Additionally (and i hope with this the matter will be settled) when you say the definition of $\models$ for a set $A$ lies outside of $A$, is this because you use $A$ in the definition (a symbol not existing in the language of set theory)? $\endgroup$
    – Ariel
    Commented Aug 19, 2015 at 20:39
  • $\begingroup$ Re: your last question, not really - it's more that the definition of the full truth predicate for $A$ involves quantifying over maps from $A$ (or finite Cartesian powers of $A$) to itself, which by definition aren't elements of $A$. So even if a specific $A$ is definable in $V$ (so we don't need it as a parameter), the definition of the truth predicate for $A$ still lives "outside $A$." A specific example: say $A=V_\omega$. Then the truth predicate will look (roughly) like "there is a map from $V_\omega$ to itself such that . . . " (cont'd) $\endgroup$ Commented Aug 19, 2015 at 20:42
  • $\begingroup$ Now, $V_\omega$ is definable in the language of set theory; so I can take this definition and look at its interpretation in $A$. The problem is, $A$ doesn't contain anything which it believes is (i.e., satisfies the definition of) $V_\omega$! So any sentence beginning "there is a map from $V_\omega$ to itself" will automatically be false in $A$. Essentially, the truth predicate for first-order sentences in a structure is second-order; does this make sense? $\endgroup$ Commented Aug 19, 2015 at 20:43
2
$\begingroup$

What you cannot define according to Tarski is not just truth in some model of $\mathcal L$, but truth about the actual set-theoretical universe in which your truth-predicate is itself evaluated.

You can't do that with the usual machinery for reasoning about models, because the usual recursive truth function would require you to recursively define a function $F$ such that among other things, if $\varphi(x)$ is a model with one free variable, $$ F(\ulcorner \varphi\urcorner) = \{ Y \in \mathbf V \mid (\mathbf V,\in,x\mapsto Y)\vDash \varphi(x) \} $$ But if $\varphi$ is true too often, the thing on the right of this may be too large to be a set at all -- so certainly it cannot be the value of some function applied to a representation of $\varphi$.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer! Regarding the first part, from the statement of Tarski's theorem in wiki (general form - en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem) it seems i cant define truth in any given model. $\endgroup$
    – Ariel
    Commented Aug 19, 2015 at 20:41
  • 1
    $\begingroup$ @Ariel: What it says is that truth cannot be defined by means of a formula that is interpreted in the same model whose truth we're trying to define. $\endgroup$ Commented Aug 20, 2015 at 0:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .