Oh Boy, A Crazy Challenge to Cantor's Argument

Jun 2014
650
54
USA
Let g(1) = 0 and g(0) = 1.

For any infinite binary string $x = x_1x_2x_3\dots$, let $f( \,x) \, = g(x_1)g(x_2)g(x_3)\dots$.

If for each element $x$ of a countable set $X$ of infinite binary strings, $f( \,x) \,$ is also in $X$, then let $X$ be considered ‘balanced.’

Let V be a collection of countable sets of infinite binary strings that partition the set of infinite binary strings where each element of V is balanced.

Given a countable list of infinite binary strings, Cantor’s diagonal argument can be used to create an infinite binary string that is not in the list (an anti-diagonal).

Let each element of V be well ordered in a fashion such that the anti-diagonal of the ordering is equal to $a = 111\dots$.

By definition, no element of V can contain $a$, so the elements of V cannot partition the set of infinite binary strings.

Now, either no such collection V can exist where each element of V is balanced or Cantor’s diagonal argument is faulty.

On a side note, December 20th is my birthday. Yay! :)
 
  • Like
Reactions: 1 person
Jun 2014
650
54
USA
PS - I used V for the collection because I'm thinking along the lines of Vitali sets...

It would also be easy to exclude 000... and 111... from the set of infinite binary strings with this argument in order to poke at the continuum hypothesis.
 
Aug 2017
313
112
United Kingdom
Let each element of V be well ordered in a fashion such that the anti-diagonal of the ordering is equal to $a = 111\dots$.
You can't well-order every element of V in this way. Indeed, since the elements of V partition the set of all infinite binary strings, $a$ must be contained in some element U of V. Now U is countable, so for any well-ordering on U, $a$ will be the $n^{th}$ smallest element of U for some $n$. Then the anti-diagonal must have a 0 in the $n^{th}$ digit, so cannot be equal to $a$.

PS happy birthday!
 
Last edited:
  • Like
Reactions: 2 people
Jun 2014
650
54
USA
You can't well-order every element of V in this way. Indeed, since the elements of V partition the set of all infinite binary strings, $a$ must be contained in some element U of V. Now U is countable, so for any well-ordering on U, $a$ will be the $n^{th}$ smallest element of U for some $n$. Then the anti-diagonal must have a 0 in the $n^{th}$ digit, so cannot be equal to $a$.

PS happy birthday!
Yes, so a well ordering of U with order type $\omega + 1$ might be able to produce the desired anti-diagonal of 111... across the first $\omega$ elements of the ordering, but a well ordering of U with order type $\omega$ would not be possible for the reasons you state. I blame my confusion on the egg nog, silly me. :rolleyes:

I have no interesting result when trying to invoke such an ordering across the elements of V. Knowing that each element of V is balanced and of an ordering that produces a similar anti-diagonal across all the elements isn't enough to provide us any additional insight, seemingly.
 
Aug 2012
2,496
781
Yes, so a well ordering of U with order type $\omega + 1$ might be able to produce the desired anti-diagonal of 111...
That doesn't entirely make sense because $\omega + 1$ is not a list. A list by definition has the order type of the naturals. It's far from clear how to define the antidiagonal of an arbitrary countable ordinal. How do you define the antidiagonal of $\omega + \omega$? Any such antidiag would not be a binary string. An expression such as 10101010...;10101010100010..., composed of two concatenated bitstrings, is not a bitstring in the conventional sense. It can't be interpreted as the binary expression of a real number (with a binary point in front), even though it's countable. It's not a function $\mathbb N \to \mathbb R$.

In any event, in your original argument if you have any partition whatsoever into countable sets (of binary strings), since it's a partition some element of the partition contains $11111...$, therefore any antidiagonal must contain a $0$. Balanced sets don't seem to make any difference at all, if I'm understanding your argument correctly.
 
Last edited:
  • Like
Reactions: 1 person
Jun 2014
650
54
USA
That doesn't entirely make sense because $\omega + 1$ is not a list. A list by definition has the order type of the naturals.
See bolded part, not sure why you omitted it.

Yes, so a well ordering of U with order type $\omega + 1$ might be able to produce the desired anti-diagonal of 111... across the first $\omega$ elements of the ordering...
Again, "knowing that each element of V is balanced and of an ordering that produces a similar anti-diagonal across all the elements isn't enough to provide us any additional insight, seemingly."

For example, what if the partition, being balanced and with each element of a certain ordering, was enough for us to do something like try and enumerate the elements of the partition with the exception of $a = 111\dots$? I don't think that's the case or anything, but that certainly would be interesting to say the least.

But, what I'm saying is that my logic was flawed and not meaningful. I have no argument for you to misinterpret.
 
Aug 2012
2,496
781
See bolded part, not sure why you omitted it.
I think my mind glazed over that part.

But, what I'm saying is that my logic was flawed and not meaningful. I have no argument for you to misinterpret.
Are you saying I should quit while I'm behind? Ok!! I do confess to being confused as to why the balanced sets make a difference, because once you have a partition then some partition class must contain 11111... and then any permutation of that class would always have a 0 somewhere in its antidiagonal. This is true whether the partitions consist of balanced classes or not.

But if this is all irrelevant now, that's ok too.

I blame my confusion on the egg nog, silly me.
Haha. You should never drink and derive!
 
Last edited:
  • Like
Reactions: 1 person