3
$\begingroup$

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.

1 Answers 1

7

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 ... .

  • 0
    Thank you, quickly answered and explained it perfectly2011-08-20