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

The set E of all even integers and the setZ of all integers.

Printable View

- Sep 10th 2012, 05:41 PMfraniosCardinality
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 PMVlasevRe: 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 PMkalyanramRe: Cardinality
- Sep 10th 2012, 10:38 PMVlasevRe: 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 AMjohnsomeoneRe: Cardinality
Someone already gave a spoiler, so I'll give another one that I think is more straightforward.

Let $\displaystyle f: \mathbb{Z} \rightarrow \mathbb{E}$ by $\displaystyle f(x)=2x$.

Let $\displaystyle g: \mathbb{E} \rightarrow \mathbb{Z}$ by $\displaystyle g(t)=t/2$.

Then $\displaystyle f ( g(t) ) = t$ for all $\displaystyle t \in \mathbb{E}$, and $\displaystyle g ( f(x) ) = x$ for all $\displaystyle x \in \mathbb{Z}$.

Thus $\displaystyle f$ is a bijection, and so $\displaystyle \mathbb{E}$ and $\displaystyle \mathbb{Z}$ have the same cardinality. - Sep 13th 2012, 08:15 AMDevenoRe: 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.