2 ms·

Yes, I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? Surely the flip

• pdonis 12y ago
  > I don't understand how he created an infinite number of binary strings, and suddenly flipping one bit means that the binary string is new? That's not quite what the diagonal argument does. Take an enumerated list of infinite binary strings, i.e., the strings are numbered as string #1, #2, #3, etc. Now construct a new infinite binary string in the following way: bit #1 of the new string is the opposite of bit #1 of string #1; bit #2 of the new string is the opposite of bit #2 of string #2; bit #3 of the new string is the opposite of bit #3 of string #3; etc. This new string cannot possibly appear in the list, because for all positive integers n, bit #n of the new string differs from bit #n of binary string #n in the list--i.e., the new string differs from every string in the list by at least one bit. In other words, if we are given any list of infinite binary strings enumerated by positive integers, we can always construct a new infinite binary string that is not in the list. So no such list can ever be complete. Hence, there must be more infinite binary strings than there are positive integers.