I was asked to prove every transitive $\in$-totally ordered set is $\in$-well ordered, and I did. However, I didn't use the transitivity, so I thought my proof must be wrong somewhere. Can you help me find the mistake?

Let X be an $\in$-totally ordered set. Let A be a non-empty subset of X. By Axiom of Foundation, there exists an element $a\in A$ such that $a \cap A = \emptyset$. Now let $b\in A$. Since A is totally ordered, a and b are comparable, ie. either $a\in b$, $a=b$ or $b\in a$. We can't have $b\in a$ since it would imply $b \in a \cap A \neq \emptyset$. Then either $a=b$ or $a\in b$. Hence, a is the least element of A. Since every non-empty subset of totally ordered set X has a least element, it is well ordered.


You are actually using transitivity (more broadly, the whole "linear order"ness) implicitly at the very end.

You've proved the more general fact:

Any set $X$ is $\in$-well-founded: every $A\subseteq X$ has an $\in$-minimal element.

This does not use any assumption on $X$. However, this lets you show that any $\in$-linearly-ordered set is $\in$-well-ordered, arguing as follows:

  • By the above, the set is $\in$-well-founded.

  • Well-orderings are exactly the well-founded linear orderings, so by linearity the set is $\in$-well-ordered.

So the assumption that $X$ was linearly ordered by $\in$ (and in particular that $\in$ is transitive on $X$) was only needed to go from "well-founded" to "well-ordered."


Well. Yes, assuming the axiom of regularity which states that $\in$ is well-founded. Then trivially any ordering via $\in$ is well-founded, so a total ordering is well-ordered.

It is consistent, however, that the axiom of regularity fails, and there is a sequence $x_n$ for $n\in\Bbb N$, such that $x_n=\{x_m\mid m>n\}$, which would give us a totally ordered set by $\in$ which is not well-ordered.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.