1
$\begingroup$

Statement of the problem: Prove that if $A_1 \supseteq A_2 \supseteq A_3 \cdots$ are all finite, nonempty sets of real numbers, then the intersection $\bigcap_{n=1}^{\infty} A_n$ is also finite and nonempty.

My solution: $\bigcap_{n=1}^{\infty} A_n = \emptyset.$ Then at least one $A_n$ is disjoint from the rest - contradiction, since each $A_n \subseteq A_{n-1}.$ Next assume that the intersection has infinite cardinality - contradiction, since $A_n \supseteq \bigcap_{n=1}^{\infty} A_n,$ but we have $A_n$ finite.

This is a homework problem and this is what I will be turning in regardless of any answers I get. I would like to know if there is a direct proof of this claim. I had considered trying to show that $\exists x \in A_n$ for each choice of $n,$ which would show that the intersection is nonempty, but: a) I don't know how to do this, and b) I still would not be able to prove the intersection was finite except by contradiction.

Thanks!

edit: Moreover, we were told not to use induction on this problem. But if $A_1$ is finite, can't we reduce the collection of A_n's to a subset of the power set of $A_1$ and then induct?

  • 0
    @JTL: Yes, it's true that $\{A_n\mid n\in\mathbb{N}\}\subseteq \mathcal{P}(A_1)$; this holds whether or not you assume that $A_1$ is finite. But if you were told not to use induction, then you shouldn't be "inducting"... at least not obviously so (it may be difficult to *actually* avoid induction; if you use the fact that every nonempty set of positive integers has a least element, you are essentially using induction, for example; or if you say "and so on..." you are implicitly using induction, etc.)2011-06-27

2 Answers 2

4

That the intersection is finite follows because it is contained in $A_1$, which is finite, and a subset of a finite set is always finite.

Note: What follows was written before the condition not to use induction was added to the problem.

One possibility to show the intersection is nonempty is to do it by induction on $|A_1|$.

If $|A_1|=1$, say $A_1 = \{a\}$. Since $A_n\subseteq A_1$ and $A_n\neq\emptyset$, then $A_n=\{a\}$; this holds for all $n$, so $\cap_{n=1}^{\infty} A_n = \cap_{n=1}^{\infty}\{a\} = \{a\}$ is nonempty.

Assume the result holds for any family $B_1\supseteq B_2\supseteq B_3\supseteq\cdots$ of finite nonempty sets in which $|B_1|\lt |A_1|=k$. We now prove it for $|A_1|=k$.

If all $A_n$ have $k$ elements, then $A_n=A_1$ for all $n$, so $\cap_{n=1}^{\infty}A_n = A_1$ is nonempty. Otherwise, let $n_0$ be the smallest index such that $A_{n_0}$ has fewer than $k$ elements. Define $B_1=A_{n_0}$, $B_2=A_{n_0+1}$, and so on, $B_k = A_{n_0+k-1}$. Then the family $B_1\supseteq B_2\supseteq B_3\supseteq\cdots$ satisfies the induction hypothesis, so $\cap_{n=1}^{\infty}B_k\neq\emptyset$.

Now simply show that $\cap_{n=1}^{\infty}A_n = \cap_{n=1}^{\infty}B_n$ to finish the proof.


How to prove it without using induction? Finiteness still follows directly from the fact that $\cap_{n=1}^{\infty}A_n \subseteq A_1$, and a subset of a finite set is finite.

Let $A=\{a_1,\ldots,a_m\}$. If $a_1\in A_n$ for all $n$, then $a_1$ lies in the intersection and we are done. Otherwise, let $n_1$ be an index such that $a_1\notin A_{n_1}$. If $a_2\in A_n$ for all $n$, we are done; otherwise, let $n_2$ be an index such that $a_2\notin A_{n_2}$. Continue this way to find either that one of $a_1,\ldots,a_{m-1}$ is in the intersection (and wee are done), or else to find $n_1,\ldots,n_{m-1}$ such that $a_i\notin A_{n_i}$. Now let $N=\max\{n_1,\ldots,n_{m-1}\}+1$. Then $A_N\subseteq A_{n_i}$, and since $a_i\notin A_{n_i}$, then $a_i\notin A_N$, for $i=1,\ldots,m-1$. Since $A_N\subseteq A_1 \{a_1,\ldots,a_m\}$, then $A_N\subseteq \{a_m\}$. Since $A_N$ is not empty, then $A_N=\{a_m\}$. For every $n\geq N$, we have $A_n\subseteq A_N=\{a_m\}$, and since $A_n$ is not empty, then $A_n=\{a_m\}$.

Thus, for all $n\geq N$ we have $a_m\in A_n$; and since $A_N\subseteq A_k$ for all $k\lt N$, we conclude that $a_m\in A_n$ for all $n\in\mathbb{N}$. Thus, $a_m\in \cap_{n=1}^{\infty} A_n$, which proves the intersection is not empty.

(In fact, there is a sort of hidden induction in the statement "continue this way", but it may pass muster as "not using induction").

0

Since the intersection is a subset of a finite set (namely $A_1$) we know that it is finite.

The simplest way to prove that the intersection is non-empty is to use the theorem that any nested sequence of compact sets is non-empty (which generalizes the nested interval property of closed intervals).

This proof is surely what the instructor intended, since the students were asked not to use induction in their proofs.

Best - Jonathan