# Transitive set ordered by epsilon

This problem is from here

Definition) A set t is called transitive if every element of every element of t is itself an element of t, or equivalently, if every element of t is a subset of t. A set t is said to be ordered by epsilon if for any two elements x and y of t, either x ∈ y or x = y or y ∈ x

5. Let x and y be transitive sets, each ordered by epsilon.

(a) Show using foundation that if y - x ≠ Ø, then x ∩ y ∈ y. [Hint: Let z be an epsilon-minimal element of y - x, and show z = x ∩ y.]

(b) Show that either x ∈ y or x = y or y ∈ x. [Hint: A proof like that of (a) shows also that if x - y ≠ Ø, then x ∩ y ∈ x]

Can there be two distinct sets each of exactly four elements, each both transitive and ordered by epsilon?

I'm solving (a), and I found out that $z\subseteq x \cap y$. (Let $w$ be an element of $z$, then since $z \in y$ implies $z \subseteq y$, $w$ is an element of $y$. If $w$ is not in $x$, then $w \in z \cap (y-x)$, a contradiction. Hence $w \in x$ and $z\subseteq x$, consequently $z \subseteq x \cap y$.)

But I don't know how to show that $z=x \cap y$. Is the problem okay? If I take $x$ to be empty set, then the conclusion is $\emptyset \in y$, which seems to be false.

Edit Thanks to hints, I solved (a),(b) and also I think that a set of exactly four elements, both transitive and ordered by epsilon is unique: Obviously $4=\{ 0,1,2,3 \}$ is one. Let $y$ be another one. If $4\in y$, then $0,1,2,3,4 \in y$, a contradiction. If $y \in 4$, then $y$ is one of $0,1,2,3$ which do not have 4 elements, a contradiction.

Also I found that every (nonempty) transitive set has the empty set: If $x$ is a nonempty transitive set, then $y \cap x = \emptyset$ for some $y\in x$. If $z\in y$, then $z \in x$, a contradiction. Hence the $\in$-minimal element of $x$ should be the empty set.

Then my question: Every transitive set ordered by epsilon is an ordinal?

-

Hint: (for (a)) We must show that every element $w$ of $x \cap y$ is an element of $z$. Show that the assumptions $w = z$ and $z \in w$ both lead to contradictions, and then use the fact that $y$ is ordered by $\in$.

Hint: (for (b)) If $x \neq y$, then without loss of generality we may assume $y \setminus x \neq \emptyset$. Applying (a) we have that $x \cap y \in y$. So it suffices to show that $x \cap y = x$. Note that $x \cap y$ is transitive and ordered in $\in$. If $x \cap y \neq x$ use (a) to show that $x \cap y \in x$. A contradiction (to Foundation) is now staring at you.

-
I got it. $w=z$ or $z \in w$ both lead to $z \in (x \cap y)\cap(y-x)=\emptyset$. – Gobi Apr 19 '13 at 9:39
But can you give me any hints for (b), last question? I'm having trouble in them, too. – Gobi Apr 19 '13 at 9:41
@Gobi: An outline for (b) has been added. Your contradictions for (a) seem fine. – inactive... for now Apr 19 '13 at 10:07
Thanks for great help. – Gobi Apr 19 '13 at 14:41

How do you define an ordinal? Often the ordinals are defined as transitive sets which are well-ordered by $\in$, these are known as the von Neumann ordinals.

However $\in$ is well-founded, so well-ordered by $\in$ is equivalent to being [linearly] ordered by $\in$.

So yes, every transitive set which is ordered by $\in$ is a von Neumann ordinal, and vice versa.

-
Thanks, I should study more about ordinals. – Gobi Apr 19 '13 at 14:40
But it is prudent to remark that foundation is essential for this equivalence. For example, there are models of the other $\mathsf{ZFC}$ axioms, where foundation fails, and there are sets $x$ that satisfy $x=\{x\}$. These sets are transitive and linearly ordered by $\in$, but are not ordinals. – Andrés Caicedo Apr 19 '13 at 14:48