Timeline for A meta-mathematical question related to Hilbert tenth problem
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2011 at 17:02 | comment | added | Emil Jeřábek | Well, your definition is actually equivalent in every model of arithmetic that satisfies the uniform $\Sigma^0_1$-reflection principle for PA. Now, there is no reason to refer to PA in the definition, you can instead use Robinson’s arithmetic Q. This modified definition only relies on the $\Sigma^0_1$-reflection principle for Q, hence it works in every model of PA, and in fact, in every model of the much weaker theory $I\Delta_0+\mathrm{SUPEXP}$. (If you further replace “consistent” with “cut-free consistent”, you can get it down to $I\Delta_0+\mathrm{EXP}$, which is about optimal.) | |
| Sep 26, 2011 at 16:17 | comment | added | Will Sawin | My definition should be equivalent only for the minimal model of the theory. Especially in arithmetic, the minimal model is usually the one we care about. (Also I think in other formal systems a minimal model may not even exist). | |
| Sep 26, 2011 at 14:54 | comment | added | Emil Jeřábek | ... One can generalize this idea to get inside the language of arithmetic the definition of truth for sentences of bounded quantifier complexity ($\Sigma^0_k$ for a fixed $k$). This is the best one can do, since by Tarski’s theorem on undefinability of truth, the full truth predicate for arithmetic is not expressible in the arithmetical language. | |
| Sep 26, 2011 at 14:52 | comment | added | Emil Jeřábek | Tarski’s definition is the usual definition in model theory which I referred to above (except that the SEP article describes in a rather long-winded way its philosophical ramifications instead of properly giving the actual definition). Will’s definition is also equivalent, but it only works for a restricted set of sentences ($\Pi^0_1$). On the other hand, it has the advantage that it is expressible within the arithmetical language itself. ... | |
| Sep 26, 2011 at 14:31 | comment | added | Joël | ...and Ed in comments under the question. What are the relations between those three notions of truth for a first order statement about numbers? Are they the same? If so, I should really have known it. In any case, can you give me more reference (or even better, more explanations) about them. Joel | |
| Sep 26, 2011 at 14:27 | comment | added | Joël | Ok, I am sorry, I overlooked that you only defined "true" in the particular case of a simple universal statement. You affirm that you can defined it for all first-order statement though, am I correct? I have to say I am getting more and more confused: in answer to my question, I have been referred to three notions of truth, but none with sufficient explanations of definitions. They were: the Tarski's notion of proof (with a long reference that I am soon going to read), your notion of truth that you explained for a universal statement but not in general, and the notion mentioned by Emil... | |
| Sep 26, 2011 at 14:00 | comment | added | Will Sawin | Actually that's not quite what my definition means, sorry for the confusion. I'm saying that "true" = "non-refutable" for a specific class of statements, those I think are usually called $\Pi_1$ statement. These consist of a universal quantifier around something that is checkable (provable or disprovable) in finite time. The negation of a Godel statement has an existential quantifier. The idea of this is that this is the class of statements in which the Platonist notion of truth is most easily translated into fomralism, and even on that limited class the theorem is proved. | |
| Sep 26, 2011 at 13:55 | comment | added | Emil Jeřábek | @Joël: The negation of Gödel’s formula is not a universal statement, but an existential one. | |
| Sep 26, 2011 at 13:44 | comment | added | Joël | So you define "true" as "non-refutable" in a given theory of arithmetic (say PA, to fix ideas). That's a notion even the most formalist mathematician can understood. And I understand that your statement "There is no algorithm for deciding if a first-order statement about numbers is non-refutable in (PA)" is correct. I note that with your notion of truth there well be a statement true in your sense but that a platonist would call plainly false (for example, the negation of Geodel's "true and undecidable" statement) but this is of course unavoidable. Thanks for your answer. | |
| Sep 26, 2011 at 3:19 | history | answered | Will Sawin | CC BY-SA 3.0 |