Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
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. – arjafi 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.

share|cite|improve this answer
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 E. Caicedo Apr 19 '13 at 14:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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