Cardinality Proof (Set Theory)

[Bachelier]

I'm trying to prove the following:
if E is infinite set and F is finite set. prove that E and E U F have the same
cardinality ?

So what I did:
I'm going to use Schroeder-Bernstein Thm.
1st, it's easy to show that |E| is less of equal to |E U F| since it is a subset of this latter.

Now I must show that |E U F| <= |E|
So I need to build an injection from E U F to E

Can I just define f(e) = e. Clearly this is 1-1 because if f(e1)= f(e2) then e1=e2. Hence |E U F| <= |E|

is this correct?

 

[yossell]

I may not have followed you correctly,

but to show that the cardinality of EUF is < or = to E, your injection should be defined on the whole of EUF. It seems that the f you construct is defined only on E, and so doesn't map elements of F anywhere.

 

[micromass]

Yosell is correct: the function you describe has E as domain, not $$E\cup F$$.

That said, you should try proving this theorem by induction. Try to prove it for |F|=1, the rest is easy/similar...

 

[disregardthat]

You can assume E and F are disjoint (or else just weed out the elements appearing in E). Choose a sequence a_n in E indexed by natural numbers, and let F = {b_1,...,b_k}. Define a bijection to E U F from E by defining f : E - {a_1,...,} --> E U F by f(x) = x, and f(a_i) = b_i for i<=k, and f(a_{i+k})=a_i. for i >= 1.

 

[Bachelier]

You can assume E and F are disjoint (or else just weed out the elements appearing in E). Choose a sequence a_n in E indexed by natural numbers, and let F = {b_1,...,b_k}. Define a bijection to E U F from E by defining f : E - {a_1,...,} --> E U F by f(x) = x, and f(a_i) = b_i for i<=k, and f(a_{i+k})=a_i. for i >= 1.

WOW, nice bijection. Thanks.

I was thinking, can this be a one line proof using the Continuum Thm. Since there exists no set with cardinality between Aleph naught and 2 to the power of aleph naught. Then there are 2 cases: where E is countable and where it isn't.
If E is countable then |E| = aleph naught and hence F U E is countable as well.
If E in uncoutable then |E| = |IR| = 2^aleph-naught and so is |F U E|.

What do you think?

 

[Office_Shredder]

WOW, nice bijection. Thanks.

I was thinking, can this be a one line proof using the Continuum Thm. Since there exists no set with cardinality between Aleph naught and 2 to the power of aleph naught. Then there are 2 cases: where E is countable and where it isn't.
If E is countable then |E| = aleph naught and hence F U E is countable as well.
If E in uncoutable then |E| = |IR| = 2^aleph-naught and so is |F U E|.

What do you think?

If E isun countable, |E| could be larger than $$2^{\aleph_0}$$.

Also, there's a reason it's called the continuum hypothesis, not the continuum theorem

 

[Bachelier]

If E isun countable, |E| could be larger than $$2^{\aleph_0}$$.

Also, there's a reason it's called the continuum hypothesis, not the continuum theorem

true. Thanks.

 

[Bachelier]

You can assume E and F are disjoint (or else just weed out the elements appearing in E). Choose a sequence a_n in E indexed by natural numbers, and let F = {b_1,...,b_k}. Define a bijection to E U F from E by defining f : E - {a_1,...,} --> E U F by f(x) = x, and f(a_i) = b_i for i<=k, and f(a_{i+k})=a_i. for i >= 1.

Thank you Jarle. great bije.
are we talking about the same function here? meaning

f: E - {a_1,...,} --> E U F
x --> x
and:
F: E ----------> E U F
a_i --------> b_i
a_{i+k})---> a_i

 

[AKG]

Thank you Jarle. great bije.
are we talking about the same function here? meaning

f: E - {a_1,...,} --> E U F
x --> x
and:
F: E ----------> E U F
a_i --------> b_i
a_{i+k})---> a_i

He means $f: E \to E \cup F$ defined by:

$$f(x) = \left\{\begin{array}{cc}x,&\mbox{ if } x \notin \{ a_1, \dots \}\\b_i, & \mbox{ if } \exists i \leq k (x = a_i)\\a_{i-k}, & \mbox{ if }\exists i > k (x = a_i)\end{array}\right$$

 

[Bachelier]

He means $f: E \to E \cup F$ defined by:

$$f(x) = \left\{\begin{array}{cc}x,&\mbox{ if } x \notin \{ a_1, \dots \}\\b_i, & \mbox{ if } \exists i \leq k (x = a_i)\\a_{i-k}, & \mbox{ if }\exists i > k (x = a_i)\end{array}\right$$

thanks.

 

[AKG]

No prob.

 

[mathwonk]

can you generalize this argument to show if A is an infinite set then there is an injection from Ax{0,1} to A? As a corollary it would follow that if there is an injection from A to B, then AUB has the same cardinality as B.

 

[AKG]

can you generalize this argument to show if A is an infinite set then there is an injection from Ax{0,1} to A? As a corollary it would follow that if there is an injection from A to B, then AUB has the same cardinality as B.

I assume that by "generalize this argument" you mean, at the very least, "prove this fact in ZF alone, i.e. without choice." The answer is "no," in fact it's possible to have an infinite set A (i.e. one that cannot be put into bijection with a natural number) such that for no proper subset B of A is there a bijection between B and A (i.e. A is not Dedekind-infinite). I don't know how one would construct the appropriate ZF model, but this is one of those standard facts.