1

Using Cantor's Diagonal Argument to compare the cardinality of the natural numbers with the cardinality of the real numbers we end up with a function $f: \mathbb{N} \to (0, 1)$ and a point $a \in (0, 1)$ such that $a \notin f((0, 1))$; that is, $f$ is not bijective.

My question is: can't we find a function $g: \mathbb{N} \to (0, 1)$ such that $g(1) = a$ and $g(x) = f(x-1)$ for $x > 1$? This function would be bijective, so the cardinality of the two sets would be the same. Actually, if we found a countably infinite set of points that weren't in $f((0,1))$, using Hilbert's Hotel argument we could find a bijective function.

groupoid
  • 362
  • 5
    Because $f$ was any function, so the same "Diagonal Argument" applies to your $g$ and shows that $g$ also misses sume point in $(0,1)$, which means that $f$ missed at least two points. In fact, you have just proved a strengthening of Cantor's theorem: a function $f:\mathbb N\to(0,1)$ not only misses one point, it misses an uncountably infinite set of points. Well done! – bof Nov 09 '19 at 08:56
  • 1
    No, we cannot find such a function as you say, not using Hilbert's hotel or Hilton's hotels. The proof by Cantor applies to any .... any at all .... function from $;\Bbb N;$ to $;(0,1);$ . – DonAntonio Nov 09 '19 at 09:19
  • 1
    Ok, $g$ will not miss $a$, but will miss other values in $(0,1)$, regardless how hard you try to refine the original function. – Berci Nov 09 '19 at 10:08
  • 1
    Okay, so let $A$ be the subset of points o $(0, 1)$ such that $A \cap f((0, 1)) = \emptyset$. Then, if $A$ is countable we can define $g$ using Hilbert's Hotel, and if it is uncountable we can't. But how can we show that there exists some $f$ such that $A$ is countable? – groupoid Nov 09 '19 at 13:11

2 Answers2

1

This was described by another contributor here as follows: You are $(0,1)$ and you are accused of being countable. The prosecutor presents a witness $f:\Bbb N \to (0,1),$ an alleged bijection. Your lawyer presents $x \in (0,1)\setminus f(\Bbb N).$ The prosecutor then presents $f^*:\Bbb N \to (0,1)$ with $f^*(\Bbb N)\supset \{x\}\cup f(\Bbb N).$ Your lawyer presents $x^*\in (0,1)\setminus f^*(\Bbb N)$.... This may go on for a while until the judge asks the prosecutor " Can you present a witness who can overcome the Cantor Diagonal Defense?" Prosecutor: "No." Judge: "Case dismissed".

Any $f(\Bbb N)\subset (0,1)$ will omit "almost all" of $(0,1).$ There will be uncountably many other $x \in (0,1).$ But we do not need to directly prove it, but can infer it after proving that $(0,1$) is uncountable.... The existence of at least one $x$ in a set is logically sufficient to show it's not empty. That is, $\forall f:\Bbb N\to (0,1)\; (\, (0,1)\setminus f(\Bbb N)\ne \emptyset\,).$

DanielWainfleet
  • 57,985
  • But the point is that the proof of the uncountability of $(0, 1)$ requires Cantor's Diagonal Argument. However, you're assuming the uncountability of $(0, 1)$ to help in Cantor's Diagonal Argument. So how do you prove that $(0, 1) \setminus f(\mathbb{N})$ is actually uncountable for every $f$? You can't assume the uncountability of $(0, 1)$. – groupoid Nov 09 '19 at 14:44
  • No I am not.....The 1st two sentences of my last paragraph are merely statements of known fact..... AFTER you have proven my last sentence (which is Cantor's theorem) you derive the corollary that $(0,1)\setminus f(\Bbb N)$ is uncountable for every $f.$ You might try to directly prove the corollary somehow. – DanielWainfleet Nov 10 '19 at 06:54
  • So then what's the purpose of Cantor's Diagonal Argument? – groupoid Nov 10 '19 at 10:07
  • THEOREM:(Cantor). $\forall f:\Bbb N\to (0,1),(,(0,1)\setminus f(\Bbb N)\ne \emptyset).$ PROOF: Diagonal argument. COROLLARY: $\forall f:\Bbb N\to (0,1),(,(0,1)\setminus f(\Bbb N)$ is uncountable ). – DanielWainfleet Nov 10 '19 at 17:11
0

Okay, thanks to all of you for your responses. I think I understood why you can never find such a bijective function.

With the aim of helping others with the same problem, I will synthetize my reasoning here.

Let $f: \mathbb{N} \to (0, 1)$ be an injective function. Using Cantor's Diagonal Argument, we can show that there exists some $a \in (0, 1)$ such that $f(n) = a$ for some $n \in \mathbb{N}$. Then, we create the funcion $g: \mathbb{N} \to (0, 1)$ as follows \begin{equation} g(x) = \left\{ \begin{matrix} a & \textrm{if}\ x = 1\\ f(x-1) & \textrm{if}\ x > 1 \end{matrix} \right. \textrm{.} \end{equation}

However, it isn't bijective, because using Cantor's Diagonal Argument again we can still find some number $b \in (0, 1)$ such that $g(n) = b$ for some $n \in \mathbb{N}$.

We could keep going on finding more functions. Let $h: \mathbb{N} \to (0, 1)$ be a function applying the previous process infinitely many times. Again, using Cantor's Diagonal Argument we see that $h$ is not bijective. Therefore, we can't find the bijective function $b: \mathbb{N} \to (0, 1)$ that would make $\textrm{card}\ \mathbb{N} = \textrm{card}\ (0, 1)$.

$\square$

Please, correct me if I'm wrong.

EDIT: I've just realised that this isn't needed for the proof of Cantor's Diagonal Argument to be completed. When we consider $f: \mathbb{N} \to (0, 1)$, it is an arbitrary function. Therefore, $\nexists\ g: \mathbb{N} \to (0, 1)$ such that $g$ is bijective, because $f$ is any function, even $g$.

groupoid
  • 362