[Math] How could a statement be true without proof

logic

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?

Best Answer

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$.

Related Question