How do we know what natural numbers are?

Do I get this right? Gödel's incompleteness theorem applies to first order logic as it applies to second order and any higher order logic. So there is essentially no way pinning down the natural numbers that we think of in everyday life?

• First order logic fails to be categorical, i.e. there are always non-standard models.
• Second order logic is categorical here, but does not allow us to prove all its true statements?
• Defining the numbers from set theory (e.g. ZFC) suffers from the same problem as all first order theories, i.e. there are non-standard models of ZFC which induce non-standard natural numbers?

How do we even know what natural numbera are, if we have no way to pin down a definition. What are the standard natural numbers? Or do we accept that second-order logic gives us this definition and we just cannot prove all there is?

LATER:

I think I can summarize my question as follows:

How do the mathematicians that write standard natural numbers have formal consensus on what they are talking about?

Solution 1:

How do the mathematicians that write standard natural numbers have formal consensus on what they are talking about?

Mathematicians work in a meta-system (which is usually ZFC unless otherwise stated). ZFC has a collection of natural numbers that is automagically provided for by the axiom of infinity. One can easily define over ZFC the language of arithmetic (as in any standard logic textbook), and also that the standard natural numbers are terms of the form "$0$" or "$1+\cdots+1$" where the number of "$1$"s is a natural number. To disambiguate these two 'kinds' of natural numbers, some authors call the standard natural numbers "standard numerals".

Do I get this right? Gödel's incompleteness theorem applies to first order logic as it applies to second order and any higher order logic. So there is essentially no way pinning down the natural numbers that we think of in everyday life?

Yes. See this post for the generalization and proof of the incompleteness theorems that applies to every conceivable formal system, even if it is totally different from first-order or higher-order logic.

First order logic fails to be categorical, i.e. there are always non-standard models.

Yes, so first-order PA does not pin down the natural numbers.

Second order logic is categorical here, but does not allow us to prove all its true statements?

Yes; there is no (computably) effective deductive system for second-order logic, so we cannot use second-order PA as a practical formal system. In the first place the second-order induction axiom is useless if you do not add some set-existence axioms. In any case, any effective formal system that describes the natural numbers will be incomplete, by the incompleteness theorem.

So although second-order PA is categorical (from the perspective of a strong enough meta-system), the categoricity does not solve the philosophical problem at all since such a meta-system is itself necessarily incomplete and hence the categoricity of second-order PA only ensures uniqueness of the natural numbers within each model of the meta-system, and cannot establish any kind of absolute categoricity.

Defining the numbers from set theory (e.g. ZFC) suffers from the same problem as all first order theories, i.e. there are non-standard models of ZFC which induce non-standard natural numbers?

Exactly; see previous point.

How do we even know what natural numbers are, if we have no way to pin down a definition.

We can only describe what we would like them to be like, and our description must be incomplete because we cannot convey any non-effective description. PA is one (incomplete) characterization. ACA is another. ZFC's axiom of infinity is a much stronger characterization. But there will never be an absolute categorical characterization.

You might hear a common attempt at defining natural numbers as those that can be obtained from 0 by adding 1 repeatedly. This is circular, because "repeatedly" cannot be defined without essentially knowing natural numbers. We are stuck; we must already know what are natural numbers before we can talk about iteration. This is why every useful foundational system for mathematics already has something inbuilt to provide such a collection. In the case of ZFC it is the axiom of infinity.

What are the standard natural numbers?

Good question. But this is highly philosophical, so I'll answer it later.

Or do we accept that second-order logic gives us this definition and we just cannot prove all there is?

No, second-order PA does not actually help us define natural numbers. The second-order induction axiom asserts "For every set of natural numbers, ...", but leaves undefined what "set" means. And it cannot possibly define "set" because it is circular as usual, and it does not help that the circularity is tied up with natural numbers...

Now for the philosophical part.

We have seen that mathematically we cannot uniquely define the natural numbers. Worse still, there does not seem to be ontological reason for believing in the existence of a perfect physical representation of any collection that satisfies PA under a suitable interpretation.

