# Cardinality

• Sep 10th 2012, 05:41 PM
franios
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.
• Sep 10th 2012, 09:06 PM
Vlasev
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?
• Sep 10th 2012, 09:13 PM
kalyanram
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|$

Quote:

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.
• Sep 10th 2012, 10:38 PM
Vlasev
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?
• Sep 11th 2012, 12:45 AM
johnsomeone
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.
• Sep 13th 2012, 08:15 AM
Deveno
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.