4
$\begingroup$

Godel`s incompleteness theorem states that there may exist true statements which have no proofs in a formal system of particular axioms. Here I have two questions; 1) How can we say that a statement is true without a proof? 2) What has the self reference to do with this? Godel sentence "G" can say that SUB(a,a, no prove) but could be this just arbitrarily judgement about non-provability of "a" because it may simply has a proof which is not yet revealed or discovered?

$\endgroup$
  • 1
    $\begingroup$ For (1), a thing that actually happens is this: you may have a predicate $\mathfrak S$ of natural numbers such that, for any fixed $n$, $\mathfrak S(n)$ can be verified in a finite number of steps. However, it turns out you cannot prove using the axioms at your disposal whether $[\forall n,\mathfrak S(n)]$ is true or not. In such a case, $[\forall n,\mathfrak S(n)]$ must be "true", in the sense that, whenever it is actually provable, it is true. $\endgroup$ – user228113 Jul 27 '16 at 17:42
  • $\begingroup$ (that's as much as I know on the subject, though :) ) $\endgroup$ – user228113 Jul 27 '16 at 17:46
  • $\begingroup$ @G.Sassatelli, even if it's not the full picture, you still made this very clear, so thank you. I was wondering about this too $\endgroup$ – Yuriy S Jul 27 '16 at 17:51
  • 1
    $\begingroup$ @G.Sassatelli: What you say is correct, though indeed it's not the full picture. The phenomenon you describe is called $ω$-incompleteness. PA is $ω$-incomplete for the following interesting reason. PA decides (proves or disproves) every quantifier-free sentence over PA. Con(PA) is an independent $Π_1$-sentence over PA (Essentially saying that every string $x$ is not a proof of "$\bot$"), but each of its instantiations is provable since PA can verify each step of a proof. We more precisely say that PA is not $Π_1$-complete. But note that PA is $Σ_1$-complete. $\endgroup$ – user21820 Jul 28 '16 at 5:18
  • 1
    $\begingroup$ @G.Sassatelli: Sorry I made an accidental mistake in my last comment, so I've deleted it. Here is the corrected version. Every structure $M$ over the language of PA that satisfies "$φ(k)$" for every $k \in M$ must also satisfy $\forall n\ ( φ(n) )$. The sentence Con(PA) shows that it is possible that $\def\nn{\mathbb{N}}$$\nn$ satisfies "$φ(k)$", and in fact PA proves "$φ(\underbrace{1+\cdots+1}_\text{$k$ terms})$", for every $k \in \nn$, but that PA does not prove "$\forall n\ ( φ(n) )$". $\endgroup$ – user21820 Aug 3 '16 at 9:55
6
$\begingroup$

Your confusing stems from the way many articles about Godel's incompleteness theorems are extremely imprecise. Here is a proper definition. $\def\nn{\mathbb{N}}$

We say that a sentence $φ$ over a language $L$ is true in an $L$-structure $M$ iff $M \vDash φ$.

For convenience, when $L$ is the language of arithmetic, we say that $φ$ is true iff $\nn \vDash φ$.

Note that these definitions are only possible in a meta-system that already has a collection called $\nn$ (also known as the standard model of PA). Thus: $\def\t#1{\text{#1}}$ $\def\con{\t{Con}}$ $\def\pa{\t{PA}}$

"$φ$ is true but unprovable" is more precisely "$\nn \vDash φ$ and $\pa \nvdash φ$".

Now there is a sentence over PA denoted by $\con(\pa)$ such that PA is consistent iff $\nn \vDash \con(\pa)$ (in other words PA is consistent iff $\con(\pa)$ is true in the standard model). It is in fact non-trivial to show that such a sentence exists, which is a crucial part of Godel's first incompleteness theorem.

The remainder of the incompleteness theorem shows that $\pa \nvdash \con(\pa)$. But the meta-system we choose always has $\nn \vDash \pa$, so $\pa$ is consistent and hence $\nn \vDash \con(\pa)$. Thus $\con(\pa)$ is the first natural example of a sentence that is true but unprovable (in the precise sense defined above).

Note that it is false that every true but unprovable sentence $φ$ can be proven by $\pa+\con(\pa)$. In particular, $\pa+\con(\pa) \nvdash \con(\pa+\con(\pa))$, even though $\nn \vDash \con(\pa+\con(\pa))$ (by essentially the same argument as above). This can be proven simply by applying Godel's proof of the incompleteness theorem to $\pa+\con(\pa)$.

Better still, we can let $\pa_0 = \pa$ and recursively let $\pa_{k+1} = \pa_k + \con(\pa_k)$ for every $k \in \nn$, and then let $\pa_ω = \bigcup_{k\in\nn} \pa_k$. Then we still have $\nn \vDash \pa_ω$, and yet $\pa_ω \nvdash \con(\pa_ω)$ even though $\pa_ω \vdash \con(\pa_k)$ for every $k \in \nn$.

$\endgroup$
  • $\begingroup$ Also see the links in math.stackexchange.com/a/1684208/21820 for introductory material to logic, as it is difficult to grasp the concepts here without a proper understanding of logic. $\endgroup$ – user21820 Jul 28 '16 at 6:12
3
$\begingroup$
  1. Assuming your formal system is consistent, Gödel shows there is a statement in that system whose interpretation is true but that is unprovable in the system. The statement is actually provable, but not in that system: you need the additional assumption that the system in consistent, and that is not provable in the system (unless the system happens to be inconsistent!).

  2. There's no "arbitrarily judgement" here. If there were a proof of "a", you could use that to produce a proof of 0=1. Thus if the system is consistent, "a" is not provable in the system.

$\endgroup$
  • $\begingroup$ What if "a" is false, then within the system, we prove that it is not provable which means it is true (because we can not prove that it is false which means it is true). This means that it is true and false at the same time even if the Godel`s sentence is true. $\endgroup$ – Isaacadel Jul 27 '16 at 18:18
  • 1
    $\begingroup$ Unprovability is not the same as falsehood; the assumption that it is is the assumption of completeness itself. This is question-begging in the context of Gödel's proof. $\endgroup$ – Malice Vidrine Jul 27 '16 at 18:29
  • $\begingroup$ Sorry but your answer is wrong. Assuming the system is consistent does not have anything to do with (arithmetical) truth, which is always the notion concerned. See my answer for an explicit sentence that is true in $\mathbb{N}$ but not provable no matter how many times you add the assumption of consistency of the system to itself. $\endgroup$ – user21820 Jul 28 '16 at 4:30
  • $\begingroup$ @user21820 That's incorrect. Robert Israel is not saying that consistency lets you prove everything - just that a consistency hypothesis is needed to prove the specific example he mentions (which is absolutely correct). $\endgroup$ – Noah Schweber May 9 '17 at 17:16
  • $\begingroup$ @NoahSchweber: It's a year since my comment, but on reading my own comment it seems that I had interpreted Robert's claim to be about any independent statement, rather than the Godel sentence specifically. Also, Godel's original proof required ω-consistency, not just consistency, so there are multiple places in his post that needs fixing or clarification. $\endgroup$ – user21820 May 9 '17 at 17:29
