You know, the concept of the first uncountable ordinal is actually one of the strongest reasons I’ve ever heard to disbelieve in set theory. ZFC, or rather NBG, does imply the existence of a first uncountable ordinal, right, or am I mistaken?
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.)
The existence of the real number line is one thing. The existence of an uncountable ordinal is another. When you consider the hierarchies of uncomputable ordinals to their various Turing degrees that are numbered among the countable ordinals, and that which countable ordinals you can constructively well-order strongly corresponds to the strength of your proof theory and which Turing machines you believe to halt, and when you combine this with the Burali-Forti paradox saying that the predicate “well-ordered” cannot be self-applicable, even though any given collection of well-orderings can be well-ordered...
...I just have trouble believing that there’s actually any such thing as an uncountable ordinal out there, because it implies an absolute well-ordering of all the countable well-orderings; it seems to have a superlogical character to it.
I wonder how much of this is just a function of what math you’ve ended up working with a lot.
Humans have really bad intuition about math. This shouldn’t be that surprising. We evolved in a context where selection pressure was on finding mates and not getting eaten by large cats.
Speaking from personal experience as a mathematician (ok a grad student but close enough for this purpose) it isn’t that uncommon for when I encounter a new construction that has some counterintuitive property to look at it and go “huh? Really?” and not feel like it works. But after working with the object for a while it becomes more concrete and more reasonable. This is because I’ve internalized the experience and changed my intuition accordingly.
There are a lot of very basic facts that don’t involve infinite sets that are just incredibly weird. One of my favorite examples are non-transitive dice. We define a “die” to be a finite list of real numbers. To role a dice we pick a die a random number from the list, giving each option equal probability. This is a pretty good representation of what we mean by a dice in an intuitive set. Now, we say a die A beats a die B if more than half the time die A rolls a higher number than die B. Theorem: There exist three 6-sided dice A, B and C with positive integer sides such that A beats B, B beats C and C beats A. Constructing a set of these is a fun exercise. If this claim seems reasonable to you at first hearing then you either have a really good intuition for probability or you have terrible hindsight bias. This is an extremely finite, weird statement.
And I can give even weirder examples including an even more counterintuitive analog involving coin flips.
I just don’t see “my intuition isn’t happy with this result” to be a good argument against a theorem. All the axioms of ZF seem reasonable and I can get the existence of uncomputable ordinals from much weaker systems. So if there’s a non-intuitive aspect here, that’s a reason to update my intuition not to reduce my confidence in set theory.
Oooh. That page is excellent. I have not seen dice with the order reversing property before. Even being a fan of non-transitive dice and having seen this sort of thing before that was highly unexpected. I’m going to have to sit down and look hard about what is going on there.
The axiom of foundation seems pretty ad hoc to me. It’s there to patch Russell’s paradox. I see no reason not to expect further paradoxes.
We arrived at the axiom of infinity from a finite amount of experience, which seems troubling to me.
This is an extremely finite, weird statement.
It’s a very cool construction, but it’s a finite one that we can verify by hand or with computer assistance. Of the things that ZF claims exist, some of them have this “verifiability” property and some don’t. At the very least don’t you agree that’s a crucial distinction, and that we ought to be strictly less skeptical of constructible, computable, verifiable things than of things like uncountable ordinals?
Also, there’s another respect in which foundation doesn’t impact Russell issues at all. Whether one accepts foundation, anti-foundation or no mention of foundation, one can still get very Russellish issues if one is allowed to form the set A of all well-founded sets. Simply ask if A is well-founded or not. This should demonstrate that morally speaking, foundation concerns are only marginally connected to Russell concerns.
To make the obvious comment, this is all unnecessary as Russell’s paradox goes through from unrestricted comprehension (or set of all sets + ordinary restricted comprehension) without any talking about any sort of well-foundedness...
But that’s a neat one, I hadn’t thought of that one before. However I have to wonder if it works without DC.
Edit: I feel silly, this doesn’t use dependent choice at all. OK, so the answer to that is “yes”. However it does require enough structure to be able to talk about infinite sequences, unless there’s some other way of defining well-foundedness.
There are (at least) three ways to define well-foundedness, roughly:
one which requires impredicative (second-order) reasoning;
one which requires nonconstructive reasoning (excluded middle);
one which requires infinitary reasoning (with dependent choice, and also excluded middle actually).
They may all be found at the nLab article on the subject; this article promotes the first definition (since we use constructive mathematics there much more often than predicative mathematics), but I think that the middle one (Lemma 2 in the article) is actually the most common. However, the last definition (which you are using, Lemma 1 in the article) is usually the easiest for paradoxes (and DC and EM aren’t needed for the paradoxes either, since they’re used only in proofs that go the other way).
One thing bothering me—is there any way to define a well-founded set without using infinitary reasoning? It’s easy enough to say that all sets are well-founded without it, by just stating that ∈ is well-founded—I mean, that’s what the standard axiom of foundation does, though with the classical definition—but in contexts where that doesn’t hold, you need to be able to distinguish a well-founded set from an ill-founded one. Obvious thing to do would be to take the transitive closure of the set and ask if ∈ is well-founded on that, but what bugs me is that constructing the transitive closure requires infinitary reasoning as well. Is there something I’m missing here?
I know one way; it cannot be stated in ZFC↺ (ZFC without foundation), but it can be stated in MK↺ (the Morse–Kelley class theory version): a set is well-founded iff it belongs to every transitive class of sets (that is every class K such that x ∈ K whenever x ⊆ K); it is immediate that we may prove properties of these sets by induction on membership, and a set is well-founded if all of its elements are, so this is a correct definition. However, it requires quantification over all classes (not just sets) to state.
Sure foundation is by far the most ad-hoc axiom. But it is also one of the one’s that is easiest to see doesn’t generally matter. For pretty much any natural theorem if a proof uses foundation then there’s a version of the theorem without it. Since not-well founded sets don’t fit most of out intuition for sets as things like boxes that’s not an issue. None of the serious apparent paradoxical properties go away if you remove foundation.
It’s a very cool construction, but it’s a finite one that we can verify by hand or with computer assistance. Of the things that ZF claims exist, some of them have this “verifiability” property and some don’t. At the very least don’t you agree that’s a crucial distinction, and that we ought to be strictly less skeptical of constructible, computable, verifiable things than of things like uncountable ordinals?
Yes, certainly but by how much? If our intuition can go this drastically wrong on small finite objects why should I trust my intuition on objects that are even further removed from my everyday experience? I mean it isn’t like I need 30 or 40 sided dice to pull this off. In fact you can actually make much smaller than 6 sided dice that are non-transitive. Working out the minimum number of sides (assuming that each die in the set doesn’t need to have the same number of sides) is a nice exercise that helps one understand what is going on.
You’re right, I see that it’s the “restriction” of restricted comprehension that actually does the work in avoiding Russell’s paradox, not foundation. Nevertheless, the story is the same: we had an ambitious set-theoretic foundation for mathematics, Russell found a simple and fatal flaw in it, and we should not simply trust that there will be no further problems after patching this one.
If our intuition can go this drastically wrong on small finite objects why should I trust my intuition on objects that are even further removed from my everyday experience?
This is hardly an argument for accepting that infinite sets exist! There may be a counterintuitive contradiction that one can arrive at from ZF, just as Russell’s paradox is a counterintuitive contradiction arrived at from 19th century foundations, and just as all kinds of counterintuitive but non-contradictory behavior is possible in the finite, constructive realm.
I am proposing that we remove the axiom of infinity from foundations, not that we go further and add its negation. (Though I see that there has been work done on the negation of the foundation axiom! And dubious speculation about its role in consciousness.)
Also one other remark: Foundation isn’t there to repair any Russel issues. You can get as a theorem that Russell’s set doesn’t exist using the other axioms because you obtain a contradiction. Foundation is more that some people have an intuition that sets shouldn’t be able to contain themselves and that together with not wanting sets that smell like Russell’s set caused it to be thrown in.
I’m really tempted to be obnoxious and present an axiomatic system with a primitive called a “paradox” and then just point out what happens one adds the axiom that there are no paradoxes. This is likely a sign that I should go to bed so I can TA in the morning.
I would be interested in knowing if there is any second-order system which is strong enough to talk about continuity, but not to prove the existence of a first uncountable ordinal.
I can do better. I can give you a complete, decidable, axiomatized system that does that: first order real arithmetic. However, in this system you can’t talk about integers in any useful way.
We can do better than that: first order real arithmetic + PA + a set of axioms embedding the PA integers into R in the obvious way. This is a second order system where I can’t talk about uncountable ordinals. However, this system doesn’t let us talk about sets.
Note that in both these cases we’ve done this by minimizing how much we can talk about sets. Is there some easy way to do this where we can talk about set a reasonable amount?
I’m not sure. Answering that may be difficult (I don’t think the question is necessarily well-defined.) However, I suspect that the following meets one’s intuition as an affirmative answer: Take ZFC without regularity, replacement or infinity, choice, power set or foundation. Then add as an axiom that there exists a set R that has the structure of a totally ordered field with the least-upper bound property.
This structure allows me to talk about most things I want to do with the reals while probably not being able to prove nice claims about Hartogs numbers which should make proving the existence of uncountable ordinals tough. It would not surprise me too much if one could get away with this system with the axiom of the power set thrown also. But it also wouldn’t surprise me either if one can find sneaky ways to get info about ordinals.
Note that none of these systems are at all natural in any intuitive sense. With the exception of first-order reals they are clear attempts to deliberately lobotomize systems. (ETA: Even first order reals is a system which we care about more for logic and model theoretic considerations than any concrete natural appreciation of the system.) Without having your goal in advance or some similar goal I don’t think anyone would ever think about these systems unless they were a near immortal who was passing the time by examining lots of different axiomatic systems.
While thinking about this I realized that I don’t know an even more basic question: Can one deal with what Eliezer wants by taking out the axiom schema of replacement, choice, and foundation? The answer to this is not obvious to me, and in some sense this is a more natural system. If this is the case then one would have a robust system in which most of modern mathematics could be done but you wouldn’t have your solution. However, I suspect that this system is enough to prove the existence of the least uncountable ordinal.
Note that without replacement, you can’t construct the von Neumann ordinal omega*2, or any higher ones, so certainly not omega_1. Of course, this doesn’t prevent uncountable well-ordered sets (obviously these follow from choice, though I guess you’re taking that out as well), but you need replacement to show that every well-ordered set is isomorphic to a von Neumann ordinal.
So I don’t think that this should prevent the construction of an order of type omega_1, even if it can’t be realized as a von Neumann ordinal. Of course losing canonical representatives means you have to talk about equivalence classes, but if all we want to do is talk about omega_1, it suffices to consider well-orderings of subsets of N, so that the equivalence classes in question will in fact be sets. Maybe there’s some other technical obstacle I’m missing here (like it somehow wouldn’t be the first uncountable ordinal despite being the right order?) -- this isn’t really my area and I haven’t bothered to work through it, I can try that later—but I wouldn’t expect one.
Maybe there’s some other technical obstacle I’m missing here
There’s not. The Hartog’s number construction gives us the set H(N) of all isomorphism classes of well-orders on subsets of any fixed countably infinite set, and we can prove that H(N) is uncountable and every proper initial segment of H(N) is countable, using power set and separation (but only bounded separation) but not replacement. I verified this just now by looking at Wikipedia’s article on Hartog’s number and checking through the proof myself.
The next step (step 4 in Wikipedia, ETA: which can be saved for the end, although WP did not do so) is to replace the elements of H(N) with von Neumann ordinals, but this is really beside the point. You already have a representation of the least uncountable ordinal, and this step is just making it canonical in a certain way.
It’s not clear to me that ZFC without regularity, replacement, infinity, choice, power set or foundation with a totally ordered field with the LUB property does allow you to talk about most things you want to do with the reals : without replacement or powerset you can’t prove that cartesian products exist, so there doesn’t seem to be any way of talking about the plane or higher-dimensional spaces as sets. If you add powerset back in you can carry out the Hartogs number construction to get a least uncountable ordinal
Hmm, that’s a good point. Lack of cartesian products is annoying. We don’t however need the full power set axiom to get them. We can simply have an axiom that states that cartesian products exist. Or even weaker do the following (ad hoc axioms) with a new property of being Cartesian: 1. The cartesian product of any two Cartesian sets exist. 2. Any subset of R is Cartesian. 3. The cartesian product of two Cartesian sets is Cartesian. 4. If A and B are Cartesian then A union B, A intersect B, and A\B are all Cartesian. That should be enough and is a lot weaker than general power set I think.
van den Dries, “Tame topology and o-minimal structures,” Cambridge U Press 1998
develops a lot of 20th century geometry in a first order theory of real numbers. You can do enough differential geometry in this setting to do e.g. general relativity.
What does “existence” have to do with anything though? Even if the real world, or morality don’t “exist” in some sense, you still go on making decisions, reason about their properties. (There appear to be two useful senses of “doesn’t exist”: the state of some system is such that some property isn’t present; or a description of a system is contradictory. These don’t obviously apply here.)
The trouble is, human value might turn out to talk about complicated mathematical objects, just like mathematicians can think about (simpler kinds of) them, and it’s not clear where to draw the line, at least to me while I still have too little understanding of what humane value is.
Reasoning about math objects, as opposed to just patterns of the world, seems to be analogous to reasoning about the world, as opposed to just patterns in observation. I don’t believe there has to be a boundary around physics, a kind of “physical solipsism”. And limitations of representation don’t seem to solve the problem, as formal systems might be unable to capture particular classes of models of interest, but they can be seen as intended to elucidate properties of those models.
(There appear to be two useful senses of “doesn’t exist”: the state of some system is such that some property isn’t present; or a description of a system is contradictory. These don’t obviously apply here.)
In set theory there’s a formal symbol that’s read “there exists”, and a pair of formal symbols that are read “there doesn’t exist”. Do you think these symbols should be understood in either of your two useful senses?
It is possible to read the existential quantifier as “for some” instead of “there exists … such that”. I often do this myself, just for euphony (and to match the dual quantifier, read “for all”, or better “for each”). But Graham Priest (pdf) has argued that the “there exists” reading is a case of ontological sleight of hand that should be resisted; in fact, he rejects the term “existential quantifier” for “particular quantifier” (and a web search for this will turn up more on the subject).
Priest (top of page 3 in the PDF above, numbered page 199) suggests an example:
I thought of something I would like to buy you for Christmas, but I couldn’t get it because it doesn’t exist.
In symbols:
∃ x, (I thought of x) & (I would like to buy you x for Christmas) & [(I couldn’t get x) ∵ (x doesn’t exist)].
Turning this back into English:
For some x, I thought of x, I would like to buy you x for Christmas, and I couldn’t get x because x doesn’t exist.
But not this:
There exists x such that I thought of x, I would like to buy you x for Christmas, and I couldn’t get x because x doesn’t exist.
One could rescue this by claiming that x exists in the speaker’s past thoughts but not in reality, or something like that. But then an uncountable ordinal may also exist in the thoughts of mathematicians without existing in reality.
There are many models of interest in set theory, with different mutually exclusive properties. A logical statement makes sense in context of axioms or intended model. I didn’t take Eliezer’s comment as referring to either of these technical senses (it’s not expecting provability of nonexistence from standard axiom systems, since they just assert existence in question, the alternative being asserting inconsistency, which would be easier to state directly; and standard model is an unclear proposition for set theory, there being so many alternatives, with one taken as the usual standard containing the elements in question). So I was talking about “ontological” senses of “existence” instead.
ZF proves in formal symbols “there exists a smallest uncountable ordinal,” and I guess you are saying that it does not mean that in an ontological sense. But then what is the ontological payoff of this proof?
Like any proof in a formal system, you can conclude that “the idea is consistent unless the formal system is inconsistent.” But that’s a tautology. If you’re not willing to say that ZF refers to things in the real world i.e. has ontological content, why aren’t you skeptical of it?
Like any proof in a formal system, you can conclude that “the idea is consistent unless the formal system is inconsistent.” But that’s a tautology.
I wasn’t saying that. If you believe that a formal system captures the idea you’re considering, in the sense of this idea being about properties of (some of) the models of this formal system, and the formal system tells you that the idea doesn’t make sense, it’s some evidence towards the idea not making sense, even though it’s also possible that the formal system is just broken, or that it doesn’t actually capture the idea, and you need to look for a different formal system to perceive it properly.
If you’re not willing to say that ZF refers to things in the real world i.e. has ontological content, why aren’t you skeptical of it?
ZF clearly refers to lots of things not related to the physical world, but if it’s not broken (and it doesn’t look like it is), it can talk about many relevant ideas, and help in answering questions about these ideas. It can tell whether some object doesn’t hold some property, for example, or whether some specification is contradictory.
(I know a better term for my current philosophy of ontology now: “mathematical monism”. From this POV, inference systems are just another kind of abstract object, as is their physical implementation in mathematicians’ brains. Inference systems are versatile tools for “perceiving” other facts, in the sense that (some of) the properties of those other facts get reflected as the properties of the inference systems, and consequently as the properties of physical devices implementing or simulating the inference systems. An inference system may be unable to pinpoint any one model of interest, but it still reflects its properties, which is why failure to focus of a particular model or describe what it is, is not automatically a failure to perceive some properties of that model. Morality is perhaps undefinable in this sense.)
This is again not the sense I discussed. A claim that an uncountable ordinal “doesn’t exist” has to be interpreted in a different way to make any sense. A claim that it does doesn’t need such excursions, and so the default senses of these claims are unrelated.
the Burali-Forti paradox saying that the predicate “well-ordered” cannot be self-applicable … I just have trouble believing that there’s actually any such thing as an uncountable ordinal out there, because it implies an absolute well-ordering of all the countable well-orderings; it seems to have a superlogical character to it.
I don’t think that it’s fair to characterise the B-F paradox this way. The argument of B-F is that, given any collection S of well-orderings closed under taking sub-well-orderings, S cannot be among the well-orderings represented in S itself. There is nothing paradoxical here. (I’m not sure whether this matches the content of Cesare Burali-Forti’s 1897 paper, which I haven’t read and of which I’ve heard conflicting accounts, but the secondary sources all seem to agree that he did not believe that he had found a paradox. ETA: After following the helpful link from komponisto, I see that sadly this is not how B-F himself viewed the matter.)
Now, if you add the assumption of an absolute collection of all well-orderings, then you get a paradox. But an absolute collection of (say) all finite well-orderings leads to no paradox; we just know that this collection is not finite. And an absolute collection of all countable well-orderings leads to no paradox either; we just know that this collection is not countable. And so on.
Of course, none of this shows that such collections actually exist. If you said that you don’t really believe in uncountable ordinals (perhaps on the grounds that they’re not needed for applications of mathematics to the real world), I would not have commented (except maybe to agree); but calling them incredible (as you seem to do, counting them as evidence against set theory, indeed among the strongest that you know) goes far beyond what I would consider justified.
There seems to be controversy about “exist” and “out there”, can you taboo those?
For example, are you saying the you think Ultimate Ensemble does not contain structures that depend on them, or that they lead to an inconsistency somewhere, or simply that your utility function does not speak about things that require them, or what exactly?
or simply that your utility function does not speak about things that require them, or what exactly?
This isn’t a much simple/weaker claim than other possible meanings for “I just have trouble believing”.
Their underlying other utility functions would be contagious. For example, if my utility function requires them, then someone of whom it is accurate to say that “His utility function does not speak about things that require them” would’t be able to include in his utility function my desires, or desires of those who cared about my desires, or desires of people who cared about the desires of people who cared about my desires, and so forth.
Eliezer cares about some people, some people care about me, and the rest is six degrees of Kevin Bacon.
The most extreme similar interpretation would have to be a statement about human utility functions in general.
I don’t know what it means to care about the existence of the smallest uncountable ordinal (as opposed to caring that this existence can be proved in ZF, or cannot be refuted in second-order arithmetic, or something like that). Can we taboo “smallest uncountable ordinal” here?
In real life, I’ve had some trouble recently admitting I hadn’t thought of something when it was plausible to claim I had. I think that admitting it would/will cost me status points, as it does not involve rationalists, “rationalists”, aspiring rationalists, or “aspiring rationalists”.
Are you sure you chose the phrase “simply that your utility function does not speak about things that require them” to describe the state of affairs where no human utility function would have it, and hence it would be unimportant to Eliezer?
If you see the thought expressed in my comment as trivially obvious, then:
1) we disagree about what people would find obvious,
2) regardless of the truth of what people find obvious, you are probably smarter than I to make that assumption, rather than simply less good at modeling other humans’ understanding,
3) I’m glad to be told by someone smarter than I that my thoughts are trivial, rather than wrong.
The comment wasn’t really intended for anyone other than Eliezer, and I forgot to correct for the halo making him out to me basically omniscience and capable of reading my mind.
he could still accept superhappies or papperclipers caring about it say.
I think he actually might intrinsically value their desires too. One can theoretically make the transition from “human” to “paperclip maximizer” one atom at a time; differences in kind are the best way for corrupted/insufficiently powerful software to think about it, but here we’re talking about logical impurity, which would contaminate with sub-homeopathic doses.
Well, in that case it’s new information and we can conclude that either his utility function DOES include things in those universes that he claim can not exist, or it’s not physically possible to construct an agent that would care about them.
For essentially the same reasons I have trouble believing that the first infinite ordinal exists.
Finite ordinals are computable, but otherwise your remarks still apply if you swap out “countable” for “finite.” According to ZF there are uncomputable sets of finite ordinals, so you can’t verify that they are well-ordered algorithmically.
The natural numbers exist in about the strongest possible sense: I can get a computer program to spit them out one by one, and it won’t stop until it runs out of resources. It’s more accurate to say I don’t believe that they’re well-ordered, see here.
You might find my reasoning preposterous, I only wanted to point out that it’s essentially the same as EYs reasoning about uncountable ordinals.
Set theory is just a made up bunch of puzzle pieces (axioms) and some rules on how to fit them together (logic) so it’s weird to hear you lot talking about “existence” of a set with some property P as something other than whether or not the statement “exists X, P(X)” has a proof or not. I thought Hilbert’s finitist approach should have slain Platonism long ago.
The following is a comment by John Baez, posted on Google+ where I linked to this thread:
It’s indeed hard to believe, at a gut level, in the existence of a well-ordered uncountable set. For example: can you take the set of real numbers and linearly order them in some funny way such that any decreasing sequence of them, say a > b > c > …, “bottoms out” after finitely many steps? (Here > is defined in the funny way you’ve chosen.) Nobody knows an explicit way to do this, and you can prove that nobody ever will. Yet the “well-ordering theorem” says you can do it:
What’s the catch? This theorem is equivalent to the Axiom of Choice, which cannot be proved (or disproved!) from the rest of the Zermelo-Fraenkel axioms of set theory.
So, we may decide to disbelieve in the Axiom of Choice. But there are other ways of stating it, which make it sound obviously true.
This makes it sound like believing in an uncountable ordinal is equivalent to AC, which would make things easier—lots of mathematicians reject AC. But you might not need AC to assert the existence of a well-ordering of the reals as opposed to any set, and others have claimed that weaker systems than ZF assert a first uncountable ordinal. My own skepticism wasn’t so much the existence of any well-ordering of the reals (though I’m willing to believe that no such exists), my skepticism was about the perfect, canonical well-ordering implied by there being an uncountable ordinal onto whose elements all the countable ordinals are mapped and ordered. Of course that could easily be equivalent to the existence of any well-ordering of the reals.
No they don’t (*). Your saying this explicitly somewhat confirms my brain’s natural, automatic assumption that your error here (and in similar comments in the past—“infinite set atheism” and all that business) is as much sociological as philosophical: all along, I instinctively thought, “he doesn’t seem to realize that that’s a low-status position”.
ZFC is considered the standard axiom system of modern mathematics. I have no doubt that if an international body (say, the IMU) were to take a vote and choose a set of “official rules of mathematics”, the way (say) FIDE decides on the official rules of chess, they would pick ZFC (or something equivalent).
Now it’s true, there are some mathematicians who are contrarians and think that AC is somehow “wrong”. They are philosophically confused, of course; but, more to the point here in this comment, they are a marginal group. (In fact, even worrying about foundational issues too much—whatever your “position”—is kind of a low-status marker itself: the sociological reality of the mathematical profession is that members are expected to get on with the business of proving impressive-looking new theorems in mainstream, high-status fields, and not to spend time fussing about foundations except at dinner parties.)
(*) I don’t know the numbers, or how you define “lots”, and there are a large number of mathematicians in the world, so technically I don’t know if it’s literally false that “lots” of mathematicians would say that they “reject AC” . But the clear implication of the statement—that constructivism is a mainstream stance—most definitely is false.
I think you are stating these things too confidently.
Most mathematicians could not state the axioms of ZFC from memory. My suspicion is that AC skepticism is highest among mathematicians who can.
One piece of evidence that AC skepticism is not low-status is that papers and textbooks will often emphasize when a proof uses AC, or when a result is equivalent to AC. People find such things interesting.
You could make a stronger case that skepticism about infinity is regarded as low-status.
But what do status considerations have to do with whether Yudkowsky’s beliefs and hunches are justified?
Most mathematicians could not state the axioms of ZFC from memory. My suspicion is that AC skepticism is highest among mathematicians who can.
I don’t see why this is even relevant, but for what it’s worth, I don’t particularly share this suspicion: I would expect those who know the axioms from memory to be more philosophically sophisticated (i.e. non-Platonist), and to be more likely to be familiar with technical results such as Gödel’s theorem that ZFC is as consistent as ZF.
My own impression is that professed “AC skepticism” (scarequotes because I think it’s a not-even-wrong confusion) is most correlated not with interest in logic and foundations, but with working in finitary, discrete, or algebraic areas of mathematics where AC isn’t much used.
One piece of evidence that AC skepticism is not low-status is that papers and textbooks will often emphasize when a proof uses AC, or when a result is equivalent to AC. People find such things interesting.
The fact that people find such things interesting is at best extremely weak evidence for the proposition that constructivism and related positions are mainstream. (After all, I find such things interesting!)
As I pointed out in the comment linked to above, there is a difference between dinner-party acknowledgement of constructivism (which is widespread) and actually taking it seriously enough to worry about whether one’s results are correct (which would be considered eccentric).
If AC skepticism were not low-status, you would expect to find papers and textbooks actively rejecting AC results, rather than merely mentioning in a remark or footnote that AC is involved. (Such footnotes are for use at dinner parties.)
And also, texts just as frequently do not bother to make apologies of the sort you allude to. A fairly random example I recently noticed was on p.98 of Algebraic Geometry by Hartshorne, where Zorn’s Lemma is used without any more apology than an exclamation point at the end of the (parenthetical) sentence.
But what do status considerations have to do with whether Yudkowsky’s beliefs and hunches are justified?
It tends to irritate me when people get something wrong which they could easily have gotten right by using a standard human heuristic (such as the “status heuristic”, noticing what the prestigious position is).
My own impression is that professed “AC skepticism” (scarequotes because I think it’s a not-even-wrong confusion) is most correlated not with interest in logic and foundations, but with working in finitary, discrete, or algebraic areas of mathematics where AC isn’t much used.
I would expect those who know the axioms from memory to be more philosophically sophisticated (i.e. non-Platonist), and to be more likely to be familiar with technical results such as Gödel’s theorem that ZFC is as consistent as ZF.
They’re also more likely to know Cohen’s theorem that ZF + not(AC) is also just as consistent. And of course, being philosophically sophisticated, it’s clear to me that they would be more likely to realise that the axioms of ZFC are fairly arbitrary and no better than many others. They’re also more likely to know, and to appreciate the philosophical significance of, that there are many axiom systems that are strong enough to do most mathematics (including all concretely applied mathematics) and yet much weaker (hence more surely consistent) than ZFC (although this has little to do with AC as such).
However, when arguing about what philosophically sophisticated people are going to think, we’re both naturally inclined to think that they’ll agree with ourselves, so our impressions about that prove nothing.
If AC skepticism were not low-status, you would expect to find papers and textbooks actively rejecting AC results
You do find such things (but they are mostly published in certain journals, which we can tell are low-status, since such things are published in them).
However, when arguing about what philosophically sophisticated people are going to think, we’re both naturally inclined to think that they’ll agree with ourselves, so our impressions about that prove nothing.
I’m not sure about that. You and komponisto seem to be using ‘philosophically sophisticated’ to contrast with Platonism. This use strikes me as similar to how arguing that ‘death is good’ is sophisticated, i.e., showing of your intelligence by providing convincing arguments for a position that violates common sense. In this case arguing that mathematical statements don’t have inherent truth value.
Remember just because you can make a sophisticated sounding argument for a preposition doesn’t mean its true.
Mathematica statements do have inherent truth value, but that value is relative to the axioms. And as far as the axioms go, the most you can say is that a system of axioms is consistent, and beyond that you get into non-mathematical statements. What exactly is sophisticated about this?
However, when arguing about what philosophically sophisticated people are going to think, we’re both naturally inclined to think that they’ll agree with ourselves, so our impressions about that prove nothing.
I’m not sure about that. You and komponisto seem to be using ‘philosophically sophisticated’ to contrast with Platonism.
Yes, which agrees with my complaint quoted above. Neither of us is a Platonist, so we both assume that philosophically sophisticated people won’t be Platonists, although we derive different things thereafter.
showing of your intelligence by providing convincing arguments for a position that violates common sense. In this case arguing that mathematical statements don’t have inherent truth value.
I’m certainly not trying to show off my intelligence. I just think that the idea of inherent truth value for abstract statements about completed infinities violates common sense!
what accounts for your intuition that ZF and other systems for reasoning about completed infinities are consistent?
To the extent that I have this intuition, this is mostly because people have used these systems without running into inconsistencies so far. (At least, not in the systems, such as ZF, that people still use!)
But strictly speaking, ‘ZF is consistent.’ is not a statement with an absolute meaning, because it is itself a statement about a completed infinity. I have high confidence that no inconsistency in ZF has a formal proof of feasible length, but I really have no opinion about whether it has an inconsistency of length 3^^^3; we haven’t come close to exploring such things.
(Come to think of it, I believe that my Bayesian probability as to whether ZF is consistent to such a degree ought to be quite low, for essentially the same reason that a random formal system is likely to be inconsistent, although I’m not really sure that I’ve done this calculation correctly; I can think of at least one potential flaw.)
I cannot speak for komponisto about any of this, of course.
But strictly speaking, ‘ZF is consistent.’ is not a statement with an absolute meaning, because it is itself a statement about a completed infinity. I have high confidence that no inconsistency in ZF has a formal proof of feasible length, but I really have no opinion about whether it has an inconsistency of length 3^^^3; we haven’t come close to exploring such things.
These feasibility issues are definitely interesting. Another possibility is that there is a formal proof of feasible length, but no feasible search will ever turn it up. (Well, unless P = NP). Yet another possibility is that a feasible search will turn it up, I certainly regard it as more likely than most people do.
To the extent that I have this intuition, this is mostly because people have used these systems without running into inconsistencies so far. (At least, not in the systems, such as ZF, that people still use!)
I agree that this counts as evidence, but it’s possible to overestimate it. Foundational issues hardly ever come up in everyday mathematics, so the fact that people are able to prove astonishing things about 3-manifolds without running into contradictions I regard as very weak evidence in favor of ZF. There have been a lot of man-hours put into set theory, but I think quite a bit less than have been put into other parts of math.
(Come to think of it, I believe that my Bayesian probability as to whether ZF is consistent to such a degree ought to be quite low, for essentially the same reason that a random formal system is likely to be inconsistent, although I’m not really sure that I’ve done this calculation correctly; I can think of at least one potential flaw.)
JoshuaZ and I had a discussion about this a while ago, starting here.
Another possibility is that there is a formal proof of feasible length, but no feasible search will ever turn it up. (Well, unless P = NP).
This reminds me of people who argue that, because P != NP, we will never prove this. (The key to the argument, IIRC, is that any proof of this fact will have very high algorithmic complexity.) I’m not sure how to find this argument now. (There is something like it one of Doron Zeilberger’s April Fools opinions.)
the fact that people are able to prove astonishing things about 3-manifolds without running into contradictions I regard as very weak evidence in favor of ZF
Yes, these results should be formalisable in higher-order arithmetic (indeed _n_th order for n a single-digit number). It is the set theorists’ work with large cardinals and the like that provides the only real evidence for the consistency of such a high-powered system as ZF.
I would expect those who know the axioms from memory… to be more likely to be familiar with technical results such as Gödel’s theorem that ZFC is as consistent as ZF.
They’re also more likely to know Cohen’s theorem that ZF + not(AC) is also just as consistent.
Yes; that’s definitely within the scope of my “such as”!
However, when arguing about what philosophically sophisticated people are going to think, we’re both naturally inclined to think that they’ll agree with ourselves, so our impressions about that prove nothing.
Not quite. Remember that I gave a specific meaning for “philosophically sophisticated”: I said it meant “non-Platonist”. And what I meant by that, here, is not believing that AC (or any other formal axiom) represents some kind of empirical claim about “the territory” that could be “falsified” by “evidence”, despite being part of a consistent axiom system.
I claim the situation with AC is like that of the parallel postulate: it makes no sense to discuss whether it is “true”; only whether it is “true within” some theory.
You do find such things (but they are mostly published in certain journals, which we can tell are low-status, since such things are published in them).
What I meant was more like: you would find some substantial proportion (say 20% or more) of textbooks being used to teach analysis (say) to graduate students in mathematics omitting all theorems which depend on AC.
Remember that I gave a specific meaning for “philosophically sophisticated”: I said it meant “non-Platonist”.
Yes, and I was happy to take it this way, as I am certainly no Platonist. Surely only a Platonist could believe that AC is true; we philosophically sophisticated people know that you can make whatever assumptions you want! And so naturally a theorem with a proof using AC is a weaker result than the same theorem with a proof that doesn’t, since it holds under fewer sets of assumptions, and thus the latter is preferred. Meanwhile, a theorem with a proof using not(AC) is just as valid as the same theorem with a proof using AC; it’s less useful only because it has fewer connections with the published corpus of mathematics, but that’s merely a sociological contingency.
Is it often the case that you need to assume the negation of AC for a proof to hold? AC comes up in seemingly-unrelated areas when you need some infinitely-hard-to-construct object to exist; I can’t imagine a similar case where you’d assume not(AC) in, e.g., ring theory.
As usual, the negation of a useful statement ends up not being a useful statement. I don’t think anyone works with not(AC), they work with various stronger things that imply not(AC) but actually have interesting consequences.
Sniffnoy may have more examples, but here are some that I know:
Every subset of the real line is Lebesgue-measurable.
Every subset of the real line has the Baire property (in much the same vein as the preceding one).
The axiom of determinacy (a statement in infinitary game theory).
Adding the first two to ZF + DC (dependent choice) is consistent (assuming that ZFC + Con(ZFC) is consistent, as just about everybody believes), and this gives a “dream universe” for analysis in which, for example, any everywhere-defined linear operator between Hilbert spaces is bounded.
Adding the first two to ZF + DC (dependent choice) is consistent (assuming that ZFC + Con(ZFC) is consistent, as just about everybody believes)
This isn’t quite right. The consistency of ZF + DC + “every subset of R is Lebesgue measurable” is equivalent to the consistency of an inaccessible cardinal, which is a much stronger assumption then the consistency of ZFC + Con(ZFC).
Surely only a Platonist could believe that AC is true; we philosophically sophisticated people know that you can make whatever assumptions you want!
Yes, indeed!
And so naturally a theorem with a proof using AC is a weaker result than the same theorem with a proof that doesn’t, since it holds under fewer sets of assumptions, and thus the latter is preferred.
Yes—but it needs to be stressed that this doesn’t distinguish AC from anything else! (Also, depending on the context, there may other criteria for selecting proofs besides the strength or weakness of their assumptions.)
If only people would talk about whether they prefer working in ZFC or ZF+not(C) (or plain ZF), or better yet what they like and don’t like about each, rather than whether AC is “true” or how “skeptical” they are.
If only people would talk about whether they prefer working in ZFC or ZF+not(C) (or plain ZF), or better yet what they like and don’t like about each, rather than whether AC is “true” or how “skeptical” they are.
Yes, indeed, that would be much more sophisticated! But scepticism of the orthodoxy can be the first step to such sophistication. (It was for me, although in my case there were also some parallel first steps that did not initially seem connected.)
If AC skepticism were not low-status, you would expect to find papers and textbooks actively rejecting AC results, rather than merely mentioning in a remark or footnote that AC is involved. (Such footnotes are for use at dinner parties.)
Not entirely. If the only known proof for a result assumes choice, then a proof that doesn’t use choice will almost certainly be publishable.
And also, texts just as frequently do not bother to make apologies of the sort you allude to. A fairly random example I recently noticed was on p.98 of Algebraic Geometry by Hartshorne, where Zorn’s Lemma is used without any more apology than an exclamation point at the end of the (parenthetical) sentence.
Using an exclamation mark like that is a pretty rare thing to do. You wouldn’t for example see this if one used the axiom of replacement. The only other axiom that would be in a comparable position is foundation but foundation almost never comes up in conventional mathematics. Hartshorne is writing for a very advanced audience so I think putting an exclamation mark like that is sufficient to get the point across especially when one is using choice in the form of Zorn’s lemma.
is most correlated not with interest in logic and foundations, but with working in finitary, discrete, or algebraic areas of mathematics where AC isn’t much used.
This seems to fit my impression as well.
Incidentally, for what it is worth, your claim that rejection of AC is low status seems to be possibly justified. I know of two prominent mathematicians who explicitly reject AC in some form. One of them does so verbally but seems to be fine teaching theorems which use AC with minimal comment. The other keeps his rejection of AC essentially private.
Using an exclamation mark like that is a pretty rare thing to do. You wouldn’t for example see this if one used the axiom of replacement. The only other axiom that would be in a comparable position is foundation but foundation almost never comes up in conventional mathematics.
Of course it’s worth noting that axiom of replacement doesn’t come up much either, though obviously the case there isn’t quite as extreme as with foundation.
We appear to have misunderstood each other, having something different in mind by words like “skepticism” and “reject.” I agree Con(ZF) entails Con(ZFC), and that every educated mathematician knows it. Beyond that I don’t have a good handle on what you’re saying, or even whether you disagree with Yudkowsky, or me. Are you saying that mathematicians pay lip service to constructivism, but ignore it in their work? Are you additionally saying that there is something false about constructivist ideas?
It tends to irritate me when people get something wrong which they could easily have gotten right by using a standard human heuristic (such as the “status heuristic”, noticing what the prestigious position is).
That doesn’t sound like such a great heuristic to me...
Now it’s true, there are some mathematicians who are contrarians and think that AC is somehow “wrong”. They are philosophically confused, of course; but, more to the point here in this comment, they are a marginal group. (In fact, even worrying about foundational issues too much—whatever your “position”—is kind of a low-status marker itself: the sociological reality of the mathematical profession is that members are expected to get on with the business of proving impressive-looking new theorems in mainstream, high-status fields, and not to spend time fussing about foundations except at dinner parties.)
This seems problematic. Many mathematicians work on foundations and are treated with respect. It isn’t that they are low status so much that a) most of the really big foundational issues are essentially done b) foundational work rarely impact other areas of math, so people don’t have a need to pay attention to foundations. There also seems to be an incredible degree of confidence in claiming that those skeptical of AC are ” philosophically confused, of course”.
It’s somewhat pertinent to point out that the highest rated contributor at MathOverflow is none other than Joel David Hamkins of ‘foundations of set theory’ fame.
I have no doubt that if an international body […] were to take a vote and choose a set of “official rules of mathematics” […], they would pick ZFC (or something equivalent).
More than that, I daresay that they’d pick something much stronger than ZFC, probably ZFC with a large cardinal axiom. (And the main debate would be how large that cardinal should be.)
(*) I don’t know the numbers, or how you define “lots”, and there are a large number of mathematicians in the world, so technically I don’t know if it’s literally false that “lots” of mathematicians would say that they “reject AC” . But the clear implication of the statement—that constructivism is a mainstream stance—most definitely is false.
And anecdotally it seems that the AC skepticism that does exist seems to largely come from constructivism, so if we rule out that (since it doesn’t seem that Eliezer wants to go all constructivist on us :) ), it’s even less so.
I’m not sure what you mean by “constructivism” here; I usually hear that term referring to doubting the law of excluded middle (when applied to statements quantified over infinite sets), but I know several mathematicians who doubt the axiom of choice without doubting excluded middle.
I should also clarify the difference between doubting AC and denying AC. If you deny AC, then you believe that it is false, and hence any theorem whose only known proofs use AC is no theorem at all; it might be true, but it has not been proved. (And if AC follows from it, then it must in fact be false.) If you only doubt AC, however, then you simply believe that a theorem with a proof that uses AC is a weaker result than the same theorem with a proof that doesn’t, and so the former theorem is still worth publishing but the latter is naturally preferred.
This seems such an obvious position to me that I doubt everything in mathematics (although there is a core which I generally assume since mathematics without it seems uninteresting (although I’m open to being proved wrong about this)).
Both AC and its negation can be made sense of in set theory. One or the other can be considered more interesting, or more relevant in the context of a particular problem, but given the extensive experience with mathematics of foundations we can safely study the properties of either. The question of which way “lies the truth” seems confused, since the alternatives coexist. Ultimately, some axiomatic options might turn out to be morally irrelevant, but that’s not a question that human philosophers can hope to settle, and all simple things are likely relevant at least to some extent.
But you might not need AC to assert the existence of a well-ordering of the reals as opposed to any set, and others have claimed that weaker systems than ZF assert a first uncountable ordinal.
On the contrary, you need almost the full strength of AC to establish that a well-ordering of the reals exists. Like you say, you don’t need it to construct uncountable ordinals, or to show that there is a smallest such. Cantor’s argument constructively shows that there are uncountable sets, and you can get from there to uncountable ordinals by following your nose.
Is this because you can’t prove aleph-one = beta-one? I’m Platonic enough that to me, “well-order an uncountable set” and “well-order the reals” sound pretty similar.
No something sillier. You can prove the axiom of choice from the assumption that every set can be well-ordered. (Proof: use the well-ordering to construct a choice function by taking the least element in every part of your partition.)
If one doesn’t wish to assume that every set has a well-ordering, but only a single set such as the real numbers, then one gets a choice-style consequence that’s limited in the same way: you can construct choice functions from partitions of the real numbers.
I’d hardly call a well-ordering on one particular cardinality “almost the full strength of AC”! I guess it probably is enough for a lot of practical cases, but there must be ones where one on 2^c is necessary, and even so that’s still a long way from the full strength...
Hm, agreed. I guess not so much “the full strength” but “the full counterintuitiveness”? Where DC uses hardly any of the counterintuitiveness, and ultrafilter lemma uses nearly all of it?
Uh, that’s a lot more than “Platonism”… how was anyone supposed to guess you’ve been assuming CH?
Edit: To clarify—apparently you’ve been thinking of this as “I can accept R, just not a well-ordering on it.” Whereas I’ve been thinking of this as “Somehow Eliezer can accept R, but not a cardinal that’s much smaller?!”
Edit again: Though I guess if we don’t have choice and R isn’t well-orderable than I guess omega_1 could be just incomparable to it for all I know. In any case I feel like the problem is stemming from this CH assumption rather than omega_1! I don’t think you can easily get rid of a smallest uncountable ordinal (see other post on this topic—throwing out replacement will alllow you to get rid of the von Neumann ordinal but not, I don’t think, the ordinal in the general sense), but if all you want is for there to be no well-order on the continuum, you don’t have to.
...I just have trouble believing that there’s actually any such thing as an uncountable ordinal out there, because it implies an absolute well-ordering of all the countable well-orderings; it seems to have a superlogical character to it.
I thought that could be proven without reference to the existence of a set of them, just from general facts about well-ordering? And then the only question is whether the class of all countable ordinals is set-sized. Which it must be since they can all be realized on N. As long as you accept the continuum, anyway! I don’t see how the continuum can possibly be more acceptable than omega_1.
I think we may have something of a clash of backgrounds here. The reason I’m inclined to take the real continuum seriously is that there are numerous physical quantities that seem to be made of real or complex numbers. The reason I take mathematical induction seriously is that it looks like you might always be able to add one minute to the total number of minutes passed. The reason I take second-order logic seriously is that it lets me pin down a single mathematical referent that I’m comparing to the realities of space and time.
The reason I’m not inclined to take the least uncountable ordinal seriously is because, occupying as it does a position above the Church-Kleene ordinal and all possible hypercomputational generalizations thereof, it feels like talking about the collection of all collections—the supremum of an indefinitely extensible quality that shouldn’t have a supremum any more than I could talk about a mathematical object that is the supremum of all the models a first-order set theory can have. If set theory makes the apparent continuum from physics collide with this first uncountable ordinal, my inclination is to distrust set theory.
The reason I take second-order logic seriously is that it lets me pin down a single mathematical referent that I’m comparing to the realities of space and time.
How can you say this after having read this thread?
If you believe in second-order model theory, then you believe in set theory. (However, by limiting it to second order over the natural numbers, without going on to third order, you are not obligated to believe in uncountable ordinals.)
ETA: It is very imprecise to compare second-order model theory and set theory like this. Already model theory is set theory, of course, albeit (potentially, not in practice) set theory without power sets. I should just leave the model theory out of it and say:
If you believe in second-order logic, then you believe in set theory. (However, ….)
The reason I take second-order logic seriously is that it lets me pin down a single mathematical referent that I’m comparing to the realities of space and time.
I have my problems with the other two, but this is the only one I don’t understand. What do you mean?
it feels like talking about the collection of all collections—the supremum of an indefinitely extensible quality that shouldn’t have a supremum any more than I could talk about a mathematical object that is the supremum of all the models a first-order set theory can have
You seem to accept the notion that all finite numbers have a supremum. Why not just iterate whatever process accounts for that?
You seem to accept the notion that all finite numbers have a supremum. Why not just iterate whatever process accounts for that?
First of all, I’ve never seen an aleph-null, just one, two, three, etc. Accepting that the integers have a supremum is a whole different kettle of fish from accepting that the collection of finite integers seems to go on without bound. Second, taking a supremum once, using a clearly defined computable notation and a halting machine that can compare any two representations, is a whole different kettle of fish than talking about the supremum of all possible ways to define countable well-orderings to and beyond computable recursion.
you can’t talk about the integers or the reals in first-order logic.
It’s more accurate to say that you can’t talk about arbitrary subsets of the integers or the reals in first-order logic.
Accepting that the integers have a supremum is a whole different kettle of fish from accepting that the collection of finite integers seems to go on without bound.
I agree. This is the difference between completed and potential infinity. Nelson.
Second, taking a supremum once, using a clearly defined computable notation and a halting machine that can compare any two representations, is a whole different kettle of fish than talking about the supremum of all possible ways to define countable well-orderings to and beyond computable recursion.
I’m not so sure. Everything you’ve ever talked about, uncountable ordinals and all, you’ve talked about using computable notation. Computable, period is a whole different kettle of fish.
OK, you say you don’t accept that sort of uncomputable leap to the end. The problem is that, AIUI, you’re already accepting it as soon as you accept the power set of N. (Of the various “axioms of power” of ZFC, power set is the only one needed here. And if you just want omega_1, you don’t need arbitrary power sets, just that of N. I mean really you want P(N x N), but since N is in an easily-described bijection with N x N, it shouldn’t make a difference; just use a pairing function instead of proper ordered pairs.) The construction of omega_1 from P(N) is pretty straightforward, really, and doesn’t use any of ZFC’s other powerful axioms. Maybe you can somehow have the reals without P(N)? I.e. without binary expansions? shrug This is getting rather far away from what I know. Constructivists—well, not the milder ones who just reject excluded middle, but the stricter ones who don’t like impredicativity (whatever that might be, don’t ask me) -- don’t accept the axiom of power sets; they consider it just as much an unjustified leap to the end.
Of course you could always try summoning TobyBartels and ask him how the constructivists do it. When you say these sorts of things I’m a little of surprised you haven’t gone constructivist already. But I guess you like classical logic. :)
(By the “axioms of power”, I mean replacement, power set, and choice; the ones anyone might object to. Well, foundation is objectionable too, but it’s more of an axiom of weakness. Healing Salve as opposed to Ancestral Recall. :P Also looking things up apparently the no-impredicativity constructivists insist on weakening axiom of separation as well? Well, I think their weaker version should suffice here. Again, I am saying these things without carefully checking them because hopefully TobyBartels will show up and correct me if I am wrong. :) )
The construction of omega_1 from P(N) is pretty straightforward, really, and doesn’t use any of ZFC’s other powerful axioms.
You either need P(P(N)) or something like an axiom of quotient sets to take the equivalence classes that are the actual elements of this version of omega_1. I presume (but haven’t checked) that this is why J_2 has R but not omega_1 (although J_2 is not written in set-theoretic language, so you have to encode these).
Maybe you can somehow have the reals without P(N)?
Assuming you accept classical logic, then P(N) may be constructed as a subset of R: that famous fractal the Cantor set.
I am saying these things without carefully checking them because hopefully TobyBartels will show up and correct me if I am wrong.
Just about everything that I know about predicative mathematics is distilled here. There I describe two schools, and the constructive one (which is less predicative than the classical one!) is the only one that I know well.
You either need P(P(N)) or something like an axiom of quotient sets to take the equivalence classes that are the actual elements of this version of omega_1.
Crap, looks like I should have checked that after all! OK, I guess if Eliezer accepts R but not P(R) then there’s less of a problem here than I thought. :P
I presume (but haven’t checked) that this is why J_2 has R but not omega_1 (although J_2 is not written in set-theoretic language, so you have to encode these).
Edit: Nevermind, this line was asking what J_2 was, you’ve given a reference elsewhere.
Maybe you can somehow have the reals without P(N)?
Assuming you accept classical logic, then P(N) may be constructed as a subset of R: that famous fractal the Cantor set.
Oh, that works. Should have thought of that.
The constructive one (which is less predicative than the classical one!)
Huh, so there’s two separate things going on here. Constructivism in the sense of no-excluded-middle, and I guess “predicativism” in the sense of, uh, things should be predicative? I probably should have realized those were largely independent, but didn’t. How is the constructive version less predicative? Is it just the function set issue?
I want to be a first-uncountable-ordinal wizard. :)
You know, the concept of the first uncountable ordinal is actually one of the strongest reasons I’ve ever heard to disbelieve in set theory. ZFC, or rather NBG, does imply the existence of a first uncountable ordinal, right, or am I mistaken?
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.)
I had to check to be sure, but then saw others noted it: Raw ZF seems quite sufficient to prove its existence.
So even tossing Choice in the bin isn’t enough to get rid of it.
EDIT: Perhaps this is math’s revenge for you having tiled a hall in Hogwarts with pentagons. :)
But he didn’t say regular pentagons. Pentagon tiles shown here. Also, he did say that Hogwarts has non-Euclidean geometry.
Actually, my understanding was that he said it didn’t have geometry at all, only topology.
It’s not Choice I have the problem with here, it’s set theory.
Do you think that uncountable sets don’t exist, or that there is no way to order them such that one is first?
The existence of the real number line is one thing. The existence of an uncountable ordinal is another. When you consider the hierarchies of uncomputable ordinals to their various Turing degrees that are numbered among the countable ordinals, and that which countable ordinals you can constructively well-order strongly corresponds to the strength of your proof theory and which Turing machines you believe to halt, and when you combine this with the Burali-Forti paradox saying that the predicate “well-ordered” cannot be self-applicable, even though any given collection of well-orderings can be well-ordered...
...I just have trouble believing that there’s actually any such thing as an uncountable ordinal out there, because it implies an absolute well-ordering of all the countable well-orderings; it seems to have a superlogical character to it.
I wonder how much of this is just a function of what math you’ve ended up working with a lot.
Humans have really bad intuition about math. This shouldn’t be that surprising. We evolved in a context where selection pressure was on finding mates and not getting eaten by large cats.
Speaking from personal experience as a mathematician (ok a grad student but close enough for this purpose) it isn’t that uncommon for when I encounter a new construction that has some counterintuitive property to look at it and go “huh? Really?” and not feel like it works. But after working with the object for a while it becomes more concrete and more reasonable. This is because I’ve internalized the experience and changed my intuition accordingly.
There are a lot of very basic facts that don’t involve infinite sets that are just incredibly weird. One of my favorite examples are non-transitive dice. We define a “die” to be a finite list of real numbers. To role a dice we pick a die a random number from the list, giving each option equal probability. This is a pretty good representation of what we mean by a dice in an intuitive set. Now, we say a die A beats a die B if more than half the time die A rolls a higher number than die B. Theorem: There exist three 6-sided dice A, B and C with positive integer sides such that A beats B, B beats C and C beats A. Constructing a set of these is a fun exercise. If this claim seems reasonable to you at first hearing then you either have a really good intuition for probability or you have terrible hindsight bias. This is an extremely finite, weird statement.
And I can give even weirder examples including an even more counterintuitive analog involving coin flips.
I just don’t see “my intuition isn’t happy with this result” to be a good argument against a theorem. All the axioms of ZF seem reasonable and I can get the existence of uncomputable ordinals from much weaker systems. So if there’s a non-intuitive aspect here, that’s a reason to update my intuition not to reduce my confidence in set theory.
ETA: If you want to learn more about this (and see solution sets for the three dice problem) see this shamelessly self-promoting link to my own blog or this more detailed and better written Wikipedia article.
Here is another page dealing with non-transitive dice that I liked.
Oooh. That page is excellent. I have not seen dice with the order reversing property before. Even being a fan of non-transitive dice and having seen this sort of thing before that was highly unexpected. I’m going to have to sit down and look hard about what is going on there.
The axiom of foundation seems pretty ad hoc to me. It’s there to patch Russell’s paradox. I see no reason not to expect further paradoxes.
We arrived at the axiom of infinity from a finite amount of experience, which seems troubling to me.
It’s a very cool construction, but it’s a finite one that we can verify by hand or with computer assistance. Of the things that ZF claims exist, some of them have this “verifiability” property and some don’t. At the very least don’t you agree that’s a crucial distinction, and that we ought to be strictly less skeptical of constructible, computable, verifiable things than of things like uncountable ordinals?
Also, there’s another respect in which foundation doesn’t impact Russell issues at all. Whether one accepts foundation, anti-foundation or no mention of foundation, one can still get very Russellish issues if one is allowed to form the set A of all well-founded sets. Simply ask if A is well-founded or not. This should demonstrate that morally speaking, foundation concerns are only marginally connected to Russell concerns.
To make the obvious comment, this is all unnecessary as Russell’s paradox goes through from unrestricted comprehension (or set of all sets + ordinary restricted comprehension) without any talking about any sort of well-foundedness...
But that’s a neat one, I hadn’t thought of that one before. However I have to wonder if it works without DC.
Edit: Answer is yes, it does, see below.
Sorry. what do you mean by DC?
Dependent choice.
Edit: I feel silly, this doesn’t use dependent choice at all. OK, so the answer to that is “yes”. However it does require enough structure to be able to talk about infinite sequences, unless there’s some other way of defining well-foundedness.
There are (at least) three ways to define well-foundedness, roughly:
one which requires impredicative (second-order) reasoning;
one which requires nonconstructive reasoning (excluded middle);
one which requires infinitary reasoning (with dependent choice, and also excluded middle actually).
They may all be found at the nLab article on the subject; this article promotes the first definition (since we use constructive mathematics there much more often than predicative mathematics), but I think that the middle one (Lemma 2 in the article) is actually the most common. However, the last definition (which you are using, Lemma 1 in the article) is usually the easiest for paradoxes (and DC and EM aren’t needed for the paradoxes either, since they’re used only in proofs that go the other way).
One thing bothering me—is there any way to define a well-founded set without using infinitary reasoning? It’s easy enough to say that all sets are well-founded without it, by just stating that ∈ is well-founded—I mean, that’s what the standard axiom of foundation does, though with the classical definition—but in contexts where that doesn’t hold, you need to be able to distinguish a well-founded set from an ill-founded one. Obvious thing to do would be to take the transitive closure of the set and ask if ∈ is well-founded on that, but what bugs me is that constructing the transitive closure requires infinitary reasoning as well. Is there something I’m missing here?
I know one way; it cannot be stated in ZFC↺ (ZFC without foundation), but it can be stated in MK↺ (the Morse–Kelley class theory version): a set is well-founded iff it belongs to every transitive class of sets (that is every class K such that x ∈ K whenever x ⊆ K); it is immediate that we may prove properties of these sets by induction on membership, and a set is well-founded if all of its elements are, so this is a correct definition. However, it requires quantification over all classes (not just sets) to state.
Sure foundation is by far the most ad-hoc axiom. But it is also one of the one’s that is easiest to see doesn’t generally matter. For pretty much any natural theorem if a proof uses foundation then there’s a version of the theorem without it. Since not-well founded sets don’t fit most of out intuition for sets as things like boxes that’s not an issue. None of the serious apparent paradoxical properties go away if you remove foundation.
Yes, certainly but by how much? If our intuition can go this drastically wrong on small finite objects why should I trust my intuition on objects that are even further removed from my everyday experience? I mean it isn’t like I need 30 or 40 sided dice to pull this off. In fact you can actually make much smaller than 6 sided dice that are non-transitive. Working out the minimum number of sides (assuming that each die in the set doesn’t need to have the same number of sides) is a nice exercise that helps one understand what is going on.
You’re right, I see that it’s the “restriction” of restricted comprehension that actually does the work in avoiding Russell’s paradox, not foundation. Nevertheless, the story is the same: we had an ambitious set-theoretic foundation for mathematics, Russell found a simple and fatal flaw in it, and we should not simply trust that there will be no further problems after patching this one.
This is hardly an argument for accepting that infinite sets exist! There may be a counterintuitive contradiction that one can arrive at from ZF, just as Russell’s paradox is a counterintuitive contradiction arrived at from 19th century foundations, and just as all kinds of counterintuitive but non-contradictory behavior is possible in the finite, constructive realm.
I am proposing that we remove the axiom of infinity from foundations, not that we go further and add its negation. (Though I see that there has been work done on the negation of the foundation axiom! And dubious speculation about its role in consciousness.)
Also one other remark: Foundation isn’t there to repair any Russel issues. You can get as a theorem that Russell’s set doesn’t exist using the other axioms because you obtain a contradiction. Foundation is more that some people have an intuition that sets shouldn’t be able to contain themselves and that together with not wanting sets that smell like Russell’s set caused it to be thrown in.
And of course more generally, for those not familiar, you can never get rid of paradoxes by adding axioms!
I’m really tempted to be obnoxious and present an axiomatic system with a primitive called a “paradox” and then just point out what happens one adds the axiom that there are no paradoxes. This is likely a sign that I should go to bed so I can TA in the morning.
How about by legislating? Has that been tried?
I would be interested in knowing if there is any second-order system which is strong enough to talk about continuity, but not to prove the existence of a first uncountable ordinal.
I can do better. I can give you a complete, decidable, axiomatized system that does that: first order real arithmetic. However, in this system you can’t talk about integers in any useful way.
We can do better than that: first order real arithmetic + PA + a set of axioms embedding the PA integers into R in the obvious way. This is a second order system where I can’t talk about uncountable ordinals. However, this system doesn’t let us talk about sets.
Note that in both these cases we’ve done this by minimizing how much we can talk about sets. Is there some easy way to do this where we can talk about set a reasonable amount?
I’m not sure. Answering that may be difficult (I don’t think the question is necessarily well-defined.) However, I suspect that the following meets one’s intuition as an affirmative answer: Take ZFC without regularity, replacement or infinity, choice, power set or foundation. Then add as an axiom that there exists a set R that has the structure of a totally ordered field with the least-upper bound property.
This structure allows me to talk about most things I want to do with the reals while probably not being able to prove nice claims about Hartogs numbers which should make proving the existence of uncountable ordinals tough. It would not surprise me too much if one could get away with this system with the axiom of the power set thrown also. But it also wouldn’t surprise me either if one can find sneaky ways to get info about ordinals.
Note that none of these systems are at all natural in any intuitive sense. With the exception of first-order reals they are clear attempts to deliberately lobotomize systems. (ETA: Even first order reals is a system which we care about more for logic and model theoretic considerations than any concrete natural appreciation of the system.) Without having your goal in advance or some similar goal I don’t think anyone would ever think about these systems unless they were a near immortal who was passing the time by examining lots of different axiomatic systems.
While thinking about this I realized that I don’t know an even more basic question: Can one deal with what Eliezer wants by taking out the axiom schema of replacement, choice, and foundation? The answer to this is not obvious to me, and in some sense this is a more natural system. If this is the case then one would have a robust system in which most of modern mathematics could be done but you wouldn’t have your solution. However, I suspect that this system is enough to prove the existence of the least uncountable ordinal.
Note that without replacement, you can’t construct the von Neumann ordinal omega*2, or any higher ones, so certainly not omega_1. Of course, this doesn’t prevent uncountable well-ordered sets (obviously these follow from choice, though I guess you’re taking that out as well), but you need replacement to show that every well-ordered set is isomorphic to a von Neumann ordinal.
So I don’t think that this should prevent the construction of an order of type omega_1, even if it can’t be realized as a von Neumann ordinal. Of course losing canonical representatives means you have to talk about equivalence classes, but if all we want to do is talk about omega_1, it suffices to consider well-orderings of subsets of N, so that the equivalence classes in question will in fact be sets. Maybe there’s some other technical obstacle I’m missing here (like it somehow wouldn’t be the first uncountable ordinal despite being the right order?) -- this isn’t really my area and I haven’t bothered to work through it, I can try that later—but I wouldn’t expect one.
There’s not. The Hartog’s number construction gives us the set H(N) of all isomorphism classes of well-orders on subsets of any fixed countably infinite set, and we can prove that H(N) is uncountable and every proper initial segment of H(N) is countable, using power set and separation (but only bounded separation) but not replacement. I verified this just now by looking at Wikipedia’s article on Hartog’s number and checking through the proof myself.
The next step (step 4 in Wikipedia, ETA: which can be saved for the end, although WP did not do so) is to replace the elements of H(N) with von Neumann ordinals, but this is really beside the point. You already have a representation of the least uncountable ordinal, and this step is just making it canonical in a certain way.
Heh, I’d forgotten how simple Hartogs number was in general.
It’s not clear to me that ZFC without regularity, replacement, infinity, choice, power set or foundation with a totally ordered field with the LUB property does allow you to talk about most things you want to do with the reals : without replacement or powerset you can’t prove that cartesian products exist, so there doesn’t seem to be any way of talking about the plane or higher-dimensional spaces as sets. If you add powerset back in you can carry out the Hartogs number construction to get a least uncountable ordinal
Hmm, that’s a good point. Lack of cartesian products is annoying. We don’t however need the full power set axiom to get them. We can simply have an axiom that states that cartesian products exist. Or even weaker do the following (ad hoc axioms) with a new property of being Cartesian: 1. The cartesian product of any two Cartesian sets exist. 2. Any subset of R is Cartesian. 3. The cartesian product of two Cartesian sets is Cartesian. 4. If A and B are Cartesian then A union B, A intersect B, and A\B are all Cartesian. That should be enough and is a lot weaker than general power set I think.
van den Dries, “Tame topology and o-minimal structures,” Cambridge U Press 1998
develops a lot of 20th century geometry in a first order theory of real numbers. You can do enough differential geometry in this setting to do e.g. general relativity.
The J_2 referenced in this subthread shoud do the trick. (See in particular number 6 in the page linked to by shinoteki there).
What does “existence” have to do with anything though? Even if the real world, or morality don’t “exist” in some sense, you still go on making decisions, reason about their properties. (There appear to be two useful senses of “doesn’t exist”: the state of some system is such that some property isn’t present; or a description of a system is contradictory. These don’t obviously apply here.)
The trouble is, human value might turn out to talk about complicated mathematical objects, just like mathematicians can think about (simpler kinds of) them, and it’s not clear where to draw the line, at least to me while I still have too little understanding of what humane value is.
Reasoning about math objects, as opposed to just patterns of the world, seems to be analogous to reasoning about the world, as opposed to just patterns in observation. I don’t believe there has to be a boundary around physics, a kind of “physical solipsism”. And limitations of representation don’t seem to solve the problem, as formal systems might be unable to capture particular classes of models of interest, but they can be seen as intended to elucidate properties of those models.
In set theory there’s a formal symbol that’s read “there exists”, and a pair of formal symbols that are read “there doesn’t exist”. Do you think these symbols should be understood in either of your two useful senses?
It is possible to read the existential quantifier as “for some” instead of “there exists … such that”. I often do this myself, just for euphony (and to match the dual quantifier, read “for all”, or better “for each”). But Graham Priest (pdf) has argued that the “there exists” reading is a case of ontological sleight of hand that should be resisted; in fact, he rejects the term “existential quantifier” for “particular quantifier” (and a web search for this will turn up more on the subject).
I can’t think of a situation where I would accept one but not the other of “there exists x such that—” and “for some x—”. Do you have an example?
Godel has a very interesting paper about syntax for intuitionism, where he introduces a new operator read “there exists constructively.”
Priest (top of page 3 in the PDF above, numbered page 199) suggests an example:
In symbols:
Turning this back into English:
But not this:
One could rescue this by claiming that x exists in the speaker’s past thoughts but not in reality, or something like that. But then an uncountable ordinal may also exist in the thoughts of mathematicians without existing in reality.
There are many models of interest in set theory, with different mutually exclusive properties. A logical statement makes sense in context of axioms or intended model. I didn’t take Eliezer’s comment as referring to either of these technical senses (it’s not expecting provability of nonexistence from standard axiom systems, since they just assert existence in question, the alternative being asserting inconsistency, which would be easier to state directly; and standard model is an unclear proposition for set theory, there being so many alternatives, with one taken as the usual standard containing the elements in question). So I was talking about “ontological” senses of “existence” instead.
ZF proves in formal symbols “there exists a smallest uncountable ordinal,” and I guess you are saying that it does not mean that in an ontological sense. But then what is the ontological payoff of this proof?
Don’t know, maybe not denying that the idea is consistent, and so doesn’t “doesn’t exist” in that sense?
Like any proof in a formal system, you can conclude that “the idea is consistent unless the formal system is inconsistent.” But that’s a tautology. If you’re not willing to say that ZF refers to things in the real world i.e. has ontological content, why aren’t you skeptical of it?
I wasn’t saying that. If you believe that a formal system captures the idea you’re considering, in the sense of this idea being about properties of (some of) the models of this formal system, and the formal system tells you that the idea doesn’t make sense, it’s some evidence towards the idea not making sense, even though it’s also possible that the formal system is just broken, or that it doesn’t actually capture the idea, and you need to look for a different formal system to perceive it properly.
ZF clearly refers to lots of things not related to the physical world, but if it’s not broken (and it doesn’t look like it is), it can talk about many relevant ideas, and help in answering questions about these ideas. It can tell whether some object doesn’t hold some property, for example, or whether some specification is contradictory.
(I know a better term for my current philosophy of ontology now: “mathematical monism”. From this POV, inference systems are just another kind of abstract object, as is their physical implementation in mathematicians’ brains. Inference systems are versatile tools for “perceiving” other facts, in the sense that (some of) the properties of those other facts get reflected as the properties of the inference systems, and consequently as the properties of physical devices implementing or simulating the inference systems. An inference system may be unable to pinpoint any one model of interest, but it still reflects its properties, which is why failure to focus of a particular model or describe what it is, is not automatically a failure to perceive some properties of that model. Morality is perhaps undefinable in this sense.)
This is again not the sense I discussed. A claim that an uncountable ordinal “doesn’t exist” has to be interpreted in a different way to make any sense. A claim that it does doesn’t need such excursions, and so the default senses of these claims are unrelated.
I don’t think that it’s fair to characterise the B-F paradox this way. The argument of B-F is that, given any collection S of well-orderings closed under taking sub-well-orderings, S cannot be among the well-orderings represented in S itself. There is nothing paradoxical here. (I’m not sure whether this matches the content of Cesare Burali-Forti’s 1897 paper, which I haven’t read and of which I’ve heard conflicting accounts, but the secondary sources all seem to agree that he did not believe that he had found a paradox. ETA: After following the helpful link from komponisto, I see that sadly this is not how B-F himself viewed the matter.)
Now, if you add the assumption of an absolute collection of all well-orderings, then you get a paradox. But an absolute collection of (say) all finite well-orderings leads to no paradox; we just know that this collection is not finite. And an absolute collection of all countable well-orderings leads to no paradox either; we just know that this collection is not countable. And so on.
Of course, none of this shows that such collections actually exist. If you said that you don’t really believe in uncountable ordinals (perhaps on the grounds that they’re not needed for applications of mathematics to the real world), I would not have commented (except maybe to agree); but calling them incredible (as you seem to do, counting them as evidence against set theory, indeed among the strongest that you know) goes far beyond what I would consider justified.
You can read Burali-Forti’s 1897 paper here
Thanks!
There seems to be controversy about “exist” and “out there”, can you taboo those?
For example, are you saying the you think Ultimate Ensemble does not contain structures that depend on them, or that they lead to an inconsistency somewhere, or simply that your utility function does not speak about things that require them, or what exactly?
This isn’t a much simple/weaker claim than other possible meanings for “I just have trouble believing”.
Their underlying other utility functions would be contagious. For example, if my utility function requires them, then someone of whom it is accurate to say that “His utility function does not speak about things that require them” would’t be able to include in his utility function my desires, or desires of those who cared about my desires, or desires of people who cared about the desires of people who cared about my desires, and so forth.
Eliezer cares about some people, some people care about me, and the rest is six degrees of Kevin Bacon.
The most extreme similar interpretation would have to be a statement about human utility functions in general.
I don’t know what it means to care about the existence of the smallest uncountable ordinal (as opposed to caring that this existence can be proved in ZF, or cannot be refuted in second-order arithmetic, or something like that). Can we taboo “smallest uncountable ordinal” here?
well, yea, presumably it implies he believes all humans have that trait, but he could still accept superhappies or papperclipers caring about it say.
In real life, I’ve had some trouble recently admitting I hadn’t thought of something when it was plausible to claim I had. I think that admitting it would/will cost me status points, as it does not involve rationalists, “rationalists”, aspiring rationalists, or “aspiring rationalists”.
Are you sure you chose the phrase “simply that your utility function does not speak about things that require them” to describe the state of affairs where no human utility function would have it, and hence it would be unimportant to Eliezer?
If you see the thought expressed in my comment as trivially obvious, then:
1) we disagree about what people would find obvious, 2) regardless of the truth of what people find obvious, you are probably smarter than I to make that assumption, rather than simply less good at modeling other humans’ understanding, 3) I’m glad to be told by someone smarter than I that my thoughts are trivial, rather than wrong.
The comment wasn’t really intended for anyone other than Eliezer, and I forgot to correct for the halo making him out to me basically omniscience and capable of reading my mind.
I think he actually might intrinsically value their desires too. One can theoretically make the transition from “human” to “paperclip maximizer” one atom at a time; differences in kind are the best way for corrupted/insufficiently powerful software to think about it, but here we’re talking about logical impurity, which would contaminate with sub-homeopathic doses.
Well, in that case it’s new information and we can conclude that either his utility function DOES include things in those universes that he claim can not exist, or it’s not physically possible to construct an agent that would care about them.
I would say “care dependent upon them”. An agent could care dependent upon them without caring about them, the converse is not true.
That’s even wider, although probably by a very small amount, thanks!
For essentially the same reasons I have trouble believing that the first infinite ordinal exists.
Finite ordinals are computable, but otherwise your remarks still apply if you swap out “countable” for “finite.” According to ZF there are uncomputable sets of finite ordinals, so you can’t verify that they are well-ordered algorithmically.
So what you’re saying is that you don’t believe the natural numbers exist.
The natural numbers exist in about the strongest possible sense: I can get a computer program to spit them out one by one, and it won’t stop until it runs out of resources. It’s more accurate to say I don’t believe that they’re well-ordered, see here.
You might find my reasoning preposterous, I only wanted to point out that it’s essentially the same as EYs reasoning about uncountable ordinals.
Set theory is just a made up bunch of puzzle pieces (axioms) and some rules on how to fit them together (logic) so it’s weird to hear you lot talking about “existence” of a set with some property P as something other than whether or not the statement “exists X, P(X)” has a proof or not. I thought Hilbert’s finitist approach should have slain Platonism long ago.
The following is a comment by John Baez, posted on Google+ where I linked to this thread:
— Jerry Bona
This makes it sound like believing in an uncountable ordinal is equivalent to AC, which would make things easier—lots of mathematicians reject AC. But you might not need AC to assert the existence of a well-ordering of the reals as opposed to any set, and others have claimed that weaker systems than ZF assert a first uncountable ordinal. My own skepticism wasn’t so much the existence of any well-ordering of the reals (though I’m willing to believe that no such exists), my skepticism was about the perfect, canonical well-ordering implied by there being an uncountable ordinal onto whose elements all the countable ordinals are mapped and ordered. Of course that could easily be equivalent to the existence of any well-ordering of the reals.
No they don’t (*). Your saying this explicitly somewhat confirms my brain’s natural, automatic assumption that your error here (and in similar comments in the past—“infinite set atheism” and all that business) is as much sociological as philosophical: all along, I instinctively thought, “he doesn’t seem to realize that that’s a low-status position”.
ZFC is considered the standard axiom system of modern mathematics. I have no doubt that if an international body (say, the IMU) were to take a vote and choose a set of “official rules of mathematics”, the way (say) FIDE decides on the official rules of chess, they would pick ZFC (or something equivalent).
Now it’s true, there are some mathematicians who are contrarians and think that AC is somehow “wrong”. They are philosophically confused, of course; but, more to the point here in this comment, they are a marginal group. (In fact, even worrying about foundational issues too much—whatever your “position”—is kind of a low-status marker itself: the sociological reality of the mathematical profession is that members are expected to get on with the business of proving impressive-looking new theorems in mainstream, high-status fields, and not to spend time fussing about foundations except at dinner parties.)
See also this comment of mine.
(*) I don’t know the numbers, or how you define “lots”, and there are a large number of mathematicians in the world, so technically I don’t know if it’s literally false that “lots” of mathematicians would say that they “reject AC” . But the clear implication of the statement—that constructivism is a mainstream stance—most definitely is false.
I think you are stating these things too confidently.
Most mathematicians could not state the axioms of ZFC from memory. My suspicion is that AC skepticism is highest among mathematicians who can.
One piece of evidence that AC skepticism is not low-status is that papers and textbooks will often emphasize when a proof uses AC, or when a result is equivalent to AC. People find such things interesting.
You could make a stronger case that skepticism about infinity is regarded as low-status.
But what do status considerations have to do with whether Yudkowsky’s beliefs and hunches are justified?
I don’t see why this is even relevant, but for what it’s worth, I don’t particularly share this suspicion: I would expect those who know the axioms from memory to be more philosophically sophisticated (i.e. non-Platonist), and to be more likely to be familiar with technical results such as Gödel’s theorem that ZFC is as consistent as ZF.
My own impression is that professed “AC skepticism” (scarequotes because I think it’s a not-even-wrong confusion) is most correlated not with interest in logic and foundations, but with working in finitary, discrete, or algebraic areas of mathematics where AC isn’t much used.
The fact that people find such things interesting is at best extremely weak evidence for the proposition that constructivism and related positions are mainstream. (After all, I find such things interesting!)
As I pointed out in the comment linked to above, there is a difference between dinner-party acknowledgement of constructivism (which is widespread) and actually taking it seriously enough to worry about whether one’s results are correct (which would be considered eccentric).
If AC skepticism were not low-status, you would expect to find papers and textbooks actively rejecting AC results, rather than merely mentioning in a remark or footnote that AC is involved. (Such footnotes are for use at dinner parties.)
And also, texts just as frequently do not bother to make apologies of the sort you allude to. A fairly random example I recently noticed was on p.98 of Algebraic Geometry by Hartshorne, where Zorn’s Lemma is used without any more apology than an exclamation point at the end of the (parenthetical) sentence.
It tends to irritate me when people get something wrong which they could easily have gotten right by using a standard human heuristic (such as the “status heuristic”, noticing what the prestigious position is).
This is also my experience.
They’re also more likely to know Cohen’s theorem that ZF + not(AC) is also just as consistent. And of course, being philosophically sophisticated, it’s clear to me that they would be more likely to realise that the axioms of ZFC are fairly arbitrary and no better than many others. They’re also more likely to know, and to appreciate the philosophical significance of, that there are many axiom systems that are strong enough to do most mathematics (including all concretely applied mathematics) and yet much weaker (hence more surely consistent) than ZFC (although this has little to do with AC as such).
However, when arguing about what philosophically sophisticated people are going to think, we’re both naturally inclined to think that they’ll agree with ourselves, so our impressions about that prove nothing.
You do find such things (but they are mostly published in certain journals, which we can tell are low-status, since such things are published in them).
I’m not sure about that. You and komponisto seem to be using ‘philosophically sophisticated’ to contrast with Platonism. This use strikes me as similar to how arguing that ‘death is good’ is sophisticated, i.e., showing of your intelligence by providing convincing arguments for a position that violates common sense. In this case arguing that mathematical statements don’t have inherent truth value.
Remember just because you can make a sophisticated sounding argument for a preposition doesn’t mean its true.
Mathematica statements do have inherent truth value, but that value is relative to the axioms. And as far as the axioms go, the most you can say is that a system of axioms is consistent, and beyond that you get into non-mathematical statements. What exactly is sophisticated about this?
Yes, which agrees with my complaint quoted above. Neither of us is a Platonist, so we both assume that philosophically sophisticated people won’t be Platonists, although we derive different things thereafter.
I’m certainly not trying to show off my intelligence. I just think that the idea of inherent truth value for abstract statements about completed infinities violates common sense!
If that’s so, what accounts for your intuition that ZF and other systems for reasoning about completed infinities are consistent?
To the extent that I have this intuition, this is mostly because people have used these systems without running into inconsistencies so far. (At least, not in the systems, such as ZF, that people still use!)
But strictly speaking, ‘ZF is consistent.’ is not a statement with an absolute meaning, because it is itself a statement about a completed infinity. I have high confidence that no inconsistency in ZF has a formal proof of feasible length, but I really have no opinion about whether it has an inconsistency of length 3^^^3; we haven’t come close to exploring such things.
(Come to think of it, I believe that my Bayesian probability as to whether ZF is consistent to such a degree ought to be quite low, for essentially the same reason that a random formal system is likely to be inconsistent, although I’m not really sure that I’ve done this calculation correctly; I can think of at least one potential flaw.)
I cannot speak for komponisto about any of this, of course.
I’m mostly with you.
These feasibility issues are definitely interesting. Another possibility is that there is a formal proof of feasible length, but no feasible search will ever turn it up. (Well, unless P = NP). Yet another possibility is that a feasible search will turn it up, I certainly regard it as more likely than most people do.
I agree that this counts as evidence, but it’s possible to overestimate it. Foundational issues hardly ever come up in everyday mathematics, so the fact that people are able to prove astonishing things about 3-manifolds without running into contradictions I regard as very weak evidence in favor of ZF. There have been a lot of man-hours put into set theory, but I think quite a bit less than have been put into other parts of math.
JoshuaZ and I had a discussion about this a while ago, starting here.
This reminds me of people who argue that, because P != NP, we will never prove this. (The key to the argument, IIRC, is that any proof of this fact will have very high algorithmic complexity.) I’m not sure how to find this argument now. (There is something like it one of Doron Zeilberger’s April Fools opinions.)
Yes, these results should be formalisable in higher-order arithmetic (indeed _n_th order for n a single-digit number). It is the set theorists’ work with large cardinals and the like that provides the only real evidence for the consistency of such a high-powered system as ZF.
Yes; that’s definitely within the scope of my “such as”!
Not quite. Remember that I gave a specific meaning for “philosophically sophisticated”: I said it meant “non-Platonist”. And what I meant by that, here, is not believing that AC (or any other formal axiom) represents some kind of empirical claim about “the territory” that could be “falsified” by “evidence”, despite being part of a consistent axiom system.
I claim the situation with AC is like that of the parallel postulate: it makes no sense to discuss whether it is “true”; only whether it is “true within” some theory.
What I meant was more like: you would find some substantial proportion (say 20% or more) of textbooks being used to teach analysis (say) to graduate students in mathematics omitting all theorems which depend on AC.
Then you would have a controversy on your hands.
Yes, and I was happy to take it this way, as I am certainly no Platonist. Surely only a Platonist could believe that AC is true; we philosophically sophisticated people know that you can make whatever assumptions you want! And so naturally a theorem with a proof using AC is a weaker result than the same theorem with a proof that doesn’t, since it holds under fewer sets of assumptions, and thus the latter is preferred. Meanwhile, a theorem with a proof using not(AC) is just as valid as the same theorem with a proof using AC; it’s less useful only because it has fewer connections with the published corpus of mathematics, but that’s merely a sociological contingency.
Is it often the case that you need to assume the negation of AC for a proof to hold? AC comes up in seemingly-unrelated areas when you need some infinitely-hard-to-construct object to exist; I can’t imagine a similar case where you’d assume not(AC) in, e.g., ring theory.
As usual, the negation of a useful statement ends up not being a useful statement. I don’t think anyone works with not(AC), they work with various stronger things that imply not(AC) but actually have interesting consequences.
That’s intriguing. Do you have any examples of what people actually work with?
Sniffnoy may have more examples, but here are some that I know:
Every subset of the real line is Lebesgue-measurable.
Every subset of the real line has the Baire property (in much the same vein as the preceding one).
The axiom of determinacy (a statement in infinitary game theory).
Adding the first two to ZF + DC (dependent choice) is consistent (assuming that ZFC + Con(ZFC) is consistent, as just about everybody believes), and this gives a “dream universe” for analysis in which, for example, any everywhere-defined linear operator between Hilbert spaces is bounded.
This isn’t quite right. The consistency of ZF + DC + “every subset of R is Lebesgue measurable” is equivalent to the consistency of an inaccessible cardinal, which is a much stronger assumption then the consistency of ZFC + Con(ZFC).
Sorry, my mistake. Still, set theorists usually believe this.
Yes, indeed!
Yes—but it needs to be stressed that this doesn’t distinguish AC from anything else! (Also, depending on the context, there may other criteria for selecting proofs besides the strength or weakness of their assumptions.)
If only people would talk about whether they prefer working in ZFC or ZF+not(C) (or plain ZF), or better yet what they like and don’t like about each, rather than whether AC is “true” or how “skeptical” they are.
Yes, indeed, that would be much more sophisticated! But scepticism of the orthodoxy can be the first step to such sophistication. (It was for me, although in my case there were also some parallel first steps that did not initially seem connected.)
Not entirely. If the only known proof for a result assumes choice, then a proof that doesn’t use choice will almost certainly be publishable.
Using an exclamation mark like that is a pretty rare thing to do. You wouldn’t for example see this if one used the axiom of replacement. The only other axiom that would be in a comparable position is foundation but foundation almost never comes up in conventional mathematics. Hartshorne is writing for a very advanced audience so I think putting an exclamation mark like that is sufficient to get the point across especially when one is using choice in the form of Zorn’s lemma.
This seems to fit my impression as well.
Incidentally, for what it is worth, your claim that rejection of AC is low status seems to be possibly justified. I know of two prominent mathematicians who explicitly reject AC in some form. One of them does so verbally but seems to be fine teaching theorems which use AC with minimal comment. The other keeps his rejection of AC essentially private.
Of course it’s worth noting that axiom of replacement doesn’t come up much either, though obviously the case there isn’t quite as extreme as with foundation.
We appear to have misunderstood each other, having something different in mind by words like “skepticism” and “reject.” I agree Con(ZF) entails Con(ZFC), and that every educated mathematician knows it. Beyond that I don’t have a good handle on what you’re saying, or even whether you disagree with Yudkowsky, or me. Are you saying that mathematicians pay lip service to constructivism, but ignore it in their work? Are you additionally saying that there is something false about constructivist ideas?
That doesn’t sound like such a great heuristic to me...
This seems problematic. Many mathematicians work on foundations and are treated with respect. It isn’t that they are low status so much that a) most of the really big foundational issues are essentially done b) foundational work rarely impact other areas of math, so people don’t have a need to pay attention to foundations. There also seems to be an incredible degree of confidence in claiming that those skeptical of AC are ” philosophically confused, of course”.
It’s somewhat pertinent to point out that the highest rated contributor at MathOverflow is none other than Joel David Hamkins of ‘foundations of set theory’ fame.
More than that, I daresay that they’d pick something much stronger than ZFC, probably ZFC with a large cardinal axiom. (And the main debate would be how large that cardinal should be.)
And anecdotally it seems that the AC skepticism that does exist seems to largely come from constructivism, so if we rule out that (since it doesn’t seem that Eliezer wants to go all constructivist on us :) ), it’s even less so.
I’m not sure what you mean by “constructivism” here; I usually hear that term referring to doubting the law of excluded middle (when applied to statements quantified over infinite sets), but I know several mathematicians who doubt the axiom of choice without doubting excluded middle.
I should also clarify the difference between doubting AC and denying AC. If you deny AC, then you believe that it is false, and hence any theorem whose only known proofs use AC is no theorem at all; it might be true, but it has not been proved. (And if AC follows from it, then it must in fact be false.) If you only doubt AC, however, then you simply believe that a theorem with a proof that uses AC is a weaker result than the same theorem with a proof that doesn’t, and so the former theorem is still worth publishing but the latter is naturally preferred.
This seems such an obvious position to me that I doubt everything in mathematics (although there is a core which I generally assume since mathematics without it seems uninteresting (although I’m open to being proved wrong about this)).
Both AC and its negation can be made sense of in set theory. One or the other can be considered more interesting, or more relevant in the context of a particular problem, but given the extensive experience with mathematics of foundations we can safely study the properties of either. The question of which way “lies the truth” seems confused, since the alternatives coexist. Ultimately, some axiomatic options might turn out to be morally irrelevant, but that’s not a question that human philosophers can hope to settle, and all simple things are likely relevant at least to some extent.
Since I found the other replies insufficiently stark here, let me just say that it is not. The details are in this subthread.
On the contrary, you need almost the full strength of AC to establish that a well-ordering of the reals exists. Like you say, you don’t need it to construct uncountable ordinals, or to show that there is a smallest such. Cantor’s argument constructively shows that there are uncountable sets, and you can get from there to uncountable ordinals by following your nose.
Is this because you can’t prove aleph-one = beta-one? I’m Platonic enough that to me, “well-order an uncountable set” and “well-order the reals” sound pretty similar.
No something sillier. You can prove the axiom of choice from the assumption that every set can be well-ordered. (Proof: use the well-ordering to construct a choice function by taking the least element in every part of your partition.)
If one doesn’t wish to assume that every set has a well-ordering, but only a single set such as the real numbers, then one gets a choice-style consequence that’s limited in the same way: you can construct choice functions from partitions of the real numbers.
I’d hardly call a well-ordering on one particular cardinality “almost the full strength of AC”! I guess it probably is enough for a lot of practical cases, but there must be ones where one on 2^c is necessary, and even so that’s still a long way from the full strength...
I just have a hard time imagining someone who was happy with “c is well-ordered” but for whom “2^c is well-ordered” is a bridge too far.
Hm, agreed. I guess not so much “the full strength” but “the full counterintuitiveness”? Where DC uses hardly any of the counterintuitiveness, and ultrafilter lemma uses nearly all of it?
Uh, that’s a lot more than “Platonism”… how was anyone supposed to guess you’ve been assuming CH?
Edit: To clarify—apparently you’ve been thinking of this as “I can accept R, just not a well-ordering on it.” Whereas I’ve been thinking of this as “Somehow Eliezer can accept R, but not a cardinal that’s much smaller?!”
Edit again: Though I guess if we don’t have choice and R isn’t well-orderable than I guess omega_1 could be just incomparable to it for all I know. In any case I feel like the problem is stemming from this CH assumption rather than omega_1! I don’t think you can easily get rid of a smallest uncountable ordinal (see other post on this topic—throwing out replacement will alllow you to get rid of the von Neumann ordinal but not, I don’t think, the ordinal in the general sense), but if all you want is for there to be no well-order on the continuum, you don’t have to.
That’s how I remember it, although I don’t know a reference (much less a proof). All we know is that omega_1 is not larger than R.
I thought that could be proven without reference to the existence of a set of them, just from general facts about well-ordering? And then the only question is whether the class of all countable ordinals is set-sized. Which it must be since they can all be realized on N. As long as you accept the continuum, anyway! I don’t see how the continuum can possibly be more acceptable than omega_1.
I think we may have something of a clash of backgrounds here. The reason I’m inclined to take the real continuum seriously is that there are numerous physical quantities that seem to be made of real or complex numbers. The reason I take mathematical induction seriously is that it looks like you might always be able to add one minute to the total number of minutes passed. The reason I take second-order logic seriously is that it lets me pin down a single mathematical referent that I’m comparing to the realities of space and time.
The reason I’m not inclined to take the least uncountable ordinal seriously is because, occupying as it does a position above the Church-Kleene ordinal and all possible hypercomputational generalizations thereof, it feels like talking about the collection of all collections—the supremum of an indefinitely extensible quality that shouldn’t have a supremum any more than I could talk about a mathematical object that is the supremum of all the models a first-order set theory can have. If set theory makes the apparent continuum from physics collide with this first uncountable ordinal, my inclination is to distrust set theory.
How can you say this after having read this thread?
If you believe in second-order model theory, then you believe in set theory. (However, by limiting it to second order over the natural numbers, without going on to third order, you are not obligated to believe in uncountable ordinals.)
ETA: It is very imprecise to compare second-order model theory and set theory like this. Already model theory is set theory, of course, albeit (potentially, not in practice) set theory without power sets. I should just leave the model theory out of it and say:
I have my problems with the other two, but this is the only one I don’t understand. What do you mean?
You seem to accept the notion that all finite numbers have a supremum. Why not just iterate whatever process accounts for that?
http://en.wikipedia.org/wiki/Second-order_logic#Expressive_power—you can’t talk about the integers or the reals in first-order logic. You can have first-order theories with the integers as a model, but they’ll have models of all other cardinalities too. http://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem
First of all, I’ve never seen an aleph-null, just one, two, three, etc. Accepting that the integers have a supremum is a whole different kettle of fish from accepting that the collection of finite integers seems to go on without bound. Second, taking a supremum once, using a clearly defined computable notation and a halting machine that can compare any two representations, is a whole different kettle of fish than talking about the supremum of all possible ways to define countable well-orderings to and beyond computable recursion.
It’s more accurate to say that you can’t talk about arbitrary subsets of the integers or the reals in first-order logic.
I agree. This is the difference between completed and potential infinity. Nelson.
I’m not so sure. Everything you’ve ever talked about, uncountable ordinals and all, you’ve talked about using computable notation. Computable, period is a whole different kettle of fish.
OK, you say you don’t accept that sort of uncomputable leap to the end. The problem is that, AIUI, you’re already accepting it as soon as you accept the power set of N. (Of the various “axioms of power” of ZFC, power set is the only one needed here. And if you just want omega_1, you don’t need arbitrary power sets, just that of N. I mean really you want P(N x N), but since N is in an easily-described bijection with N x N, it shouldn’t make a difference; just use a pairing function instead of proper ordered pairs.) The construction of omega_1 from P(N) is pretty straightforward, really, and doesn’t use any of ZFC’s other powerful axioms. Maybe you can somehow have the reals without P(N)? I.e. without binary expansions? shrug This is getting rather far away from what I know. Constructivists—well, not the milder ones who just reject excluded middle, but the stricter ones who don’t like impredicativity (whatever that might be, don’t ask me) -- don’t accept the axiom of power sets; they consider it just as much an unjustified leap to the end.
Of course you could always try summoning TobyBartels and ask him how the constructivists do it. When you say these sorts of things I’m a little of surprised you haven’t gone constructivist already. But I guess you like classical logic. :)
(By the “axioms of power”, I mean replacement, power set, and choice; the ones anyone might object to. Well, foundation is objectionable too, but it’s more of an axiom of weakness. Healing Salve as opposed to Ancestral Recall. :P Also looking things up apparently the no-impredicativity constructivists insist on weakening axiom of separation as well? Well, I think their weaker version should suffice here. Again, I am saying these things without carefully checking them because hopefully TobyBartels will show up and correct me if I am wrong. :) )
You either need P(P(N)) or something like an axiom of quotient sets to take the equivalence classes that are the actual elements of this version of omega_1. I presume (but haven’t checked) that this is why J_2 has R but not omega_1 (although J_2 is not written in set-theoretic language, so you have to encode these).
Assuming you accept classical logic, then P(N) may be constructed as a subset of R: that famous fractal the Cantor set.
Just about everything that I know about predicative mathematics is distilled here. There I describe two schools, and the constructive one (which is less predicative than the classical one!) is the only one that I know well.
Crap, looks like I should have checked that after all! OK, I guess if Eliezer accepts R but not P(R) then there’s less of a problem here than I thought. :P
Edit: Nevermind, this line was asking what J_2 was, you’ve given a reference elsewhere.
Oh, that works. Should have thought of that.
Huh, so there’s two separate things going on here. Constructivism in the sense of no-excluded-middle, and I guess “predicativism” in the sense of, uh, things should be predicative? I probably should have realized those were largely independent, but didn’t. How is the constructive version less predicative? Is it just the function set issue?
Would Chaitin’s constant also be one of these “superlogical” things that cannot “exist” “out there”?
I know that you rescinded this question, but intuitionists (at least) would answer it affirmatively.