1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Infinite/Finite Set Proof

  1. Aug 4, 2013 #1
    1. The problem statement, all variables and given/known data
    Let S be in finite and, A a subset of S be finite.
    Prove that that the cardinality of S = the cardinality of S excluding the subset of A.



    2. Relevant equations



    3. The attempt at a solution
    We can write out the finite subset A as (x1, x2, ... xn) which can be put into a one to one correspondence with N. S is infinite so a bijection to N is not possible by definition. The cardinality of S excluding A is still uncountable but I don't see why they MUST have the same cardinality.
     
  2. jcsd
  3. Aug 4, 2013 #2
    I know to show cardinalities are equal I need to be able to construct a bijection between them...

    Bijection between two infinite sets seems confusing.
     
  4. Aug 4, 2013 #3

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Start with something simple. Do you see how to make a bijection between the natural numbers ##\mathbb N## and ##\mathbb N## excluding {1,2,3,4,5,6,7,8,9,10}? It's the same idea.
     
  5. Aug 4, 2013 #4
    Sure I'd map 1 from the first set N to say 11, map 2 to 12, 3 to 13....

    My bijection would be for n in N (the fully inclusive N) f(n) = n+ 10?
     
  6. Aug 5, 2013 #5

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Sure. Now can you figure out how to use that kind of thinking for your original problem.
     
  7. Aug 5, 2013 #6
    I guess how I would write it is problematic for me, I understand your idea, take that excluding set A, which is a set from x1 to xn and begin the mapping from a xn + 1. But how do I know my excluded set is ordered, and how do I know that the numbers are consecutively equally spaced the set from 1 to 10 is easy to visualize as an example. But this random set A seems like it could cause problems for the function I would have to write if it isnt as simple.

    Or does what I mention even matter when writing a bijection?
     
  8. Aug 5, 2013 #7

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You're right, the set in your problem isn't ##\mathbb R##. But it's the idea that counts. Can you find an infinite sequence of distinct points from S where the first N terms of the sequence are the points from A (which has only N points) and the rest are not from A? Then....
     
  9. Aug 5, 2013 #8

    vela

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You seem to be assuming S is uncountable, but is that really the case? In the problem statement, you simply say S is infinite, so you need to make sure your argument works for both the countably infinite and uncountably infinite cases.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Infinite/Finite Set Proof
Loading...