3
$\begingroup$

1) How can we say that a statement is true without a proof?

The main idea behind the standard definitions of truth used by most mathematicians and logicians that study mathematical logic, model theory and related topics is the one given by Tarski. As you can see at the link, he separated the concept of truth from the syntax of the language (for a good number of reasons, e.g., to not allow statements such as "this statement is false"), i.e., the truth concept is not given within the language but by the metalanguage. As the concept of proof is syntactical, at first you won't need any proved formula to be true or any true formula to be provable, but there's a property called soundness and it gives the following result:

In a first order theory, if $\Sigma \vdash \varphi$ then $\Sigma\vDash \varphi$.

First, $\Sigma \vdash \varphi$ means that a set of formulas $\Sigma$ can prove the formula $\varphi$, i.e., you have $\Sigma$ and logical axioms (and, maybe, some aditional nonlogical axioms from the theory) as assumptions and are able to derive or deduce $\varphi$ using the rules of inference of your theory, so this is a syntactical process. Now, in my notation, $\Sigma \vDash \varphi$ means that all structures (which carry the concept of truth) that satisfy the formulas in $\Sigma$ also satisfy $\varphi$, in other words, if all formulas in $\Sigma$ are true in some structure $\mathfrak{M}$, then $\varphi$ must be true in $\mathfrak{M}$. As $\Sigma$ usually is a set of axioms that define a theory, if $\mathfrak{M}$ is a structure that satisfies $\Sigma$ (i.e., all formulas in $\Sigma$ are true in $\mathfrak{M}$) we say that $\mathfrak{M}$ is a model of $\Sigma$. In his doctoral dissertation , Gödel proved the converse, which is known as his Completeness Theorem:

In a first order theory, if $\Sigma \vDash \varphi$ then $\Sigma\vdash \varphi$.

We say that a theory is complete in that sense (some authors call it semantically complete, to not make confusion with other type of completeness that is used in the Incompleteness Theorems, which they may call syntactical completeness) if this statement is valid (and it is, Gödel proved it).

Now we can observe the fact that in some theories there are statements that can't be proved as well as their negation, you don't need to go too far to have some examples of this happening, if you have a system where you axioms $\Sigma$ are the Field Axioms you can't prove the formula $\varphi$ where it is $(\exists x)(x^2=-1)$ for the following reason: we can see (in a not rigorous manner) both $\mathbb{C}$ and $\mathbb{R}$ as models of $\Sigma$ and $\varphi$ is true in $\mathbb{C}$ (as you can take $x=i$) and false in $\mathbb{R}$, which means that not all models of $\Sigma$ satisfy $\varphi$, i.e., $\Sigma \nvDash \varphi$ and, by the soundness property, we have that $\Sigma \nvdash \varphi$ and, with a similar argument, you also have that $\Sigma \nvdash \neg \varphi$.

Now that we know that there are some theories that have statements that you can't prove (as well as their negation), we call such systems incomplete (or, as I commented early, syntactically incomplete), what Gödel showed in his First Incompleteness Theorem was that any first order theory that satisfy some conditions will be incomplete, and that proved that, because the way mathematicians axiomatize the standard mathematical theories, we can't scape from the fact that there will always be statements such as $\varphi$ I showed early. In particular this will be valid for some theories that have a set of axioms $\Sigma$ with some properties and such that $\textbf{PA}\subset \Sigma$ where $\textbf{PA}$ is the set of Peano's Axioms.

On the other hand, mathematicians suppose that there's a standard model for arithmetics, i.e., a structure $\mathfrak{N}$ that satisfies $\textbf{PA}$ and every arithmetical statement, to be considered true, must be satisfied in that structure. Now I can finally give you an answer to your question: by the First Incompleteness Theorems, loosely speaking, any system of axioms $\Sigma$ (given some conditions) for the standard arithmetic will have statements $\varphi$ such that $\Sigma \nvdash \varphi$ and $\Sigma \nvdash \neg \varphi$, but $\mathfrak{N}$ satisfies $\varphi$ or $\neg \varphi$, that means that there will always be a true statement (a formula satisfied by $\mathfrak{N}$) that can't be proven by a given system of axioms $\Sigma$.

2) What has the self reference to do with this? Godel sentence "G" can say that SUB(a,a, no prove) but could be this just arbitrarily judgement about non-provability of "a" because it may simply has a proof which is not yet revealed or discovered?

The self-reference is just an argument used by Gödel in his original proof from which he was able to construct a sentence that is not provable by the system and will be true when you see it with the lens of the meta-theory. With all I said I hope you can comprehend that some statements in a given fixed theory are impossible to prove, it's not a matter of something not being revealed or discovered.

For further reference and lots of details and technicalities that are missing in my answer, as well as aspects of the problem consisting on deciding if a statement is true or not, I can recommend the following textbooks:

  • Hinman, Peter G. Fundamentals of Mathematical Logic. Wellesley, MA: A.K. Peters, 2005.

  • Dalen, Dirk. Logic and Structure. Fifith Edition. Berlin: Springer-Verlag, 2013

  • Tourlakis, George. Lectures in Logic and Set Theory. Vol. 1, Mathematical Logic (Cambridge Studies in Advanced Mathematics ; 82). N.p.: Cambridge UP, 2003.

  • Shoenfield, Joseph R. Mathematical Logic. Reading, MA: Addison-Wesley Pub., 1967.

There are also good references and links here and here.

