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}$?

  • 12
    $\begingroup$ What if I told you $\mathbb{Z}$ and $\mathbb{N}$ have the same size? $\endgroup$ Nov 19 '14 at 1:39
  • 3
    $\begingroup$ Perfectly possible. For example there is a bijection from the natural numbers to the even natural numbers, given by $f(n)=2n$. $\endgroup$ Nov 19 '14 at 1:41
  • 2
    $\begingroup$ As pointed out by the comments above this gets into the question of what you mean by "domain > co-domain". If both of the sets are finite then it is impossible (you should try to prove it!). But $\mathbb{Z}$ and $\mathbb{N}$ are both countable, and have the same "size". It might be good to review what it means for a set to be finite, countable, and uncountable. $\endgroup$
    – wondermech
    Nov 19 '14 at 1:44

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.

  • 2
    $\begingroup$ In other words,$$n\mapsto\frac{1-(2n+1)(-1)^n}4.$$ $\endgroup$
    – bof
    Nov 19 '14 at 2:18

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.

  • 1
    $\begingroup$ The statement "A bijection can be formed between two sets if and only if they have the same cardinalities" looks like a theorem here, but it is acctually just a definition of what we mean by cardinality. $\endgroup$
    – Winther
    Nov 19 '14 at 2:02

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}.$

  • $\begingroup$ Actually $(-1)^n\lfloor\frac{n}{2}\rfloor=\frac{1+(-1)^n(2n-1)}{4}.$ $\endgroup$
    – azc
    Aug 16 '20 at 7:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.