1. I'm studying set theory, and finite is quite rigidly defined (albeit there's multiple definitions, which require the axiom of choice to prove identical.)
We can define natural number as an ordinal that's well ordered by its element relation and the reverse of the element relation (all those terms are defined). Or just as a finite ordinal, in the sense of not being equipollent to any strict subset. Or as the ordinals not containing any limit ordinals or being a limit ordinal.
2. This should probably be thought of as the machine doesn't halt, but in some models, we can "prove" that it halts and has any result. This is kind of like how you can rearrange the terms of some series to sum to any number. https://en.wikipedia.org/wiki/Riemann_series_theorem
(I wonder if there's a way to get the computability result from this result by some clever isomorphism.)
Even for those mathematicians who embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so-called non-standard models of both theories. A seeming paradox, non-standard models of the theory of hereditarily finite sets contain infinite sets - but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first-order predicate, nor even any recursive scheme of first-order predicates, can characterize the standard part of all such models. So, at least from the point of view of first-order logic, one can only hope to characterize finiteness approximately.
Can you have a model of ZF with natural numbers that aren't just 0,1,2,...? Or only PA?
It seemed obvious that defining the natural numbers in the way above results in only such numbers. You can give an intuitive argument that any natural number can be recursively generated from 0 by the successor operator. Is this wrong?
>A model M of (some) set theory is non-standard if it contains an ordinal α such that M |= “α is finite”, i.e. M |= “α is less than the first limit ordinal”, but looking from outside, the set of all ordinals β < α is infinite. The proof of the existence of non-standard models of set theory is basically the same as for PA.
It turns out this only pushes back the problem. You can write down second-order axioms for arithmetic which have a unique model, but in a model of a second-order theory predicates are interpreted as sets. So, you need to choose a version of set theory, to know what a model actually is. Suppose you choose ZFC (the usual axioms of set theory). Unfortunately this itself has infinitely many models!
You could try, but your internal view of "standardness" won't always coincide with the external view, just like with finiteness or countability. In fact, here's a proof that the attempt can never succeed:
Take any formal theory T that talks about natural numbers, like PA or ZF. We'll assume that T can be encoded as a computer program, printing out sentences about natural numbers in some simple language with arithmetic and quantifiers. We won't make any other assumptions about the theory's internal workings, it can use any axioms it likes.
Thanks to the miracle of Turing completeness, any facts about that computer program can also be encoded as sentences about natural numbers. So we can construct a sentence called Con(T) which says essentially "the program will never print 0=1", or equivalently "there's no natural number N encoding a proof in T that 0=1". That sentence encodes the idea that "T is a consistent theory" within T itself.
Godel's theorem says that T cannot prove Con(T). Therefore we can extend T with the negation of Con(T), and the resulting "self-hating" theory T+¬Con(T) will be as consistent as T itself. Like all consistent theories, that theory will have a model, which is also a model of the original theory T. In that model, Con(T) is axiomatically false, so the above-defined number N is asserted to exist. But if we assume that T was consistent to begin with, then there's actually no finite proof in T that 0=1, so N can't be a standard natural number. Therefore N is nonstandard, so T has a model with a nonstandard natural number. QED.
After considering the responses, I declare the analogue of Hofstadter's law: foundations of math are always weirder than you give them credit for, even after you've taken Hofstadter's law into account.
Most of the weirdness comes from Godel's and Lob's theorems, and they don't seem that strange to me anymore.
Here's a little tidbit that might make you more at peace with what's happening. Imagine that you didn't know anything about Godel's results. If you found some theory that proved its own consistency, would that be a reason to trust that theory more? Not at all! Inconsistent theories also happily prove their own consistency (because they prove all sentences). So it seems like Godel's theorems are thwarting a desire that was wrong-headed to begin with.
Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean? I used to think that I knew what I had always thought it to mean, but I no longer think so.
If we go down this road, Hamkins’ result takes on a different significance. It says that any subjectivity in the notion of ‘natural number’ may also infect what it means for a Turing machine to halt, and what function a Turing machine computes when it does halt.
Is beautiful. It seems like another proof for a leaky abstraction and incomepleteness.
We have to forget finite or admit that it has bounds on what we can explore with it, as it already defines our model.
Am I thinking of this correctly? In PA, you start with zero and a successor function, such that > is transitive and succ(a) > a. In nonstandard models, you start with a successor function and zero, but also at least one other weird entity not reachable by any number of applications of the successor function to zero. You can apply the successor function to that entity to get new numbers that are all greater than anything reachable from zero.
OR is it that there have to be infinite starting objects? OR should we think of it as having zero and both a successor function and a weirdSuccessor function (whose applications commute) such that > considers the number of weirdSuccessor applications before it looks at the number of successor applications?
It means that you have 0, and you have Big, and Big is axiomatically larger than all iterated successors of 0. And Big has iterated successors as well.
For example, consider the set embedded in the rationals as
23 comments
[ 0.23 ms ] story [ 53.8 ms ] thread"I used to think that I knew what I had always thought it to mean, but I no longer think so".
We can define natural number as an ordinal that's well ordered by its element relation and the reverse of the element relation (all those terms are defined). Or just as a finite ordinal, in the sense of not being equipollent to any strict subset. Or as the ordinals not containing any limit ordinals or being a limit ordinal.
2. This should probably be thought of as the machine doesn't halt, but in some models, we can "prove" that it halts and has any result. This is kind of like how you can rearrange the terms of some series to sum to any number. https://en.wikipedia.org/wiki/Riemann_series_theorem
(I wonder if there's a way to get the computability result from this result by some clever isomorphism.)
Edit: fixed definition and added another one.
It's a bit more subtle. Wikipedia puts it well:
Even for those mathematicians who embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so-called non-standard models of both theories. A seeming paradox, non-standard models of the theory of hereditarily finite sets contain infinite sets - but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first-order predicate, nor even any recursive scheme of first-order predicates, can characterize the standard part of all such models. So, at least from the point of view of first-order logic, one can only hope to characterize finiteness approximately.
https://en.wikipedia.org/wiki/Finite_set
It seemed obvious that defining the natural numbers in the way above results in only such numbers. You can give an intuitive argument that any natural number can be recursively generated from 0 by the successor operator. Is this wrong?
Edit: looks like http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf says you can get such a model.
>A model M of (some) set theory is non-standard if it contains an ordinal α such that M |= “α is finite”, i.e. M |= “α is less than the first limit ordinal”, but looking from outside, the set of all ordinals β < α is infinite. The proof of the existence of non-standard models of set theory is basically the same as for PA.
Another fun fact is that ZF has a countable model, even though ZF proves that uncountable sets exist. https://en.wikipedia.org/wiki/Skolem%27s_paradox
I explained this in a bit more detail here:
https://johncarlosbaez.wordpress.com/2016/04/02/computing-th...
Take any formal theory T that talks about natural numbers, like PA or ZF. We'll assume that T can be encoded as a computer program, printing out sentences about natural numbers in some simple language with arithmetic and quantifiers. We won't make any other assumptions about the theory's internal workings, it can use any axioms it likes.
Thanks to the miracle of Turing completeness, any facts about that computer program can also be encoded as sentences about natural numbers. So we can construct a sentence called Con(T) which says essentially "the program will never print 0=1", or equivalently "there's no natural number N encoding a proof in T that 0=1". That sentence encodes the idea that "T is a consistent theory" within T itself.
Godel's theorem says that T cannot prove Con(T). Therefore we can extend T with the negation of Con(T), and the resulting "self-hating" theory T+¬Con(T) will be as consistent as T itself. Like all consistent theories, that theory will have a model, which is also a model of the original theory T. In that model, Con(T) is axiomatically false, so the above-defined number N is asserted to exist. But if we assume that T was consistent to begin with, then there's actually no finite proof in T that 0=1, so N can't be a standard natural number. Therefore N is nonstandard, so T has a model with a nonstandard natural number. QED.
Set theory have infinite number of models, each model having different kind of "finite" ordinals.
Here's a little tidbit that might make you more at peace with what's happening. Imagine that you didn't know anything about Godel's results. If you found some theory that proved its own consistency, would that be a reason to trust that theory more? Not at all! Inconsistent theories also happily prove their own consistency (because they prove all sentences). So it seems like Godel's theorems are thwarting a desire that was wrong-headed to begin with.
Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean? I used to think that I knew what I had always thought it to mean, but I no longer think so.
If we go down this road, Hamkins’ result takes on a different significance. It says that any subjectivity in the notion of ‘natural number’ may also infect what it means for a Turing machine to halt, and what function a Turing machine computes when it does halt.
Is beautiful. It seems like another proof for a leaky abstraction and incomepleteness.
We have to forget finite or admit that it has bounds on what we can explore with it, as it already defines our model.
OR is it that there have to be infinite starting objects? OR should we think of it as having zero and both a successor function and a weirdSuccessor function (whose applications commute) such that > considers the number of weirdSuccessor applications before it looks at the number of successor applications?
For example, consider the set embedded in the rationals as