In my math class, we had an exercise asking us to prove that the following set is not countable:
$$\prod \limits^\infty_{i=1} \{0,1\} = \{0,1\} \times \{0,1\} \times \{0,1\} \times \cdots$$
By Cantor's diagonalization argument, we can show that
$$f : \mathbb{N} \to \prod \limits^\infty_{i=1} \{0,...
The flaw is that you only considered the FINITE binary strings , the set of which is of course countable and $1-1$ to the natural numbers. An INFINITE binary string does not correspond to a natural number and in fact the set of those is uncountable.
@Peter Isn't an infinite binary string of zeros still equivalent to any finite binary string of zeros, just like how having leading zeros in a base-10 number makes it still equivalent to the base-10 number without them? Adding more zeros onto the front doesn't change the precision of a base-2 integer, unlike how trailing zeros to a decimal increases the precision.
@Joseph, you are thinking of these binary infinite strings as of base-2 integers. The problem is that most of these strings do not correspond to any integers. Which integer would a string of all ones correspond to?
@SergeyGuminov Ah, I see now. Never thought of that, but I suppose that would be some infinitely large number we cannot comprehend :) Thanks for enlightening me and clarifying Peter's point!
Actually, the binary strings with eventually only zeros still form a countable set (and also the period strings and many more), but they do not correspond with a natural number. This is not like $0.5=0.5\bar 0$. $11010\cdots $ (only zeros following) is not a natural number in binary expansion.
"Which integer would a string of all ones correspond to?" "I suppose that would be some infinitely large number we cannot comprehend" And so what about the string of all ones except for in the first position there is a zero, or the string of all ones except for in the second position, or the string where every even position is a $1$ and every odd position is a zero, etc... These can't all be the same "infinitely large number" and if you were to have included a distinct infinite "number" for each then you no longer talk about $\Bbb N$
@Peter to be completely pedantic, technically the string $11010\cdots$ is a binary integer if you use little endian, in the same way that $9=09=009=\cdots 009$ in base ten, which uses big endian by convention. Little endian is common for binary, specifically because the map OP describes (between integers and their binary representation) is exactly the conversion between naturals and little endian binary, and it's slightly more efficient for computers than the conversion to big endian. Your other points still stand though.
@Peter As you well know, character strings are used to talk about mathematical objects. I know you know this, because you did it when asserting $0.5=0.5\overline{0}$, a string you used to communicate an idea about mathematics. My assertion that $\overline{0}9=9$ differs from your assertion only by popularity. It is not inherently invalid. These expressions are useful in some contexts, such as the field of $p$-addic numbers, and the analogous ring structures which exist for non-prime $p$, like $p=10$. I only meant to inform you that little endian exists, and permits $1101\overline{0}=1101$.
@JadeVanadium This is something else. It does not make sense to consider $1000\cdots$ with infinite many zeros as an integer , because every trailing zero multiplies the number with $10$ (this is not the same as with $0.5000\cdots $ where the zeros are just unnecessary, but do not change the value and we have just $0.5$) , but $1000\cdots$ is not $1$ !
@JadeVanadium If you insist that every such string you work with eventually ends with infinitely many $0$'s, then that is all well and good. The problem is that you have "numbers" like $101010\dots$ where we alternate between $1$'s and $0$'s. We also have $110110110110\dots$ where we have every third bit be zero with all others $1$. Should these be the same number? Should these be different numbers? Should these even be numbers in the first place? The answer is that even with your "little endian" convention, these do not correspond to natural numbers, hence why it falls apart.
@JadeVanadium if your whole point was to be pedantic and to say that "Oh, actually, these five people write numbers like this" and only talk about conventions about how information is conveyed, and not about the actual underlying math... then who cares! Someone quickly glancing over might think that you believe the theorem is wrong. Further, the way you describe is hardly if ever used outside of a computing context and certainly does not alter the results... it just makes us have to explain what notation we are (or aren't) using at the time.
@JMoravitz You seem to be arguing with an imaginary version of me. I'm a set theorist, I understand (and agree with!!!) Cantor's theorem. I never expressed the views you attribute to me. To your second reply, Peter said "the binary strings with eventually only zeros ... do not correspond with a natural number". This is false, the OP literally defines the correspondence in their post, and it's exactly little endian binary. That's why I brought it up. The two of you need to actually read before you reply, you can't just reply to what you imagine someone said.
@JadeVanadium You misinterpreted my claim. I only said that such infinite strings are not integers (which is what I meant with "considered to be integers") , not that we cannot establish a correpsondence between them (if eventually infinite many zeros follow) and the natural numbers. This of course is possible , we just need to omit the comma in a terminating decimal expansion of a rational number and add infinite many trailing zeros.
Discussion on question by Joseph: Is …
Discussion on question by Joseph: Is …