0
$\begingroup$

This question already has an answer here:

I'm currently trying to write up a solution to the following problem:

If $ \displaystyle A_1 \supseteq A_2 \supseteq A_3 ... $ where each $ \displaystyle A_j $ is a non-empty, finite set of real numbers, prove (or disprove) the intersection $\displaystyle \bigcap_{n \in \mathbb{N}} A_n $ is non-empty and finite.

My thoughts: this is obviously true, as for some point onwards we must, for some $ \displaystyle N \in \mathbb{N}$, have the following equality for all $ \displaystyle k \ge N$: $\displaystyle A_k = A_N$.

If this did not hold, then the only way it could fail would be for us to have strict super-set relations (at some stage), which can't continue indefinitely, for we know $ \displaystyle A_1$ is finite, and hence each set is finite.

However, I'm having trouble writing this up as a proper mathematical rigorous direct proof; my thought for a proof is something like follows.

Proof. We prove this by contrapostion. It follows that we should consider either (i) the intersection is infinite, or (ii) the intersection is empty.

If (i), then as the intersection is a subset of each $\displaystyle A_j$ for every $ \displaystyle j \in \mathbb{N}$, it follows that, in particular, $ \displaystyle A_1$ must be infinte, because it has an infinite subset.

We now suppose (ii); then for any element, $ \displaystyle x $, we cannot have $ \displaystyle x \in \bigcap_{N \in \mathbb{N}} A_n$. In particular, if $ \displaystyle A_1 = \{a_1, ..., a_k\}$, we can find a $ \displaystyle j_1 \in \mathbb{N}$ such that $\displaystyle a_1 \not\in A_{j_1}$, and generally find a $ \displaystyle j_s \in \mathbb{N}$, with $\displaystyle j_s > j_t$ if $ \displaystyle t < s$ such that $\displaystyle a_s \not\in A_{j_s}$, where $ \displaystyle 1 \le s \le k$. In particular, for $ \displaystyle s = k$, by the fact the $ \displaystyle j's$ are increasing, it follows $ \displaystyle a_1, ..., a_k \not\in A_{j_k}$, and from the original superset relation, this set is empty. $ \displaystyle \square$

My concerns: I think this is a valid proof, but I'd much rather prove it directly by using the first observation that eventually the subsets of $ \displaystyle A_1$ are all equal. However, I'm finding this hard to explicitly, and basically end up writing the above argument to show that eventually the sets are empty.

How can one prove this directly?

$\endgroup$

marked as duplicate by Community Jun 30 '15 at 14:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Why should it follow that the intersection is either infinite or empty? You can have intersection of infinite sets which is finite so as part of the proof you must use the finiteness in some other way. As a hint I would point out that you can look at the size of the differences $|A_i\setminus A_{i+1}|$ and consider how this sequence behaves. $\endgroup$ – DRF Jun 30 '15 at 14:31
  • $\begingroup$ I'm proving the contrapostive so I assume it is not (finite and non-empty), so it is either infinite or empty, and I split the cases accordingly. I don't think your suggestion is helpful for this problem. $\endgroup$ – WierdFishes Jun 30 '15 at 14:38
  • $\begingroup$ Ahh I see your point I misread what you were trying to prove. As for the hint I think it's quite responsive a sketch of the proof would be as follows: Let $|A_i\setminus A_{i+1}|=s_i$. Since $|A_1|\geq \sum_{i=0}^\infty s_i$ only finitely many $s_i$ are non zero. Let $j=\max\{i:s_i\neq 0\}$ then $A_{j+1}$ is the intersection of the infinite sequence and thus is non-empty. $\endgroup$ – DRF Jun 30 '15 at 14:44
  • $\begingroup$ I'm not sure that is a direct proof (with your claim requiring a proof via contradiction/contraposition), or at least, even if it is, it is very "removed" from the problem in-so far you are invoking something more complicated unnecessarily. It's rather like saying "is 2 > 1" and replying; yes, consider f(x) = 2x and g(x) = x on [0.5,5]. Then f - g = g and g is strictly increasing, in particular g(0.5) = 0.5, hence f - g > 0 on the interval, (0.5,5) so f(1) > g(1). I wouldn't class that as a nice proof. $\endgroup$ – WierdFishes Jun 30 '15 at 14:50
  • $\begingroup$ Hmm. I'm not sure what you mean by more complicated then necessary? All I'm using is being able to count, which unless you're using dedekind finiteness you are probably using anyway. I admit that it is not obvious that an infinite sum of natural numbers being finite implies that only finitely many of the $s_i$ are non zero can be proved directly. $\endgroup$ – DRF Jun 30 '15 at 15:00
1
$\begingroup$

Sketch (but still using contradiction): Let $A=\cap A_n$. Then, you know $A\subseteq A_1$, which is a finite set, so $A$ is finite.

Let $A_1=\{x_1,\cdots,x_k\}$ if $A=\emptyset$, then $x_i\not\in A$, so there is some $m_i$ such that $x_i\not\in A_{m_i}$. But then, for all $n\geq m_i$, $x_i\not\in A_n$. Let $m=\max\{m_i\}$. Then, $A_m\cap A_1=\emptyset$, but $A_m\subseteq A_1$, so $A_m=\emptyset$, a contradiction.

$\endgroup$

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