Is every $\in$-totally ordered set is $\in$-well ordered?

Question

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, i.e. 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.

Answer 1

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.

Answer 2

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."