12
$\begingroup$

I learned that the set of all one-to-one mappings of $\mathbb{N}$ onto $\mathbb{N}$ has cardinality $|\mathbb{R}|$.

What about surjective functions and bijective functions?

$\endgroup$
4

5 Answers 5

18
$\begingroup$

The same. It suffices to show that there are $2^\omega=\mathfrak c=|\Bbb R|$ bijections from $\Bbb N$ to $\Bbb N$. Let $P$ be the set of pairs $\{2n,2n+1\}$ for $n\in\Bbb N$. (My $\Bbb N$ includes $0$.) For each $S\subseteq P$ define

$$f_S:\Bbb N\to\Bbb N:k\mapsto\begin{cases} k+1,&\text{if }k\in p\text{ for some }p\in S\text{ and }k\text{ is even}\\ k-1,&\text{if }k\in p\text{ for some }p\in S\text{ and }k\text{ is odd}\\ k,&\text{if }k\notin\bigcup S\;; \end{cases}$$

the function $f_S$ simply interchanges the members of each pair $p\in S$. Clearly $|P|=|\Bbb N|=\omega$, so $P$ has $2^\omega$ subsets $S$, each defining a distinct bijection $f_S$ from $\Bbb N$ to $\Bbb N$. Thus, there are at least $2^\omega$ such bijections. And each function of any kind from $\Bbb N$ to $\Bbb N$ is a subset of $\Bbb N\times\Bbb N$, so there are at most $2^\omega$ functions altogether. Thus, there are exactly $2^\omega$ bijections.

$\endgroup$
4
$\begingroup$

Both have cardinality $2^{\aleph_0}$. Note that the set of the bijective functions is a subset of the surjective functions.

To see that there are $2^{\aleph_0}$ bijections, take any partition of $\Bbb N$ into two infinite sets, and just switch between them. It is not hard to show that there are $2^{\aleph_0}$ partitions like that, and so we are done.

$\endgroup$
3
  • 1
    $\begingroup$ I leave the part of proving there are $2^{\aleph_0}$ partitions like that as an exercise, but if you want I can elaborate or give hints. $\endgroup$
    – Asaf Karagila
    Apr 20, 2013 at 9:33
  • $\begingroup$ I would be very thankful if you elaborate. $\endgroup$
    – HeMan
    Sep 25, 2017 at 7:04
  • 1
    $\begingroup$ For every $A\subseteq\Bbb N$ which is infinite and has an infinite complement, there is a permutation of $\Bbb N$ which "switches" $A$ with its complement (in an ordered fashion). How many infinite co-infinite sets are there? Well, only countably many subsets are finite, so only countably are co-finite. It follows there are $2^{\aleph_0}$ subsets which are infinite and have an infinite complement. So there are at least $2^{\aleph_0}$ permutations of $\Bbb N$. $\endgroup$
    – Asaf Karagila
    Sep 25, 2017 at 15:46
4
$\begingroup$

In addition to Asaf's answer, one can use the following direct argument for surjective functions:


Consider any mapping $f: \Bbb N \to \Bbb N$ such that:

$$\forall n \in \Bbb N: f(2n) = n$$

Then $f$ is surjective, but for any $g: \Bbb N \to \Bbb N$ we may define $f(2n+1) = g(n)$, effectively showing that there are at least $2^{\aleph_0}$ surjective functions -- we've demonstrated one for every arbitrary function $g: \Bbb N \to \Bbb N$.

$\endgroup$
3
$\begingroup$

Choose one natural number. How many are left to choose from?

More rigorously, $$\operatorname{Aut}\mathbb{N} \cong \prod_{n \in \mathbb{N}} \mathbb{N} \setminus \{1, \ldots, n\} \cong \prod_{n \in \mathbb{N}} \mathbb{N} \cong \mathbb{N}^\mathbb{N} = \operatorname{End}\mathbb{N},$$ where $\{1, \ldots, 0\} := \varnothing$. The first isomorphism is a generalization of $\#S_n = n!$ Edit: but I haven't thought it through yet, I'll get back to you.

$\endgroup$
6
  • 2
    $\begingroup$ I don't understand that equation. $\endgroup$
    – Asaf Karagila
    Apr 20, 2013 at 10:03
  • 1
    $\begingroup$ The first two $\cong$ symbols (reading from the left, of course). Especially the first. $\endgroup$
    – Asaf Karagila
    Apr 20, 2013 at 10:10
  • 1
    $\begingroup$ @Asaf, Suppose you want to construct a bijection $f: \mathbb{N} \to \mathbb{N}$. You can do it by taking $f(0) \in \mathbb{N}$, $f(1) \in \mathbb{N} \setminus \{f(0)\}$ etc. I'll fix the notation when I finish writing this comment. The second isomorphism is obtained factor-wise. $\endgroup$ Apr 20, 2013 at 10:18
  • 2
    $\begingroup$ Ah. I understand your claim, but the part you wrote in the answer is wrong. Because $f(0)=2; f(1)=2; f(n)=n+1$ for $n>1$ is a function in that product, and clearly this is not a bijection (it is neither surjective nor injective). $\endgroup$
    – Asaf Karagila
    Apr 20, 2013 at 10:25
  • 1
    $\begingroup$ @Asaf, I admit I haven't worked out the first isomorphism rigorously, but at least it looks plausible :D And it's just an isomorphism, I don't claim that it's the trivial one. $\endgroup$ Apr 20, 2013 at 10:26
-1
$\begingroup$

Upper bound is $N^N=R$; lower bound is $2^N=R$ as well (by consider each slot, i.e. element on $x-$axis, as having $2i, 2i+1$ two choices and each combination of such choices is bijection). So answer is $R$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .