[yequalsx]

I don't think this is a correct view of what the Incompleteness Theorem says. The Incompleteness Theorem says that there are statements that are true in the standard model of the integers that are not provable in the first order Peano axioms. This does not mean that such statements are not provable. They just aren't provable in the first order axioms. The second order axioms are categorical and this means using the second order axioms any true statement can be proven.

The second order Peano axioms are a superset of the first order axioms. There is one small change in one of the axioms and that is the difference between the two systems.

[johnbender]

Since we're here maybe I can ask you for clarification/help!

When I said "true statements that can't be proven" it should have been qualified to a particular set of axioms. That is, I am claiming each set of axioms has it's own set of true but unprovable statements but none have an empty set of those statements. Correct or not?

Based what you say about the second order axioms it seems not, in which case I have some reading to do :)

[yequalsx]

That is not quite correct. Some axioms systems are categorical. This means that there is only one model up to isomorphism. For instance, take the collection of all statements about the Natural numbers (using the standard model of them under the first order Peano Axioms). This collection forms an axiom system for the Natural numbers and all true statements are provable in this system. Indeed, every true statement is an axiom.

The problem with doing this is that the collection of all true statements about the Natural numbers is not recursively enumerable. There is no effective (algorithmic) procedure for determining when a given statement is an axiom or not. This means that under this system we can't find all true statements, even theoretically, using a computer because of the non recursively enumerable nature of the axiom system.

The first order system provides a nice recursively enumerable set of axioms. But these axioms are not powerful enough to deduce all true statements about the Natural numbers. The second order axioms are powerful enough but are not recursively enumerable.

Recursively enumerable was the goal of Hilbert and others because they wanted to reduce mathematics to an algorithmic or mechanical process of verification. That isn't possible and this is the main reason why Roger Penrose (and me) think that computers will never be able to do mathematically what humans can do.

[johnbender]

I will try to translate my understanding:

> This collection forms an axiom system for the Natural numbers and all true statements are provable in this system. Indeed, every true statement is an axiom.

You have defined the axiom system as the set of all true statements about natural numbers so of course all true statements are provable! But crucially ...

> The problem with doing this is that the collection of all true statements about the Natural numbers is not recursively enumerable.

We want an extensional definition of a set of axioms. One way to get that is to enumerate it! This is important because ...

> Recursively enumerable was the goal of Hilbert and others because they wanted to reduce mathematics to an algorithmic or mechanical process of verification.

I can sympathize with this goal being that I use a proof assistant quite frequently.

Thank you for taking the time to respond!

[yequalsx]

You're welcome. I think your understanding is correct.

I will add one more thing for completeness sake. There are statements that are true of the natural numbers, the natural numbers that you and I think of when see this term, that can't be proven in the first order theory. This means that there is a non-standard model in which there is a non-standard integer that is a counterexample to the statement. The second order axioms are categorical so there is a proof of such a statement using the second order axioms. One may not be able to find such a proof but there is one.