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
    It is false in general that if the intersection is empty, then one of the $A_n$ is disjoint from the rest. For example, the intersection of $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$ is empty, but none of the three is disjoint from the rest. For nested examples, take $A_n = [n,\infty)$, $n=1,2,3,\ldots$; the intersection is empty, but no $A_n$ is disjoint from the rest.2011-06-27
  • 0
    @Arturo Wow, quick response! I had read this fact in my textbook, but I was unable to come up with a counterexample for finite nested sets. Is this true in this case?2011-06-27
  • 0
    Are you sure that each $A_n$ is finite? A decreasing chain of non-empty finite sets has to stabilize after finitely many steps, that means that for there is $k$ such that for $n>k$ we have $A_n=A_k$.2011-06-27
  • 0
    @Asaf I gave the problem exactly as stated. I was worried it was badly formed as well and if it is, I'm not sure how to proceed2011-06-27
  • 0
    @JTL: "This fact". Which fact are you refering to? The given statement (the one you are trying to prove) is true; one proof I give below (induction on $|A_1|$); another is to prove what Asaf says: show that if $|A_1|=k$, then at most $k-1$ of the inclusions can be proper inclusions, and the rest must be equalities (since at each proper inclusion you "lose" at least one element, and every set is assumed to be nonempty).2011-06-27
  • 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