Eliezer_Yudkowsky comments on Harry Potter and the Methods of Rationality discussion thread, part 8 - Less Wrong

8 Post author: Unnamed 25 August 2011 02:17AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (653)

You are viewing a single comment's thread. Show more comments above.

Comment author: TobyBartels 28 August 2011 10:50:20PM 15 points [-]

At the secret inner double-witch school, everyone's most concerned with figuring out who the top-secret super-inner triple-witches are.

Comment author: Eliezer_Yudkowsky 30 August 2011 07:57:37AM 13 points [-]

The thought had occurred to me. And if you were a double witch, wouldn't you think it was pretty darned plausible that there were triple witches?

Comment author: Psy-Kosh 30 August 2011 05:04:55PM 14 points [-]

I want to be a first-uncountable-ordinal wizard. :)

Comment author: Eliezer_Yudkowsky 05 September 2011 06:54:03AM 0 points [-]

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: TobyBartels 05 September 2011 08:59:47AM 3 points [-]

Yes, and in fact it can be proved in weaker axiom systems than that.

Comment author: Psy-Kosh 05 September 2011 02:15:53PM 1 point [-]

Okay, are there any decent foundational theories that won't prove it?

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: shinoteki 05 September 2011 09:06:48PM *  3 points [-]

You don't need Z, third-order arithmetic is sufficient. Every set of ordinals is well-ordered by the usual ordering of ordinals.

Comment author: [deleted] 05 September 2011 09:30:10PM 0 points [-]

Only if you accept excluded middle.

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: Eugine_Nier 06 September 2011 06:08:40AM 2 points [-]

Why not go even further and declare yourself uncomfortable with any finite set of ordinals bigger then what you've personally written down?

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: Eugine_Nier 09 September 2011 01:16:33AM 2 points [-]

What about something like 10^100, i.e., something you could easily wright out in decimal but couldn't count to?

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: 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 [-]

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: Psy-Kosh 05 September 2011 02:15:16PM *  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. :)

Comment author: Alex_Altair 06 September 2011 02:12:02AM 7 points [-]

Perhaps this is math's revenge for you having tiled a hall in Hogwarts with pentagons. :)

But he didn't say regular pentagons. Pentagon tiles shown here. Also, he did say that Hogwarts has non-Euclidean geometry.

Comment author: ec429 23 September 2011 06:21:01PM 0 points [-]

Actually, my understanding was that he said it didn't have geometry at all, only topology.

Comment author: Eliezer_Yudkowsky 06 September 2011 12:41:38AM 2 points [-]

It's not Choice I have the problem with here, it's set theory.

Comment author: Alex_Altair 06 September 2011 02:13:02AM 2 points [-]

Do you think that uncountable sets don't exist, or that there is no way to order them such that one is first?

Comment author: Eliezer_Yudkowsky 06 September 2011 02:44:47AM -1 points [-]

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.

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.

Comment author: XiXiDu 07 September 2011 08:21:10AM 5 points [-]

One of my favorite examples are non-transitive dice.

Here is another page dealing with non-transitive dice that I liked.

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: Eliezer_Yudkowsky 07 September 2011 04:50:39AM 1 point [-]

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: Vladimir_Nesov 06 September 2011 08:19:07AM *  6 points [-]

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 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: komponisto 11 September 2011 09:05:08PM 2 points [-]

You can read Burali-Forti's 1897 paper here

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

http://en.wikipedia.org/wiki/Well-ordering_theorem

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.

Comment author: CronoDAS 07 September 2011 10:58:36AM 9 points [-]

"The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"

— Jerry Bona

Comment author: Eliezer_Yudkowsky 07 September 2011 04:08:11PM 1 point [-]

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

Comment author: Eliezer_Yudkowsky 08 September 2011 02:52:20AM 0 points [-]

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: [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: Eugine_Nier 06 September 2011 06:01:41AM 4 points [-]

For essentially the same reasons I have trouble believing that the first infinite ordinal exists.

So what you're saying is that you don't believe the natural numbers exist.

Comment author: cousin_it 14 September 2011 04:52:36PM *  0 points [-]

Would Chaitin's constant also be one of these "superlogical" things that cannot "exist" "out there"?

Comment author: TobyBartels 17 September 2011 09:18:44PM 0 points [-]

I know that you rescinded this question, but intuitionists (at least) would answer it affirmatively.

Comment author: Solvent 30 August 2011 08:39:42AM 6 points [-]

I'm reminded of the concept of information cascades: With every new level of witchness discovered, the probability of the next one increases.

Comment author: JoshuaZ 30 August 2011 05:18:44PM *  7 points [-]

There's a limit though since we have a decent estimate for how many wizards and witches there are in the world. That gives a strict upper bound on the total number of levels unless some of the levels are completely empty, tthat is something like every 12th level witch is also a 13th level witch. And if that's the case it isn't clear why the levels are being countered separately.

Comment author: NancyLebovitz 31 August 2011 08:07:12AM 5 points [-]

If there are much more powerful levels of magic, our estimate of the number of witches could be wildly off.

Comment author: JoshuaZ 31 August 2011 12:53:16PM 3 points [-]

How do you figure that? The double-wizard idea doesn't seem to be that there are apparent Muggles with some form of magic. It seems to be that that there are people who seem to be ordinary wizards but really have additional powers. So levels of wizardry should be strictly ordered.

Comment author: drethelin 31 August 2011 07:49:24PM 5 points [-]

regular wizards have little trouble concealing the existence of their entire culture from every muggle, so presumably double wizards could have similar levels of control over whether or not regular wizards can perceive them. Double witches might be a group that's separate from as well as a subset of regular witches

Comment author: TobyBartels 01 September 2011 03:29:42AM *  4 points [-]

So the Witches (when compared to Double Witches) aren't analogous to Muggles (when compared to Witches); they're analogous to people. Although we have heard rumours to the contrary, we Muggles tend to just think of ourselves as people, and any Witches that there may be are a special class of people; however (according to some versions of the rumours) there are actually quite a few Witches whom we would never perceive and therefore never even count as people. Similarly, although Witches have heard rumours to the contrary, they tend to just think of themselves as Witches, and any Double Witches that there may be are a special class of Witches; however (according to some versions of the rumours) there are actually quite a few Double Witches whom they would never perceive and therefore never even count as Witches.

Comment author: Normal_Anomaly 31 August 2011 09:27:33PM 6 points [-]

In canon, it sounded like some witches pretended to live ordinary lives, and others lived "off the grid" in the middle of nowhere. The same mix might happen with higher-order witches, with some attending Hogwarts, some pretending to be muggles, and others going unnoticed by anybody.

If there are an arbitrarily high number of witch-levels, then the limit is the earth's population, not the magical population. But that's only a potential limit, as witches of arbitrarily high level can support an arbitrarily high number of themselves on one planet (or go to other ones).