Timeline for Tarski's truth theorem — semantic or syntactic?
Current License: CC BY-SA 4.0
36 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2020 at 15:51 | comment | added | Pace Nielsen | @Burak I'm no longer bugged by any issues. My confusion arose from my misunderstanding of how a formula was being used in Jech's proof. While $\#\varphi_x(x)$ is not technically a formula in the language of set theory, it is representable by such a formula (when $\#$ is recursive, etc...). | |
| Apr 28, 2020 at 15:45 | vote | accept | Pace Nielsen | ||
| Apr 28, 2020 at 14:21 | comment | added | Burak | @PaceNielsen: If you are bugged by this issue, it is also present in the definition of "truth definition". Is this a definition in ZFC, in which case all formulas in that definition are indeed the formal objects (sets) that represent those formulas, or is this a "metadefinition" that says that a formula $T(x)$ that I write down is a truth definition if I can prove the item (i) and every instance of item (ii)? | |
| Apr 28, 2020 at 14:15 | comment | added | Burak | Noah, I don't think Jech is working in NBG (at least, he does not hint this at any point.) @PaceNielsen I think the issue here depends on whether you see this theorem as a single theorem or a theorem scheme. If you treat this as a theorem scheme for each $T(x)$, then he explicitly produces a sentence $\sigma$, for which we can prove that $\sigma \leftrightarrow \neg T(\# \sigma)$. If you want to see this a single theorem that quantifies over all formulas $T(x)$, then you need a satisfaction relation for proper classes which would require you to work in a class theory such as NBG. | |
| Apr 27, 2020 at 20:15 | comment | added | Noah Schweber | So intuitively "conjunction is the standard part of a definable relation in all models of $T$." This is all nuked by the theorem that (for $T$ appropriate) the (total) computable functions are exactly the functions which are representable in $T$ in this sense; although it's overkill for that specific purpose, this result is generally proved in modern expositions of Godel's incompleteness theorem. | |
| Apr 27, 2020 at 20:13 | comment | added | Noah Schweber | @PaceNielsen Well, for an arbitrary numbering there's not much that can be said. For example, map all the true sentences onto the evens and the false sentences onto the odds. So some constraint is needed to get anything useful. The key properties we need for these sorts of results are representability, or invariant definability, properties: for example, we want there to be a formula $\psi$ such that for every standard $i,j,k$ we have $T\vdash\psi(i,j,k)$ iff $i=\#(\#^{-1}(j)\wedge\#^{-1}(k))$ and $T\vdash\neg\psi(i,j,k)$ otherwise. (cont'd) | |
| Apr 27, 2020 at 20:10 | comment | added | Pace Nielsen | @NoahSchweber There is one additional point. I believe Godel's lemma requires that the numbering is given by a nice enough function. What happens if you allow an arbitrary numbering? | |
| Apr 27, 2020 at 20:07 | comment | added | Pace Nielsen | Perfect! I've accepted the answer | |
| Apr 27, 2020 at 20:07 | vote | accept | Pace Nielsen | ||
| Apr 28, 2020 at 15:44 | |||||
| Apr 27, 2020 at 20:06 | comment | added | Noah Schweber | @PaceNielsen I've added the diagonal lemma to my answer. | |
| Apr 27, 2020 at 20:06 | comment | added | Pace Nielsen | Great, I think this is what I was looking for. | |
| Apr 27, 2020 at 20:04 | comment | added | Monroe Eskew | @PaceNielsen- See for example the end of the first chapter of Kunen’s book. | |
| Apr 27, 2020 at 20:00 | comment | added | Noah Schweber | @PaceNielsen Yes, that's just Godel's diagonal lemma (and it's provable in $I\Sigma_1$ for example). | |
| Apr 27, 2020 at 19:59 | comment | added | Pace Nielsen | And to clarify, by a Godel numbering, I mean an injective map from the true formulas of that signature (not the internal formulas) to the elements of $\omega$ (inside the formal system). | |
| Apr 27, 2020 at 19:55 | comment | added | Pace Nielsen | @MonroeEskew Are you asserting the following metamathematical statement? For every formula with one free variable $\varphi(v)$ in the signature $(\in)$, and every Godel numbering $\#$ of sentences in that language, there exists a sentence $\sigma$ such that ZFC proves $\sigma\leftrightarrow \neg\varphi(\#\sigma)$. If so, where is the easiest place to find a complete (easy) proof of this? | |
| Apr 27, 2020 at 19:53 | history | edited | Noah Schweber | CC BY-SA 4.0 |
added 375 characters in body
|
| Apr 27, 2020 at 19:44 | comment | added | Noah Schweber | @MonroeEskew And that syntactic result - or more accurately, that result with the hypothesis that ZFC is consistent - is itself provable in a very weak theory (way below $I\Sigma_1$ certainly). | |
| Apr 27, 2020 at 19:43 | comment | added | Monroe Eskew | @PaceNielsen You can also take from this argument the syntactic result that there is no formula $\phi(v)$ such that for every sentence $\sigma$, ZFC proves $\phi(\#\sigma) \leftrightarrow \sigma$. Because given $\phi(v)$, you can construct a particular $\sigma$ that is provably equivalent to $\neg\phi(\#\sigma)$. This is just Goedel's fixed point lemma. | |
| Apr 27, 2020 at 19:40 | comment | added | Noah Schweber | The formal version of that definition is: "$T$ is the Godel number of a truth predicate iff ... (ii) if $\sigma$ is a sentence, then $V\models\sigma$ iff $V\models T(\#\sigma)$." This indeed uses satisfaction with respect to a specific structure, namely $V$. | |
| Apr 27, 2020 at 19:38 | comment | added | Noah Schweber | @PaceNielsen No, it's a single assertion and it's referring to what's true in $V$. (What does "holds" mean otherwise? It can't possibly refer to holding across all models of ZFC, since that is definable.) | |
| Apr 27, 2020 at 19:37 | comment | added | Pace Nielsen | The wording in my version of the book is exactly the following: "if $\sigma$ is a sentence, then $\sigma\leftrightarrow T(\#\sigma)$." This is a schema of assertions. For each statement $\sigma$ (in the FOL language in the signature $(\in)$, in the theory given by the axioms of ZFC and the usual logical axioms), it is being asserted that $\sigma\leftrightarrow T(\#\sigma)$ holds. | |
| Apr 27, 2020 at 19:31 | history | edited | Noah Schweber | CC BY-SA 4.0 |
deleted 96 characters in body
|
| Apr 27, 2020 at 19:30 | comment | added | Noah Schweber | @PaceNielsen No, he doesn't: he says "if $\sigma$ is a sentence [then] $T(\ulcorner\sigma\urcorner)$ holds if and only if $\sigma$ holds." "Holds" here is implicitly with respect to $V$. Where are you getting the contrary? | |
| Apr 27, 2020 at 19:28 | comment | added | Pace Nielsen | No, it is still not right. His definition of $T$ (the purported truth predicate) is purely syntactical (up to choice of Godel numbering). He doesn't say $M\models \sigma$ if and only if $M\models T(\#\sigma)$. He says that for each sentence $\sigma$, the formula $\sigma\leftrightarrow T(\#\sigma)$ is valid (i.e., true in all worlds). | |
| Apr 27, 2020 at 19:25 | comment | added | Noah Schweber | @PaceNielsen I've edited my answer to hopefully better address your question; let me know if I'm still not getting your point. | |
| Apr 27, 2020 at 19:24 | history | edited | Noah Schweber | CC BY-SA 4.0 |
deleted 96 characters in body
|
| Apr 27, 2020 at 19:17 | comment | added | Noah Schweber | @PaceNielsen I'm looking at the book right now. The only thing I'm guessing at is the book's specific choice of metatheory, which I'd have to search for. But regardless of whether he uses $\mathsf{NBG}$ or $\mathsf{MK}$ or similar, the point is the same: there is a specific model he's (implicitly) talking about there, namely the true $V$, and the truth definition is with respect to that (proper class sized) structure. That is, for Jech "true" is a proxy for "true in $V$." | |
| Apr 27, 2020 at 19:17 | comment | added | Pace Nielsen | Noah, rather than making guesses, perhaps you should find a copy of the book and look at the relevant sections. In case you don't have a copy, here are the conditions: (i) $\forall x\, (T(x)\rightarrow x\in \omega)$ and (ii) for every sentence $\sigma$, then $\sigma\leftrightarrow T(\#\sigma)$. As you can see, there is no reference to modeling here. These conditions are independent of the choice of model. | |
| Apr 27, 2020 at 19:17 | comment | added | Noah Schweber | Note that if we take the $\mathsf{NBG}$ approach - which I think is what Jech is implicitly doing - then we are (in the metatheory $\mathsf{NBG}$) proving a result about the actual universe of all sets ($V$), so the issue of "correct natural numbers" doesn't come up. The "de-classed" version of the result in my previous comment is applicable more broadly. | |
| Apr 27, 2020 at 19:13 | comment | added | Noah Schweber | We can "de-classify" this along the usual lines of course: if we want to use $\mathsf{ZFC}$ as our metatheoy, Theorem $12.7$ is then understood as a natural-language version of a $\mathsf{ZFC}$-proof of "If $\mathcal{M}\models \mathsf{ZFC}$ then $Th(\mathcal{M})$ is not (the standard part of) a definable subset of $\mathcal{M}$." | |
| Apr 27, 2020 at 19:12 | comment | added | Noah Schweber | @PaceNielsen No, there is a reference to a structure there although it's implicit: the book (if I recall correctly) uses $\mathsf{NBG}$ as the metatheory throughout. So $\mathsf{NBG}$ is proving "The set of sentences true in the structure $V$ is not a definable element of $V$." The structure in question is $V$ itself, which is a directly-handleable object in $\mathsf{NBG}$. | |
| Apr 27, 2020 at 19:04 | comment | added | Pace Nielsen | Regarding truth predicates requiring structure---that's what my question was asking about! Jech defines a truth condition without any reference to a structure. (See his condition (12.17) on page 162.) | |
| Apr 27, 2020 at 19:04 | comment | added | Noah Schweber | The natural-language version of Tarski's theorem is "$Th(\mathbb{N};+,\cdot)$ is not definable in $(\mathbb{N};+,\cdot)$." To even express that, our metatheory needs to be able to talk about $(\mathbb{N};+,\cdot)$ as a structure appropriately. | |
| Apr 27, 2020 at 19:00 | comment | added | Noah Schweber | @PaceNielsen What is a truth predicate for ZFC? Truth predicates only make sense for structures. | |
| Apr 27, 2020 at 19:00 | comment | added | Pace Nielsen | But I don't care what ZFC proves about its internal formulas. I want, from a metatheoretical point of view, to know what it takes to show that there is not definable truth predicate for ZFC. My metatheory doesn't necessary assume ZFC, per se. | |
| Apr 27, 2020 at 18:27 | history | answered | Noah Schweber | CC BY-SA 4.0 |