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

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

Justify your answers (briefly).

  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

share|cite|improve this question
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.

share|cite|improve this answer
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.

share|cite|improve this answer

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.