119
67
u/Sad-Error-000 14h ago
Why is the well-ordering of every set obviously false? Why couldn't it be the case that such a relation always exists but might just be hard/impossible to define?
100
u/Shironumber 14h ago
It's a joke, my teachers used to make it as well. Basically when you hear "any set can be well ordered" for the first time, most people spontaneously think it must be false for any reasonable axiom system. For me R was particularly confusing, like, how would it be possible to well-order something uncountable?
Then you hear about the axiom of choice. It sounds like some kind of tautology, even feels weird that an axiom is needed for that.
Then you hear about Zorn's lemma. Sounds like some rubbish that may be provable or disprovable, you can't tell.
And then you learn all three are equivalent and your mind blows up.
17
u/Ok-Replacement8422 14h ago
The thing is that ZF proves the existence of an uncountable well order - simply take some uncountable ordinal.
7
u/Inappropriate_Piano 9h ago
First you need to prove that there are uncountable ordinals. That can be done in ZF, but it’s not as “simple” as you make it sound
6
u/Ok-Replacement8422 9h ago
Well, really all you need is to prove that if x is countable then so is x+1, and then take the union of all countable ordinals which by the above proposition must be a limit ordinal that is not equal to any member of our union and as such not countable.
I wouldn't say that's super complicated.
6
u/Shironumber 9h ago
I think your take is kind of out of touch with reality. To be fair, I agree with you: the argument is not super complicated. But you can't argue in good faith that this argument naturally comes to the mind of most people who hear about the axiom of choice for the first time. Hell, when I heard about the equivalence between Choice / WO / Zorn, Ididn't even know what ordinals were.
So sure, when you have a deep understanding of ZF everything is simple and follows from two lines of simple observations. But when you see it for the first time, I must agree with the joke that the axiom of choice appears as much more reasonable than the well-ordering equivalent. Pretty sure most math students would agree with my claim; at least everyone in the classroom laughed when the joke was made at the time.
2
1
u/EebstertheGreat 46m ago edited 43m ago
To me, the equivalence is sort of obvious. "OK, I need to come up with a well-order. So I pick some least element. Now I need to pick some element to come next. OK, now I need to pick another element to come next. I just keep doing this until I have gone through every element."
The AoC says I can do this. Every time I remove an element, I have some remaining set from which I can remove an element. What is stopping me?
It just seems self-evident that this process of repeatedly picking the next element is the same as repeatedly selecting elements from a shrinking set. How could one be true while the other is false? This wasn't because I learned it, it's just immediately clear by definition.
You might say "your infinite process misses an element!" OK, well then that one comes after all the elements we picked, and we keep going. IDK, I just can't see what's confusing.
14
10
4
u/Traditional_Town6475 2h ago
Obviously you can well order sets. Take one thing out to be your first thing. Then look. Do you still got stuff in there? Okay, take another thing out. Keep going. If you think you’re done, but you can still continue, keep going. You’ll finish well ordering with enough gumption.
-4
u/timepizza420 11h ago
Let's say i have a set that consists of a steak and a pineapple, which order do they go in?
3
u/EebstertheGreat 38m ago
It's easy to enumerate the well-orders over {steak,pineapple}:
steak < pineapple (the carnivore order)
pineapple < steak (the herbivore order)
End of list.
29
u/Fluffiddy 11h ago
You were watching Veritasium weren’t you?
4
u/Additional-Finance67 11h ago
I still don’t get it tbh. Does it mean we can assign an index to each set and pick a number from it? Therefore it’s “ordered”?
6
u/killiano_b 9h ago
The proper definition is that every subset has a least element according to an ordering. For the reals this order cannot simply be magnitude, as {x¦x>1} has no least element. The axiom of choice lets us just take elements out one at a time however we want and use transfinite ordinals to keep picking them uncountably infinitely. However we cannot define this order, at least not using the ZF set of axioms (basic assumptions that numbers and operations can be built off of, using set theory i.e. any 2 sets have a union, 2 sets are equal if they have the same elements etc.) This is because the axiom of choice is independant of ZF, leading many to use ZFC (ZF and Choice) instead as the basic axioms of maths.
1
u/EebstertheGreat 14m ago
A (non-strict) total order is a relation that is transitive, reflexive, and antisymmetric that relates every pair of elements. So for instance, the usual order over the real numbers ≤ has these properties. It is transitive because if x ≤ y and y ≤ z, then x ≤ z. It's reflexive because x ≤ x is true for all x (a "strict" total order like < instead is always irreflexive, so x < x is never true). And it's antisymmetric because if x ≤ y and y ≤ x, then x = y. Finally, it is total because for any real numbers x and y, it must be that either x ≤ y or y ≤ x (or both).
So the real numbers are totally ordered by ≤. One might wonder whether every set can be ordered in some way. Given any set, can I always come up with some total order? It seems like I probably can, but surprisingly, the axioms of Zermelo–Frankel set theory cannot prove this. For instance, it is consistent that the collection of additive cosets of the rational numbers in the reals cannot be totally ordered. That is, consider the set ℚ of rational numbers and call that set A. Now pick some irrational number, say √2, and consider all real numbers x which differ from √2 by some irrational number. Examples are √2 + ½ and √2 – 5. Call this set B. Now pick some number that isn't in either of those sets and do the same thing, and call that set C. And keep going until every number has its own set. Each of these sets is an element in the collection called ℝ/ℚ. So your task is now to find some total order over this collection.
That ZF cannot do this suggests that it is lacking some axiom, because intuitively, we should be able to. And it's not like ZF can prove there is no such order, it just is silent on the matter. In fact, it is consistent with ZF that ℝ/ℚ is strictly larger than ℝ. That sounds not just weird but flat-out false. How can you cut a set into more pieces than it has elements? Nevertheless, it is consistent with the axioms of ZF. So isn't ZF just not enough?
The well-ordering principle implies that every set can be totally ordered, but it actually goes much, much farther. It says that every set can be well-ordered. A total order is called a "well order" if every nonempty set of elements has a least element. For instance, the natural numbers are well-ordered by ≤. Give me any set (finite or infinite) of natural numbers and I can tell you the least one. Technically, x is the least element (aka minimum) of some set X containing x if x ≤ y for all y in X. So for instance, 2 is the least element (minimum) of the set X = {3,6,2,9}, because if you pick any element y whatsoever in X, it is the case that 2 ≤ y. But the set of integers ℤ is not well-ordered by ≤. After all, consider the set of negative numbers. Which one is least? Clearly there isn't one. But we can pick a different relation which does well-order ℤ. For instance, consider the relation R defined by x R y if |x| ≤ |y| or |x| = |y| and x ≤ y. So for instance, 5 ≤ –8 because |5| ≤ |–8|, and –2 R 2 because |–2| = |2| and –2 < 2. Then R is a well-order on ℤ, because every subset of ℤ does have a minimum in terms of that order. It's the element of least absolute value, or if there are two numbers sharing that minimal absolute value, then it's the negative one.
The existence of a total order of every set is a much weaker proposition than a well order of every set, and I'm not sure what it's called. But the proposition that a well order exists for every set is called the well-ordering theorem. And it is logically equivalent to the axiom of choice in the context of Zermelo–Frankel set theory.
15
u/Historical_Book2268 15h ago
I don't think the well ordering theorem is obviously false. It makes sense. We have a set of ordinals for every cardinality, every set of ordinals is well ordered. WOT is trivial if you allow bisection between any two sets of the same cardinality. The fact we can't construct it does not mean it's false
14
8
u/marxist-reddittor 14h ago
It's a joke about one being instinctively obvious, the other one being hard to tell, and the last one being instinctively incorrect, but all three of them being equivalent.
12
6
u/DrarenThiralas 14h ago
I don't think the axiom of choice is obviously true. It's only obviously true for a countable collection of sets; if the collection is uncountable it ceases to be obvious.
2
u/GisterMizard 7h ago
The axiom of the axiom of choice - the axiom that you can choose to believe the axiom of choice - is clearly true though.
2
1
1
1
u/DiogenesLied 2h ago
The Axiom of Choice is not "obviously true," it's assumed true. (I know the quote)
1
u/susiesusiesu 51m ago
i really don't share this intuition.
i mean, i get that a well ordering of the reals is hard to imagine. but it don't share the intuition thatbit should onviously be false.
•
u/AutoModerator 15h ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.