2
$\begingroup$

This may have been asked before, since it seems like an obvious question, but I couldn't find it.

I just read some interesting stuff about set theory and how the size of the natural numbers is not the same as the size of the real numbers.

How I understand it is that there is no function $f$ whose domain is all natural numbers and whose range is all real numbers such that $f^{-1}$ also exists.

Obviously, if we allow each natural number to pair with two real numbers instead of just one, there still aren't enough natural numbers. This is pretty intuitive.

But what if we allowed each natural number to pair with countably infinitely many real numbers. Then does a mapping exist?

Mathematically, does there exist a function $f$ (domain: all real numbers, range all natural numbers) such that for every natural number $n$, the set of real numbers $r$ satisfying $f(r) = n$ is countably infinite?

$\endgroup$
1
  • $\begingroup$ In addition to what you said, there is no function with domain all natural numbers and with range all real numbers, at all, whether or not we want $f^{-1}$ to exist. (Functions like $f(n)=n$ don't have a range of all real numbers.) $\endgroup$
    – Akiva Weinberger
    Commented Dec 3, 2015 at 3:23

2 Answers 2

Reset to default
3
$\begingroup$

Functions are single-valued. Your two examples at the start of your question are relations $S\subset \Bbb N \times \Bbb R$, where for each $n$, $$S[n] = \{r\in \Bbb R\mid (n,r)\in S\}$$ and each $S[n]$ is countable. The corresponding function has values that are subsets of $\Bbb R$: $$f_R\colon n\to S[n]\colon \Bbb N \to \mathcal{P}(\Bbb R).$$ In your actual question, you change the direction and ask, $$ \it\text{Is there a surjection $f\colon \Bbb R\to \Bbb N$ such that for every $r\in \Bbb R$, $f^{-1}(y)$ is countable?} $$ This is really the same question as: $$ \it\text{Is there a function $F\colon \Bbb N \to \mathcal{P}(\Bbb R)$ such that every $F(n)$ is countable and $\Bbb R = \bigcup_{n\in\Bbb N} F(n)$?} $$

In other words, can $\Bbb R$ be a countable union of countable sets?

The answer is, no it cannot. It's a theorem of ZF set theory + at least a weak form of the Axiom of Choice, that a countable union of countable sets is countable.

$\endgroup$
8
  • $\begingroup$ His thing would be a single-valued function. Note that he wants it to be a function from $\Bbb R\to\Bbb N$, not the other way around. $\endgroup$
    – Akiva Weinberger
    Commented Dec 3, 2015 at 3:25
  • $\begingroup$ @AkivaWeinberger No, OP says "How I understand it is that there is no function f whose domain is all natural numbers and whose range is all real numbers... " $\endgroup$
    – BrianO
    Commented Dec 3, 2015 at 3:27
  • $\begingroup$ He wants to know if there is a countable-to-one function from the reals to the naturals. (Is that a real term? "Countable-to-one"?) $\endgroup$
    – Akiva Weinberger
    Commented Dec 3, 2015 at 3:27
  • $\begingroup$ Read his last paragraph again. $\endgroup$
    – Akiva Weinberger
    Commented Dec 3, 2015 at 3:28
  • $\begingroup$ Ahh ok, I misread: he finally asks, Is there a surjection $f\colon \Bbb R\to \Bbb N$ with every $f^{-1}(y)$ countable? I'll redo my answer..... $\endgroup$
    – BrianO
    Commented Dec 3, 2015 at 3:29
2
$\begingroup$

There is no surjection $\mathbb R \to \mathbb N$ with countable fibers, because the union of a countable family of countable sets is countable, and $\mathbb R$ is not countable.

$\endgroup$
1
  • 1
    $\begingroup$ Note for the OP: "fiber" means "preimage." $\endgroup$
    – Noah Schweber
    Commented Dec 3, 2015 at 3:12

You must log in to answer this question.

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