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

In summary: Once you have the idea behind the proof clear, then you can write it down formally. I recommend that you stick to the main points - don't try to be ultra-formal - and include enough detail to make the proof comprehensible. Also, I recommend that you start with a clear statement of what you are trying to prove, before you start proving it. Here's a suggestion:We prove that there is no surjection from ##\mathbb N## onto ##\mathbb R##.Proof: Suppose that ##f## is a surjection from ##\mathbb N## onto ##\mathbb R##. We show that this leads to a contradiction.... details go here...Hence we
  • #1
docnet
Gold Member
734
384
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.
 
Last edited:
Physics news on Phys.org
  • #2
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?
 
  • Like
  • Informative
Likes docnet, sysprog and PeroK
  • #3
fresh_42 said:
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?
 
Last edited:
  • #4
docnet said:
##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.

docnet said:
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.
docnet said:
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.
docnet said:
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.
 
  • Informative
Likes docnet
  • #5
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.
 
  • Informative
Likes docnet

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

1. What is a surjection?

A surjection is a function that maps elements from one set to another in such a way that every element in the target set is mapped to by at least one element in the source set. In simpler terms, it means that every element in the target set has at least one corresponding element in the source set.

2. What are the natural numbers?

The natural numbers, also known as counting numbers, are a set of positive integers that start from 1 and continue infinitely. They are denoted by the symbol "ℕ". Examples of natural numbers include 1, 2, 3, 4, 5, etc.

3. What are the real numbers?

The real numbers are a set of numbers that include all rational and irrational numbers. They are denoted by the symbol "ℝ" and can be represented on a number line. Examples of real numbers include integers, fractions, decimals, and irrational numbers such as π and √2.

4. Can a surjection exist from the natural numbers to the real numbers?

No, a surjection cannot exist from the natural numbers to the real numbers. This is because the set of natural numbers is countably infinite, while the set of real numbers is uncountably infinite. This means that there is no way to map every natural number to a unique real number, as there are infinitely more real numbers than natural numbers.

5. Why is the existence of a surjection from the natural numbers to the real numbers important?

The existence of a surjection from the natural numbers to the real numbers has significant implications in mathematics and philosophy. It is closely related to the concept of infinity and the idea of countable versus uncountable sets. The non-existence of such a surjection is also known as Cantor's diagonal argument, which has been used to prove other important mathematical theorems.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
8
Views
864
  • Precalculus Mathematics Homework Help
Replies
2
Views
5K
  • Calculus and Beyond Homework Help
Replies
3
Views
604
  • Calculus and Beyond Homework Help
Replies
1
Views
561
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
15
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
612
  • Calculus and Beyond Homework Help
Replies
4
Views
537
Back
Top