I am aiming to prove that: if $\alpha$ is an ordinal number and $\beta\in\alpha$, then $\beta$ is an ordinal number.

The definition of ordinal is given by:

An ordinal number is a set that is transitive and is well-ordered by the relation $\alpha<\beta\Leftrightarrow\alpha\in\beta$

where transitive is defined to be:

$x\subseteq S$ for every $x\in S$

And well-ordered is defined to be:

For every non-empty subset $A\subseteq S$, there exists an element $m\in A$ such that $\forall x\in A$, $m\leq x$

Here is a solution:

Theorem 4: Elements of ordinals are ordinals.

Proof: Elements of ordinals are subsets and so are well-ordered. Let $x\in y \in z \in\alpha $ where $\alpha$ is an ordinal. Then since $\alpha$ is transitive, $x, y, z\in\alpha$. Since $\in$ is transitive on $\alpha$, $x\in z$.

I cannot understand the method of checking of transitivity. I think in order to prove the element $z\in\alpha$ is transitive, we need to pick any element $x\in z$ and by definition conclude $x\subseteq z$ rather than assume that $x\in y\in z\in \alpha$. In fact, I cannot understand the whole part of the argument about transitivity in this proof.

Could someone please help to explain it explicity using definition? Thanks a lot.

EDIT:NOTE: Latter I realized that the answer below has not solved my question (Sorry).This version of definition of well ordering does not mention transitivity.

EDIT:Here I am asking about how to use this version of well-orderedness to prove that $\in $ is transitive. What makes ordinal special and allows $\in$ to be transitive? Could someone please use the definition above to prove it?

  • $\begingroup$ Hint: $\in$ is a well ordering in $\alpha$. $\endgroup$ – Renan Maneli Mezabarba Mar 21 '17 at 12:21
  • $\begingroup$ @RenanManeliMezabarba I know that, and it is mentioned by the proof. May I please ask for an explicit solution? $\endgroup$ – PropositionX Mar 21 '17 at 12:25

We want to show that $z\in\alpha$ is transitive, i.e., if $y\in z$ then $y\subset z$. In order to prove this inclusion we take an arbitrary $x\in y$ and we show that $x\in z$. So, if $x\in y$, notice that $x,y,z\in\alpha$:

  • $z\in\alpha$ is our hypothesis;

  • since $z\in\alpha$, we know that $z\subset\alpha$, hence $y\in z$ yields $y\in\alpha$;

  • similarly, $x\in \alpha$.

Now, we have $x\in y\in z$ in $\alpha$. But $(\alpha,\in)$ is a well ordering and particularly $\in$ is transitive. Thus, $x\in y\in z$ implies $x\in z$, as desired.

  • $\begingroup$ In my opinion, to prove that $z\in \alpha$ is transitive, we should start with the assumption $y\in z$ and get $y\subseteq z$ rather then assume that $x\in y$ and get $x\subseteq z$. May I ask how does this prove actually shows if $y\in z$ then $y\subseteq z$? $\endgroup$ – PropositionX Mar 21 '17 at 12:36
  • 1
    $\begingroup$ Exactly! Thanks so much! $\endgroup$ – PropositionX Mar 21 '17 at 12:38
  • $\begingroup$ Sorry but I think this time I am not given that a well-ordering is transitive in this version of definition, which I forgot. So without the transitivity of well ordering, could you please explain in another way using the definition above? $\endgroup$ – PropositionX Mar 21 '17 at 13:33
  • $\begingroup$ Or is it possible to prove the transitivity of $\in$? $\endgroup$ – PropositionX Mar 21 '17 at 13:43
  • $\begingroup$ Could you please tell me from which reference are you taking your definitions? I ask this because usually a well order in $P$ is a partial ordering $\leq$ such that for every $\emptyset\ne A\subset P$ there exists $\operatorname{min}⁡⁡A$. But a partial order is particularly transitive. Anyway, you may find this and this useful. $\endgroup$ – Renan Maneli Mezabarba Mar 21 '17 at 17:25

We must be careful to distinguish between a transitive set and a transitive binary relation on a set.

(1). Let $R$ be a binary relation on a set $X$. Then $R$ is a well-ordering iff

(1a). For all $x\in X$ we have $\neg (xRx)$, and also

(1b). For every non-empty $Y\subset X$ there is a unique $p\in Y$ such that $pRq$ for all $q\in Y$ \ $\{p\}.$....... We call such $p$ the unique $R$-least member of $Y.$

It follows that

(i) R satisfies Trichotomy, and

(ii) R is a transitive relation on $X$.

To prove (i): If $p,q\in X$ and $p\ne q$ then $\{p,q\}$ has a unique $R$-least member. So by (1b) we have $pRq$ or $qRp$, but not both of these..... And we have $\forall p\in X(\;\neg pRp)$ by (1a).

To prove (ii): If $pRq$ and $qRr$ then $\{p,q,r\}$ has a unique $R$-least member....

It can't be $r$ because by (i), $\;qRr\implies (\;q\ne r\land \neg rRq\;)$.

It can't be $q$ because by (i), $\;pRq\implies (\;p\ne q\land \neg qRp \;)$.

So $ p$ is $R$-least. And we must have $p\ne r$, because $(p=r\land pRq\land qRr)\implies (pRq \land qRp)$, and we would violate (i) (Trichotomy). Since $p$ is the $R$-least member of $\{p,q,r\}$ and $p\ne r$, we have $pRr$.

(2). If $<$ is a well-ordering on a set $X$ then for any $Y\subset X$, the restriction of $<$ to $Y$ is a well-ordering of $Y$. For if $\phi\ne Z\subset Y$, then $\phi \ne Z\subset X.$ And any $Z$ that satisfies $\phi \ne Z\subset X$ has a $<$-least member.

(3). Let $A$ be an ordinal and $z\in A$.

(3a). $z\subset A$, so the restriction of $\in$ to $z$ is a well-order on $z$.

(3b). Now $\in$ is a well-order on $A$ and therefore $\in$ is a transitive relation on $A$. So by transitivity of the relation $\in$ on $A$,for any $y\in Z$ and any $x\in y$ we have $$(x\in y\land y\in z)\implies x\in z.$$ So for any $y\in z$ we have $y\subset z.$

By (3a) and (3b), $z$ is an ordinal.

  • 1
    $\begingroup$ We cannot show that a member of an ordinal is an ordinal without using both parts of the def'n of an ordinal. A member of a transitive set need not be a transitive set. For example if $x=\phi , y=\{x\}, z=\{y\}$ then $A=\{x,y,z\}$ is a transitive set and $z\in A$ but $z$ is not a transitive set $\endgroup$ – DanielWainfleet Mar 22 '17 at 10:26

Let $\alpha$ be an ordinal and $z\in\alpha$. Thus $z\subsetneq\alpha$.

  1. $z$ is well-ordered under $\in$. For $X\subseteq z,X\subsetneq\alpha$, which is well-ordered. Thus $z$ is well-ordered too.

  2. $z$ is transitive. For all $m\in n\in z\in\alpha$, $m\in n\in z\subsetneq\alpha$, hence $m\in n\in\alpha$. Thus $m\in n \subsetneq\alpha$, hence $m\in\alpha$. Since $m,n,z\in \alpha$ and $m\in n\in z\in\alpha$, then $m\in z$. To sum up, $(m\in n\implies m\in z)\implies n\subsetneq z$.


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.