Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First some definitions: $X$ is inductive if $\emptyset\in X$ and $x\in X\implies x\cup\{x\}\in X$

Let $N = \cap\{X : X \text{ is inductive }\}$. Let us use the following notation:

$0 = \emptyset$, $1 = \{0\}$, $2 = \{0 , 1\}$, ...

if $n\in N$ let $n + 1 = n \cup \{n\}$. Let us define $<$ (on $N$) by $n < m$ iff $n\in m$.

A set $T$ is transitive if $x\in T$ implies $x\subset T$.

Then I have :

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

Solution. Suppose $X$ is inductive, it follows that $\emptyset\in X$. The empty set is also vacuously transitive, hence $\emptyset\in \{ x\in X : x$ is transitive}. Now suppose that $x\in\{ x\in X : x$ is transitive} it follows that $x\in X$ and hence $x\cup\{x\} \in X$. Similarly it follows that $x$ is transitive. Now, let $a\in x\cup\{x\}$, then there are two cases either $a\in x$ or $a\in \{x\}$. In the first case it follows that since $a\in x$ and $x$ is transitive $a\subset x$, and hence $a\subset x\cup\{x\}$. In the second case since $a\in\{x\}$ and $\{x\}$ is a singleton set it follows that $a = x$, thus $a \subset x\cup\{x\}$. Thus $x\cup\{x\}$ is transitive, and hence $x\cup\{x\} \in\{ x\in X : x$ is transitive}. Therefore we can conclude that $\{ x\in X : x$ is transitive} is inductive. $\Box$

Now the problem, I really cannot see how the corollary "Hence every $n\in N$ is transitive." follows from this.

But I do note that I know $N$ is transitive, and for each $n\in N$, $n = \{m\in N : m < n\}$ by the previous question.

So I was wondering if someone could help shed light on how the corollary follows from the initial question, or point out the flaw in my proof thus suggesting a reason it doesn't currently follow.

Thank you very much.

share|cite|improve this question
up vote 7 down vote accepted

First verify that $N$ is inductive. This is straightforward: if $n \in N$, and let $X$ be any inductive set. Then $n \in X$ by the definition of $N$, and since $X$ is inductive, $n \cup \{n\} \in X$. This is true for all inductive $X$, so $n \cup \{n\} \in \bigcap \{X:X\text{ is inductive}\} = N$. Now let $T = \{n \in N:n\text{ is transitive}\}$; $T$ is inductive by the theorem. But then $N \subseteq T$, since $N$ is the intersection of all inductive sets, and since by construction $T \subseteq N$, we must have $T=N$, i.e., each $n \in N$ is transitive.

Added: Taking a closer look at your proof of the theorem, I see one significant infelicity. It’s a bad idea to write ‘suppose that $x \in \{x \in X:x\text{ is transitive}\}\text{’}$: you're using the letter $x$ simultaneously to refer to a specific object and as the dummy variable in the set definition. Make it $$x \in \{y \in X:y\text{ is transitive}\}$$ instead. The rest is okay, though I think that parts could be worded a bit more clearly. For instance, after defining/choosing $x$, I’d continue something like this:

Clearly $x$ is transitive, and since $X$ is inductive, $x \cup \{x\} \in X$. If $a \in x \cup \{x\}$, then either $a \in x$, or $a \in \{x\}$. In the first case ... .

share|cite|improve this answer
Thank you, quickly answered and explained it perfectly – Deven Ware Aug 20 '11 at 1:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.