Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

All but finitely many theorem

  1. Mar 27, 2012 #1
    "All but finitely many" theorem

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

    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.
  2. jcsd
  3. Mar 27, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: "All but finitely many" theorem

    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 ≠∅.
    Last edited: Mar 27, 2012
  4. Mar 27, 2012 #3
    Re: "All but finitely many" theorem


    [tex]S\setminus (A\cap B)=????[/tex]
  5. Mar 27, 2012 #4
    Re: "All but finitely many" theorem

    Ah, I see, thanks!

    [itex]S\setminus (A\cap B) = (S\setminus A)\cup (S\setminus B).[/itex]

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

    To see that the union of two finite sets is finite, let [itex]P,Q[/itex] be finite. [itex]P\cup Q = P\cup (Q\setminus P)[/itex]. As a subset of a finite set, [itex]Q\setminus P[/itex] is finite. As a http://planetmath.org/encyclopedia/CardinalityOfDisjointUnionOfFiniteSets.html [Broken], [itex]|P\cup (Q\setminus P)| = |P| + |Q\setminus P|[/itex]. So [itex]|P\cup Q|=|P\cup (Q\setminus P)|=|P| + |Q\setminus P| \in \left \{ 0 \right \}\cup \mathbb{N}[/itex].
    Last edited by a moderator: May 5, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook