-1
$\begingroup$

Consider a function f that takes all the supraunitary digits of the real number and assign them on the odd positions of the natural number and all the subunitary digits in reverse order and assign them on the even positions of the natural number. This mapping is unique.

How would Cantor's diagonal argument work on this mapping? Surely for any real number r, constructed using this argument, f would construct a unique natural number, which is part of the mapping, contradicting that r isn't mapped.

A more formal definition for the proposed function and its inverse:

Let $f\colon\mathbb{R}\to\mathbb{N}$ such as for any real number with the decimal representation $a_n ... a_2 a_1. b_1 b_2 ... b_m$ with $a_n \neq 0$ and $b_m \neq 0$: \begin{equation} f(a_n ... a_2 a_1. b_1 b_2 ... b_m)= \begin{cases} b_m 0 \dots b_2 a_2 b_1 a_1& \text{if}\ n<m\\ b_n a_n \dots b_2 a_2 b_1 a_1& \text{if}\ n=m\\ a_n 0 \dots b_2 a_2 b_1 a_1& \text{if}\ n>m\\ \end{cases}\label{fdef} \end{equation}

Let $f^{-1}\colon\mathbb{N}\to\mathbb{R}$ such as for any natural number with the decimal representation $\dots x_6 x_5 x_4 x_3 x_2 x_1$: \begin{equation} f^{-1}(\dots x_6 x_5 x_4 x_3 x_2 x_1)= \dots x_5 x_3 x_1. x_2 x_4 x_6 \dots\label{finvdef} \end{equation}

$\endgroup$
  • 2
    $\begingroup$ "Surely for any real number r, constructed using this argument, f would construct a unique natural number." Sentences like that are exactly where to look for the mistake - in particular, $f$ does not in general yield a natural number, as stated above and below. When you're trying to prove something, always focus special attention on the claims that are "too obvious" to warrant explicit proof (and this doesn't just apply to you; I've been nailed by this more times than I am comfortable admitting). $\endgroup$ – Noah Schweber Jan 5 '17 at 15:42
  • 1
    $\begingroup$ @ctapus "The set of natural numbers is infinite, so there are naturals number with an infinity of digits." That's nonsense. Every natural number is finite - so every natural number has finitely many digits. Just because the set of natural numbers is infinite, doesn't mean any individual natural number is infinite. (Incidentally, there are number systems where "infinite leftward expansions" make sense - look at the $p$-adics, for instance - but $\mathbb{N}$ isn't one of them.) $\endgroup$ – Noah Schweber Jan 5 '17 at 22:55
  • 1
    $\begingroup$ @ctapus Re: your comment to me, those are - but something like "$...3030303030$" isn't. (Incidentally, if you insist on such things being in your number system, how do you compare them? Which is larger: $...121212$ or $...212121$? Note that they "keep switching": $2>1$, $21>12$, $212>121$, .... So even if you insist on a number system with such weird objects (which, to reiterate, will not be $\mathbb{N}$), things are going to get ugly.) $\endgroup$ – Noah Schweber Jan 5 '17 at 23:02
  • 2
    $\begingroup$ I hope you agree that every non-empty set of natural numbers has a minimal element. What is the smallest natural number to have infinitely many digits? $\endgroup$ – Asaf Karagila Jan 6 '17 at 7:43
  • 1
    $\begingroup$ I have negative idea what you're talking about. Note that 1/3 is not a natural number, nor its integral part (which is 0, by the way) has infinitely many non-zero digits. What is the next number after 1/3, by the way? You got me curious. $\endgroup$ – Asaf Karagila Jan 7 '17 at 12:50
2
$\begingroup$

The problem is that almost all real numbers will have infinitely many nonzero digits $b_i$ following their decimal point. These numbers are not mapped to natural numbers by your scheme, since they have an infinite number of digits, while all natural numbers only have a finite number of digits.

For instance $1/3$ gets mapped to $\dots 30303030$ with an infinite number of copies of $30$, which is not a natural number.

$\endgroup$
  • $\begingroup$ Why 30303030... is not a natural number? Every natural number has a successor, which means that there are infinitely big natural numbers, meaning there are natural numbers with an infinity of digits. And wouldn't Cantor's proof for countability of rational numbers would suffer from the same issue? Given the fact that there are infinitely many prime numbers, in his ordering schema you will get to a rational number that is the ratio of two infinite prime numbers. $\endgroup$ – ctapus Jan 5 '17 at 23:00
  • $\begingroup$ @ctapus "Every natural number has a successor, which means that there are infinitely big natural numbers, meaning there are natural numbers with an infinity of digits." That's incorrect. And incidentally, the "number" $f$ gives on input ${1\over 3}$ isn't $303030...$ but rather $...303030$: it has a last term, but no first term. $\endgroup$ – Noah Schweber Jan 5 '17 at 23:04
  • $\begingroup$ @NoahSchweber Thank you for the insight, Noah. If I may draw a similarity with the proof of countability of Q, why can't real numbers be ordered by their number of digits? So first you will have real numbers with 1 digit (0..9), followed by numbers with 2 digits(10..99, with 0.1 .. 0.9) followed by real numbers with 3 digits, etc? Is it be because of numbers like 0.(3)? I mean if all the real numbers will be listed, 0.(3) should be there, mapped to a number with an infinite number of digits. This is what I was actually trying to capture in f's definition. $\endgroup$ – ctapus Jan 7 '17 at 17:42
  • $\begingroup$ @ctapus Yes, the problem is numbers like ${1\over 3}$ - they won't appear anywhere in your proposed list. Indeed, no matter how you define $f$, it will miss most of the reals; this is suggested by the experience you get playing around with a bunch of possible $f$s (and seeing how they each break), and proved by Cantor's argument. $\endgroup$ – Noah Schweber Jan 7 '17 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.