Even if we discard the arithmetical properties of natural numbers, there is not even a complete theory of finite strings, in the sense that TC (the theory of concatenation) is essentially incomplete, despite having just the concatenation operation and no arithmetic operations, so we cannot pin down even the finite strings!

So we do not even have hope of giving a description that uniquely identifies the collection of finite strings, which naturally precludes doing the same for natural numbers. This fact holds under very weak assumptions, such as those required to prove Godel's incompleteness theorems. If one rejects those... Well one reason to reject them is that there is no apparent physical model of PA...

As far as we know in modern physics, one cannot store finite strings in any physical medium with high fidelity beyond a certain length, for which I can safely give an upper bound of $2^{10000}$ bits. This is not only because the observable universe is finite, but also because a physical storage device with extremely large capacity (on the order of the size of the observable universe) will degrade faster than you can use it.

So description aside, we do not have any reason to even believe that finite strings have actual physical representation in the real world. This problem cannot be escaped by using conceptual strings, such as iterations of some particular process, because we have no basis to assume the existence of a process that can be iterated indefinitely, pretty much due to the finiteness of the observable universe, again.

Therefore we are stuck with the physical inability to even generate all finite strings, or to generate all natural numbers in a physical representation, even if we define them using circular natural-language definitions!

Now I am not saying that there is absolutely no real-world relevance of arithmetical facts.

Despite the fact that PA (Peano arithmetic) is based on the assumption of an infinite collection of natural numbers, which as explained above cannot have a perfect physical representation, PA still generates theorems that seem to be true at least at human scales. My favourite example is HTTPS, whose decryption process relies crucially on the correctness of Fermat's little theorem applied to natural numbers with length on the order of thousands of bits. So there is some truth in PA at human scales.

This may even suggest one way to escape the incompleteness theorems, because they only apply to deterministic formal systems that roughly speaking have certain unbounded closure properties (see this paper about self-verifying theories for sharp results about the incompleteness phenomenon). Perhaps the real world may even be governed by some kind of system that does is syntactically complete, since it has physical 'fuzziness' due to quantum mechanics or the spacetime limitations, but anyway such systems will not have arithmetic in full as we know it!

Solution 2:

Yes, as you phrased it in a comment:

So even the academic usage of the term standard natural number trusts in our intuitive understanding from preschool?

That's exactly how it is.

We believe, based on experience, that the intuitive concept we learned in preschool has meaning, and mathematics is an endeavor to explore that concept with more powerful tools than we had available in preschool -- not to construct it from scratch.

There are the Peano axioms either in their first- or second-order guise, of course. However, even if Gödel hadn't sunk the hope that they would tell us all truth about our intuitive natural numbers, they would still just be ink. The fundamental reason why we care about those axioms is that we believe they capture truth (only some of the truth, but truth nonetheless) about our intuitive conception of number.

Indeed it is hard to imagine how one could construct the natural numbers from scratch. To demand that, one would need to build on something else that we already know -- but it can't be turtles all the way down, and somewhere the buck has to stop. We can kick it around a bit and say, for example, that our fundamental concept is not numbers, but the finite strings of symbols that make up formal proofs -- but that's not really progress, because the natural numbers are implicit even there: If we can speak of strings, then we can speak of tally marks, and there's the natural numbers already!

Solution 3:

Any set-theoretic universe (or similar sort of object) will define a unique (up to isomorphism) set of natural numbers.

In that universe, that set of natural numbers is the standard one.

In some sense, natural numbers, manipulating strings, and logic are all synonymous subjects. So if you are working with some form of logic, one could consider the associated natural numbers to be the standard natural numbers.

(e.g. formal logic incorporates string manipulations, string manipulations let you compute arithmetic on numerals, and Godel's work shows how to encode logic in natural numbers)

I get the impression that this adequately describes the usage of the term by mathematicians who believe the notion has some real meaning.

However! We can conceive of logic as a mathematical construction rather than an attempt to capture the behavior of real-world mathematicians — that is, formal logic is something you develop within a mathematical universe.

In this setting, both of the above definitions of "standard natural numbers" are consistent; e.g. if you develop formal logic in ZFC, then the natural numbers associated to that development of logic are precisely the natural numbers of set theory.