8
$\begingroup$

Godel's incompleteness theorem says that in mathematics there will be always true statements that cannot be proved and that adding that statement as a axiom generates other unprovable true statements.

So, mathematics clearly has logical inconsistencies. I was wondering if it it is possible to find a language that doesn't satisfy Godel's incompleteness theorem or, to put it more simply, such that all its true statements are provable?

$\endgroup$
10
  • $\begingroup$ Yes can we construct a language of which all of its true statements would be provable? $\endgroup$ Jun 20, 2023 at 3:42
  • 9
    $\begingroup$ @appliedSciences Sure. For instance, the first-order theory of the natural numbers with only addition is complete. Also the first-order theory of the rational numbers $(\mathbb Q, <)$ with only ordering (which has the exact same true/false sentences as the first-order theory of $(\mathbb R, < )$). Or the first-order theory of real closed fields. $\endgroup$ Jun 20, 2023 at 4:14
  • $\begingroup$ @spaceisdarkgreen are there any specific operations(or abscence) which make a language incomplete? $\endgroup$ Jun 20, 2023 at 4:35
  • 2
    $\begingroup$ @appliedSciences Having addition and multiplication certainly does it. In general, it suffices that the theory be able to interpret natural number addition and multiplication in some sense, or really to be able implement computation (in the sense of Church/Turing). The quotable sufficient condition is "recursively axiomatizable and capable of interpreting Robinson arithmetic" (you can find that in most discussions of the first incompleteness theorem). $\endgroup$ Jun 20, 2023 at 5:04
  • 15
    $\begingroup$ I should point out that incompleteness and inconsistency are not the same thing. In fact, you cannot have both at the same time (at least with classical logic), since if you have an inconsistency, that means you can prove every statement (including their negations). $\endgroup$ Jun 20, 2023 at 6:26

3 Answers 3

22
$\begingroup$

"Godel's incompleteness theorem says that in mathematics there will be always true statements which cannot be proved." Not quite. It says that in a given particular theory $T$, assuming $T$ is consistent, is recursively axiomatized and contains enough arithmetic, then there will be sentences undecidable by $T$. (But that doesn't rule out some other theory being able to give a verdict on that sentence. Peano Arithmetic, for example, can't decide $G_{PA}$, a canonical Gödel sentence for PA. But that doesn't rule out our being able to prove the truth of $G_{PA}$. Every textbook presentation of Gödel's theorem does just that!) "So mathematics clearly has logical inconsistencies." Why on earth think that follows from Gödelian incompleteness ... which, for a start, only applies to consistent theories $T$?

It may be that mathematics is in some sense inexhaustible (whatever conglomation of theories we so far endorse, there will be truths that escape the deductive reach of these theories). But inexaustibility isn't inconsistency.

A clear presentation of Gödel's theorems should disabuse you. There are some good ones recommended in the Beginning Mathematical Logic Study Guide.

$\endgroup$
1
  • 1
    $\begingroup$ Hey Peter i love the study guide! i just downloaded one for my own library. great work $\endgroup$ Jun 20, 2023 at 6:21
21
$\begingroup$

Your understanding of Godel's incompleteness theorem is incorrect. In short, Godel stated: for any formal system capable of arithmetic no weaker than Robinson arithmetic, if that system is consistent, then it will always possess true statements that cannot be proven AND it will be unable to prove its own consistency.

This does not imply that mathematics "clearly has logical inconsistencies" as you say. You seem to be confusing the existence of unprovable statements with inconsistency when in fact they are two distinct concepts. An example of a logical inconsistency is two proofs, one showing some statement $P$ is true while the other shows that $P$ is false. This is very different than there being a statement $P$ for which no proof exists. It may very well be the case that our mathematics is perfectly consistent. However, if that were true, then there would be no mathematical proof to show it and mathematics would be plagued with annoying "Godel statements" for which proofs don't exist.

