All but finitely many theorem

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

 

[blue_raver22]

The "all but finitely many" theorem is a fundamental result in mathematics that states that if a set has an infinite cardinality and two of its subsets are finite, then their intersection must be non-empty. This theorem is often used in various proofs, such as the one you mentioned regarding the convergence of a sequence in a metric space.

To understand why this theorem holds, let's consider an example. Suppose we have a set S with infinitely many elements, and two subsets A and B with finite elements. This means that there are only a finite number of elements that are not in A and B, and the rest of the elements must be in both A and B. In other words, the intersection of A and B must contain at least one element.

Now, let's generalize this to any set with infinite cardinality. Since there are infinitely many elements in S, there must be infinitely many elements that are not in either A or B. However, since both S\backslash A and S\backslash B are finite, there must be a finite number of elements that are not in both A and B. Therefore, the intersection of A and B must contain at least one element, proving the "all but finitely many" theorem.

This theorem has many applications in mathematics, such as in topology, number theory, and analysis. It also has implications in real-world problems, such as in computer science and economics. Overall, the "all but finitely many" theorem is a powerful tool that helps us understand the behavior of infinite sets and their subsets.