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?

Comment author:TobyBartels
05 September 2011 08:28:04AM
10 points
[-]

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.)

Comment author:CronoDAS
05 September 2011 08:37:20AM
2 points
[-]

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?

Comment author:shinoteki
05 September 2011 03:23:19PM
3 points
[-]

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.

Comment author:TobyBartels
08 September 2011 08:38:03PM
*
1 point
[-]

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.)

Comment author:hairyfigment
05 September 2011 08:10:31PM
0 points
[-]

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.)

Comment author:[deleted]
05 September 2011 06:15:03PM
0 points
[-]

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.

Comment author:TobyBartels
09 September 2011 03:17:59AM
*
2 points
[-]

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.

Comment author:[deleted]
05 September 2011 09:56:42PM
-1 points
[-]

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.

Comment author:[deleted]
06 September 2011 04:25:17PM
0 points
[-]

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.

Comment author:[deleted]
09 September 2011 08:24:10AM
1 point
[+]
(2
children)

Comment author:[deleted]
09 September 2011 08:24:10AM
1 point
[-]

"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.

Comment author:TobyBartels
27 September 2011 06:57:04PM
*
1 point
[-]

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.

Comment author:TobyBartels
09 September 2011 01:52:32PM
0 points
[-]

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.

Comment author:benelliott
08 September 2011 09:57:14AM
1 point
[-]

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?

Comment author:[deleted]
08 September 2011 12:49:56PM
*
1 point
[+]
(3
children)

Comment author:[deleted]
08 September 2011 12:49:56PM
*
1 point
[-]

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.

Comment author:benelliott
08 September 2011 06:05:00PM
*
2 points
[-]

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).

Comment author:[deleted]
08 September 2011 08:55:18PM
4 points
[-]

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.

Comment author:benelliott
09 September 2011 10:51:24AM
1 point
[-]

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.

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.

Comment author:JoshuaZ
07 September 2011 02:01:15AM
*
7 points
[-]

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.

Comment author:JoshuaZ
07 September 2011 01:58:05PM
0 points
[-]

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.

Comment author:[deleted]
07 September 2011 11:45:19AM
3 points
[-]

All the axioms of ZF seem reasonable.

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?

Comment author:JoshuaZ
14 September 2011 02:44:40AM
*
2 points
[-]

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.

Comment author:Sniffnoy
14 September 2011 04:47:46AM
*
1 point
[-]

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.

Comment author:JoshuaZ
07 September 2011 04:09:07PM
2 points
[-]

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.

Comment author:JoshuaZ
08 September 2011 04:52:44AM
*
1 point
[-]

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.

Comment author:JoshuaZ
07 September 2011 02:02:38PM
*
3 points
[-]

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.

Comment author:[deleted]
07 September 2011 05:12:38PM
2 points
[-]

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.)

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.

Comment author:JoshuaZ
07 September 2011 05:12:32AM
*
4 points
[-]

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.

Comment author:Sniffnoy
07 September 2011 10:13:18PM
*
4 points
[-]

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.

Comment author:TobyBartels
11 September 2011 08:44:20PM
*
3 points
[-]

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.

Comment author:shinoteki
07 September 2011 06:19:04PM
4 points
[-]

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

Comment author:JoshuaZ
07 September 2011 07:21:43PM
*
1 point
[-]

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.

Comment author:[deleted]
07 September 2011 12:02:16PM
2 points
[-]

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.

Comment author:[deleted]
06 September 2011 10:50:07PM
0 points
[-]

(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?

Comment author:TobyBartels
11 September 2011 08:13:25PM
2 points
[-]

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).

Comment author:[deleted]
12 September 2011 01:34:58AM
*
0 points
[-]

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."

Comment author:TobyBartels
12 September 2011 06:35:31PM
*
0 points
[-]

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.

Comment author:[deleted]
07 September 2011 12:16:29AM
0 points
[-]

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?

Comment author:TobyBartels
11 September 2011 07:41:19PM
*
4 points
[-]

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.

Comment author:Armok_GoB
06 September 2011 09:06:27AM
4 points
[-]

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?

Comment author:lessdazed
06 September 2011 09:11:41PM
0 points
[-]

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.

Comment author:TobyBartels
07 September 2011 08:00:38PM
*
0 points
[-]

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?

Comment author:lessdazed
06 September 2011 09:40:30PM
1 point
[-]

well, yea, presumably

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.

Comment author:Armok_GoB
06 September 2011 09:51:32PM
0 points
[-]

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.

Comment author:XiXiDu
07 September 2011 08:33:03AM
3 points
[-]

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.

Comment author:komponisto
09 September 2011 04:03:06AM
4 points
[-]

lots of mathematicians reject AC

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.

Comment author:JoshuaZ
12 September 2011 12:19:30AM
6 points
[-]

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".

Comment author:Will_Newsome
14 September 2011 05:39:23AM
3 points
[-]

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.

Comment author:TobyBartels
11 September 2011 09:26:26PM
3 points
[-]

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.)

Comment author:[deleted]
10 September 2011 12:30:36AM
6 points
[-]

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?

Comment author:komponisto
10 September 2011 01:34:59AM
*
0 points
[-]

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).

Comment author:Sniffnoy
10 September 2011 03:12:39AM
2 points
[-]

(*) 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.

Comment author:TobyBartels
11 September 2011 09:24:37PM
2 points
[-]

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.

Comment author:[deleted]
07 September 2011 05:35:07PM
1 point
[+]
(7
children)

Comment author:[deleted]
07 September 2011 05:35:07PM
1 point
[-]

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.

Comment author:[deleted]
08 September 2011 01:22:11AM
4 points
[-]

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.

Comment author:Sniffnoy
08 September 2011 01:42:53AM
*
3 points
[-]

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.

Comment author:[deleted]
14 September 2011 10:36:56PM
2 points
[-]

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.

Comment author:Sniffnoy
07 September 2011 10:16:50PM
2 points
[-]

...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.

Comment author:TobyBartels
11 September 2011 10:01:31PM
*
3 points
[-]

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, ….)

Comment author:[deleted]
08 September 2011 03:34:40AM
2 points
[-]

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.

Comment author:[deleted]
08 September 2011 01:15:43PM
4 points
[-]

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.

Comment author:Sniffnoy
10 September 2011 03:40:26AM
*
0 points
[-]

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. :) )

Comment author:TobyBartels
11 September 2011 09:53:39PM
*
3 points
[-]

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.

Comment author:Sniffnoy
11 September 2011 10:21:20PM
*
2 points
[-]

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?

Comment author:[deleted]
06 September 2011 05:37:15AM
2 points
[-]

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.

Comment author:[deleted]
06 September 2011 04:03:20PM
2 points
[-]

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.

## Comments (653)

BestYou 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'tprove 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.

*1 point [-]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 had to look carefully in order to see that it doesn't

necessarilycontradict itself even though I should have known this fromGö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.)

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.

*3 points [-]You don't need Z, third-order arithmetic is sufficient.

Everyset of ordinals is well-ordered by the usual ordering of ordinals.Only if you accept excluded middle.

*2 points [-]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 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

isproblematic 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.*1 point [-]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

mightlead to a false statement, you are not logically omniscient and therefore wouldn't necessarily know if they did. Why not be uncomfortable with everything?*1 point [-]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

havegiven 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.*2 points [-]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.

*5 points [-]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

regularpentagons. Pentagon tiles shown here. Also, hedidsay 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.

*7 points [-]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?

*2 points [-]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.

*1 point [-]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?

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

addingaxioms!*1 point [-]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?

*3 points [-]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.)

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.

*4 points [-]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.

*4 points [-]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.*3 points [-]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

doesallow 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*1 point [-]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.

*2 points [-]The J_2 referenced in this subthread shoud do the trick. (See in particular number 6 in the page linked to by shinoteki there).

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.

*6 points [-]What does "existence" have to do with anything though? Even if the

real world, ormoralitydon'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).

*0 points [-]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."

*0 points [-]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

xexists 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.*0 points [-]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?

*4 points [-]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

Sof well-orderings closed under taking sub-well-orderings,Scannot be among the well-orderings represented inSitself. 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 thathedid not believe that he had found a paradox. ETA: After following the helpful link from komponisto, I see that sadly this isnothow B-F himself viewed the matter.)Now, if you add the assumption of an absolute collection of

allwell-orderings,thenyou get a paradox. But an absolute collection of (say) allfinitewell-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.

*0 points [-]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.

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

realsas opposed toany set, and others have claimed that weaker systems than ZF assert a first uncountable ordinal. My own skepticism wasn't so much the existence ofanywell-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 uncountableordinalonto 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.Since I found the other replies insufficiently stark here, let me just say that it is not. The details are in this subthread.

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

somemathematicians 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, evenworryingabout 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

implicationof the statement -- that constructivism is a mainstream stance -- most definitelyisfalse.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

somewhatpertinent 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.)

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?

*0 points [-]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,

Ifind 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

notbother to make apologies of the sort you allude to. A fairly random example I recently noticed was on p.98 ofAlgebraic Geometryby 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).

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

doubtingAC anddenyingAC. 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)).

*1 point [-]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.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.

*3 points [-]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 acceptR, but not a cardinal that's much smaller?!"Edit again: Though I guess if we don't have choice and

Risn'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.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.

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 bemoreacceptable 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

modelsa 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.*3 points [-]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

theintegers orthereals 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_theoremFirst 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.

*0 points [-]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 ofN. I mean really you want P(NxN), but sinceNis in an easily-described bijection withNxN, 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?shrugThis 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. :) )

*3 points [-]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

lesspredicative than the classical one!) is the only one that I know well.*2 points [-]Crap, looks like I should have checked that after all! OK, I guess if Eliezer accepts

Rbut not P(R) then there's less of a problem here than I thought. :PEdit: 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?

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.

*0 points [-]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.