# $A_1 \cap A_2 \cap \cdots \cap A_n \ne \emptyset$ holds for all $n$. Must it be that $\bigcap_{n = 1}^{\infty} A_n \ne \emptyset$?

Let $A_1, A_2, A_3, \,\ldots$ be sets such that $A_1 \cap A_2 \cap \cdots \cap A_n \ne \emptyset$ holds for all $n$.

Must it be that $\bigcap_{n = 1}^{\infty}A_n \ne \emptyset$?

I answered no. Here is my "proof".

Define $A_n = \{n+1, n+2, \,\ldots\}$.

Then $A_1 \cap A_2 \cap \cdots \cap A_n = \{n+1, n+2, \,\ldots\}$.

For all integers $n$, $\{n+1, n+2, \,\ldots\} \ne \emptyset$, since it contains $n+1$, and there is no largest integer.

Now consider $\bigcap_{n = 1}^{\infty} A_n$.

Suppose it contains an integer $m$. But $m \notin A_{m}$ by definition, hence $m \notin \bigcap_{n = 1}^{\infty} A_n$, so $\bigcap_{n = 1}^{\infty} A_n = \emptyset$.$$\tag*{\blacksquare}$$

Is that correct?

I ask because in my lecture notes, the definition of $\bigcap_{n = 1}^{\infty} A_n$ is $\{x : x \in A_n \ \forall n \}$ which (to me) seems to be equivalent to "$A_1 \cap A_2 \cap \cdots \cap A_n \ne \emptyset$ holds for all $n$", which would of course mean the answer is yes.

• no is the correct answer- and your example works. – voldemort Oct 17 '14 at 15:32
• Looks fine to me. +1 for showing your work. – Timbuc Oct 17 '14 at 15:33
• No is the correct answer, your example works, and this is still compatible with the definition you were given. $\bigcap_{n=1}^\infty A_n \neq \emptyset$ does imply that for any $m$ you have $\bigcap_{n=1}^m A_n \neq \emptyset$. But it is stronger, as your example demonstrates. – Ian Oct 17 '14 at 15:34
• I think your confusion comes down to order of quantifiers. The finite intersections all being nonempty means $(\forall m \in \mathbb{N}) (\exists x)(\forall n \in \{ 1,\dots,m \}) \, x \in A_n$. This means $x$ can depend on $m$ because $x$ is bound under the scope of the $m$ quantifier. But the countable intersection being nonempty means $(\exists x) (\forall n \in \mathbb{N}) \, x \in A_n$. Here $x$ is independent of $n$. – Ian Oct 17 '14 at 15:40
• Another interesting example, not discrete, is to take $A_n = (0,\frac1n)$. Then $$A_1\cap\cdots\cap A_n = A_n$$ but there is no point in $\bigcap_{n=1}^{\infty}A_n$ because any such point $a$ would have to satisfy $0<a<\frac1n$ for all $n$, which is impossible. – MPW Oct 17 '14 at 15:41

The key here, as Ian's comment says, is that the first statement $\;\langle \forall n :: \langle \cap i : i \leq n : A_i \rangle \not= \emptyset \rangle\;$ is (by the definitions) equivalent to $$\langle \forall n :: \langle \exists x :: \langle \forall i : i \leq n : x \in A_i \rangle \rangle \rangle$$ while the second statement $\;\langle \cap i :: A_i \rangle \not= \emptyset\;$ is equivalent to $$\langle \exists x :: \langle \forall i :: x \in A_i \rangle \rangle$$

These two are not equivalent, as you correctly show by your counterexample of $\;A_i = \{j | j > i\}\;$ which makes the first statement true (by choosing $\;x := n+1\;$) and the second false.


$$\calc \langle \forall n :: \langle \exists x :: \langle \forall i : i \leq n : x \in A_i \rangle \rangle \rangle \calcop{\Leftarrow}{logic: strengthen by weakening range of \;\forall i\;} \langle \forall n :: \langle \exists x :: \langle \forall i :: x \in A_i \rangle \rangle \rangle \calcop{\Leftarrow}{logic: remove unused \;\forall n\;} \langle \exists x :: \langle \forall i :: x \in A_i \rangle \rangle \endcalc$$

Take $A_n = \left(0, \dfrac{1}{n}\right)$, then $\displaystyle \bigcap_{k=1}^n A_k = \left(0,\dfrac{1}{n}\right)$, and $\displaystyle \bigcap_{k=1}^\infty A_k = \emptyset$.

• Did you read the question...? – Najib Idrissi Oct 17 '14 at 18:11
• @NajibIdrissi: yes he did,this is a counter example. – Arjang Oct 18 '14 at 10:08
• @Arjang The question isn't asking for a counterexample, the question is asking to check the proof. Notice that the question already contains a counterexample. – Najib Idrissi Oct 18 '14 at 10:15
• @NajibIdrissi : Ahaa! I didn't read the question either :) – Arjang Oct 18 '14 at 10:23