Cardinality Proof (Set Theory)

  • Thread starter Bachelier
  • Start date
  • #1
376
0
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?
 

Answers and Replies

  • #2
yossell
Gold Member
365
16
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.
 
  • #3
22,129
3,297
Yosell is correct: the function you describe has E as domain, not [tex]E\cup F[/tex].

That said, you should try proving this theorem by induction. Try to prove it for |F|=1, the rest is easy/similar...
 
  • #4
disregardthat
Science Advisor
1,866
34
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.
 
  • #5
376
0
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:
  • #6
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,635
648
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 [tex]2^{\aleph_0}[/tex].

Also, there's a reason it's called the continuum hypothesis, not the continuum theorem
 
  • #7
376
0
If E isun countable, |E| could be larger than [tex]2^{\aleph_0}[/tex].

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

true. Thanks.
 
  • #8
376
0
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
 
  • #9
AKG
Science Advisor
Homework Helper
2,565
4
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 [itex]f: E \to E \cup F[/itex] defined by:

[tex]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[/tex]
 
  • #10
376
0
He means [itex]f: E \to E \cup F[/itex] defined by:

[tex]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[/tex]

thanks.
 
  • #11
AKG
Science Advisor
Homework Helper
2,565
4
No prob.
 
  • #12
mathwonk
Science Advisor
Homework Helper
2020 Award
11,208
1,414
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.
 
  • #13
AKG
Science Advisor
Homework Helper
2,565
4
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.
 

Related Threads on Cardinality Proof (Set Theory)

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
1
Views
1K
Replies
2
Views
870
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
12K
  • Last Post
Replies
8
Views
3K
Replies
16
Views
3K
Replies
3
Views
661
M
  • Last Post
Replies
13
Views
4K
Top