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}$.