0
$\begingroup$

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

  • 0
    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](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference)'s a basic tutorial and quick reference. There's an "edit" link under the question.2012-09-26
  • 2
    @joriki: This time I was going to add a note! :-)2012-09-26
  • 0
    @Brian: :-) ${}$2012-09-26
  • 1
    How much could you find out yourself?2012-09-26
  • 1
    I might be missing something, but what does this question have to do with computability?2012-09-26
  • 0
    As @Asaf said. It doesn't seem to have anything to do with comparability either, as the title suggests.2012-09-26
  • 0
    Welcome to the site! Here, we generally frown on the imperative. One could read your post as "Do this for me." While the purpose of this site is to ask and answer mathematical questions, people will be more likely to respond if you demonstrate that you've at least tried to provide some answers. In short, give us a clue about what you've done on these problems.2012-10-03

2 Answers 2

1

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.

  • 0
    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).2012-09-26
  • 0
    @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$.2012-09-26
  • 0
    Ah! Excellent choice. I should have known better than to question you on a pedagogical matter.2012-09-27
  • 0
    @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.2012-09-27
0

($*$)$\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.