FYI, I went ahead and checked this by hand. It turns out that the natural numbers stop at 67*10^11288764. Once you get there you have to go back the way you came.
A common way to support induction is via the monologue: "It's true for zero. Since it's true for zero it's true for one. Since it's true for one it's true for two. Continuing like this we can show that it's true for one hundred and for one hundred thousand and for every natural number." It's hard to imagine actually going through this proof for very large numbers -- this is Nelson's objection.
Actually, for moderately large numbers it's easy:
"Since it's true for numbers one higher than numbers it's true for, it's true for numbers two ...
A side note of possible interest. Under ZF, as well as ZFC, one can actually prove that induction works, via Tarski's fixed point theorem. Thus, if you think that induction seems a little weird as an axiom,, but set theory is cool, you still get to use induction.
What is arithmetic like if we reject induction?
A lot of things are trivially and obviously true on arbitrarily large but finite domains. People tend to assume that it will naturally transfer to countable domains. It doesn't look that different. But very often it breaks there.
On finite domains, everything is trivially decidable. On infinite domains, nearly everything is undecidable.
It doesn't feel like "does Riemann hypothesis have a proof in less than 1TB" and "does Riemann hypothesis have a proof" are entirely different categories o...
There are formal systems that can't construct exponentiation but still have weak versions of induction. in mainstream language, they have proof-theoretic ordinal ω^2. That exponentiation leads to proof theoretic ordinal ω^3 gives a precise way of saying that this is a natural place to stop. Ultrafinitists like Nelson appear to want something even more restrictive, but they refuse to talk in this language, so it's hard to tell. I don't blame them for wanting their own axiomatization, but their failure to even mention these systems makes me suspicious of the...
Trying to download this paper, the connection timed out.
I just found that amusing, given the subject matter.
Anyway. I don't see how you could possibly believe that axioms 1 through 4 are meaningful and axiom 5 is too infinite to be meaningful. If you deny infinity then you should deny that axioms 1 through 4 are together meaningful, because they only have infinite models. 5 just restricts that infinity to the smallest one, the intersection of all the models that match 1 through 4.
Try the new link.
I don't see how you could possibly believe that axioms 1 through 4 are meaningful and axiom 5 is too infinite to be meaningful.
Nelson does not believe that axiom 5 is any less meaningful than axioms 1-4. He believes that, granting axioms 1-4, axiom 5 is false.
If you deny infinity then you should deny that axioms 1 through 4 are together meaningful, because they only have infinite models.
Yes all models, in the sense of model theory, of axioms 1-4 are infinite. But why would you require a model of PA before regarding PA as meaningful? After all no one actually possesses such an infinite model, or any other infinite set.
Model theory is based on set theory. With a powerful enough set theory (including ZF) one can actually prove that arithmetic is consistent. Nelson believes that such strong forms of set theory are inconsistent.
5 just restricts that infinity to the smallest one, the intersection of all the models that match 1 through 4.
You're mistaken. There exist nonstandard models of Peano arithmetic.
If you have a single second-order axiom over all predicates, as in the wording "all properties" above, then the model is unique, and can be proven unique in second-order logic.
The model is unique within any given model of set theory, but isn't there more than one model of set theory? Or, to ask the same question in different terms, isn't there more than one second-order logic?
I don't know to what extent community norms around here allow me to make this request, but: can you guys start a new post on this topic, before my thoughtful and informative contribution turns into an area with 40 nice comments about Peano arithmetic and a thousand about Eliezer Yudkowsky?
Suggested title: "Remarks on a possibly arrogant comment made by Eliezer Yudkowsky."
You are using strong theories to reason about Peano arithmetic. If Nelson doubts the consistency of PA, he's not going to buy your argument.
As a quick heuristic, Edward Nelson has done some very impressive stuff. But a) his investigation into this question is by his own account motivated by pre-existing beliefs and b) he was 84 at the time he wrote this essay. The two of those don't give me a great amount of confidence in the likelyhood that this is correct.
As a more direct issue, saying that induction doesn't hold in general is akin to saying that I can have an infinite chain of dominoes such that each one will cause the next to fall if it falls over, and that the first has fallen, but all ...
it has another thing going against it: it is the only one that seems like a claim that could be either true or false.
For models for which axiom 3 (0 is not a successor of any number) is false, but the others, including induction, hold, look at modular arithmetic.
Induction is more similar to the fact that the bishop in chess can only move on half the squares -- this is a theorem about chess, not one of the rules.
Consider the set {n / 2 : n is a natural number } which follows all axioms except induction.
I didn't yet read the paper, but it occurs to me that the direction he seems to want to go in (based on your summary) would be better achieved not by directly weakening/removing induction, but by removing axiom 2.
This would "cut off" induction after a certain point while being more directly in the spirit of ultrafinitism. Also, it seems less "brain breaking" to me. (I don't reject axiom 2, but the notion of rejecting 2 seems less WTF to me then rejecting 5.)
The great Catholic mathematician Edward Nelson does not believe in completed infinity, and does not believe that arithmetic is likely to be consistent. These beliefs are partly motivated by his faith: he says arithmetic is a human invention, and compares believing (too strongly) in its consistency to idolatry. He also has many sound mathematical insights in this direction -- I'll summarize one of them here.
http://www.mediafire.com/file/z3detbt6int7a56/warn.pdf
Nelson's arguments flow from the idea that, contra Kronecker, numbers are man-made. He therefore does not expect inconsistencies to have consequences that play out in natural or divine processes. For instance, he does not expect you to be able to count the dollars in a stack of 100 dollars and arrive at 99 dollars. But it's been known for a long time that if one can prove any contradiction, then one can also prove that a stack of 100 dollars has no more than 99 dollars in it. The way he resolves this is interesting.
The Peano axioms for the natural numbers are these:
1. Zero is a number
2. The successor of any number is a number
3. Zero is not the successor of any number
4. Two different numbers have two different successors
5. If a given property holds for zero, and if it holds for the succesor of x whenever it holds for x, then it holds for all numbers.
Nelson rejects the fifth axiom, induction. It's the most complicated of the axioms, but it has another thing going against it: it is the only one that seems like a claim that could be either true or false. The first four axioms read like someone explaining the rules of a game, like how the pieces in chess move. Induction is more similar to the fact that the bishop in chess can only move on half the squares -- this is a theorem about chess, not one of the rules. Nelson believes that the fifth axiom needs to be, and cannot be, supported.
A common way to support induction is via the monologue: "It's true for zero. Since it's true for zero it's true for one. Since it's true for one it's true for two. Continuing like this we can show that it's true for one hundred and for one hundred thousand and for every natural number." It's hard to imagine actually going through this proof for very large numbers -- this is Nelson's objection.
What is arithmetic like if we reject induction? First, we may make a distinction between numbers we can actually count to (call them counting numbers) and numbers that we can't. Formally we define counting numbers as follows: 0 is a counting number, and if x is a counting number then so is its successor. We could use the induction axiom to establish that every number is a counting number, but without it we cannot.
A small example of a number so large we might not be able to count that high is the sum of two counting numbers. In fact without induction we cannot establish that x+y is a counting number from the facts that x and y are counting numbers. So we cut out a smaller class of numbers called additionable numbers: x is additionable if x + y is a counting number whenever y is a counting number. We can prove theorems about additionable numbers: for instance every additionable number is a counting number, the successor of an additionable number is additionable, and in fact the sum of two additionable numbers is an additionable number.
If we grant the induction axiom, these theorems lose their interest: every number is a counting number and an additionable number. Paraphrasing Nelson: the significance of these theorems is that addition is unproblematic even if we are skeptical of induction.
We can go further. It cannot be proved that the product of two additionable numbers is additionable. We therefore introduce the smaller class of multiplicable numbers. If whenever y is an additionable number x.y is also additionable, then we say that x is a multiplicable number. It can be proved that the sum and product of any two multiplicable numbers is multiplicable. Nelson closes the article I linked to:
The proof of the last theorem [that the product of two multiplicable numbers is multiplicable] uses the associativity of multiplication. The significance of all this is that addition and multiplication are unproblematic. We have defined a new notion, that of a multiplicable number, that is stronger than the notion of counting number, and proved that multiplicable numbers not only have successors that are multiplicable numbers, and hence counting numbers, but that the same is true for sums and products of multiplicable numbers. For any specific numeral SSS. . . 0 we can quickly prove that it is a multiplicable number.
But now we come to a halt. If we attempt to define “exponentiable number” in the same spirit, we are unable to prove that if x and y are exponentiable numbers then so is x ↑y. There is a radical difference between addition and multiplication on the one hand and exponentiation, superexponentiation [what is commonly denoted ^^ here], and so forth, on the other hand. The obstacle is that exponentiation is not associative; for example, (2↑2)↑3 = 4↑3 = 64 whereas 2↑(2↑3) = 2↑8 = 256. For any specific numeral SSS...0 we can indeed prove that it is an exponentiable number, but we cannot prove that the world of exponentiable numbers is closed under exponentiation. And superexponentiation leads us entirely away from the world of counting numbers.
The belief that exponentiation, superexponentiation, and so forth, applied to numerals yield numerals is just that -- a belief.
I've omitted his final sentence.