1. If $X$ is inductive, then the set $\{x\in X\mid x\text{ is transitive}\}$ is inductive. Hence every $n\in\mathbb{N}$ is transitive.

  2. If $X$ is inductive, then the set $\{x\in X\mid x\text{ is transitive and }x\notin x\}$ is inductive. Hence, $n\notin n$ and $n\neq n+1$ for each $n\in\mathbb{N}$.

  • 3
    $\begingroup$ Well, what about them? Are you just letting us know about interesting stuff you've discovered? If you have a question, how about asking it? $\endgroup$ – Arturo Magidin Feb 20 '11 at 19:36

Please ask questions, don't just quote your assingment/problem. It's better if you specify what you have tried or where you are stuck.

To prove that a set $S$ is inductive, you need to prove that:

  1. $\emptyset\in S$; and
  2. If $a\in S$, then $a\cup\{a\} \in S$.

Conversely, if $S$ is inductive, then 1 and 2 will hold.

So, for your first problem: to show the set you are given is inductive, you must show that $\emptyset$ is in the set. That is, you need to show that $\emptyset \in X$ and that $\emptyset$ is transitive. Since $X$ is assumed inductive, then $\emptyset\in X$. And $\emptyset$ is transitive, so $\emptyset$ is in the set.

Then, assume $a$ is in the set; you need to show that $a\cup\{a\}$ is in the set. That is, assume that $a$ is an element of $X$ and is transitive; use that to show that $a\cup \{a\}$ is in $X$ and is transitive. That will show your set is inductive.

As for the final clause: $\mathbb{N}$ is inductive, so that means that $\{n\in\mathbb{N}\mid n\text{ is transitive}\}$ is an inductive set by what you will have proven by this point. It is also a subset of $\mathbb{N}$. What subsets of $\mathbb{N}$ are inductive?

Part 2 is proven the same way: show $\emptyset$ is in the given set, then show that if $a$ is in the set, then so is $a\cup\{a\}$. The first part of the "Hence" is immediate from the first clause of $2$. for the second part of the "Hence", let me ask you a question: is $n\in n+1$?


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.