$\endgroup$
  • $\begingroup$ So if the truth is isolated from the syntax of the proof of a particular statement within one theory, it should itself be a conclusion within another more general theory. Then what is the most fundamental true statement that we should begin in order to reach to the proof of any other possible statement? And more importantly, how could be know that this fundamental truth is true if it is not preceded with any other theory to prove it is true? $\endgroup$ – Isaacadel Aug 1 '16 at 10:43
  • $\begingroup$ @Isaacadel Truth it's not a conclusion in a more general theory, truth is just a property that a sentence may have if there's model satisfying it. Inside a theory, a statement can be true or false depending on two things: if it's provable, then it's true (soundness), if its negation is provable, then it's false, if it's neither provable nor disprovable, it can be either true or false depending on your context (i.e., dpeneding on your especific model), think about my example. The question about fundamental truths is more philosofical than technical, you should ask it somewhere else. $\endgroup$ – Pedro Vaz Pimenta Aug 1 '16 at 15:20
0
$\begingroup$

As is convenient in discussions of the completeness theorems, let's focus on the theory of arithmetic over the natural numbers. We have a well-defined notion of truth in the natural numbers under the usual arithmetic operations: e.g., the sentence $\forall i\cdot \exists a, b, c\cdot \ a > i \land a^2 + b^2 = c^2$ asserts the existence of arbitrarily large Pythagorean triples and we "know" what that means (specifically it means that it is valid in what model theorists call the structure comprising the natural numbers and the usual arithmetic operations).

Now let's think about methods for deducing which sentences are true in this theory, e.g., we might take our method to be first-order logic and Peano's axioms. What Gödel's incompleteness theorem says is that (under some very reasonable hypotheses on the method), there is no method that will let us deduce all true sentences and no false sentences. The theorem does not say "there is no proof", it says "a specific method of finding proofs will never find one".

The philosophical interest is that the theorem applies to an enormous range of "specific methods of finding proofs" and indicates that there is no chance of finding an adequate foundation system for mathematics that can prove its own consistency.

$\endgroup$
  • $\begingroup$ While your explanation is not wrong, it is not the one that logicians have in mind for (arithmetical) truth (which I've defined in my answer). One could hence argue that Godel's incompleteness theorems have much less philosophical impact than Tarski's undefinability theorem, though both are essentially the same from a purely mathematical viewpoint (because mathematics is always done in a formal system). Hence I suggest that you clearly specify that "true" and "false" is in mathematics ill-defined without reference to a structure, because it's wishy-washy to say "we know what that means". $\endgroup$ – user21820 Jul 28 '16 at 4:36
  • $\begingroup$ It's contentious from a philosophical point of view, that's true. But most modern logicians consider it to be so, and even go further than me by always asserting that the meta-system is ZFC. I don't even assume the meta-system to be ZFC, but I insist that one makes clear what is used, because otherwise everything one says is wishy-washy, and often people who refuse to specify their meta-system shift goal-posts. I don't agree with people who claim that mathematics can be done outside a formal system; their 'mathematics' is nothing but philosophical opinion (even if not necessarily false). $\endgroup$ – user21820 Jul 28 '16 at 7:15
  • $\begingroup$ For a more precise calibration of possible meta-systems, see my (very) brief outline at math.stackexchange.com/a/1808558/21820. $\endgroup$ – user21820 Jul 28 '16 at 7:18
  • $\begingroup$ Well you said "we have a well-defined notion of truth in the natural numbers" and later "we 'know' what that means". Read ordinarily, this means that you are relying on the intuitive notion of natural numbers as a platonic collection, but the fact is that we do not actually have a way to pin down any such thing. Natural language is problematic (see math.stackexchange.com/a/1867336/21820), so we need some formalizable meta-system. Modern logicians use ZFC, in which ω is a model of PA given by the axiom of infinity, and then define arithmetical truth based on whether ω satisfies it. $\endgroup$ – user21820 Aug 1 '16 at 7:35
  • $\begingroup$ This notion is now implied by your updated answer. Note that it may well be the case that ZF is consistent and yet proves "not Con(ZF)", in which case ZF proves that ω does not satisfy "Con(ZF)", and yet if we move out one more level to a higher meta-system MS we can see that the natural numbers in MS do satisfy "Con(ZF)"! If it is difficult for you to grasp this, first consider the analogous situation of T = PA + not Con(PA), in which case you can check that T is consistent but proves "not Con(T)". $\endgroup$ – user21820 Aug 1 '16 at 7:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.