4

I have a questions about the definability of truth in set theory.

Suppose that $\mathcal{L}$ is a language for a first order set theory $T$.

Let $Sat(A,x, y)$ be the formula that define the satisfaction relation, that this, $Sat(A,\ulcorner \varphi\urcorner, a)$ if only if $A \vDash \varphi[a]$, where $\varphi$ is a formula in the language of $\mathcal{L}$, $A$ is a transitive set, $\ulcorner \varphi\urcorner$ is the Gödel codification, and $a=(a_1, \ldots, a_n) \subset A^n$.

If $\varphi$ is a sentence, $Sat(A,\ulcorner \varphi\urcorner, \emptyset)$ if only if $A \vDash \varphi$.

If this is correct, the following is correct: $\psi(x) := \forall A (Sat(A,x, \emptyset))$ is definable. The above formula say "for all $A$ transitive, $\varphi$ is truth in $A$". But by the Gödel's completeness theorem we know that for all sentence $\varphi$, $\psi(\ulcorner \varphi\urcorner)$ if only if $\ulcorner \varphi\urcorner$ is a theorem, but this contradicts the Tarski's theorem of undefinability of truth. What is wrong?

The problem is that $Sat(A,x, y)$ is definable for $A$ transitive set , but $A$ is a model of $T$ is not definable? for example when $T$ is $ZFC$. Is there a set theory $T$ in which the above reasoning is correct?

Thanks.

PGarcía
  • 43

1 Answers1

8

Yes, it is true that "$\ulcorner\phi\urcorner$ is true in all models of ZFC" is expressible in set theory (all transitive models, or just all models, period). But that is not the same thing that Tarski's theorem prohibits. Tarski's theorem says "$\ulcorner\phi\urcorner$ is true" is not definable. In other words it prohibits defining a predicate $T$ such that for any $\phi,$ $T(\ulcorner \phi\urcorner)\leftrightarrow \phi.$

The error you are making is confusing the logical consequences of ZFC with the true statements (in V). What the completeness theorem tells you is that "$\phi$ is true in all models of ZFC" is the same as "$\phi$ is a theorem of ZFC" which means the syntactic definition of consequence is equivalent to the model-theory definition. It doesn’t say that something is true (in $V$) if and only if it is true in all models.

Also, on a more minor note, it's not the case that if something is true in all transitive models then it is true in all models. For instance, any arithmetical statement that is true in $V$ will be true in all transitive models of ZFC, since $V_\omega$ in a transitive model will be the same thing as in $V$. But of course there are many arithmetic statements that ZFC does not decide, so there will be non-transitive models that disagree with $V$ on these.

spaceisdarkgreen
  • 58,508
  • Thank you very much. I still have one doubt. Is it possible to prove that there is no formula $ \varphi(x)$ such that for every natural number $n$, $n$ codes a theorem of $ZFC$ if only if $ZFC \vdash \varphi(n)$. The proof is the same as in Tarski's theorem. I don't see why this doesn't contradict what I wrote before. – PGarcía Apr 02 '21 at 17:30
  • 1
    @PGarcía I don't think I follow. One would hope that the provability predicate for ZFC that you can express in ZFC has this property. Of course there's no proof it works without correctness assumptions on ZFC, specifically that ZFC is $\omega$-consistent. But if there were a proof that it didn't work, that would be a big problem. Provability in an effective formal system is a very tangible thing that we should hope to capture fully... truth not so much. – spaceisdarkgreen Apr 02 '21 at 17:48
  • @PGarcía "The proof is the same as in Tarski's theorem" Try writing that proof out in full detail. I think things are a bit more subtle than you claim. – Noah Schweber Apr 02 '21 at 17:56
  • @NoahSchweber Suppose that $\varphi(x)$ is the formula. Let $ \lbrace \psi_i(x) : i \in \omega \rbrace$ be a enumeration of all formulas. Let $\chi(x) := \neg \varphi(\ulcorner \psi(x) \urcorner) \wedge (x\in \omega)$. Let $k$ such that $\chi(x) = \psi_k$. Then $\chi$ is a theorem of $ZFC$ if only if $ZFC \vdash \neg \varphi(\ulcorner \chi \urcorner)$. I don't doubt that it's much more subtle, but I don't see the error. – PGarcía Apr 02 '21 at 18:04
  • 1
    @PGarcía First, a couple minor quibbles. In your definition of $\chi(x)$, what is $\psi(x)$? Do you mean $\psi_x(x)$? Also, $\chi$ is a formula, not a sentence, so in what sense can $\chi$ be a theorem of ZFC? Do you mean $\chi(k)$? – Noah Schweber Apr 02 '21 at 18:20
  • 2
    But note that your goal isn't actually problematic. Suppose you have a sentence $\Theta$ such that $ZFC\vdash\Theta$ iff $ZFC\vdash\neg\varphi(\ulcorner\Theta\urcorner)$, where $\varphi$ is the usual provability formula for $ZFC$. Clearly then $\Theta$ can't be a theorem of $ZFC$ (since from $ZFC\vdash\Theta$ we would get $ZFC\vdash\varphi(\ulcorner\Theta\urcorner)$ by $\Sigma_1$-completeness, and so a contradiction). But what's the problem with $\Theta$ simply not being a $ZFC$ theorem? All that follows from that is $ZFC\not\vdash\neg\varphi(\ulcorner\Theta\urcorner)$ ... but so what? – Noah Schweber Apr 02 '21 at 18:25
  • 2
    In particular, $ZFC\not\vdash\neg\varphi(\ulcorner\Theta\urcorner)$ does not imply $ZFC\vdash\varphi(\ulcorner\Theta\urcorner)$. This is a key difference between truth and provability: obviously for a structure $M$ we do have an equivalence between $M\not\models\neg\eta$ and $M\models\eta$, simply because of the negation clause in the definition of satisfaction. – Noah Schweber Apr 02 '21 at 18:26
  • 2
    @PGarcía Noah put it much more precisely than I will, but the analogue of Tarski's theorem for provability is Godel's theorem. "I am not true" (clearly contradictory) becomes "I am not provable" (not contradictory cause nobody said every true statement needed to be provable... and in fact this shows that is not the case). – spaceisdarkgreen Apr 02 '21 at 18:38