Yes, ZFC is quite enough to imply the existence of the first uncountable ordinal.
On the other hand, I don’t see what’s unbelievable about such a thing; it’s just (the order type of) the set of all countable ordinals, and I don’t see why it’s unbelievable that there is such a set. (That is, if you’re going to accept uncountable sets in the first place; and if you don’t want that, then you can criticise ZFC on far more basic grounds than anything about ordinals.)
Wikipedia seems to be saying that you can prove the existence of the first uncountable ordinal in pure ZF without the axiom of choice. Is that correct?
It is basically the main point of the definition of ordinals that for any property of ordinals , there is a first ordinal with that property. There are, however, foundational theories without uncountable ordinals , for instance Nik Weaver’s Mathematical Conceptualism.
Well, that depends on what you take to be decent. In the sibling, shinoteki has pointed (via Nik Weaver) to J_2. As Weaver argues, this is plenty strong enough to do ordinary mathematics: the mathematics that most mathematicians work on, and the mathematics that (almost always, perhaps absolutely always) is used in real-world applications. On the other hand, I find it difficult to work with, and prefer explicit reasoning about sets (but I’m a mathematician, so maybe I’m just used to that). That said, I think that properly limiting the impredicativity of set-based constructions should allow one to create a set-like theory that corresponds to something like J_2. (I’m being vague here because I don’t know better; it’s possible, I’d even say likely, that other mathematicians know better responses.)
I think the fact that considering the set of all ordinals leads to trouble should make you somewhat uncomfortable with the set of countable ordinals.
I’d go a step further and say you should be uncomfortable with the set of finite ordinals. But maybe these are the more basic criticisms you’re talking about.
Well, I trust well-written computer programs as much or more as I trust my own pen-and-paper stuff, but otherwise that’s pretty accurate. I’m uncomfortable with claims about the existence of 3^^^3, for instance.
“Uncomfortable” isn’t just empty skepticism, it’s shorthand for something precise: I think that by reasoning about very large numbers (say, large enough that it’s physically impossible to so reason without appealing to induction) it might be possible to give a valid proof of a false statement.
“Do my ten fingers exist” is a hard question for reasons that are mostly orthogonal to what I think you intend to ask about 10^100. Let’s start by stipulating that zero exists, and that if a number n exists then so does n+1. Then by induction, you can easily prove that 10^100, 3^^^3 and worse exist. But this whole discussion boils down to whether we should trust induction.
It turns out that without induction, we can prove in less than a page that 10^100 and even 2^^5 = 2^(60000 or so) exists in my sense. In terms of cute ideas involved, if not in raw complexity, this is a somewhat nontrivial result. See pages 4 and 5 of the Nelson article I linked to earlier. One cannot prove that 3^^^3 exists, at any rate not with a proof of length much less than 3^^^3.
What I’ve called “existing numbers,” Nelson calls “counting numbers.” The essence of the proof is to first show that addition and multiplication are unproblematic in a regime without induction, and then to construct 2^^5 with a relatively small number of multiplications. But exponentiation is problematic in this regime, for the somewhat surprising reason that it’s not associative. It does not lend itself to iteration as well as multiplication does.
Edward Nelson has now announced a proof that Peano Arithmetic (and even the weaker Robinson Arithmetic) is inconsistent. His proof is not yet fully written up, but there’s an outline (see the previous link). Terry Tao (whose judgement I trust, since this goes beyond my expertise) reports on John Baez’s blog that he believes that he knows where a flaw is.
Edit: Terry and Nelson are now debating live on the blog!
Edit again: I should have reported long ago that Nelson has conceded defeat.
What I’ve called “existing numbers,” Nelson calls “counting numbers.”
Another term to search for is “feasible numbers”. There are several theories of these, and Nelson’s theory of countable (addable, multipliable, etc) numbers is yet another.
Why stop at big numbers? Even the numbers you handle in everyday life might lead to a false statement, you are not logically omniscient and therefore wouldn’t necessarily know if they did. Why not be uncomfortable with everything?
Scenario 1: I have defined a sequence of numbers Xn, but these numbers are not computable. Nevertheless you give a proof that the limiting value of these numbers is 2, and then another, entirely different proof that the limiting value is 3. Therefore, 2 = 3. But since Xn is not computable, your proofs are necessarily non-constructive, so you haven’t given me a physical recipe for turning 2 quarters into 3 quarters. I would sooner say that you had proved something false, and re-examine some of your nonconstructive premises.
Scenario 2: You prove that 2 = 3 constructively. This means you have given me a recipe for turning 2 quarters into 3 quarters. I wouldn’t say you had proved something false but that you had discovered a new phenomenon, weird but true.
In both cases I would suspect my own mathematical ability, or even my sanity, before suspecting maths. Lcpwing those concerns away, I would observe that a certain set of statements had been proven not mutually consistent which in turn means they do not underpin our physics (granted this would be more surprising in one case than the other).
Something like Scenario 1 has already happened, with Russell’s paradox. People did not react by questioning their own sanity but by regarding Russell’s construction as “cheating”, and reconstituting the axioms so that Russell’s construction was forbidden.
We’re deep into insanity territory with Scenario 2, but people have speculated about such things here before.
I am fully aware of Russell’s paradox. I still think some sanity checks may be worthwhile, as the number of people who have thought they achieved scenario 1 but were in fact crackpots significantly exceeds one.
That there is a set of all countable ordinals is one thing; that it can be well-ordered is quite another. Not to mention that I doubt you can prove omega_1 exists in Z, which has quite a few uncountable sets.
That depends on what you mean by “well-ordered”. My philosophy of doing constructive mathematics (mathematics without excluded middle, and often with other restrictions) is that one should define terms as much as possible so that the usual theorems (including the theorems that the motivating examples are examples) become true, so long as the definitions are classically (that is using the usually accepted axioms) equivalent to the usual definitions.
As the motivating example of a well-ordered set is the set of natural numbers, we should use a definition that makes this an example. Such a definition may be found at a math wiki where I contribute my research (such as it is). Then (adopting a parallel definition of “ordinal”) it remains a theorem that every set of ordinals is well-ordered.
I had to look carefully in order to see that it doesn’t necessarily contradict itself even though I should have known this from Gödel, Escher, Bach.
On reflection this ordinal probably represents something real—a set of Gödel statements, which we’d regard as ‘true’ if we knew about them. Or rather, the fact that it seems meaningful to deny the existence of a general formula for producing these Gödel statements that will generate any given example if the process runs long enough. (To get an uncountable set of the right kind I might have to qualify this by saying something like “G-statements you could generate starting from a given system and a given method of Gödel numbering,” but I can’t tell how much of that we actually need.)
Yes, ZFC is quite enough to imply the existence of the first uncountable ordinal.
On the other hand, I don’t see what’s unbelievable about such a thing; it’s just (the order type of) the set of all countable ordinals, and I don’t see why it’s unbelievable that there is such a set. (That is, if you’re going to accept uncountable sets in the first place; and if you don’t want that, then you can criticise ZFC on far more basic grounds than anything about ordinals.)
Wikipedia seems to be saying that you can prove the existence of the first uncountable ordinal in pure ZF without the axiom of choice. Is that correct?
Yes, and in fact it can be proved in weaker axiom systems than that.
Okay, are there any decent foundational theories that won’t prove it?
It is basically the main point of the definition of ordinals that for any property of ordinals , there is a first ordinal with that property. There are, however, foundational theories without uncountable ordinals , for instance Nik Weaver’s Mathematical Conceptualism.
Well, that depends on what you take to be decent. In the sibling, shinoteki has pointed (via Nik Weaver) to J_2. As Weaver argues, this is plenty strong enough to do ordinary mathematics: the mathematics that most mathematicians work on, and the mathematics that (almost always, perhaps absolutely always) is used in real-world applications. On the other hand, I find it difficult to work with, and prefer explicit reasoning about sets (but I’m a mathematician, so maybe I’m just used to that). That said, I think that properly limiting the impredicativity of set-based constructions should allow one to create a set-like theory that corresponds to something like J_2. (I’m being vague here because I don’t know better; it’s possible, I’d even say likely, that other mathematicians know better responses.)
I think the fact that considering the set of all ordinals leads to trouble should make you somewhat uncomfortable with the set of countable ordinals.
I’d go a step further and say you should be uncomfortable with the set of finite ordinals. But maybe these are the more basic criticisms you’re talking about.
Why not go even further and declare yourself uncomfortable with any finite set of ordinals bigger then what you’ve personally written down?
Well, I trust well-written computer programs as much or more as I trust my own pen-and-paper stuff, but otherwise that’s pretty accurate. I’m uncomfortable with claims about the existence of 3^^^3, for instance.
“Uncomfortable” isn’t just empty skepticism, it’s shorthand for something precise: I think that by reasoning about very large numbers (say, large enough that it’s physically impossible to so reason without appealing to induction) it might be possible to give a valid proof of a false statement.
What about something like 10^100, i.e., something you could easily wright out in decimal but couldn’t count to?
“Do my ten fingers exist” is a hard question for reasons that are mostly orthogonal to what I think you intend to ask about 10^100. Let’s start by stipulating that zero exists, and that if a number n exists then so does n+1. Then by induction, you can easily prove that 10^100, 3^^^3 and worse exist. But this whole discussion boils down to whether we should trust induction.
It turns out that without induction, we can prove in less than a page that 10^100 and even 2^^5 = 2^(60000 or so) exists in my sense. In terms of cute ideas involved, if not in raw complexity, this is a somewhat nontrivial result. See pages 4 and 5 of the Nelson article I linked to earlier. One cannot prove that 3^^^3 exists, at any rate not with a proof of length much less than 3^^^3.
What I’ve called “existing numbers,” Nelson calls “counting numbers.” The essence of the proof is to first show that addition and multiplication are unproblematic in a regime without induction, and then to construct 2^^5 with a relatively small number of multiplications. But exponentiation is problematic in this regime, for the somewhat surprising reason that it’s not associative. It does not lend itself to iteration as well as multiplication does.
Edward Nelson has now announced a proof that Peano Arithmetic (and even the weaker Robinson Arithmetic) is inconsistent. His proof is not yet fully written up, but there’s an outline (see the previous link). Terry Tao (whose judgement I trust, since this goes beyond my expertise) reports on John Baez’s blog that he believes that he knows where a flaw is.
Edit: Terry and Nelson are now debating live on the blog!
Edit again: I should have reported long ago that Nelson has conceded defeat.
Another term to search for is “feasible numbers”. There are several theories of these, and Nelson’s theory of countable (addable, multipliable, etc) numbers is yet another.
Why stop at big numbers? Even the numbers you handle in everyday life might lead to a false statement, you are not logically omniscient and therefore wouldn’t necessarily know if they did. Why not be uncomfortable with everything?
Scenario 1: I have defined a sequence of numbers Xn, but these numbers are not computable. Nevertheless you give a proof that the limiting value of these numbers is 2, and then another, entirely different proof that the limiting value is 3. Therefore, 2 = 3. But since Xn is not computable, your proofs are necessarily non-constructive, so you haven’t given me a physical recipe for turning 2 quarters into 3 quarters. I would sooner say that you had proved something false, and re-examine some of your nonconstructive premises.
Scenario 2: You prove that 2 = 3 constructively. This means you have given me a recipe for turning 2 quarters into 3 quarters. I wouldn’t say you had proved something false but that you had discovered a new phenomenon, weird but true.
In both cases I would suspect my own mathematical ability, or even my sanity, before suspecting maths. Lcpwing those concerns away, I would observe that a certain set of statements had been proven not mutually consistent which in turn means they do not underpin our physics (granted this would be more surprising in one case than the other).
Something like Scenario 1 has already happened, with Russell’s paradox. People did not react by questioning their own sanity but by regarding Russell’s construction as “cheating”, and reconstituting the axioms so that Russell’s construction was forbidden.
We’re deep into insanity territory with Scenario 2, but people have speculated about such things here before.
I am fully aware of Russell’s paradox. I still think some sanity checks may be worthwhile, as the number of people who have thought they achieved scenario 1 but were in fact crackpots significantly exceeds one.
That there is a set of all countable ordinals is one thing; that it can be well-ordered is quite another. Not to mention that I doubt you can prove omega_1 exists in Z, which has quite a few uncountable sets.
You don’t need Z, third-order arithmetic is sufficient. Every set of ordinals is well-ordered by the usual ordering of ordinals.
Only if you accept excluded middle.
That depends on what you mean by “well-ordered”. My philosophy of doing constructive mathematics (mathematics without excluded middle, and often with other restrictions) is that one should define terms as much as possible so that the usual theorems (including the theorems that the motivating examples are examples) become true, so long as the definitions are classically (that is using the usually accepted axioms) equivalent to the usual definitions.
As the motivating example of a well-ordered set is the set of natural numbers, we should use a definition that makes this an example. Such a definition may be found at a math wiki where I contribute my research (such as it is). Then (adopting a parallel definition of “ordinal”) it remains a theorem that every set of ordinals is well-ordered.
I had to look carefully in order to see that it doesn’t necessarily contradict itself even though I should have known this from Gödel, Escher, Bach.
On reflection this ordinal probably represents something real—a set of Gödel statements, which we’d regard as ‘true’ if we knew about them. Or rather, the fact that it seems meaningful to deny the existence of a general formula for producing these Gödel statements that will generate any given example if the process runs long enough. (To get an uncountable set of the right kind I might have to qualify this by saying something like “G-statements you could generate starting from a given system and a given method of Gödel numbering,” but I can’t tell how much of that we actually need.)