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

    Fredrik

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Re: "All but finitely many" theorem

    Hint:

    [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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: All but finitely many theorem
  1. Finite expectation (Replies: 1)

  2. Finite Elogx (Replies: 3)

Loading...