1
$\begingroup$

From what I've been taught in school, the well-ordering principle states that every non-empty set must have a least element. To me, the least element of some set $X$ is an element $a$ such that, for all $a \in X$, $a < x$.

This principle makes to me sense for most sets, but it not for a set with one element, as a consequence of my own definition of a least element. Say $X$ is a set with $1$ element. By the well-ordering principle, $X$ must have a least element, so there must be an $a \in S$ such that, $\forall x \in X$, $a < x$. But that can't be, since the only element in $X$ is $a$, and to say that $a$ is less than all elements in $X$ would be saying $a < a$, which is impossible! So, by this notion, $X$ does not have a least element.

This leads me to think that a set should have at least two elements in order for the well-ordering principle to apply--that way, two elements could be compared with respect to their sizes. However, whenever I share this with my peers and professors, they tend to regard my deduction as "wrong" somehow, without sufficiently explaining why.

The closest I have gotten to understanding why the well-ordering principle applies to sets with only one element is looking at the axiom of choice, which if I'm not mistaken is equivalent to the well-ordering principle. According to Wikipedia, the axiom of choice reads:

"For any set $X$, there exists a binary relation $R$ which well-orders $X$. This means $R$ is a linear order on $R$ such that every nonempty subset of $R$ has a member which is minimal under $R$."

Looking into the definition of a linear order, its first axiom is $a \leq a$. At first, I thought this might satisfy my question, but looking closer at the definition, there is still a concept of a "minimum," which to me does not make sense without at least two elements, for the reasons given prior. Moreover, the definition of a well-order seems to rely on the notion of a least element, which again brings me back to my prior confusion.

So, is there anything wrong with my reasoning? Is my definition of the well-ordering principle or of a least element of a set flawed, or different than that of what most people have? Why is it that the well-ordering principle applies for all non-empty sets, and not just for sets with at least two elements?

$\endgroup$
4
  • 2
    $\begingroup$ Per the Wikipedia article you linked, a well-order is a kind of total order. What is the definition of a total order? $\endgroup$ Commented Jan 29, 2024 at 18:43
  • 3
    $\begingroup$ I'm also somewhat confused about your question. The well order principle and the well order theorem are two different things. You seem to be asking about the principle, but your opening paragraph asks about the theorem. The version of the theorem that I know is about the natural numbers---every nonempty set of natural numbers has a least element---this fails for other totally ordered sets, e.g. the reals (an open interval does not have a least element). This can be generalized to well-ordered sets, but I think it becomes circular at this point. $\endgroup$ Commented Jan 29, 2024 at 18:49
  • 1
    $\begingroup$ For reference: the well order principle (every nonempty set of natural numbers has a least element) and the well order theorem every set can be well-ordered. The question seems to belie some confusion between the two. $\endgroup$ Commented Jan 29, 2024 at 18:51
  • 7
    $\begingroup$ One mistake you have made is to use strict inequality when defining least element, when you should instead be using nonstrict inequality. To say that $a$ is the least element of a totally ordered set $X$ means that for all $x \in X$, $a \le x$ (and you mistyped $a \in X$ instead of $x \in X$). $\endgroup$ Commented Jan 29, 2024 at 18:52

3 Answers 3

Reset to default
18
$\begingroup$

You have not distinguished an order $\le$ and a strict order $<$. Set theorists usually do not distinguish these two since one induces the other, but you should distinguish in this context. You can see that your definition of the least element does not make sense if we understand $<$ to mean a strict order: If $a$ satisfies $a<x$ for all $x$, then we have $a<a$, a contradiction.

When we say "Every set has a well-order," it means for every set $A$ there is a well-order $\le$ over $A$. Every well-order (or a linear order, in general) induces an associated strict order $$a<b \iff a\le b\land a\neq b.$$ Conversely, for every strict order $<$ we can associate an order by letting $$a\le b \iff a<b\lor a=b.$$

If you define the minimum as an element $a$ satisfying $a\le x$ for all $x$, then there is no contradiction. Clearly, every singleton $\{a\}$ has a well-order given by $${\le} = \{(a,a)\}.$$ And we can go one step down! Even the empty set has a well-order, and the empty relation is the well-order.

$\endgroup$
10
$\begingroup$

Corrections:

From what I've been taught in school, the well-ordering principle states that every non-empty set must have a least element.

Usually, the "well-ordering principle" refers to the fact that the standard ordering on the natural numbers $\mathbb{N}$ is a well-order. That is, every non-empty set of natural numbers has a least element.

This should be distinguished from the definition of well-order (a linear/total order $<$ on a set $X$ such that every non-empty subset of $X$ has a least element) and the well-ordering theorem (see the next point).

On Wikipedia, they say the well-ordering "theorem" states that any non-empty set can be well-ordered.

The well-ordering theorem states that every set can be well-ordered. Yes, this applies to the empty set too: the unique (empty) binary relation on the empty set is a well-ordering.

To me, the least element of some set $X$ is an element $a$ such that, for all $a\in X$, $a<x$.

What you've written doesn't make any sense. You probably meant "an element $a$ such that, for all $x\in X$, $a<x$." But this is not correct either: you need to say "for all $x\in X$, $a\leq x$" or "for all $x\in X$ with $a\neq x$, $a<x$".

Say $X$ is a set with $1$ element. By the well-ordering principle, $X$ must have a least element, so there must be an $a \in S$ such that, $\forall x \in X$, $a < x$. But that can't be, since the only element in $X$ is $a$, and to say that $a$ is less than all elements in $X$ would be saying $a < a$, which is impossible! So, by this notion, $X$ does not have a least element.

Your argument works just as well to show that (with your flawed definition of "least element") no strictly linearly ordered set $(X,<)$ has a least element. Indeed, suppose $X$ has a least element $a$. Then for all $x\in X$, $a<x$. Since $a\in X$, we have $a<a$, contradiction.

The problem, of course, is that your definition of "least element" was wrong in the way I pointed out above.

According to Wikipedia, the axiom of choice reads: "For any set $X$, there exists a binary relation $R$ which well-orders $X$."'

No, this is the statement of the well-ordering theorem. It happens to be equivalent to the axiom of choice over ZF set theory, so if you like, you can take this as a basic axiom instead of the axiom of choice and get a logically equivalent theory. Some authors may choose to do this, possibly because they view well-orderings as more fundamental than choice functions. The usual statement of the axiom of choice can be found on Wikipedia here.

$\endgroup$
1
  • 3
    $\begingroup$ Rather confusingly, on the Wikipedia article about the axioms of ZFC, it lists the well-ordering theorem as an axiom of ZFC, in place of the usual statement of the axiom of choice. $\endgroup$ Commented Jan 30, 2024 at 11:59
3
$\begingroup$

"The least element of some set $X$ is an element $a$ such that, for all $x \in X$, $a<x$." This is incorrect, and you showed why yourself: if $a<x$ for every $x$, then $a<a$, which is impossible. This reasoning works for any set $X$, not just for sets with one element as you described.

To fix the definition of "least element", simply change it to either "for every $x \in X\backslash\{a\}$, $a<x$", or "for all $x \in X$, $a\leq x$". With either of these corrections, the well-ordering principle holds, even for sets with one element.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.