[Maxatar]

Correct, it's impossible to specifically and formally define the natural numbers so that addition and multiplication work. Any definition of the natural numbers will also define things that look very similar to natural numbers but are not actually natural numbers.

[sam_ezeh]

>Any definition of the natural numbers will also define things that look very similar to natural numbers but are not actually natural numbers

This isn't correct. This is only true for first-order theories of the natural numbers using the axiom schema of induction. Second-order Peano arithmetic with the full axiom of induction has the natural numbers as its only model. This property is called "categoricity" and you can find the proof here [1] if you're interested

[1]: https://builds.openlogicproject.org/content/second-order-log...

[Maxatar]

This isn't correct. While it's true that in second order logic the natural numbers admit categoricity, second order logic lacks axiomatic semantics. So yes, there is a single set which can be called the natural numbers in second order logic (namely the intersection of all sets that satisfy Peano's axioms), but this set has no interpretation.

You can adopt Henkin semantics to give the naturals an interpretation, which is still second order logic, but then you're back to lacking a categorical model of the naturals.

[sam_ezeh]

> So yes, there is a single set which can be called the natural numbers in second order logic (namely the intersection of all sets that satisfy Peano's axioms), but this set has no interpretation.

Can you explain what you mean here? Full semantics for second-order logic has a unique interpretation i.e. the standard natural numbers

[Maxatar]

Interpretation under full second‑order logic is not intrinsic to the logic itself but is always supplied by a richer meta‑theory, usually set theory/ZF. The sentence "All subsets of N" has no standalone meaning in second-order logic, it must be defined inside of the meta-theory, which in turn relies on its own meta‑theory, and so on ad infinitum.

Thus, although full second order Peano axioms are categorical, second order logic by itself never delivers a self‑contained model of the natural numbers. Any actual interpretation of the natural numbers in second order logic requires an infinite regress of background theories.

[john-h-k]

Can you elaborate on this?

My understanding is you can specifically and formally define the natural numbers with addition and multiplication, although multiplication means the language is no longer decidable.

You can define natural numbers with just addition ( Presburger arithmetic ) and it’s decidable.

Im not sure how undecidable <=> “will define things that are similar to natural numbers but are not” but maybe I am missing something

[Maxatar]

Yeah for sure.

If a sentence S is undecidable from your axioms for the natural numbers then there are two models A and B satisfying those axioms where A satisfies S and B satisfies not S. So which one is the standard natural numbers, is it A or B?

Either A or B will be an example of something that satisfies your definition of natural numbers and yet is not the natural numbers.

[pja]

> Correct, it's impossible to specifically and formally define the natural numbers so that addition and multiplication work. Any definition of the natural numbers will also define things that look very similar to natural numbers but are not actually natural numbers.

Are such objects not inevitably isomorphic to the natural numbers?

Can you give an example of a formal definition that leads to something that obviously isn't the same as the naturals?

[btilly]

The Peano Axioms lead to both the standard model of arithmetic (the integers that we want), and nonstandard models. See https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet....

In that article you'll see references to "first order logic" and "second order logic". First order logic captures any possible finite chain of reasoning. Second order logic allows us to take logical steps that would require a potentially infinite amount of reasoning to do. Gödel's famous theorems were about the limitations of first order logic. While second order logic has no such limitations, it is also not something that humans can actually do. (We can reason about second order logic though.)

Anyways a nonstandard model of arithmetic can have all sorts of bizarre things. Such as a proof that Peano Axioms lead to a contradiction. While it might seem that this leads to a contradiction in the Peano Axioms, it doesn't because the "proof" is (from our point of view) infinitely long, and so not really a proof at all! (This is also why logicians have to draw a very careful distinction between "these axioms prove" and "these axioms prove that they prove"...)

[pja]

All of these models appear to contain infinitely sized objects that are explicitly named / manipulable within the model, which makes them extensions of the Peano numbers though, or else they add other, extra axioms to the Peano model.

If you (for example) extend Peano numbers with extra axioms that state things like “hey, here are some hyperreals” or “this Goedel sentence is explicitly defined to be true (or false)” it’s unsurprising that you can end up in some weird places.

[btilly]

We are able to recognize that they are nonstandard because they contain numbers that we recognize are infinite. But there is absolutely no statement that can be made from within the model from which it could be discovered that those numbers are infinite.

Furthermore, it is possible to construct nonstandard models such that every statement that is true in our model, remains true in that one, and ditto for every statement that is false. They really look identical to our model, except that we know from construction that they aren't. This fact is what makes the transfer principle work in nonstandard analysis, and the ultrapower construction shows how to do it.

(My snark about NSA is that we shouldn't need the axiom of choice to find the derivative of x^2. But I do find it an interesting approach to know about.)

[Maxatar]

No additional axioms are needed for the existence of these models. On the contrary additional axioms are needed in order to eliminate them, and even still no amount of axioms can eliminate all of these extensions without introducing an inconsistency.

[stouset]

Do you have a link to where I could learn more about this?

[gerdesj]

You might start here: https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

That's the GEB I mentioned above.

[pinkmuffinere]

I know this is a great book, it’s been on my to-read list for about 5 years. But I never get to it. Is there not another (shorter) discussion I could read on this? Even an academic paper would be acceptable.

[ForOldHack]

You could read Kurt Godels paper,but it's literally undecyperable. The book is one on the best reads ever. It will also teach you how to think in very very formal ways. It made Calculus half the class it was, and I breezed through finite math.

Propositional Calulus will teach you to think in symbols you cannot even fathom. This alone is worth every minute reading the book.

Every few years I reread it, and get a new sense of solving problems. The book can be divided into parts... But the whole...

[Maxatar]

There's no shortage of blog posts on the topic, but here is one that is fairly rigorous but doesn't assume too much background knowledge:

https://risingentropy.com/a-result-on-the-incompleteness-of-...

[gerdesj]

As I said above, I'm not an expert. However, I read GEB on a whim when bored at school and I think it still informs my thinking 35 years later.

Move GEB up the reading list right now! The edition I initially read was hard bound and was quite worn. I bought and read it again about 20 years ago and found more treasures.

It is a proper nerd grade treatise for non experts who are interested in maths, music and art. Really: maths, music and art from a mostly mathematical perspective. Hofstadter's writing style is very easy going and he is a master of clarity without complexity.

I don't think you need any more Maths than you would get up to age 18 or so at school to understand the entire book and probably less. Even if you gloss the formal Maths the book still works.

[overboard2]

What do you mean by "not actually"?

Edit: do you mean literally impossible?

[Maxatar]

I mean it's logically impossible to formally and specifically define the natural numbers without introducing a logical inconsistency. The best you can do is define a set that has all the properties of natural numbers but will also define things that aren't natural numbers as well.

As an analogy you could imagine trying to define the set of all animals with a bunch of rules... "1. Animals have DNA, 2. Animals ingest organic matter. 3. Animals have a nervous system. 4. ... etc..."

And this is true of all animals, but it will also be true of things that aren't animals as well, like slime molds which are not quite animals but very similar to them.

Okay so you keep adding more rules to narrow down your definition and stamp out slime molds, but you find some other thing satisfy that definition...

Now for animals maybe you can eventually have some very complex rule set that defines animals exactly and rules out all non-animals, but the principle is that this is not possible for natural numbers.

We can have rules like "0" is a natural number. For every natural number N there is a successor to it N + 1. If N + 1 = M + 1 then N = M. There is no natural number Q such that Q + 1 = 0.

Okay this is a good starting point... but just like with animals there are numbers that satisfy all of these rules but aren't natural numbers. You can keep adding more and more rules to try to stamp these numbers out, but no matter how hard, even if you add infinitely many rules, there will always be infinitely many numbers that satisfy your rules but aren't natural numbers.

In particular what you really want to say is that a natural number is finite, but no matter how hard you try there is no formal way to actually capture the concept of what it means to be finite in general so you end up with these mutant numbers that satisfy all of your rules but have infinitely many digits, and these are called non-standard natural numbers.

The reason non-standard natural numbers are a problem is because you might have a statement like "Every even integer greater than 2 can be written as the sum of two primes." and this statement might be true of the actual natural numbers but there might exist some freak mutant non-standard natural number for which it's not true. Unless your rules are able to stamp out these mutant non-standard natural numbers, then it is not possible to prove this statement, the statement becomes undecidable with respect to your rules. The only statements you can prove with respect to your rules are statements that are true of the real natural numbers as well as true of all the mutant natural numbers that your rules have not been able to stamp out.

So it's in this sense that I mean that it's not possible to specifically define the natural numbers. Any definition you come up with will also apply to mutant numbers, and these mutant numbers can get in the way of you proving things that are in principle true about the actual natural numbers.

[gerdesj]

It seems you know what you are on about! Thank you for a cracking comment.

I've always had this feeling that the foundations (integers etc) are a bit dodgy in formal Maths but just as with say Civil Engineering, your world hasn't fallen apart for at least some days and it works. Famously, in Physics involving quantum: "Shut up and calculate".

Thankfully, in the real world I just have to make web pages, file shares and glittery unicorns available to the computers belonging to paying customers. Securely ...

The foundational aspect equivalent of integers in IT might be DNS. Fuck around with either and you come unstuck rather quickly without realising exactly why until you get suitably rigorous ...

I'm also a networking bod (with some jolly expensive test gear) but that might be compared to pencils and paper for Maths 8)

[LudwigNagasena]

Second-order arithmetic formalizes both natural and real numbers. Though it has a host of issues with inference.