Construct a bijective map and prove it is bijective

$\begingroup$

S is a finite set with more than 1 element. Construct a bijective map $f:S\times \mathbb{Z}\rightarrow\mathbb{Z}$ and prove it is bijective. ($\mathbb{Z}$ is the set of all integers)

I'm at a lost at how to solve this. Wouldn't the cardinality of the domain be higher than the range? If so, then how is it possible to create a bijective function?

$\endgroup$ 3

1 Answer

$\begingroup$

You can come up with a bijection between the two sets, and for that reason they will have the same cardinality. It does seem like the domain should be bigger, but you can use a similar trick as you do to show that the integers and the rationals are the same cardinality (countable).

Imagine $S = {s_1, s_2, ..., s_n}$, with n finite. Then, have $f(s_1,1) = 1, f(s_2,1) = 2, ..., f(s_n,1) = n, f(s_1, 2) = n+1,$ etc.

$\endgroup$ 4

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy