0
$\begingroup$

Let $A$ be a nonempty subset of $\omega$, the set of natural numbers. I want to prove this statement:

If $\bigcup A=A$ then $n\in A \implies n^+\in A$.

Help...

  • 0
    Charles C.Pinter. This book defines w as the intersection of all the successor sets.2012-04-25

2 Answers 2

3

$\bigcup A\subseteq A$ says that $A$ is transitive and is therefore an ordinal. Now if $A$ were a successor ordinal $\alpha+1 = \alpha\cup\{\alpha\}$, then $\alpha\in A$ but $\bigcup A = (\bigcup\alpha)\cup\alpha \not\ni \alpha$. Thus $A$ must be either $0$ or $\omega$.


Or more directly: Assume $n\in A$. Then $n\in\bigcup A$, that is, there exits $y$ such that $n\in y \in A$. Then $n^+ \le y$. In the case $n^+=y$ we have $n\in A$ directly. Otherwise $n^+\in y\in A$ so $n^+\in\bigcup A$.

  • 0
    This is first time im studying set theory.. It feels weird to study further and come back to the problem i couldnt prove and prove it with the concept not in that chapter...2012-04-25
0

Oh yes, this can be pretty confusing! Here is how I think of it:

$\bigcup A = A$ really means $\bigcup A \subseteq A$ and $\bigcup A \supseteq A$.

Now assume $a \in A$. From $A \subseteq \bigcup A$, we get $a \in \bigcup A$, which, looking at the definition of $\bigcup A$, means that $a$ is an element of some element of $A$, say $b$. That is, $a \in b \in A$. But $b$ is a natural number, and since $a \in b$, $b$ is a $strictly$ $bigger$ natural than $a$. If $b = a^+$, we have $a^+ \in A$, and we are done. Otherwise, $a^+$ is an element of $b$. But then from $\bigcup A \subseteq A$, we get $a^+ \in A$ again.

And looking at the proof, we see that $A$ must have actually been $\omega$ all along!