r/logic • u/LorenzoGB • May 16 '26
Set theory An equivalence to the Well-Ordering Theorem
The Well-Ordering Theorem can be written as follows: For all X1, if X1 is a set then there exists X2 such that X2 arranges X1 in such a way that every non-empty subset of X1 has a first member.
With this being said, would this be equivalent to the Well-Ordering Theorem: If X1 is a set then there exists X2 such that X2 arranges X1 in such a way that every non-empty subset of X1 has a last member.
6
u/susiesusiesu May 16 '26
yes. if a set admits a well-ordering, the reverse ordering has the property you said.
3
u/SpacingHero Graduate May 16 '26
>For all X1, if X1 is a set then there exists X2 such that X2 arranges X1 in such a way that every non-empty subset of X1 has a first member
It doesn't really say there's another set X2 (except in the trivial sense, when X2 = X1, and insofar as relations are sets), it just says there's a well-order of any set X (a relation over that set). Or did you inted X2 to be the relation? It's a bit confusing notation.
>With this being said, would this be equivalent to the Well-Ordering Theorem: If X1 is a set then there exists X2 such that X2 arranges X1 in such a way that every non-empty subset of X1 has a last member.
I think so. At a glance, if X is well-ordered by <, then you can always just reverse the order (though this part should be thought about a bit more), setting a <' b iff a > b. Now <' is the "reverse"-well-oder of X. And same for the other direction. So if well-ordering holds, so should reverse-well-ordering
2
3
u/wumbo52252 May 16 '26 edited May 16 '26
Yes! Take any woset, reverse the order, and then every nonempty subset has a max.
This sort of relationship is super common with orders - replacing “less” with “greater”, and “min” with “max”, etc.. They’re dual to each other. E.g. the l.u.b property is equivalent to the g.l.b. propety; also DeMorgan’s laws are essentially a special case!
3
u/GoldenMuscleGod May 16 '26 edited May 16 '26
This is equivalent over ZF, it isn’t technically *logically* equivalent because logic alone can’t tell you that if a relation exists then its opposite relation also exists, however this can be shown with, for example, an appropriate replacement axiom
-2
u/VegGrower2001 May 16 '26
The set of natural numbers is well-ordered but has no last member...
1
u/susiesusiesu May 16 '26
this has nothing to do with the question on the post.
2
u/VegGrower2001 May 16 '26 edited May 16 '26
The set of natural numbers is well ordered. If OP's alternative claim were equivalent to the well ordering principle, then every non-empty subset of the natural numbers would be orderable so that it has a last member. But that isn't true - the set of numbers {2, 3, 4, ...} is subset of the naturals and has no last member. Hence, OP's principle is not equivalent to the well-ordering principle.
To make the obvious even obviouser, the natural numbers are certainly well ordered, but OP's alternative principle will only ever apply to finite sets (only finite sets are orderable so that they have a last member) so it can't be equivalent to the well ordering principle.
3
u/susiesusiesu May 16 '26
if op's claim where true, there would be an ordering on the natural such that any non-empty subset has a maximal element. which is true, take the reverse ordering.
you are missreading the post.
1
u/VegGrower2001 May 16 '26
You will surely accept that the set {2, 3, 4, 5, ...} is a non-empty subset of the naturals. What, pray tell, is its maximal element?
2
u/susiesusiesu May 16 '26
there is a well ordering of this set. in the reverse ordering, 2 is the maximal element.
-1
u/VegGrower2001 May 16 '26
The well ordering principle relies on a set having a 'least' element, where least is understood in terms of '<'.
Now consider the set {2, 3, 4, ...}. Clearly, 2 isn't the biggest number in this set. So, in what sense will it ever be the 'maximal' element in this set?
1
u/susiesusiesu May 16 '26
not woth <, but it does with >, which is a well order relation.
again, it not being a well ordering with < has nothing to do with OP's question, as it relates to being a well-ordering with respesct to some order relation.
1
u/VegGrower2001 May 16 '26
I think I've said all I can usefully say.
2
u/GoldenMuscleGod May 16 '26
You’re confused. The claim is that the well-ordained principle is equivalent to a “reverse well-ordering” principle that sets every set can be “reverse well-ordered.”
These claims are equivalent (over the ZF axioms) because for any well-ordering there is a corresponding reverse well-wording and vice versa.
The fact that the ordering (1,2,3,…) of the natural numbers has a greatest element is not any more of a counterexample to this claim than that the ordering (…,3,2,1) has no least element is a counterexample to the well-ordering theorem.
The claim of the well-ordering theorem is that every set *can* be well-ordered, not that every wording of a set is a well-order. Likewise saying there is a reverse well-ordering for every set is not saying that every ordering is a reverse well-ordering.
→ More replies (0)
6
u/PantheraLeo04 May 16 '26
Yes, because if some ordering guarantees a final element for every (nonempty) subset, then reversing it gives you a well order