6
$\begingroup$

I am reading Bjorn Poonen's very nice survey on Hilbert's Tenth problem (http://www-math.mit.edu/~poonen/papers/uniform.pdf), and while I believe I understand the mathematics well, I have widespread difficulties with the meta-mathematics of these questions. To illustrate them, and to ask a question that is answerable and whose answer might be helpful for me, let me focus on one little passage of this paper, that concerns not directly Matthiasevich's theorem that the tenth problem has a negative solution but an older, weaker version :

"[...] the work of K. Gödel, A. Church, and A. Turing in the 1930s made it clear that there was no algorithm for solving the [...] problem of deciding the truth of first-order sentences over $\mathbb{Z}$". (page 6)

What does that assertion exactly mean?

I understand well what an algorithm is and what a first-order sentence in arithmetic is. The difficult word in the quoted sentence is "truth".

Here is my tentative interpretation. Define a "platonist" as someone who believes that natural integers actually exist and that first order sentences about them are either absolutely true or absolutely false. I am such a person. So for a platonist, the passage quoted above would mean: "there is no Turing machine that take a first-order sentence as input and produces the output TRUE or FALSE according to wether the sentence is absolutely true or absolutely false." Ok. The problem is that this interpretation makes sense only for a platonist. I am not going to name names here, but I know very good mathematicians that are not platonists in the above sense.

Is there another (weaker) interpretation of the quoted sentence, that would make sense for pretty all mathematicians?

Or, is the statement from Poonen's paper simply rejected as non-sensical by those non-platonist mathematicians ?

I have in mind Gödel's incompleteness theorem itself, that comes in two versions: one for everyone, that says that there is a first-order arithmetical sentence that can not be proved nor disproved in, say, PA; and one stronger version for platonists that says that there is a first-order arithmetical sentence, that cannot be proved in, say, PA, but that is nevertheless true. But for the theorem of Gödel-Church-Turing quoted by Poonen I don't see what would be the version acceptable by everyone.

Edit: Many people seem to have great difficulties to understand my question. I am not sure I understand why. Let me try to explain it more from the "philosophical" point of view. I think anyone would agree that it is not self-evident that a first-order statement about numbers makes sense, and is either true or false independently of the system of axioms we choose. (Surely, a statement about sets does not necessary make sense, like "is the set of all sets an element of itself".) Actually, I do believe that any first-order statement about numbers makes sense, but for me this is like a religious belief, not something I would feel authorized to use in a serious mathematical theorem. Basically, like most number theorists I suppose, I work with ZF with the enumerable axiom of choice, and I feel pain in the stomach when occasionally I need to use the full axiom of choice or Grothendieck's axiom of universes (and in general, we convince ourselves that they are just used "to simplify the exposition", and that they could be avoided at the cost of just a lost in elegance). So when I see a statement like the one in boldface above, as a platonist I understand what it means, but I wonder if it is a reasonable statement that I can agree with with non-platonist colleagues.

Improve this question
$\endgroup$
35
  • 5
    $\begingroup$ @Thierry: Platonism doesn't require one to reject Godel's theorem. Why should it? Godel was a platonist. For a post-Godel platonist, every assertion about natural number is either true or false, simply no system of axioms (satisfying some conditions I don't recall) is strong enough to allow to deduce all truths. $\endgroup$
    – Joël
    Commented Sep 26, 2011 at 4:15
  • 4
    $\begingroup$ The structure $\langle\mathbb Z,+,\cdot\rangle$ is a mathematical object as any other, and so is the satisfaction relation $\mathbb Z\models\phi$, whose usual inductive definition you can find in any textbook on mathematical logic. $\mathrm{Th}(\mathbb Z)$ is then the set of all sentences $\phi$ such that $\mathbb Z\models\phi$. This does not have anything to do with any philosophical interpretation of truth, this is a mathematical construction, which can be carried out in a fairly weak fragment of ZF. It all comes down to the fact that the integers form a set. $\endgroup$
    – Emil Jeřábek
    Commented Sep 26, 2011 at 13:42
  • 5
    $\begingroup$ And your opinion is relevant because...? $\endgroup$
    – Joël
    Commented Sep 26, 2011 at 22:24
  • 6
    $\begingroup$ @Joёl: ... because I can vote to close your question. $\endgroup$
    – user6976
    Commented Sep 26, 2011 at 23:11
  • 4
    $\begingroup$ Joёl, any mathematical theorem T is something that your non-platonist colleagues can agree with, as long as your non-platonist colleagues understand that what is being asserted is, "T is a theorem of ZFC." This is why we don't have to settle philosophical debates in order to do math. We all agree what the theorems are. It's just that platonists take all the theorems at face value, and the formalists have to revert to the "T is a theorem" format for T's that they feel queasy about taking at face value. The word "truth" here presents no special problems; it is easily formalized in ZFC. $\endgroup$
    – Timothy Chow
    Commented Sep 26, 2011 at 23:59

5 Answers 5

Reset to default
13
$\begingroup$

There's a general "trick" for handling all issues of this sort. Take any mathematical theorem that a platonist regards as meaningful. Formalize it as a formal theorem T in ZFC. The formalist will now accept the sentence, "ZFC proves T."

Here, the only potentially confusing concept is that of truth. But to say that some first-order sentence of arithmetic is true just means that it is satisfied by the structure $\mathbb N$. The satisfaction relation, like all ordinary mathematics, is readily defined set-theoretically, as you can see in any textbook on logic. So the nonexistence of the algorithm in question can be expressed as a first-order sentence of set theory, and the formalist will agree that this sentence is a theorem of ZFC.

For some kinds of finitistic statements, the formalist doesn't have to do this little dance of translating "true" into formal set-theoretic terms and replacing "T" with "ZFC proves T." For example, in the sentence, "It is true that ZFC proves T," the formalist can use his "native" understanding of the word "true" and doesn't have to convert "ZFC proves T" into an arithmetic statement S and use the set-theoretic definition of truth to get a set-theoretic assertion whose ZFC-theoremhood he can agree with. But the little dance is always available as an option.

EDIT: Reading various comments to the original question and to other answers, I see that something more may need to be said about the satisfaction relation, even though it is standard textbook material. To say that a first order sentence $\phi$ is true, or that it belongs to $\mathrm{Th}(\mathbb N)$, means that it is satisfied by $\mathbb N$, where satisfiability is defined inductively. For example, $\exists x: \phi(x)$ is satisfied by $\mathbb N$ if there exists $x\in \mathbb N$ such that $\phi(x)$ is satisfied by $\mathbb N$. Further details may be found here.

Now, you might complain that in order to "make sense" of the satisfiability relation, you have to "make sense" of $\mathbb N$. However, you don't have to believe in $\mathbb N$ as some kind of platonically existing thing in order to correctly manipulate sentences about $\mathbb N$. Any sufficiently powerful set-theoretic meta-theory will suffice to carry out the definition of $\mathbb N$ and the satisfaction relation. ZFC is the standard choice but you could use something else if you prefer. A way to assert the existence of $\mathbb N$ in the first-order language of set-theory is as follows: $$\exists x:(\emptyset \in x \wedge \forall y\in x: (y\cup\lbrace y\rbrace\in x))$$ Here I've used various abbreviations, e.g., $\emptyset\in x$ expands formally to $\exists z : (z\in x \wedge \neg \exists w: (w\in z))$. Similar but more complicated formalizations can be produced for "set of first-order sentences of arithmetic" and "$\mathbb N$ satisfies $\phi$." As long as you know the axioms and rules of inference for ZFC, you can verify that the existence of $\mathrm{Th}(\mathbb N)$ is provable in ZFC. (Note: This is NOT the same as saying that every true sentence of arithmetic is provable in ZFC, which is absolutely false!) And once you have $\mathrm{Th}(\mathbb N)$, you can simply interpret "x is true" as $x\in \mathrm{Th}(\mathbb N)$. In particular, there is nothing mysterious about truth; it is just a mathematical concept formalizable in ZFC like any other mathematical concept.

Improve this answer
$\endgroup$
43
  • 1
    $\begingroup$ Very clear answer. But I think there's one more ambiguity on which one should shed some light. A formalist (such as myself, I think) interprets "The arithmetic sentence $\phi$ is true" as "ZFC (formally) proves that $\mathbb{N} \models\phi$" or "$\phi\in\mathrm{Th}(\mathbb{PA})$" (where both $\mathbb{N} \models\phi$ and $\phi\in\mathrm{Th}(\mathbb{PA})$ are really first-order sentences of ZFC). But with this formalistic definition of truth (lacking a "real world" against which to check truth), which is always relative to a certain metatheory such as ZFC, by Goedel incompleteness... $\endgroup$
    – Qfwfq
    Commented Sep 27, 2011 at 17:24
  • 1
    $\begingroup$ ... of ZFC the alternative "Either $\phi$ is true or $\phi$ is false" doesn't always hold: $\phi\in\mathrm{Th}(\mathbb{PA})$ could be undecidable in ZFC (in the sense that ZFC doesn't formally prove "$\phi\in\mathrm{Th}(\mathbb{PA})$" nor its negation). Am I saying nonsense? $\endgroup$
    – Qfwfq
    Commented Sep 27, 2011 at 17:25
  • 1
    $\begingroup$ ϕ∈Th(N) could be undecidable in ZFC; however, ZFC will prove (ϕ∈Th(N))∨(ϕ∉Th(N)). In other words, "either ϕ is true or false" is a theorem of ZFC even if neither ϕ∈Th(N) nor ϕ∉Th(N) is provable in ZFC. Again, there's nothing special about "true sentences of arithmetic" here. ZFC always proves $\psi\vee\neg\psi$ for any $\psi$ regardless of whether $\psi$ or $\neg\psi$ is provable, because ZFC is based on classical logic. I will reiterate that my suggestion here is NOT that "ϕ is true" should be interpreted as "ϕ is provable in ZFC" but as "ϕ∈Th(N)" (for ϕ a first-order sentence of arithmetic). $\endgroup$
    – Timothy Chow
    Commented Sep 27, 2011 at 17:58
  • 2
    $\begingroup$ @Joël: No, I don’t agree at all. Everywhere in mathematics, it is quite usual to spell most statements in words, including quantifiers and logical connectives. It would be completely crazy to write everything as a symbolic formula. In any case, it makes no difference, since the two are just different ways of writing the same thing, and you have yourself just admitted that you understand what it means, so the conclusion is that you are only trying to make a point. $\endgroup$
    – Emil Jeřábek
    Commented Sep 28, 2011 at 13:25
  • 2
    $\begingroup$ Joël: Yes, model theory, like any other piece of mathematics, is written in a human-friendly style, rather than in a style which makes it evident that everything can be built on set theory as a foundation. I suspect that you, like most mathematicians, have glibly accepted that "everything can be based on set theory" without thinking too hard about what that means. If you do think about it, you'll see that this means that everything you talk about in mathematics—a differential equation, a symbol, a number, a homomorphism, whatever—must be encoded as a set. $\endgroup$
    – Timothy Chow
    Commented Sep 28, 2011 at 14:56
8
$\begingroup$

We can avoid the issue of truth by simply proving the following statement:

There is no Turing machine which, given a statement S, returns TRUE if S is provable in PA, returns FALSE if NOT(S) is provable in PA, and returns either TRUE or FALSE for all S.

Philosophers can then argue about what truth means. As long as you believe that PA is consistent true, and that every statement is either true or false, this shows that a Turing machine cannot capture truth. A formalist may not agree with this interpretation of the above statement, but they certainly will agree that this statement is meaningful.

UPDATE: See discussion below of whether what a person who thinks PA is consistent, but not true, might make of this answer.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ The belief necessary for this to work is not merely that PA is consistent but that it is true. A consistent theory might prove false statements. So there would be a problem if philosophers came up with a notion of truth such that some PA axioms aren't true. The problem could be alleviated by using weaker theories in place of PA, but really obstinate philosophers might still be a problem. $\endgroup$
    – Andreas Blass
    Commented Sep 27, 2011 at 12:46
  • 3
    $\begingroup$ This certainly gives a statement that almost any formalist would agree with, but to elaborate a bit on what Andreas Blass said, it's not a plausible interpretation of the original sentence, and it's not even a weakening of the original sentence unless you assume that theorems of PA are true. Truth and provability are not the same, and it may cause confusion later down the line to think that whenever one sees "true" one can replace it with "provable" to get a "formalist version" of the statement. $\endgroup$
    – Timothy Chow
    Commented Sep 27, 2011 at 15:55
  • 2
    $\begingroup$ First of all, I'm surprised this answer was chosen. I thought Timothy Chow's was clearly better, and that this was a less good alternative perspective. That said, while I certainly understand that truth and provability are different, I don't see what is wrong with describing some properties we would want truth to have: True statements are consistent with each other, the axioms of PA are true, and so forth, and then demonstrate that no Turing computable property has those features. That isn't a weakening of the statement that truth isn't Turing computable; it's a strengthening! $\endgroup$
    – David E Speyer
    Commented Sep 27, 2011 at 16:24
  • 1
    $\begingroup$ Would it help to make an analogy to Arrow's theorem? Arrow roughly says that there is no fair voting method; and makes that precise by giving a list of features any fair voting method should have. Similarly, I am giving a list of features that any notion of truth should satisfy. I'm not saying this is what truth is, just like Arrow isn't saying that any method that satisfies these features is fair, he's just saying that these features already rule out existence (or, in my case, rule out Turing computability.) $\endgroup$
    – David E Speyer
    Commented Sep 27, 2011 at 16:28
  • 1
    $\begingroup$ Probably part of my mental block here is that, while I could imagine someone who suspected there might be a technical difficulty in PA, I have trouble imagining someone who doesn't think that PA should be true, and that any technical flaw is an error in how we have encoded our intuition about finite sets into our axioms. That sounds to me like someone who thinks that there is nothing unfair about a voting system with a dictator. $\endgroup$
    – David E Speyer
    Commented Sep 27, 2011 at 16:31
5
$\begingroup$

Well, suppose you believe in the notion of consistency of theories of arithmetic. Then I believe you can define the notion of truth. In particular, any simple universal statement is "true" if and only if adding it to PA produces a consistent system. (If it were "false", there would be a counterexample constructible in finite time.)

The statement "There is no algorithm for deciding whether adding simple universal statements to PA produces a consistent system" is true and, with this partial definition of truth, implies the quoted statement.

Another version is this:

There is no algorithm for sorting first-order statements into a boxe labeled "true" and a boxe labeled "false" such that the negation of each statement in the "false" box is in the "true" box and the set of statements in the "true" box is consistent.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joël
    Commented Sep 26, 2011 at 13:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Commented Sep 26, 2011 at 14:00
  • 2
    $\begingroup$ 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. ... $\endgroup$
    – Emil Jeřábek
    Commented Sep 26, 2011 at 14:52
  • 3
    $\begingroup$ ... 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. $\endgroup$
    – Emil Jeřábek
    Commented Sep 26, 2011 at 14:54
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Emil Jeřábek
    Commented Sep 26, 2011 at 17:02
4
$\begingroup$

"True" in this context surely refers to Tarski's inductive definition of truth.

Improve this answer
$\endgroup$
0
2
$\begingroup$

I would take the sentence to mean something like:

Given any model of PA in any axiomatic system, there is no Turing machine that ... according to whether the sentence is true or false for that model.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Thanks for your answer, but I do not think that it solves the problem: You need to be a super-platonist to believe to the notion of truth in a model: that is, you need to believe in the absolute existence of sets, not just of integers. $\endgroup$
    – Joël
    Commented Sep 26, 2011 at 13:24
  • 1
    $\begingroup$ No i don't need to believe in the absolute existence of sets - only the axiom system in which the model is constructed needs to believe in the absolute existence of sets. "True or false for that model" means "true or false for that model according to that axiomatic system". (Since I am not a Platonist, that's all it could mean!) (Yes the sentence could be undecidable, but one could just extend the axiomatic system - I guess one has to careful about the order of quantifiers to allow the axiomatic system to be extended after the statement is chosen.) $\endgroup$
    – Alexander Woo
    Commented Sep 26, 2011 at 18:06
  • 1
    $\begingroup$ Thanks, I now understand that your answer is more or less equivalent to the other ones I received, and I need to read more in the link Emil gave me to be sure I understand them all, and then to see if I can accept them. I'll try to do that tonight. But meanwhile, let me just say that you put the finger exactly on where I have a problem with. Roughly speaking, you guys all define true as true in a model of arithmetic in set theory. But either you interpret the truth in this model as some absolute platonistic truth and we are not better than at the beginning... or you interpret it as what is $\endgroup$
    – Joël
    Commented Sep 26, 2011 at 18:25
  • 1
    $\begingroup$ Or we interpret it as "provability" in some axiomatic of set theory, but then we get the problem that there will always be undecidable statement, that is with your definition, statements that are neither nor true nor false, and then what the algorithm we are talking about is suppose to do when such a statement is fed to it as input? So you say we can change our axiomatic of set theory to get rid of in decidable statement, but as you say it is a little tricky (plus it is not canonical) and I need to understand exactly what we're doing here. $\endgroup$
    – Joël
    Commented Sep 26, 2011 at 18:29
  • $\begingroup$ How about, "Given any axiomatic system X containing a model M of PA and any Turing machine T that takes first order sentences as input and produces TRUE or FALSE, there exists an axiomatic system Y extending X and a sentence A such that Y proves one answer for the interpretation of A in M and T gives the other answer on A." $\endgroup$
    – Alexander Woo
    Commented Sep 26, 2011 at 18:31

You must log in to answer this question.

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