# Proofs involving nested families of sets?

Suppose $$\mathscr{A}=\{A_i:i\in\mathbb{N}\}$$ is a family of sets such that for all $$i,j\in\mathbb{N}$$, if $$i\le j$$ then $$A_j\subseteq A_i$$. (Such a family is called a nested family of sets).

a) Prove for every $$k\in\mathbb{N}$$, $$\bigcap_{i=1}^{k}A_i=A_k$$

b) Prove that $$\bigcup_{i=1}^{\infty}A_i=A_1$$

Proof of a):

Suppose $$x\in\bigcap_{i=1}^{k}A_i$$

iff $$x\in A_i$$ for all $$i\in\mathbb{N}$$.

iff $$x\in A_j$$ since $$A_i\cap A_j= A_j$$, $$A_j \subseteq A_i$$ and $$A_i=A_j$$ since $$j\in\mathbb{N}$$

iff $$x\in A_k$$ for all $$k\in\mathbb{N}$$, since $$A_k=A_j\cap A_k$$, $$A_k\subseteq A_j$$ and $$k\in\mathbb{N}$$.

Proof of b)

Suppose $$x\in\bigcup_{i=1}^{\infty}A_i$$. Then $$x\in A_1$$ since it is contained in $$\bigcup_{i=1}^{\infty}A_i$$. Hence $$\bigcup_{i=1}^{\infty}A_i\subseteq A_1$$.

Now suppose $$x\in A_1$$ since $$1\le i \le j$$ for all $$i,j\in\mathbb{N}$$, it follows $$1\le i \le j$$ for some $$i,j\in\mathbb{N}$$. Since $$A_j\subseteq A_i\subseteq A_1$$, it follows $$x\in A_i$$ for some $$i\in\mathbb{N}$$. Hence $$x\in > \bigcup\limits_{i\in\mathbb{N}}A_i$$. Hence $$x\in\bigcup_{i=1}^{\infty}A_i$$.

Hence $$\bigcup_{i=1}^{\infty}A_i=A_1$$

I’m afraid that neither argument makes sense. In the first argument it is not true that $$x\in\bigcap_{i=1}^kA_i$$ iff $$x\in A_i$$ for all $$i\in\Bbb N$$. For example, let $$A_1=\{0\}$$, and let $$A_i=\varnothing$$ for all $$i\ge 2$$; then $$\{A_i:i\in\Bbb N\}$$ is a nest. Now take $$k=1$$: then

$$\bigcap_{i=1}^kA_i=\bigcap_{i=1}^1A_i=A_1=\{0\}\,,$$

so $$0\in\bigcap_{i=1}^kA_i$$, but clearly $$0\notin A_2$$ (and in fact $$0\notin A_i$$ whenever $$i\ge 2$$).

In the next line you talk about some $$A_j$$, but you never define it, so nothing that you say about it is meaningful. At the end you conclude that $$x\in A_k$$ for all $$k\in\Bbb N$$; this is just a repetition of what you said in the second line, but with a different name for the subscript, and it is every bit as false in general.

In the argument for (b) you start with an $$x\in\bigcup_{i=1}^\infty A_i$$ and conclude that it must be in $$A_1$$, since $$A_1\subseteq\bigcup_{i=1}^\infty A_i$$. Your reasoning here is exactly backwards: the fact that $$A_1\subseteq\bigcup_{i=1}^\infty A_I$$ tells you that if $$x\in A_1$$, then $$x\in\bigcup_{i=1}^\infty A_i$$, not the reverse.

Then when you try to prove the trivial implication that if $$x\in A_i$$, then $$x\in\bigcup_{i=1}^\infty A_i$$, you pick some unspecified positive integers $$i$$ and $$j$$ with $$i\le j$$ and claim that the fact that $$A_j\subseteq A_i\subseteq A_1$$ somehow proves that $$x\in A_i$$ for some $$i\in\Bbb N$$. This is a complete non sequitur, and in any case we already know that $$x\in A_i$$ for some $$i\in\Bbb N$$, since we assumed at the beginning that $$x\in A_1$$, and certainly $$1\in\Bbb N$$.

To prove (a), first observe that if $$x\in\bigcap_{i=1}^kA_i$$, then $$x\in A_k$$, so $$\bigcap_{i=1}^kA_i\subseteq A_k$$. Now suppose that $$x\in A_k$$, and let $$i\in\{1,\ldots,k\}$$; then $$i\le k$$, so $$A_k\subseteq A_i$$, and therefore $$x\in A_i$$. Thus, $$x\in A_i$$ for all $$i\in\{1,\ldots,k\}$$, and hence $$x\in\bigcap_{i=1}^kA_i$$. In other words, $$A_k\subseteq\bigcap_{i=1}^kA_i$$, and it follows that $$\bigcap_{i=1}^kA_i=A_k$$.

For (b) it’s immediate that if $$x\in A_1$$, then $$x\in\bigcup_{i=1}^\infty A_i$$, so $$A_1\subseteq\bigcup_{i=1}^\infty A_i$$. Now suppose that $$x\in\bigcup_{i=1}^\infty A_i$$; then there is some $$i\in\Bbb N$$ such that $$x\in A_i$$. And $$i\ge 1$$, so $$A_i\subseteq A_1$$, so $$x\in A_1$$. Thus, $$\bigcup_{i=1}^\infty A_i\subseteq A_1$$, and we conclude that $$\bigcup_{i=1}^\infty A_i=A_1$$.

None of the proofs is correct.

a) You mention a $$j$$ without saying what $$j$$ is.

b) You claim that every element of $$\bigcup_{i\in\Bbb N}A_i$$ belongs to $$A_1$$. That's not obvious.

These statements can be proved as follows:

a) Clearly, $$\bigcap_{i=1}^kA_i\subset A_k$$. On the other hand, if $$x\in A_k$$ and if $$i\in\{1,2,\ldots,k\}$$, then, since $$i\leqslant k$$, $$x\in A_i$$. Since this occurs for each $$i\in\{1,2,\ldots,k\}$$, $$x\in\bigcap_{i=1}^kA_i$$.

b) Clearly, $$A_1\subset\bigcup_{i\in\Bbb N}A_i$$. On the other hand, if $$x\in\bigcup_{i\in\Bbb N}A_i$$, then $$x\in A_i$$, for some $$i\in\Bbb N$$. Since $$i\geqslant1$$, $$x\in A_1$$.

I think it makes more sense to call it a 'decreasing family of sets' than a 'nested family of sets' because you can consider all those sets as subsets of $$A = \bigcup_{i \in \mathbb N} A_i$$, and the power set $$\mathcal P(A)$$ can be equipped with a partial order where $$B \le C$$ if and only if $$B \subseteq C$$. This makes the sequence $$\mathscr A$$ decreasing in that sense, since $$i \le j$$ implies $$A_i \ge A_j$$.

Your proof of (a) shows that you are confused about what the notation actually means. You are right that since $$A_i \supseteq A_k$$, $$x \in \bigcap_{i=1}^k A_i$$ if and only if $$x \in A_k$$, but the formulation is not quite enlightening. Usually you use the axiom of extensionality and try to prove that both sets admit the same elements. Something like this.

($$\supseteq$$) Since $$1 \le i \le k$$, we have $$A_i \supseteq A_k$$ for $$i \in \mathbb N$$ satisfying $$1 \le i \le k$$, and therefore $$\bigcap_{i=1}^k A_i \supseteq A_k$$.

($$\subseteq$$) We have $$\bigcap_{i=1}^k A_i \subseteq A_k$$ because $$A_k$$ is a member of that intersection.

Since both sets contain the same elements, they are equal. Usually the above two sentences suffice, i.e. proving that ($$\subseteq$$) and ($$\supseteq$$) hold.

You can do the proof for (b) in the same way. Again, not quite sure what you were trying to say, you seem confused there as well.

($$\subseteq$$) We have $$A_1 \supseteq A_i$$ for $$i \in \mathbb N$$ since $$i \ge 1$$, and therefore $$\bigcup_{i=1}^{\infty} A_i \subseteq A_1$$.

($$\supseteq$$) We have $$\bigcup_{i=1}^{\infty} A_i \supseteq A_1$$ because $$A_1$$ is a member of that union.

Hope that helps,