Bijections Question (from TAACOPS) About Integers to Evens

Question

I was working on a problem about bijections (just learned about this today, so please be harsh/uber-specific when answering/correcting me so that I get a handle on the terminology). So far, my very limited understanding of a bijection is that it is both onto (meaning that the function in question's range is all reals) and a 1-to-1 relationship (correct me if I'm wrong).

The problem that I'm working on is this:

Let A denote the even integers (remember, 0 is even). Is there a bijection from $\mathbb Z$ to A?

Now the answer that I got was yes, but I struggle to understand how. Since a bijection is 1-to-1, that means that for every one input there is exactly one output for the function. So what would the bijection describing the transformation from $\mathbb Z$ to A look like?

To give you an example of what I mean, a previous problem/exercise had asked whether there was a bijection from $\mathbb N$ to $\mathbb Z$. The answer (which I managed to solve) was

$$f(x) = \begin{cases} x/2, \text{if x is even} \\ -\frac{x+1}{2}, \text{if x is odd} \end{cases}$$

This ensures that every single natural number gets mapped as an integer successfully, and accounts for all cases. I am trying to look for a similar one for $\Bbb Z$ to A.

Thanks!

Answer 1

You can use the map $f:\mathbb{Z}\to A$ defined by $n\mapsto 2n.$ In many, if not most cases, it is a good idea to prove that a map is a bijection by proving that it is an injection and a surjection. The function $f$ is an injection because $$2n=2m\implies n=m$$ and $f$ is a surjection because for all $t\in A,$ there exists an element $r\in \mathbb{Z}$ such that $f(r)=t,$ namely $r=\frac{t}{2}.$ Also I recommend not using the term "one-to-one" for a bijection because, although a "one-to-one correspondence" can refer to a bijection, it is easy to confuse with a "one-to-one function" which is another term for an injection. Confusing, I know.

Of course, there are other ways of proving that a bijection exists, like taking the composition of bijections, taking the inverse of a bijection, or using the Cantor-Schröder–Bernstein theorem.

Let me know if you have any questions. By the way, that's a great book by Zeitz. I read an older edition years ago when I was in high school.

Answer 2

A wonderful and very important theorem is the Cantor-Schröder-Bernstein Theorem. It says, if $|A|\leq |B|$ (This means that there is an injection from $A$ to $B$) and $|B|\leq |A|$ then there is a bijection between $A$ and $B$.

A common form to construct injections with natural numbers, or integers, is using prime numbers. For example, define a function $f:\mathbb{Z}\longrightarrow \mathbb{N}$ with $f(n)= 3^{n}$ if $n \in \mathbb{N}$ and $f(z)= 2^{|z|}$ if $z\in \mathbb{Z}$. So you have a injection between $\mathbb{Z}$ and $\mathbb{N}$.

Another important fact is the following: If $f,g$ are injections, then $f\circ g$ is an injection too. Using these two theorems you can construct an injection from $\mathbb{Z}$ to $A$, and for Cantor-Schörer-Bernstein you will have that $|A|=||\mathbb{Z}|$