To answer your last question, yes, it is possible to construct a formal, mathematical system that is both consistent (i.e. free of contradictions) and complete (i.e. all statements are provable). However, that system would have to be connected to a some arithmetic weaker than Robinson arithmetic. For instance, Presburger arithmetic is provably consistent and complete, but it lacks the expressive power to perform multiplication. If you want a formal system capable of Robinson arithmetic or something stronger, then the answer to your question is no. If you managed to construct such a system that was complete, Godel's theorem tells us it would necessarily be inconsistent.

So, when it comes to formal systems connected with Robinson arithmetic (or something stronger), you cannot have both consistency and completeness. Any such system will either have annoying contradictions or annoying statements with no proof.

$\endgroup$
7
  • 2
    $\begingroup$ Isn’t it actually easy to find a (hopefully) consistent complete formal system capable of formal arithmetic: just use the language of $\mathbb{N}$ and add as axiom every statement true in $\mathbb{N}$? Unless I’m mistaken, the issue is that this requires adding infinitely many axioms in a non-recursively enumerable way. $\endgroup$
    – Aphelli
    Jun 20, 2023 at 17:10
  • 1
    $\begingroup$ I see a couple of problems with your example. For one, how can ensure any such system is consistent? According to Godel, if it was, then no such proof would exist. Nonetheless, lets assume the system is indeed consistent. You attempt to resolve its incompleteness by adding every true statement to the axioms. Of course, to suceed in this task, you must add every Godel statement to the axioms, but there is no proof that Godel statements are true. So, how will you label all true statements as axioms when you're unable to determine whether some true statements are true in the first place? $\endgroup$ Jun 20, 2023 at 18:35
  • 4
    $\begingroup$ ZFC provides a model of what I called “the theory of $\mathbb{N}$” (it’s $\mathbb{N}$), which proves its consistency. But this is a tricky point (that remains obscure to me) because we need to specify with respect to what we prove statements and it gets confusing. I understand the first incompleteness theorem as a computability statement: if the language and axioms are recursively enumerable (and powerful enough), then it can’t derive all truths. In other words, one can’t make a computer list off (an infinite list of) axioms that suffice to prove every true proposition about $\mathbb{N}$. $\endgroup$
    – Aphelli
    Jun 20, 2023 at 18:35
  • $\begingroup$ okay that is an interesting point you make. i will have to go and read up on that myself. $\endgroup$ Jun 20, 2023 at 18:39
  • 1
    $\begingroup$ Presburger Arithmetic is consistent but does not have a definition of multiplication. Skolem Arithmetic doesn't contain addition. Both are decidable. Of course, things are missing; Presburger Arithmetic isn't strong enough to define prime numbers. It seems that multiplication isn't really repeated addition (though the multiplication of any two given numbers can be described as repeated addition.) $\endgroup$
    – ttw
    Jun 21, 2023 at 3:34
1
$\begingroup$

Have you ever heard of the engineer's trilemma? Good, fast, cheap: pick two. Gödel's incompleteness theorem is basically the mathematician's equivalent. Constructive, consistent, complete: pick two.

If a mathematical system is constructive (it can do all the math we want) and consistent (there are no contradictory proofs), it cannot be complete (there are statements we cannot prove either true or false). If it's constructive and complete, it cannot be consistent (for some of the statements we can prove true, we can also prove them false). And if it's consistent and complete, it cannot be constructive (there is math we simply cannot do without introducing either inconsistency or incompleteness).

The reason many learners stumble over this is because they don't realize that "constructive" and "complete" are two different things. A weak, "inconstructive" mathematical system is incomplete in the lay sense of the word - it cannot do things we would consider mathematics - but not in Gödel's - every statement we can state within the system, we can prove either true or false within the system, sometimes both (just because we can pick two, doesn't mean we must).

That "within the system" is important: We can still determine the truth or falsity of a statement in, say, Peano arithmetic by looking at its equivalent in, say, ZFC set theory, which is a stronger, "more constructive" system, but that doesn't make PA complete. The two systems are independent.

PS: "Constructive" is my own term, chosen for the alliteration. The usual term is "strong", but that's incredibly vague.

$\endgroup$

You must log in to answer this question.

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