1. ## 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.

2. ## Re: Cardinality

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?

3. ## Re: Cardinality

Spoiler:
Two sets have the same cardinality if $\exists$ bijection between then consider $f:Z \rightarrow E$ defined as $f(x) = \left \{ \begin{matrix} -4x & x < 0 \\ 2(1+2x) & x > 0 \\ 2 & x=0 \end{matrix} \right.$.
$f$ is a bijection. Hence $|Z|=|E|$

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.

4. ## Re: Cardinality

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?

5. ## Re: Cardinality

Someone already gave a spoiler, so I'll give another one that I think is more straightforward.
Let $f: \mathbb{Z} \rightarrow \mathbb{E}$ by $f(x)=2x$.
Let $g: \mathbb{E} \rightarrow \mathbb{Z}$ by $g(t)=t/2$.
Then $f ( g(t) ) = t$ for all $t \in \mathbb{E}$, and $g ( f(x) ) = x$ for all $x \in \mathbb{Z}$.
Thus $f$ is a bijection, and so $\mathbb{E}$ and $\mathbb{Z}$ have the same cardinality.

6. ## Re: 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.