3
$\begingroup$

Whilst learning about infinities, I attempted to construct a proof by contradiction that the continuum of real numbers ($\aleph_1$) could not be represented by the set of positive integers ($\aleph_0$). It is as follows (simplified):

Let $x$ be a real number where $0 \leq x < 1$. Interpret $x$ as a base-2 string of the form $0.d_1d_2d_3d_4\dots$. Let there be an $\aleph_0$-dimensional cube. Each value of $x$ can be represented as the coordinate $(d_1, d_2, d_3, d_4 \dots)$ which is a vertex of the cube, therefore there exists a mapping of each real number onto an $\aleph_0$-dimensional cube. An $n$-dimensional cube has $2^n$ vertices, therefore an $\aleph_0$-dimensional cube has $2^{\aleph_0}$ vertices, therefore $\aleph_1 = 2^{\aleph_0}$.

If the coordinates of point $x$ are treated as a big-endian bit-string representing a number (i.e. $d_1$ is the $2^0$ digit, $d_2$ is the $2^1$ digit etc.) then $x$ can be mapped to an integer. This integer can have an infinite number of digits. There are $\aleph_0$ integers.

If there is a mapping between the reals and the integers then $\aleph_0 = 2^{\aleph_0} = \aleph_1$. This is obviously false, and is what I was trying to disprove. What part(s) of my proof is / are wrong?

$\endgroup$
  • 2
    $\begingroup$ You lost me at "If the coordinates of point $x$ are treated as big-endian integers...i.e., $d_1$ is $2^0$, $d_2$ is $2^1$, etc." This is because such a summation $\sum_{i=0}^{\infty}d_{i+1} 2^i$ may diverge to infinity, which is not an integer. In fact it diverges whenever the number of 1-bits is infinity. $\endgroup$ – Michael Mar 4 '17 at 18:43
  • 2
    $\begingroup$ @Michael I think that proof is very elegant, but I was trying to create my own to ensure that I understood the topic. It turns out that I don't. :-) $\endgroup$ – wizzwizz4 Mar 4 '17 at 18:45
  • 3
    $\begingroup$ "If the coordinates of point x are treated as a string then x can be mapped to an integer". That's only true if the string is finite. "This integer can have an infinite number of digits". No it can't. Or if it did it wouldn't be an integer. $\endgroup$ – fleablood Mar 4 '17 at 19:08
  • 4
    $\begingroup$ That is just bad teaching, I'm sorry. $\aleph_1$ is the cardinality of all the countable ordinals, that is its definition. It is the smallest uncountable cardinal, and there is no such thing as $\aleph_{0.5}$. The real numbers have cardinality $2^{\aleph_0}$ which is uncountable, and therefore $\aleph_1\leq2^{\aleph_0}$ is an easy theorem, more or less by definition, whether or not there is an equality is known as Cantor's Continuum Hypothesis. It is not "unknown", but neither provable nor disprovable from the standard axioms of set theory. $\endgroup$ – Asaf Karagila Mar 4 '17 at 19:17
  • 3
    $\begingroup$ Well, $2^{\aleph_0}$. $\endgroup$ – Asaf Karagila Mar 4 '17 at 19:23
8
$\begingroup$

"This integer can have an infinite number of digits."

No it can't.

There's no such thing as an integer with an infinite number of (non-zero) integers.

Such a construct is not an integer and has no finite value.

More thouroughly, this construct will be an infinite sum (all non-negative summands) with an infinite number of terms greater or equal to $1$ (or, actually greater than or equal to any positive power of 2). Such a sum is divergent, infinite, and certainly not an integer.

$\endgroup$
  • $\begingroup$ This seems the same as my first comment. $\endgroup$ – Michael Mar 4 '17 at 23:33
4
$\begingroup$

Your mistake is that a vector is "a full string". But in fact a linear combination is by definition finite. So if $x$ is an element of an $\aleph_0$-dimensional space, then $x$ has only finitely many non-zero coordinates.

This means that the cube of an $\aleph_0$-dimensional space has $\aleph_0$ vertices.

On the other hand, you are thinking about the space of infinite strings, whose dimension is indeed $2^{\aleph_0}$.

(Also, $\aleph_1$ is the first uncountable cardinal, which may or may not be equal to $2^{\aleph_0}$, depending on your choice of set theory.)

$\endgroup$
  • $\begingroup$ Sorry, I still don't understand the second paragraph of your answer. It seems like you thought I meant $\aleph_0^3$ from your wording, and if you meant an $\aleph_0$-cube like I did I'm not sure how it can not be $2^{\aleph_0}$: a three-cube has $2^3=8$ vertices and an $n$-cube has $2^n$, and as you have explained $2^{\aleph_0} \neq \aleph_0$. $\endgroup$ – wizzwizz4 Mar 4 '17 at 19:41
  • $\begingroup$ Why do you think that the number of vertices on a cube is continuous? Sure, the function $f(n)=2^n$ is "continuous" as a real-valued function, but this is a cardinal function, and there is no reason to expect that. For the same reason you could argue that $\mathcal P(\Bbb N)$ is countable, because it is the union of $\mathcal P([n])$, where $[n]=\{0,\ldots,n-1\}$. Just because something is "easily definable by something seemingly simple and continuous" does not mean it is continuous at domains which are not real or complex numbers. $\endgroup$ – Asaf Karagila Mar 4 '17 at 19:44
  • $\begingroup$ The point is that a vertex on the cube is a vector that only has $0$'s and $1$'s, and since there are only finitely many non-zero coordinates, there can only be countably many of these vectors. $\endgroup$ – Asaf Karagila Mar 4 '17 at 19:45
  • $\begingroup$ You have said that before, but I don't understand how there being finitely many non-zero coordinates (i.e. 1: ${1}$) means that there are only countably many vectors that are made up of a countable number of coordinates. Or am I misunderstanding what you have said? $\endgroup$ – wizzwizz4 Mar 4 '17 at 19:50
  • $\begingroup$ Because there is a bijection between the natural numbers and the eventually zero binary sequences. $\endgroup$ – Asaf Karagila Mar 4 '17 at 19:51
1
$\begingroup$

As mentioned elsewhere, integers don't have an infinite number of digits.

Something that should be mentioned as well, though:

At the end of your proof, you also say that $\aleph_0 = 2^{\aleph_0} = \aleph_1$ (where by $\aleph_1$ you mean the cardinality of $[0, 1)$) is "obviously false". Er, no it's not... it's what you're trying to disprove! This is like trying to prove $\sqrt 2$ is irrational by saying "Suppose $\sqrt 2=\frac a b$. But this would mean $\sqrt 2$ is rational, which is obviously false. Therefore $\sqrt 2$ is irrational."

$\endgroup$
  • $\begingroup$ The "obviously false" part wasn't part of my proof, but I thought that that is what my proof showed and $\aleph_1$ is by definition greater than $\aleph_0$. $\endgroup$ – wizzwizz4 Mar 5 '17 at 8:56
  • $\begingroup$ I see. I interpreted it as an attempt at a proof by contradiction. $\endgroup$ – Jack M Mar 5 '17 at 9:52

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.