# Cardinality Proof (Set Theory)

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 gonna 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
Gold Member
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.

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.

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?

Last edited:
Office_Shredder
Staff Emeritus
Gold Member
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

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.

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
Homework Helper
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$$

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
Homework Helper
No prob.

mathwonk