My Math Forum Oh Boy, A Crazy Challenge to Cantor's Argument

 Number Theory Number Theory Math Forum

 December 19th, 2017, 07:41 PM #1 Senior Member   Joined: Jun 2014 From: USA Posts: 364 Thanks: 26 Oh Boy, A Crazy Challenge to Cantor's Argument 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! Thanks from Joppy
 December 19th, 2017, 08:07 PM #2 Senior Member   Joined: Jun 2014 From: USA Posts: 364 Thanks: 26 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.
December 20th, 2017, 02:35 AM   #3
Senior Member

Joined: Aug 2017
From: United Kingdom

Posts: 219
Thanks: 70

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
 Originally Posted by AplanisTophet 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 by cjem; December 20th, 2017 at 03:18 AM.

December 21st, 2017, 02:48 PM   #4
Senior Member

Joined: Jun 2014
From: USA

Posts: 364
Thanks: 26

Quote:
 Originally Posted by cjem 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.

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.

December 21st, 2017, 02:56 PM   #5
Senior Member

Joined: Aug 2012

Posts: 1,999
Thanks: 572

Quote:
 Originally Posted by AplanisTophet 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 by Maschke; December 21st, 2017 at 03:15 PM.

December 21st, 2017, 03:30 PM   #6
Senior Member

Joined: Jun 2014
From: USA

Posts: 364
Thanks: 26

Quote:
 Originally Posted by Maschke 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.

Quote:
 Originally Posted by AplanisTophet 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.

December 21st, 2017, 04:20 PM   #7
Senior Member

Joined: Aug 2012

Posts: 1,999
Thanks: 572

Quote:
 Originally Posted by AplanisTophet See bolded part, not sure why you omitted it.
I think my mind glazed over that part.

Quote:
 Originally Posted by AplanisTophet 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.

Quote:
 Originally Posted by AplanisTophet I blame my confusion on the egg nog, silly me.
Haha. You should never drink and derive!

Last edited by Maschke; December 21st, 2017 at 04:28 PM.

 Tags argument, boy, cantor, challenge, crazy

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Mathbound Math 26 January 11th, 2017 05:30 PM zylo Topology 12 March 24th, 2016 09:53 AM zylo Math 22 January 26th, 2016 08:05 PM mjcguest Applied Math 9 July 25th, 2013 07:22 AM netzweltler Applied Math 191 November 7th, 2010 01:39 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top