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.
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 = 1B, gf = 1A.
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.