Set theory, transitive sets

Printable View

February 22nd 2009, 05:41 AM
georgel

Set theory, transitive sets

Could someone please prove, using the principle of mathematical induction, that the set $\omega$ consisting of all natural numbers is a transitive set?

That is, prove that:
$y \in x \in \omega \rightarrow y \in \omega$

Thank you.
February 22nd 2009, 06:30 AM
clic-clac

Hi

Do you agree that, for $x=\emptyset,$ your formula is true?

Now assume that it is true for a $x\in\omega,$ we have to show that it's also true for its successor, $x\cup\{x\}.$

Let $y$ be an element of $x\cup\{x\},$ i.e. $y\in x\ \text{or}\ y\in \{x\}.$ In the first case, the induction hypothesis states that $y\in\omega.$ In the second case, $y=x$ and then $y\in\omega .$

So, using the mathematical induction principle, we proved that $\omega$ is a transtive set.
February 22nd 2009, 07:10 AM
ThePerfectHacker

Here is a non-induction way to prove this. I know you asked for induction but I bring this approach up because it might help you when you do more stuff on ordinals. If $X$ is a set of ordinals then $\cup X$ is a set of ordinals. Since $\omega$ is the union of all natural numbers and since each natural number is an ordinal it follows that $\omega$ is an ordinal.
February 23rd 2009, 06:29 AM
georgel

Thanks to both of you, I will probably have another question or two in the next couple of days.. :)

All times are GMT -8. The time now is 11:04 AM.