5 ms·

Genuinely asking: Consider decimal numbers between 0 and 1 in binary. Here's how I am going to synthesize this set. Step 1: Take non-decimal binary numbers

by alok-g 10y ago

Genuinely asking: Consider decimal numbers between 0 and 1 in binary. Here's how I am going to synthesize this set. Step 1: Take non-decimal binary numbers and consider them to be padded with an infinite of zeros at the left. ...0000000 ...0000001 ...0000010 ...0000011 ...0000100 ...0000101 ...0000110 .......... Do we agree that this will contain all the non-decimal non-negative binary numbers? In particular, is the following number in the above set? ...111111 (all ones, not zero-padding on the left). If not, why not. And if not, this seems to be a matter of definition to me. If yes, move on. Step 2: Place a decimal at the end of each line above and flip left and right. 0.0000000... 0.1000000... 0.0100000... 0.1100000... 0.0010000... ............ Do we agree that this contains all the decimal positive binary numbers between zero and one: [0, 1). Let's now apply diagonalisation on this. It says that the number 0.11111111... will not be present in the above set. Perhaps someone can see my confusion and enlighten me. :-) Thanks!

BuuQu9hu 10y ago
The number ...1 in your first notation is actually -1, using 2-adic interpretation. The number 0.1... is actually 1, which lies outside your expected range. Maybe another base will help. In base 3: 0.0... 0.10... 0.20... 0.010... Once again, a naive diagonalization yields 0.1... but this time at least we have not extended past 1. Is there a way to avoid that convergence? Sure, we can change the 0 digit to either 1 or 2 randomly, or based on some pattern or enumeration, instead of just 1. So now we can take many diagonals, and they all look like: 0.121212... 0.122122... 0.121121... 0.22212221... ... Augh! What happened? Our diagonalization appears to have revealed an infinity of missed reals! This is similar to the construction of the Cantor set (https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set) and hopefully illustrates the problem with your enumeration of the reals.
- alok-g 10y ago
  Thanks. This was helpful. I am not sure that I fully get it, but I think I do. :-)
wayn3 10y ago
The confusion in your argument is rather simple. You construct the set of INTEGERS in a binary representation. Then you flip them over to the other side,in an operation that you yourself do not fully understand. The first number that you flip (0.1) turns into 0.5 decimal The second number that you flip (0.01) turns into 0.25 decimal The third is 0.75 0.125 and so on. You are creating a subset of the rational numbers, which is obviously countable. It is countable because you constructed it to be countable. You constructed something that was countable and then tried to prove that it is countable. Happens all the time :)
- alok-g 10y ago
  This was helpful. Thanks. I did understand before how flipping changed the numbers into 0.5, 0.25, etc., but had missed that this process would only create rational, thereby missing the irrationals altogether. There's enough food for thought for me now. :-)
  - wayn3 10y ago
    What you really want to understand is "where's pi", right? Pi looks somewhat like this: 3.1415... "and so on". Let's ditch the 3. 0.1415... and so on. flipped over equals: ...5141 Easy enough, right? But pi had infinite decimals. Infinite decimals on the left side means what? You tell me :) Infinity is not an element in the real numbers. All the irrationals, when flipped over, get absorbed into infinity - and infinity itself has no decimal representation. For people who are not in math, saying "and so on" is fine. But you can't do math on "and so on". "And so on" is a handwaving way of saying that you lack the mathematical language to describe whats going on. Which is fine, for casuals.
    - alok-g 10y ago
      You have gotten to exactly what my confusion has been! I had assumed from the middle school itself that the set {1, 2, 3, ...} includes infinity, and I still am questioning if this not being is just a matter of definition or it has to be that way. More below: We say that the size of the set {1, 2, 3, 4} is 4, in which scenario, the number 4 happens to be an element in the set. Likewise for {1, 2, 3, 4, ..., 100000}. Now we say that the size of the set {1, 2, 3, 4, ...} is infinity, but infinity is not an element of that set. It seems what I am missing is the formal definition of this "..." or "and so on". If these two were not allowed in any of the proofs, how would you word Cantor's Diagonalisation and other theorems in mathematics that currently involve these. (Or alternatively, what is the formal definition of "...") PS: I do understand limits and calculus but perhaps from an engineering perspective, not for pure mathematics where I have these confusions. Thanks! :-)
