Does there exist a surjection from the natural numbers to the reals?

[docnet]

Homework Statement

1) What does it mean if two sets $X$ and $Y$ have the same cardinality?

2) Given sets $A$ and $B$ what does $|A|\leq |B|$ mean?

3) Does there exist a surjection from the natural numbers to the reals? If so, define one. If not, explain why one cannot exist.

Relevant Equations

$\mathbb{N}$ and $\mathbb{R}$

1)
Two sets have the same cardinality if there exists a bijection (one to one correspondence) from $X$ to $Y$. Bijections are both injective and surjective. Such sets are said to be equipotent, or equinumerous. (credit to wiki)

2)
$|A|\leq |B|$ means that there is an injective function from $A$ to $B$. An injective function maps distinct elements of $A$ to distinct elements in $B$.

3)
No.

Cantor's proof that there is no surjection $f:\mathbb{N}\longrightarrow \mathbb{R}$ seems relevant here.

I'm wondering if there is a lazier way to answer this question, although I think the following logic is flawed.

In class, we are given as a theorem that there is no bijection $f:\mathbb{N}\longrightarrow \mathbb{R}$. Bijective functions are both injective and surjective, so there is no such $f:\mathbb{N}\longrightarrow \mathbb{R}$ that is both injective and surjective.

An example of an injection $f:\mathbb{N}\longrightarrow \mathbb{R}$:

Let $f:\mathbb{N}\longrightarrow \mathbb{R}$ be a function defined by the rule $f(n)=n$. $f(n)\neq f(m)$ whenever $n\neq m$, so $f$ is injective. Since an injection $f:\mathbb{N}\longrightarrow \mathbb{R}$ was defined, it exists.

The issue is that this logic cannot deal with the possibility of an $f$ being surjective and not injective.

 

[fresh_42]

You are right, including your assessment of the last argument. It does not help that there is an injection, or that there is no bijection. You must take a possible surjection and deduce a contradiction. Just an idea: Assume $f\, : \,\mathbb{N}\longrightarrow \mathbb{R}$ is surjective. Then $\emptyset \neq f^{-1}(r)\subseteq \mathbb{N}$ for every $r\in \mathbb{R}.$ Hence we have a well-defined smallest element $\mathbb{N}\ni N_r\in f^{-1}(r)$ for all $r\in \mathbb{R}.$ This defines a function $r\longmapsto N_r\,.$
What can you say about it?

 

[docnet]

You must take a possible surjection and deduce a contradiction. Just an idea: Assume $f\, : \,\mathbb{N}\longrightarrow \mathbb{R}$ is surjective. Then $\emptyset \neq f^{-1}(r)\subseteq \mathbb{N}$ for every $r\in \mathbb{R}.$ Hence we have a well-defined smallest element $\mathbb{N}\ni N_r\in f^{-1}(r)$ for all $r\in \mathbb{R}.$ This defines a function $r\longmapsto N_r\,.$
What can you say about it?

$f$ is surjective, so it is well-defined. So $f(n)\neq f(m)\Longrightarrow n\neq m$. This leads to $f^{-1}(f(m))\neq f^{-1}(f(n))$ whenever $m\neq n$. So the $f^{-1}(r)$ are disjoint in $\mathbb{N}$ for all $r$. $N_r\in f^{-1}(r)$. Hence the $N_r$ are disjoint for all $r$. Hence $r\longmapsto N_r$ is injective.

(Is this okay?)

This means the image of $r\longmapsto N_r$ (we could call the set $\mathbb{N}_r$ for brevity) has a cardinality equal to $|\mathbb{R}|=𝔠$. $N_r\in \mathbb{N}$ for all $r$, so we have $\mathbb{N}_r\subset\mathbb{N}$. So it must also be that $|\mathbb{N}|\geq 𝔠$.

(Is this still okay?)

There can be no bijections from $\mathbb{N}$ to $\mathbb{R}$. This means $|\mathbb{N}|\neq 𝔠$. So we have $|\mathbb{N}|> 𝔠$.

I am stumped trying to derive a contradiction. @fresh_42 could you please drop a little hint?

 

[fresh_42]

$f$ is surjective, so it is well-defined.

These are two unrelated properties. A function is well-defined if it doesn't map one element on two targets. A function is surjective if every possible target is actually hit at least once. You can only construct an implicit dependency. By saying a function is surjective, it is already assumed that it is a function, i.e. especially well-defined. If you meant this, then you are right. But it would be better to state that $f$ is well-defined by assumption, rather than by surjectivity.

So $f(n)\neq f(m)\Longrightarrow n\neq m$. This leads to $f^{-1}(f(m))\neq f^{-1}(f(n))$ whenever $m\neq n$. So the $f^{-1}(r)$ are disjoint in $\mathbb{N}$ for all $r$. $N_r\in f^{-1}(r)$. Hence the $N_r$ are disjoint for all $r$. Hence $r\longmapsto N_r$ is injective.

(Is this okay?)

Think so.

This means the image of $r\longmapsto N_r$ (we could call the set $\mathbb{N}_r$ for brevity) has a cardinality equal to $|\mathbb{R}|=𝔠$. $N_r\in \mathbb{N}$ for all $r$, so we have $\mathbb{N}_r\subset\mathbb{N}$. So it must also be that $|\mathbb{N}|\geq 𝔠$.

(Is this still okay?)

Yes. You could also simply observe that $f(\varphi (r))=r$ where $\varphi (r)=N_r$ is the function we get from $f^{-1}$ by picking the least number. Now $\mathbb{R}\stackrel{\varphi }{\longrightarrow }\mathbb{N}_r\stackrel{f}{\longrightarrow }\mathbb{R}$ is the identity map, and since $f$ is surjective, we have $\mathbb{R}=\mathbb{N}_r$ and there is no such bijection.

There can be no bijections from $\mathbb{N}$ to $\mathbb{R}$. This means $|\mathbb{N}|\neq 𝔠$. So we have $|\mathbb{N}|> 𝔠$.

I am stumped trying to derive a contradiction. @fresh_42 could you please drop a little hint?

Well, you could simply say that we already know that $|\mathbb{N}|<|\mathbb{R}|$ by Cantor's diagonal enumeration argument.

 

[PeroK]

I suggest it's better to really understand the strategy of the proof before you get into the complications of writing it down formally:

1) We know that there is no bijection from $\mathbb N$ to $\mathbb R$.

2) We also know that there is no bijection from a subset of $\mathbb N$ to $\mathbb R$.

3) Suppose $f$ is a surjection from $\mathbb N$ onto $\mathbb R$.

3a) The idea is to use $f$ to construct a bijection from a subset of $\mathbb N$ to $\mathbb R$, which proves that no such surjection exists.

3b) Every real number $r$ is in the range of $f$. Hence, there exists a non-empty set of natural numbers $S_r$ than are all mapped to $r$. Note that $S_r$ may be a single element, finite or infinite subset of $\mathbb N$. Note that the $S_r$ are disjoint, as $f$ is a (well-defined) function.

3c) Each $S_r$ has a smallest element $n_r$.

3d) The set $S = \{n_r: r \in \mathbb R \}$ is a subset of (or equal to) $\mathbb N$.

3e) Technical point: $S$ cannot be finite(!)

3f) Define $\tilde f : S \rightarrow \mathbb R$, by $\tilde f(n_r) = r$ (or, if you prefer, $\tilde f(n) = f(n)$.

3g) $\tilde f$ is a bijection from $S$ to $\mathbb R$. Which is the required contradiction.