8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ no is the correct answer- and your example works. $\endgroup$ – voldemort Oct 17 '14 at 15:32
  • 1
    $\begingroup$ Looks fine to me. +1 for showing your work. $\endgroup$ – Timbuc Oct 17 '14 at 15:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Ian Oct 17 '14 at 15:34
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ian Oct 17 '14 at 15:40
  • $\begingroup$ 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. $\endgroup$ – MPW Oct 17 '14 at 15:41
2
$\begingroup$

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.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} $However, note that the second statement does imply the first:

$$\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$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Did you read the question...? $\endgroup$ – Najib Idrissi Oct 17 '14 at 18:11
  • $\begingroup$ @NajibIdrissi: yes he did,this is a counter example. $\endgroup$ – Arjang Oct 18 '14 at 10:08
  • 1
    $\begingroup$ @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. $\endgroup$ – Najib Idrissi Oct 18 '14 at 10:15
  • $\begingroup$ @NajibIdrissi : Ahaa! I didn't read the question either :) $\endgroup$ – Arjang Oct 18 '14 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.