= 27d567bc2d48d9f40e9ccc20ea370b15)
Exponentiation goes wrong first
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.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
= f037147d6e6c911a85753b9abdedda8d){kind=logo}
Comments (81)
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 higher than numbers it's true for." "....two....four...." "....four....eight..." "....eight....sixteen..."
Of course, if that's not fast enough you can try:
"Since it's true for gaps double the size of gaps it's true for, it's true for gaps quadruple the size it's true for" "...quadruple... sixteen times..." "...sixteen times...256 times..."
So, we've gone from N repetitions proving it for numbers up to N, to N repititions proving it for numbers up to 2^N, to N repititions proving it for numbers up to 2^(2^N). And we could continue.
Very nice. It's interesting to think about how hard it would be to prove the proposition "3^^^3 is a counting number" using your trick but not using induction.
You'd have to meta my trick (apply it to itself) at least once. Probably several times.
ponders
Let's go with 4s instead of 2s.
"Since it's true for gaps of one, and 1+1+1+1 equals four, it's true for gaps of four" "....4....16...." "....16....64..." So that's 4^N
"Since it's true for gaps 4 times larger than it's true for, it's true for gaps 444*4=256 times larger" "...256...4 294 967 296..." so that's 4^(4^N)
"Since it's true for gaps the fourth power of gaps it's true for, it's true for the 256th power of gaps it's true for" "...256th power....4 294 967 296th power..."
That's 4^(4^(4^N), or 4^^4 if N=4.
But I'm really struggling to get from that to 4^^^4
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.
Oh, good, I can stop torturing this guy then.
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.
It's always the fifth postulate...
I just realized Nelson numbers them differently, building in + and x at the start and giving two axioms explaining how they work. Induction is number 7 on his list. I hope this doesn't create confusion; I think it would create more if I changed the OP.
Huh, I didn't know Wikipedia has SSL. Thanks. (The day may come when looking up Unpopular_Person_or_Event, even on WP, ends me up on some Interpol watchlist.)
HTTPS Everywhere is a Firefox extension that automatically loads the HTTPS version of several websites, including Wikipedia and Google.
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 them. Here is a Math Overflow discussion of ultrafinitist foundations.
The Buss axiom mentioned on Math Overflow is very cool.
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.
Consider the set {n / 2 : n is a natural number } which follows all axioms except induction.
I think pointing out that modular arithmetic violates axiom 3 is akin to pointing out that in yahtzee, four-in-a-row beats three-of-a-kind. You're not really disputing the rules of poker. I'm speaking gut-wise, not mathematically here.
The point is that that axiom 3 and induction both exclude some models while allowing others. They are both part of defining the natural numbers.
I can't tell if you're arguing with me. One of the points of the post is that if you reject axiom 5 you are left with something that strongly resembles the natural numbers -- in fact I would agree with Nelson and say that they are what people thought of as natural numbers before induction was codified.
That doesn't work. If you reject induction, your remaining four axioms also describes the set {(n,m) such that n and m are natural numbers}, where (0, 0) is the zero element and the successor of (n, m) is (n, m + 1). That seems a bit different than the natural numbers, because I added, without violating the first four axioms, additional elements that are not the successor of any element.
I think you're correct. It is more accurate to say that the counting numbers strongly resemble the natural numbers, than it is to say that every element of every model of axioms 1-4 resembles a natural number.
Note that one can create "weird" models of axioms 1-5 as well.
There are a lot of systems that look almost like the natural numbers but clearly are not. I claim that even if you replace 5 with a succession of weaker axioms you can still get objects that are clearly not the natural numbers.
Consider for example the much weaker claim that every element in N is either 0 or the successor of some other element. It is still easy to see that one can have things that don't look at all like N. And one can keep adding additional theorems about what N needs to satisfy and still get objects that are pretty concrete and don't look like what we want the natural numbers to satisfy.
You can actually get some other very weird systems if you want to play around. For example, if you have some underlying set theory and replace induction with the well-ordering principle (which is equivalent modulo some minor technicalities) you can then look at some very interesting systems. For example, well-ordering is second-order, and applies to all sets, so this is in some sense stronger than some first order descriptions of PA where you replace induction with a separate induction axiom for each definable predicate. So one obvious system then is to restrict your well-ordering claim so that it quantifies not over all subsets but over all subsets of some form. Visualizing what such weakened versions of N look like can be quite hard.
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 of statements. The first must be true or false. We don't know, but the truth exists. Just ask a perfect Bayesian.
Drop the space requirement, and now you have to deal with some theorems being true but unprovable. There's this third emergent state between provably true and provably false. Everyone has their pet way of dealing with it, usually involving a lot of handwaving and then pretending nothing changed. For example - perfect Bayesians are no longer possible. There is just no self-consistent assignment of probabilities possible.
You can handwave some deeper notion of "truth" beyond computability without much clue how it would work like so many, or you can insist uncomputable things don't exist like intuitionists, or even just say huge numbers don't exist.
It all sucks one way or the other.
Rather just ask a tree searching algorithm running on a fast machine, in this case.
Really? Do you have an example? I'd be interested in seeing one.
(What do you mean here by "self-consistent"?)
Making this statement more precise is difficult. To make things easy I'm going to assume that probabilities live between 0 and 1 and that our general system of axioms is first order R with first order Q.
Now, our probability assignments are consistent iff they don't lead to a contradiction. So, assign our probabilities, then whatever you do, I note that by Robinson's theorems, I can describe PA using our axioms (this isn't precisely true but is close enough to be true for our purposes.) I then invoke the contradiction we have in PA. No matter what initial probability assignment you choose I can do this.
Note that this argument might not work if we just have first order reals as our axiomatic system because that's not sufficient to define PA in R, assuming that PA is consistent (to see this note that we have a decision procedure for first order reals and so if we could we'd have a way of deciding claims in PA.). I don't think there's any way to import contradictions in PA into first order R and I suspect this can't be done in general. (I suspect that I'm missing some technical details here so take this with a handful of salt.)
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.
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.
Try the new link.
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.
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.
You're mistaken. There exist nonstandard models of Peano arithmetic.
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 the dominoes won't eventually fall. That's an essentially physical representation of induction. If that's not valid then things are very weird.
The mathematics he is summarizing is utterly correct. Actually the small things I singled out I think are due to Godel and not to Nelson. But my summary is much more likely to have errors.
The dominoes analogy is revealing. If you lay out one million actual dominoes as usual and push over the first one I think it's very unlikely that the millionth one will fall.
Yes, the basic math is correct. That's not the point. Nelson's objection is to say that the axiom of induction is not supported in the same way as the others. That's not a math issue, that's an issue of what intuition and evidence tell us. In that sense, the evidence is overwhelming that induction is fine. Almost anyone who thinks for even a short period of time will be ok with it, unless, like Nelson, they have an external motive to be uncomfortable with it.
Incidentally, if one started with the assumption that PA has a contradiction, and asked me given that assumption who would I think is most likely to find the contradiction, Nelson would be very high up on the list simply given his work in foundations. The fact that he has a special motive to find such and still hasn't found it is additional evidence that the system is really consistent.
The only real upshot of this essay is that a contradiction in PA might not result in a contradiction in a sufficiently weakened form of PA that we can still do most forms of useful arithmetic.
Thinking about motives and contradictions, you might find this interesting:
http://video.ias.edu/voevodsky-80th
I hope you are referring to my essay and not Nelson's, which is a gem.
No, I was talking about Nelson's essay. There's nothing in that essay that wouldn't be covered in a basic course in foundations, aside from his ramblings on the nature of monotheistic faith and the meaning of "I AM WHO I AM" (capitalization in the original). The point that there's a distinction between how addition and multiplication behave and how exponentiation and higher analogs behave is not new either, although some sections of the essay might be worth explaining some concepts if one removes the theology.
I'm open to the possibility that PA might be inconsistent, although I assign this claim a very low probability. If one asked the question about some broader useful foundational system, such as ZF, I'd assign a much higher but still low probability.
If you think that either of these claims is wrong, I'd be happy to discuss making some form of wager over the likelyhood of an inconsistency being found within some fixed timespan (say 5 years or a decade?).
I've heard that Nelson has a standing bet with a colleague: he pays one dollar each year until an inconsistency is found in ZF, is paid one hundred dollars each year after an inconsistency is found.
I might take a more domino-oriented bet.
Do you mean one that focuses on PA? Do you care to suggest a specific bet? (For what matters, I'd estimate around a 10^-6 chance that PA is inconsistent.)
I'm teasing. I don't think your domino argument can be used to support induction.
Ok. So joking aside, do you want to make a bet on an inconsistency being found in PA in the next five years? 10 years?
I am fairly certain that no inconsistency will be found in the next 10 years.
Incidentally, I'm a little put off by your bringing up betting so early in the conversation. Isn't it clear that I'm interested in talking about this stuff? That should be enough, especially before you've even located a place where you and I disagree.
I'll mention that if PA is inconsistent, then a consistent prior probability distribution must have P(PA is inconsistent) = 1. (This might not be true if PA is consistent.) Developing a formalism for handling uncertainty about mathematical truths is a line of research in the same ballpark as developing mathematics without 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.)
Can you upload the paper somewhere (I suggest MediaFire)? This interests me, but I can't download the .pdf.
Done