Why is the All but Finitely Many Theorem Important?

[Rasalhague]

"All but finitely many" theorem

Let S be a set with cardinality |S|=\aleph_0. Let A,B \subseteq S. Let S\backslash A and S\backslash B be finite. Then A \cap B \neq \varnothing.

How can this be shown? I came across it as an assumption in a proof that a sequence in a metric space can converge to at most one limit.

 

[Fredrik]

There's something wrong with that assumption. I'll show you a counterexample.

S = the set of integers
A = all integers except 0
B = all integers except 1

S-A = {0}
S-B = {1}

$A\cap B$ = all integers except 0 and 1
$A\cap B$ ≠ ∅.

Also, you don't need any assumptions that look anything like that to prove that limits with respect to a metric are unique, but you probably know that. $x_n\to x$ means that every open ball around x contains all but a finite number of terms of the sequence. So if $x_n\to x$, $x_n\to y$ and x≠y, just define r=(1/2)d(x,y) and consider the open balls B(x,r) and B(y,r). Since all but a finite number of terms are in B(x,r), and since B(y,r) is disjoint from B(x,r), B(y,r) contains at most a finite number of terms. This contradicts the assumption that $x_n\to y$.

Edit: Apparently I can't even read today. thought your post said =∅, not ≠∅.

 

[micromass]

Hint:

S\setminus (A\cap B)=?

 

[Rasalhague]

Hint:

S\setminus (A\cap B)=?

Ah, I see, thanks!

S\setminus (A\cap B) = (S\setminus A)\cup (S\setminus B).

If A\cap B = \varnothing, then S\setminus (A\cap B) = S\setminus \varnothing = S. So (S\setminus A)\cup (S\setminus B) = S. But |S|=\aleph_0, whereas S\setminus A and S\setminus B are each finite, and the union of two finite sets is finite. Contradiction. Therefore A\cap B \neq \varnothing.

To see that the union of two finite sets is finite, let P,Q be finite. P\cup Q = P\cup (Q\setminus P). As a subset of a finite set, Q\setminus P is finite. As a http://planetmath.org/encyclopedia/CardinalityOfDisjointUnionOfFiniteSets.html , |P\cup (Q\setminus P)| = |P| + |Q\setminus P|. So |P\cup Q|=|P\cup (Q\setminus P)|=|P| + |Q\setminus P| \in \left \{ 0 \right \}\cup \mathbb{N}.