Every member of a finite ordinal is a finite ordinal

182 Views Asked by At

This seems to be an obvious fact but I don't know how to prove it.

Let $\omega$ be the set of all finite ordinals, and I've shown that $\omega$ is an inductive set. So let $n\in\omega$, and suppose $n'\in n$. I want to show $n'\in\omega$.

Since $\omega$ is an inductive set, $n\cup\{n\}=n+1\in\omega$.

Since $n+1$ is transitive, and $n'\in n\in\ n+1$, we have $n'\in n+1$.

But this doesn't mean $n'\in\omega$. What am I missing?

A finite ordinal $x$ must satisfy the following 5 properties:

(1) if $x\neq\emptyset$,then $\emptyset\in x$

(2) $x$ is well ordered by $\in$

(3) if $z\in y\in x$, then $z\in x$

(4) if $x\neq\emptyset$, then $\emptyset$ is the only element of $x$ that is not a successor.

(5) if $x\neq\emptyset$, then $x$ contains precisely one element that does not have a successor, namely $x-1$.

1

There are 1 best solutions below

4
On BEST ANSWER

Let $n$ be a finite ordinal and suppose $x\in n$.

To prove $x$ satisfies (1), suppose $x\neq\emptyset$. Since $x\in n$ and $n$ is a finite ordinal, $\emptyset\in n$ by (1). Since $n$ is well-ordered by $\in$ (in particular, totally ordered), we have either $\emptyset\in x$ or $x\in\emptyset$. The latter is impossible, and therefore $\emptyset\in x$.

To prove $x$ satisfies (2), note that since $n$ satisfies (3), $x\subseteq n$, and any subset of a well-ordered set is well-ordered (by the restricted order relation).

To prove $x$ satisfies (3), note that if $z\in y\in x$ then since $y\in x\in n$ we have $y\in n$ and since $z\in y\in n$, we have $z\in n$. Now $n$ is well-ordered by $\in$ and in particular $\in$ is a transitive relation on $n$, so since $x,y,z\in n$, $z\in y\in x$ implies $z\in x$.

To prove $x$ satisfies (4), suppose $y\in x$ is not a successor. Then $y$ is not a successor in $n$ either, since by (3) any predecessor of $y$ in $n$ would be an element of $x$. Since $n$ satisfies (4), we must have $y=\emptyset$.

To prove $x$ satisfies (5), note first that any element of a well-ordered set which is not the greatest element has a successor (the least element which is greater than it). So it suffices to show that if $x$ has no greatest element, then it is empty. If $x$ did not have a greatest element, then there would be no greatest element of $n$ which is less than $x$, so $x$ would not be a successor. Since $n$ satisfies (4), this implies $x=\emptyset$.