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?
Best Answer
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").