I have been asked both these questions on a paper, the questions are next to each other and distinct.

I feel that these questions appear to be asking the same thing or at least similar things, what are the key differences to look out for when proving each of them?

How do these proofs differ? Have I encapsulated these differences?

This is my attempt at each proof:

Q1: Prove that every natural number is transitive

A1:The same as: Show the set of transitive natural numbers is inductive

We have $0=\varnothing$ is transitive so $0\in Z=\{k\in\omega\vert\text{Trans}(k)\}$

Suppose $k\in Z$. We know if $k$ is transitive then $S(k)$ is transitive.

Proof of Trans($k$)$\rightarrow$Trans($(S(k)$)

Trans($k$)$\leftrightarrow\forall x\in k(x\subseteq k)$ and $S(k)\leftrightarrow k\cup\{k\}$

Let $y\in k\cup\{k\}$, show $y\subseteq k\cup\{k\}$

If $y\in k$, then $y\subseteq k$ follows immediately from Trans($k$)$\therefore y\subseteq k\subseteq k\cup\{k\}$

If $y\in\{k\}$, then since $\{k\}$ has 1 element namely $k$,

then $k=y\therefore y\subseteq k\cup\{k\}\therefore$ Trans($S(k)$)\

Q2: Prove that $\omega$ is transitive

A2: Trans($\omega$)$\leftrightarrow\forall x\in\omega(x\subseteq\omega)$

Let $Z$ be the set of all transitive natural numbers.

That is $n\in Z\leftrightarrow n\in\mathbb{N}\wedge\forall x\in n(x\subseteq n)$

It is true that $0\in Z$ as $\not\exists x\in 0$

Assume $n\in Z$

If $x\in S(n)\leftrightarrow x\in n\cup\{n\}$

then $x\in n$ or $x\in\{n\}\Leftrightarrow x=n$

If $x\in n$ then $x\subseteq n$ by $n\in Z$

If $x=n$ then $x\subseteq n$

By the principle of finite induction it follows that $Z=\mathbb{N}$

Progress: I am fine with the proof that every natural number is transitive, but am unsure about the proof that $\omega$ is transitive. If this could be clarified for me it would be greatly appreciated.

  • $\begingroup$ Looking to award this bounty, post some useful or interesting information and I will award the bounty. Would be a shame for it to go to waste. $\endgroup$ – Sam Houston Jan 10 '15 at 11:53

Finally got the answer

Proof that $\omega$ is transitive:

Let $X=\{n\in\omega\vert n\subseteq\omega\}$

If $X=\omega$ then by definition Trans$(\omega)$

So we show that $X$ is inductive

$\varnothing\in X$; assume that $n\in X$ then $n\subseteq\omega$ and $n\in\omega$ implying $\{n\}\subseteq\omega$

So $S(n)=n\cup\{n\}\subseteq\omega$

So $X$ is inductive and $\omega=X$

*answer to part $1$ is above


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.