powera 10y ago
Step 1 fails because there is no such number that is an infinite number of 1s. Only infinity has infinitely many digits. Step 2 fails because you can't create a 1-1 correspondence between the real numbers between zero and one, and the integers. That is what you are trying to prove. I'm too tired to figure out if your proof is valid or not, but your conclusion is correct.
pwdisswordfish 10y ago
> decimal positive binary numbers Make up your mind.
- alok-g 10y ago
  Clarifications: decimal: Not base 10, but fractional, those with a decimal point binary: Not just 0 or 1, but base 2. 0.01 is a binary positive decimal number which is 0.25 in base 10.

by alok-g 10y ago

BuuQu9hu 10y ago

The number ...1 in your first notation is actually -1, using 2-adic interpretation. The number 0.1... is actually 1, which lies outside your expected range. Maybe another base will help. In base 3: 0.0... 0.10... 0.20... 0.010... Once again, a naive diagonalization yields 0.1... but this time at least we have not extended past 1. Is there a way to avoid that convergence? Sure, we can change the 0 digit to either 1 or 2 randomly, or based on some pattern or enumeration, instead of just 1. So now we can take many diagonals, and they all look like: 0.121212... 0.122122... 0.121121... 0.22212221... ... Augh! What happened? Our diagonalization appears to have revealed an infinity of missed reals! This is similar to the construction of the Cantor set (https://en.wikipedia.org/wiki/Cantor_set https://en.wikipedia.org/wiki/Cantor_set) and hopefully illustrates the problem with your enumeration of the reals.

alok-g 10y ago
Thanks. This was helpful. I am not sure that I fully get it, but I think I do. :-)

wayn3 10y ago

The confusion in your argument is rather simple. You construct the set of INTEGERS in a binary representation. Then you flip them over to the other side,in an operation that you yourself do not fully understand. The first number that you flip (0.1) turns into 0.5 decimal The second number that you flip (0.01) turns into 0.25 decimal The third is 0.75 0.125 and so on. You are creating a subset of the rational numbers, which is obviously countable. It is countable because you constructed it to be countable. You constructed something that was countable and then tried to prove that it is countable. Happens all the time :)

alok-g 10y ago
This was helpful. Thanks. I did understand before how flipping changed the numbers into 0.5, 0.25, etc., but had missed that this process would only create rational, thereby missing the irrationals altogether. There's enough food for thought for me now. :-)
- wayn3 10y ago
  What you really want to understand is "where's pi", right? Pi looks somewhat like this: 3.1415... "and so on". Let's ditch the 3. 0.1415... and so on. flipped over equals: ...5141 Easy enough, right? But pi had infinite decimals. Infinite decimals on the left side means what? You tell me :) Infinity is not an element in the real numbers. All the irrationals, when flipped over, get absorbed into infinity - and infinity itself has no decimal representation. For people who are not in math, saying "and so on" is fine. But you can't do math on "and so on". "And so on" is a handwaving way of saying that you lack the mathematical language to describe whats going on. Which is fine, for casuals.
  - alok-g 10y ago
    You have gotten to exactly what my confusion has been! I had assumed from the middle school itself that the set {1, 2, 3, ...} includes infinity, and I still am questioning if this not being is just a matter of definition or it has to be that way. More below: We say that the size of the set {1, 2, 3, 4} is 4, in which scenario, the number 4 happens to be an element in the set. Likewise for {1, 2, 3, 4, ..., 100000}. Now we say that the size of the set {1, 2, 3, 4, ...} is infinity, but infinity is not an element of that set. It seems what I am missing is the formal definition of this "..." or "and so on". If these two were not allowed in any of the proofs, how would you word Cantor's Diagonalisation and other theorems in mathematics that currently involve these. (Or alternatively, what is the formal definition of "...") PS: I do understand limits and calculus but perhaps from an engineering perspective, not for pure mathematics where I have these confusions. Thanks! :-)

powera 10y ago

Step 1 fails because there is no such number that is an infinite number of 1s. Only infinity has infinitely many digits. Step 2 fails because you can't create a 1-1 correspondence between the real numbers between zero and one, and the integers. That is what you are trying to prove. I'm too tired to figure out if your proof is valid or not, but your conclusion is correct.

pwdisswordfish 10y ago

> decimal positive binary numbers Make up your mind.

alok-g 10y ago
Clarifications: decimal: Not base 10, but fractional, those with a decimal point binary: Not just 0 or 1, but base 2. 0.01 is a binary positive decimal number which is 0.25 in base 10.