My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree5Thanks
  • 1 Post By AplanisTophet
  • 2 Post By cjem
  • 1 Post By Maschke
  • 1 Post By Maschke
Reply
 
LinkBack Thread Tools Display Modes
December 19th, 2017, 08:41 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
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
AplanisTophet is offline  
 
December 19th, 2017, 09:07 PM   #2
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
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.
AplanisTophet is offline  
December 20th, 2017, 03:35 AM   #3
Senior Member
 
Joined: Aug 2017
From: United Kingdom

Posts: 284
Thanks: 86

Math Focus: Algebraic Number Theory, Arithmetic Geometry
Quote:
Originally Posted by AplanisTophet View Post
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!
Thanks from Maschke and AplanisTophet

Last edited by cjem; December 20th, 2017 at 04:18 AM.
cjem is offline  
December 21st, 2017, 03:48 PM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by cjem View Post
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.
AplanisTophet is offline  
December 21st, 2017, 03:56 PM   #5
Senior Member
 
Joined: Aug 2012

Posts: 2,101
Thanks: 605

Quote:
Originally Posted by AplanisTophet View Post
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.
Thanks from AplanisTophet

Last edited by Maschke; December 21st, 2017 at 04:15 PM.
Maschke is offline  
December 21st, 2017, 04:30 PM   #6
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by Maschke View Post
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 View Post
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.
AplanisTophet is offline  
December 21st, 2017, 05:20 PM   #7
Senior Member
 
Joined: Aug 2012

Posts: 2,101
Thanks: 605

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

Quote:
Originally Posted by AplanisTophet View Post
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 View Post
I blame my confusion on the egg nog, silly me.
Haha. You should never drink and derive!
Thanks from AplanisTophet

Last edited by Maschke; December 21st, 2017 at 05:28 PM.
Maschke is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
argument, boy, cantor, challenge, crazy



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
I don't see the significance of Cantor's diagonal argument Mathbound Math 26 January 11th, 2017 06:30 PM
Cantor's Diagonal Argument Reconsidered zylo Topology 12 March 24th, 2016 10:53 AM
Cantor's Diagonal Argument zylo Math 22 January 26th, 2016 09:05 PM
Help! Cantor's Diagonal Argument mjcguest Applied Math 9 July 25th, 2013 08:22 AM
Cantors diagonal argument netzweltler Applied Math 191 November 7th, 2010 02:39 PM





Copyright © 2018 My Math Forum. All rights reserved.