What's the matter of Cantor's diagonal argument in binary system?

879 Views Asked by At

In binary system, Cantor's diagonal argument lost its effect.(https://zhuanlan.zhihu.com/p/20197130)(Sorry for the Chinese needed to translating) What can we say about it? How can we improve it?

In binary system,if we construct like this: r = 0.d1d2d3… di = 1 - dii

Then we fail. For an example: r1 = 0.1 r2= 0. 001 r3 = 0.0001 r4 = 0.00001 …

The thing we diagonally inverted constructed is: r = 0.0111…

But in this way,it just is r1.

And it seems other ways of diagonal construction fails too.

(Sorry for my be utterly ignorant of things like Latex)

2

There are 2 best solutions below

0
On BEST ANSWER

There are several ways to fix this; here are two.

  • We can look at more than one digit at a time. Given our starting list $$(0.a^1_1a^2_2a^3_3, \quad 0.a^2_1a^2_2a^2_3...,\quad 0.a^3_1a^3_2a^3_3..., \quad ...)$$ of binary representations of reals in $[0,1)$, we define a sequence $b_1,b_2,b_3,...$ as follows: the two-digit block $b_{2i-1}b_{2i}$ is "$01$" if $a_{2i-1}a_{2i}$ is not "$01,$" and $b_{2i-1}b_{2i}$ is "$10$" otherwise.

  • We can just transfer between contexts. We don't have to use the binary representations; we could always switch to (say) decimal representations, apply diagonalization there (where having more than two digits gives us "room" to work without having to consider multiple digits at once), and then convert back to binary. This might feel like cheating, but it's perfectly valid.

I'd say that both approaches have their advantages; ultimately each is teaching a kind of flexibility when it comes to constructions, either at the specific implementation level or right at the formulation level.

0
On

The argument Georg Cantor presented was in binary. And I don't mean the binary representation of real numbers. Cantor did not apply the diagonal argument to real numbers at all; he used infinite-length binary strings (quote: "there is a proof of this proposition that ... does not depend on considering the irrational numbers.") So the string "10000..." is different than the string "01111...".

There are several other discrepancies about the way it is taught, and almost all of the objections to it stem from one of them.