Bijective function $f: \mathbb{Z} \to \mathbb{N}$

Question

Is it possible to have a bijective function between two sets if the domain is bigger than the co-domain, for instance, a function $f:\mathbb{Z} \to \mathbb{N}$?

Answer 1

Consider the following function from $\mathbb{N}$ to $\mathbb{Z}$:

$$ 0 \mapsto 0 $$ $$ 1 \mapsto 1 \hspace{2cm} 2\mapsto -1$$ $$ 3 \mapsto 2 \hspace{2cm} 4\mapsto -2$$ $$ 5 \mapsto 3 \hspace{2cm} 6\mapsto -3$$ $$ \vdots \hspace{2cm} \vdots$$

And, more generally, if $n$ is even, $n\mapsto -\frac{n}{2}$; if $n$ is odd, $n \mapsto \frac{n+1}{2}$. This function would be bijective.

The trouble is, when we begin to deal with infinite sets, size is no longer a tangible thing. As you can see, $\mathbb{N} \subset \mathbb{Z}$, but acording to this function, both have the same size. We call this size cardinality, and we write $\#(\mathbb{N}) = \#(\mathbb{Z}) = \aleph_0$. That is, the cardinal of both sets is aleph sub zero. However, this is the smallest infinity out there (and we know it as the countable infinity). The cardial of, say, the real numbers $\mathbb{R}$ is bigger than the cardinal $\aleph_0$ because you can't generate a bijective function from any countable set to the reals, this is known as Cantor's diagonal argument.

Answer 2

Yes, it is impossible for a bijection to be constructed between two sets with different cardinalities. In fact, that's how we figure out in math if two sets are equal in size. A bijection can be formed between two sets if and only if they have the same cardinalities.

The two sets ($\mathbb{Z}$ and $\mathbb{N}$) you mentioned in your question actually have the same cardinality, since you can form a bijection between them, as in Miguel's answer.

However, if you take the two sets $\Bbb{Z}$ and $\Bbb{R}$, no matter what you try to do, no function can be formed that maps an integer to a real number that is both injective and surjective. That's how we discovered the different infinities.

It's quite an interesting topic, which I highly recommend reading about.

*EDIT* It turns out that $$2^{|\Bbb{Z}|}=\Bbb{R}$$ or more generally, $$|S|<2^{|S|}$$ I guess we both learned something today.

Answer 3

Let $\mathbb{N}$ denote the set of positive integers. Consider the function $\sigma$ from $\mathbb{N}$ to $\mathbb{Z}$ defined by $\sigma(n)=(-1)^n \lfloor\frac{n}{2}\rfloor$ for every $n\in\mathbb{N},$ where $\lfloor x\rfloor$ denotes the greatest integer part of $x.$ Then $\sigma$ is also a bijection from $\mathbb{N}$ onto $\mathbb{Z}.$