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.

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:Sniffnoy
14 September 2011 09:57:35PM
*
0 points
[-]

Dependent choice.

Edit: I feel silly, this doesn't use dependent choice at all. OK, so the answer to that is "yes". However it does require enough structure to be able to talk about infinite sequences, unless there's some other way of defining well-foundedness.

Comment author:TobyBartels
17 September 2011 09:13:47PM
*
3 points
[-]

There are (at least) three ways to define well-foundedness, roughly:

one which requires impredicative (second-order) reasoning;

one which requires nonconstructive reasoning (excluded middle);

one which requires infinitary reasoning (with dependent choice, and also excluded middle actually).

They may all be found at the nLab article on the subject; this article promotes the first definition (since we use constructive mathematics there much more often than predicative mathematics), but I think that the middle one (Lemma 2 in the article) is actually the most common. However, the last definition (which you are using, Lemma 1 in the article) is usually the easiest for paradoxes (and DC and EM aren't needed for the paradoxes either, since they're used only in proofs that go the other way).

Comment author:Sniffnoy
17 September 2011 10:33:04PM
*
1 point
[-]

One thing bothering me -- is there any way to define a well-founded set without using infinitary reasoning? It's easy enough to say that all sets are well-founded without it, by just stating that ∈ is well-founded -- I mean, that's what the standard axiom of foundation does, though with the classical definition -- but in contexts where that doesn't hold, you need to be able to distinguish a well-founded set from an ill-founded one. Obvious thing to do would be to take the transitive closure of the set and ask if ∈ is well-founded on that, but what bugs me is that constructing the transitive closure requires infinitary reasoning as well. Is there something I'm missing here?

Comment author:TobyBartels
18 September 2011 01:47:33AM
0 points
[-]

I know one way; it cannot be stated in ZFC↺ (ZFC without foundation), but it can be stated in MK↺ (the Morse–Kelley class theory version): a set is well-founded iff it belongs to every transitive class of sets (that is every class K such that x ∈ K whenever x ⊆ K); it is immediate that we may prove properties of these sets by induction on membership, and a set is well-founded if all of its elements are, so this is a correct definition. However, it requires quantification over all classes (not just sets) to state.

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.

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.

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.

## Comments (653)

Best*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?

*0 points [-]Dependent choice.

Edit: I feel silly, this doesn't use dependent choice at all. OK, so the answer to that is "yes". However it does require enough structure to be able to talk about infinite sequences, unless there's some other way of defining well-foundedness.

*3 points [-]There are (at least) three ways to define well-foundedness, roughly:

They may all be found at the nLab article on the subject; this article promotes the first definition (since we use constructive mathematics there much more often than predicative mathematics), but I think that the middle one (Lemma 2 in the article) is actually the most common. However, the last definition (which you are using, Lemma 1 in the article) is usually the easiest for paradoxes (and DC and EM aren't needed for the paradoxes either, since they're used only in proofs that go the other way).

*1 point [-]One thing bothering me -- is there any way to define a well-founded

setwithout using infinitary reasoning? It's easy enough to say that all sets are well-founded without it, by just stating that ∈ is well-founded -- I mean, that's what the standard axiom of foundation does, though with the classical definition -- but in contexts where that doesn't hold, you need to be able to distinguish a well-founded set from an ill-founded one. Obvious thing to do would be to take the transitive closure of the set and ask if ∈ is well-founded on that, but what bugs me is that constructing the transitive closure requires infinitary reasoning as well. Is there something I'm missing here?I know one way; it cannot be stated in ZFC↺ (ZFC without foundation), but it can be stated in MK↺ (the Morse–Kelley class theory version): a set is well-founded iff it belongs to every transitive class of sets (that is every class

Ksuch thatx∈Kwheneverx⊆K); it is immediate that we may prove properties of these sets by induction on membership, and a set is well-founded if all of its elements are, so this is a correct definition. However, it requires quantification over all classes (not just sets) to state.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.

Heh, I'd forgotten how simple Hartogs number was in general.

It's not clear to me that ZFC without regularity, replacement, infinity, choice, power set or foundation with a totally ordered field with the LUB property

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.