1
$\begingroup$

On the wikipedia about Tarski's undefinability theorem the theorem is formulated as:

Tarski's undefinability theorem: There is no L-formula True(n) that defines T*. That is, there is no L-formula True(n) such that for every L-formula A, True(g(A)) ↔ A holds.

Shouldn't it say:

there is no L-formula True(n) such that for every L-formula A, True(g(A)) is true in the standard model N if and only if A holds.

?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I noticed you deleted your comments below my answer. Would you like me to delete mine as well, or should I leave them up? $\endgroup$ – Noah Schweber Dec 3 '16 at 19:13
0
$\begingroup$

Saying "$True(g(A))\iff A$ holds" is implicitly saying that that statement is true in the standard model - in the same way that if I say "Fermat's last theorem is true," I mean that it is true in the standard model. So in fact the two versions are equivalent.

Indeed, if you want to make the model explicit, you should apply that to the $A$-side too: "$True(g(A))$ is true in the standard model iff $A$ is true in the standard model."

However, there's a value to phrasing it without reference to a specific model: Tarski's undefinability theorem doesn't only apply to the standard model! If $N$ is a model of $PA$, then there is no formula $True$ such that $N\models True(g(A))\iff N\models A$, via the same proof as usual, the key point being that the conclusion of the diagonal lemma is about provability in $PA$, not merely truth in the standard model.


EDIT: I think it would help if Tarski's theorem were stated in the following way (and indeed, this is how I state it when I teach it):

If $A\models PA$, then there is no formula $\varphi(x)$ (in one free variable, in the language of arithmetic) such that for all sentences $p$ in the language of arithmetic, $$A\models \varphi(g(p))\quad\iff\quad A\models p,$$ where "$g(\cdot)$" is the Goedel number function.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ @rere No, you don't. And I quote: "there is no L-formula True(n) such that for every L-formula A, True(g(A)) is true in the standard model N if and only if A holds." The last two words should be replaced by "A holds in the standard model," if you're trying to make the model explicit everywhere. $\endgroup$ – Noah Schweber Dec 3 '16 at 18:48
  • $\begingroup$ @rere That's incorrect. True(g(A)) is a statement - specifically, g(A) is some natural number, and True(g(A)) is a statement about that number in the language of arithmetic. So saying "True(g(A)) is true" is the same, implicitly, as saying "True(g(A)) is true in the standard model," and when we say "True(g(A)) iff [stuff]" we mean (as usual in mathematics) "True(g(A)) is true iff [stuff]." There's no issue here. $\endgroup$ – Noah Schweber Dec 3 '16 at 19:06
  • $\begingroup$ I mean, True(g(A)) is also a string of symbols, but something can be both: every string of symbols which is a "sentence of first-order logic" corresponds to a statement (although not conversely), which may be true or false in a given model, and which we say is "true" or "false" without explicit reference to a particular model if we happen to have some distinguished model in mind. Is "$\forall x\exists y(y>x)$" a statement, or a string of symbols? $\endgroup$ – Noah Schweber Dec 3 '16 at 19:08
  • $\begingroup$ @rere That's simply not true. We need the semantics for Tarski's theorem to even make sense. The best way to state the theorem is: "If $A\models PA$, then there is no formula $\varphi(x)$ in the language of arithmetic with one free variable such that for all sentences $p$, we have $A\models\varphi(g(p))\iff A\models p$." We have to talk about truth in a model, which means we have to talk about semantics. $\endgroup$ – Noah Schweber Dec 3 '16 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy