# Possible implications of $A_{0}\subseteq A_{1}\subseteq A_{2}\subseteq A_{3}\cdots\subseteq\Bbb N$.

Assume $(A_{i})_{i\in\Bbb N}$ to be an infinite sequence of sets of natural numbers, satisfying

$$A_{0}\subseteq A_{1}\subseteq A_{2}\subseteq A_{3}\cdots\subseteq\Bbb N\tag{*}$$

For each property $p_{i}$ shown below, state whether

• the hypothesis (*) is sufficient to conclude that $p_{i}$ holds; or

• the hypothesis (*) is sufficient to conclude that $p_{i}$ does not hold; or

• the hypothesis (*) is not sufficient to conclude anything about the truth of $p_{i}$ .

1. $p_{1}$ : $\forall k\in\Bbb N.\ A_{k}=\bigcup_{i=0}^{k}A_{i}$

2. $p_{2}$ : for all $i$, if $A_{i}$ is infinite, then $A_{i}=A_{i+1}$

3. $p_{3}$ : if $\forall i\in\Bbb N.\ A_{i}\neq A_{i+1}$, then $\bigcup_{i=0}^{\infty}A_{i}=\Bbb N$

4. $p_{4}$ : if $\forall i\in\Bbb N.\ A_{i}$ is finite, then $\bigcup_{i=0}^{\infty}A_{i}$ is finite

5. $p_{5}$ : if $\forall i\in\Bbb N.\ A_{i}$ is finite, then $\bigcup_{i=0}^{\infty}A_{i}$ is infinite

6. $p_{6}$ : if $\forall i\in\Bbb N.\ A_{i}$ is infinite, then $\bigcup_{i=0}^{\infty}A_{i}$ is infinite

-
You can use $\TeX$ on this site by enclosing formulas in dollar signs; single dollar signs for inline formulas and double dollar signs for displayed equations. You can see the source code for any math formatting you see on this site by right-clicking on it and selecting "Show Math As:TeX Commands". Here's a basic tutorial and quick reference. There's an "edit" link under the question. –  joriki Sep 26 '12 at 22:27
@joriki: This time I was going to add a note! :-) –  Brian M. Scott Sep 26 '12 at 22:29
@Brian: :-) ${}$ –  joriki Sep 26 '12 at 22:29
How much could you find out yourself? –  Hagen von Eitzen Sep 26 '12 at 22:37
I might be missing something, but what does this question have to do with computability? –  Asaf Karagila Sep 26 '12 at 22:49

You really shouldn’t have any trouble with $p_1$ or $p_6$. I’ll do $p_3$ as an illustration.

First, $p_3$ is consistent with (*). For example, let $A$ be the set of odd positive integers, and for $n\in\Bbb N$ let $A_n=A\cup\{2k:k\le n\}$: then $2(n+1)\in A_{n+1}\setminus A_n$, and $\bigcup_{n\in\Bbb N}A_n=\Bbb N$.

On the other hand, $\lnot p_3$ is also consistent with (*). This time let let $A_n=A\cup\{2k+2:k\le n\}$. Once again the sets $A_n$ form a strictly increasing sequence of subsets of $\Bbb N$, but $0\notin\bigcup_{n\in\Bbb N}A_n$.

Thus, (*) is not sufficient to decide $p_3$ one way or the other.

-
For even simpler examples, in the first case, we can let $A_n=\{k\in\Bbb N:k\leq n\}$, and in the second, we can let $A_n=\{k\in\Bbb N:2\leq n+2\}$ (I chose that because I wasn't sure if the OP considers $0$ to be a natural number). –  Cameron Buie Sep 26 '12 at 23:15
@Cameron: I deliberately chose to use infinite sets, even though it wasn’t required, partly because I think that it gives more insight into what’s going on overall and partly as a silent hint for $p_2$. –  Brian M. Scott Sep 26 '12 at 23:27
Ah! Excellent choice. I should have known better than to question you on a pedagogical matter. –  Cameron Buie Sep 27 '12 at 0:53
@Cameron: I think that one could make a good case either way, actually; which one works better depends so much on the person asking that there’s really no way to guess. –  Brian M. Scott Sep 27 '12 at 0:56
($*$)$\Rightarrow p_1,p_6$.
The rest, $p_2, p_3, p_4, p_5$ are not in general true, even if we assume (*). Try to find counterexamples.