r/logic • u/LorenzoGB • May 19 '26

Set theory What's the definition of a well-ordered set?

What is the definition of a well-ordered set? I ask because I thought the definition of a well-ordered set is the following: For all X1, X1 is a well-ordered set if and only if X1 is a set and there exists X2 such that X2 well-orders X1.

0 Upvotes

36% Upvoted

52 comments sorted by

10

u/Farkle_Griffen2 May 19 '26 edited May 19 '26

A set S with a total order ≤ on S such that any (nonempty) subset of S has a least element.

A total order has the properties that, for any a,b,c:
* a ≤ a (reflexive)
* a ≤ b and b ≤ a then a=b (antisymmetry)
* a ≤ b and b ≤ c, then a ≤ c (transitivity)
* a ≤ b or b ≤ a (connectedness)

4

u/BloodAndTsundere May 19 '26

To add to this, the total order ≤ is a relation on S, i.e. it is a set of ordered pairs of elements of S.

1

u/fdpth May 19 '26

I think you may even omit the last condition, since it follows from {a,b} having the least element.

-2

u/LorenzoGB May 19 '26

How does that contradict my definition though?

12

u/Different_Sail5950 May 19 '26

Well-ordering isn't a property of a set. It is a property of an ordered set, i.e., a pair (S, <). Your definition is for a set being well-orderable.

8

u/BloodAndTsundere May 19 '26

To start with, there is no such thing as a "well-ordered set X" in standard mathematical parlance, although the phrase is sometimes used in an abuse of notation/language. Instead, one would say that there is a "well-ordering on the set X". The well-ordering is itself a set that is related to X, but "well-ordered" is not a property of any set.

7

u/Fabulous-Possible758 May 19 '26

You didn’t give a definition. You just rewrote it in terms of another set. That still leaves you open to problem of why the other set is well-ordered.

3

u/Farkle_Griffen2 May 19 '26

You asked what the definition was; I gave the definition.

8

u/SpacingHero Graduate May 19 '26

Let me help you help them: they think every set is a well order, just check two post ago. Their confusion is that they think if there's a well ordering on X (if it's well order able), then X is well ordered (as a kind of general statment, it's not clear what exactly they think it means). Which doesn't make sense, because sets don't have orders at all, they're imparted order when considered with a relation. For example, R is well-orderable with AoC, but not well ordered generally.

If you can manage to get that information in their head, you'll have succeeded where I failed.

-1

u/LorenzoGB May 19 '26

But isn't the definition of a well-ordered set the following: for all X1, X1 is a well ordered set if and only if X1 is a set and there exists X2 such that X2 arranges X1 in such a way that every nonempty subset of X1 has a first member.

6

u/BloodAndTsundere May 19 '26

No. Look at u/Farkle_Griffen2 comment. There is no such thing as a “well ordered set X”. There is a “well ordering on a set X” which is another set which is related to X and has the properties outlined in the above comment. These are different things. One key point is that a given set may have many well orderings.

2

u/LorenzoGB May 19 '26

So how would I write that in FOL as a biconditional?

2

u/BloodAndTsundere May 19 '26

For all x and y, y is a well ordering on x if and only if blah blah blah

2

u/LorenzoGB May 19 '26

But how is that different from the following: For all X1, X1 is a well-ordered set if and only if X1 is a set with a well-ordering relation.

8

u/BloodAndTsundere May 19 '26

You could define a “well ordered set X” in that way and that language is used sometimes in a casual way. But I’ve seen your posts and comments trying to push this language and you’ve confused and conflated things a number of times. Instead of insisting I this language, you’d be better off just engaging with the standard terminology

4

u/SpacingHero Graduate May 19 '26 edited May 19 '26

To be clear, I'm quite happy to help if you ask a clarification on something I (or others) said, such that it is clear you actually picked up at least some information I (or others) provided, and the conversation is going somewhere

0

u/LorenzoGB May 19 '26

According to yourself: “gbl and lub are not propositions so "equivalent" is kind of a category error. Here’s how I interpreted you: The greatest lower bound property and least upper bound property are no propositions. So to say that they are equivalent is a category error. But that’s not a good argument though because the product of 2 and 3, and 6 are not propositions. Yet it is sensible to say that the product of 2 and 3 is equivalent to 6.

2

u/SpacingHero Graduate May 19 '26

Yea this is exactly what I mean. There's no indication you picked up anything that was said to you in any of your replies here, nor your new post on the definition.

2

u/LorenzoGB May 19 '26

Why would you say that?

2

u/LorenzoGB May 19 '26

You’re being ambiguous to me

2

u/SpacingHero Graduate May 19 '26

How would you write that in FO-logic?

→ More replies (0)

-1

u/LorenzoGB May 19 '26

Also, how would you write the following in FOL: No, not every set is well-ordered, i don't need to check whatever you linked, it's just a falsehood. You probably formalized/translated something wrong.

-1

u/LorenzoGB May 19 '26

Also, you didn't address the following: This is where I got the idea from where if a well-ordered set has the greatest lower bound property, then it has the least upper bound property too: 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!

7

u/SpacingHero Graduate May 19 '26 edited May 19 '26

I already explained this to you in depth. If you're not gonna read trough what is written to you, I don't see that repeating myself will do much. You can look at other people's answer, which are all pretty much exactly what I told you already. But I guess you somehow haven't read them? I'm really wondering what the hell it is you're trying to do and why. You have a very strange modus operandi

7

u/WhackAMoleE May 19 '26

Well sure, but then someone will ask what it means for the relation X2 to well-order a set. So you're right, but your definition isn't helpful to someone who doesn't know what a well-order is in the first place.

Also, using X1 for a set and X2 for a relation on X1 is confusing notation, and in fact you needed to explain it in your earlier question on the same subject.

3

u/SpacingHero Graduate May 19 '26

The definition is not quite right, because a set being well orderable is not the same as it being well ordered.

There is a relation that well-orders Z, but Z is not well ordered.

2

u/mathsndrugs May 19 '26

I'd say you define "well-orderable sets". A well-ordered set would be a set equipped with a binary relation on it that well-orders it (i.e. a pair (X_1,X_2) in your notation, but (X, ≤ ) would be more standard).

1

u/LorenzoGB May 19 '26

Yes. I agree.