Hacker News new | ask | show | jobs
by hfhdjdks 902 days ago
>Since this theorem is true for the standard model of the natural numbers but not provable

I've always found the provable vs true comparison confusing. How can we say the statement is true under the standard model if we cannot prove it? I understand that it could be true, but how do we know it? If it's proven with second order arithmetic, then this implies it is true under the standard model too?

Or are there statements true independently of the axiomatic system you use to prove them? (Apologies if this is too off-topic)

1 comments

The provability of a statement depends upon which system you are in. For instance, within PA one can’t prove that PA is consistent but within ZFC one can prove that PA is consistent. We can say of a statement: Statement A can’t be proven in a given axiomatic system but it can be proven in a different system.

Let’s assume the Natural Numbers are consistent system. Let’s collect all true statements in this system and use that collection as our axioms. It is now the case that every true statement about the Natural Numbers can be proven in this system. The problem with this system of axioms is that there is no effective procedure for determining if a statement is an axiom or not. It is not a useful system.

Every true statement can be proven in some system. The incompleteness theorems show that we can’t have a relatively simple set of axioms that are powerful enough to prove all true statements about the Natural Numbers. Every simple enough set of axioms for the Natural Numbers will have nonstandard implementations (models) in which some statements are false in these nonstandard models but true in the Natural Numbers.