Thread: Cardinality

Show that the following pairs of sets have the same cardinality:

The set E of all even integers and the set Z​ of all integers.

Just giving you the solution won't help you. Instead, can you tel me what you've tried so far? Any relevant definitions you can think of?

Spoiler:

Two sets have the same cardinality if bijection between then consider defined as .
is a bijection. Hence

Originally Posted by Vlasev

Just giving you the solution won't help you. Instead, can you tel me what you've tried so far? Any relevant definitions you can think of?

I did not see you post sorry for the spoiler.

It's ok. Maybe you can put SPOILER /SPOILER around the solution (with square brackets) to hide it. Also, your solution could use some insight to make it better in terms of explanation. That is, where did this function come from?

Someone already gave a spoiler, so I'll give another one that I think is more straightforward.
Let by .
Let by .
Then for all , and for all .
Thus is a bijection, and so and have the same cardinality.

the previous post uses a fact which may appear obvious, so i am hesitant to post it here, but perhaps the OP may find it useful:

the function f:A→B is a bijection if and only if there is a function g:B→A with fg = 1_B, gf = 1_A.

suppose that there is such a function g, and f(a) = f(a').

then g(f(a)) = g(f(a')), so gf(a) = gf(a'), and thus a = a'. hence f is injective.

now let b be any element of B. then b = fg(b) = f(g(b)), so g(b) is an element of A which is a pre-image (under f) of b, thus f is surjective.

*******

on the other hand, suppose f is bijective. define g:B→A by: g(f(a)) = a

is this a function (that is, is it well-defined)? well, since f is surjective, every b in B is some f(a), for some a in A. but we need to show that if f(a) = f(a'), g(f(a)) = g(f(a')), which follows because:

g(f(a)) = a = a' = g(f(a')), since f is injective.

*******

in fact, it suffices to show that we have two surjections f:A→B and g:B→A to show that |A| = |B|, but i will not prove that, here.