Homework Help: Infinite/Finite Set Proof

1. Aug 4, 2013

ribbon

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. Aug 4, 2013

ribbon

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.

3. Aug 4, 2013

LCKurtz

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.

4. Aug 4, 2013

ribbon

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?

5. Aug 5, 2013

LCKurtz

Sure. Now can you figure out how to use that kind of thinking for your original problem.

6. Aug 5, 2013

ribbon

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?

7. Aug 5, 2013

LCKurtz

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

8. Aug 5, 2013

vela

Staff Emeritus
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.