My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Thanks Tree3Thanks
Reply
 
LinkBack Thread Tools Display Modes
May 24th, 2015, 01:01 PM   #11
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

The partial list written is incomplete, the imagined "complete" list will include that number. The contradiction is that we postulate completeness but examine incompleteness.

Last edited by skipjack; May 29th, 2015 at 04:45 PM.
Tau is offline  
 
May 24th, 2015, 01:06 PM   #12
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by Tau View Post
The partial list written is incomplete, the imagined "complete" list will include that number. The contradiction is that we postulate completeness but examine incompleteness.
Think a little bit more, do not draw fast conclusions. The assumption of completeness is fragile in the first example, in the second example the key-step is that the diagonal biconditional shows the list is non completable. All numbers can be represented in binary form, so this argument can be treated to show the list of Reals is not completable, since the number in the diagonal (in binary form to ease the argument) would need to be on the list, but you see that you create a new number changing 0 for 1, or 1 for 0, precisely in the (n,n) position.

Last edited by skipjack; May 29th, 2015 at 04:45 PM.
al-mahed is offline  
May 24th, 2015, 01:10 PM   #13
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Another way to look at this: the decimal expansion of any real number can be seen as a infinite set of natural numbers, so the assumption that the Reals are countable is equivalent to the assumption of the power set of the naturals being countable. This I have show is not possible.
al-mahed is offline  
May 24th, 2015, 01:44 PM   #14
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

What does it mean for an infinite list to be completable?
Tau is offline  
May 24th, 2015, 01:47 PM   #15
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by Tau View Post
What does it mean for an infinite list to be completable?
Simply that all desired objects can be there. For instance, the list of all even numbers, you can start with numbers divisible by 4, and then complete it by adding the ones of the form 4n+2.
al-mahed is offline  
May 24th, 2015, 01:57 PM   #16
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Tau, what is the notion of a collection of objects being countable? This is the first fundamental step. Normally we use the notion:

$\displaystyle S\text{ is countable iff }\forall\sigma\in S\exists f\text{ such that } f: S\mapsto\mathbb{N}\text{ is not surjective}.$
al-mahed is offline  
May 24th, 2015, 02:18 PM   #17
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

Quote:
Originally Posted by al-mahed View Post
Simply that all desired objects can be there. For instance, the list of all even numbers, you can start with numbers divisible by 4, and then complete it by adding the ones of the form 4n+2.
That list has infinite cardinality and an infinite interval. The numbers on the number line are intervals, or differentials from zero and not points. This simple fact alone shows a contradiction between a set of numbers and their position on the number line. I can rewrite your list as sums of all rationals so the notion that it is a set only of the even numbers thus is false. Similarly an infinite set is always complete.

Last edited by Tau; May 24th, 2015 at 02:21 PM.
Tau is offline  
May 24th, 2015, 02:19 PM   #18
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by al-mahed View Post
Tau, what is the notion of a collection of objects being countable? This is the first fundamental step. Normally we use the notion:

$\displaystyle S\text{ is countable iff }\forall\sigma\in S\exists f\text{ such that } f: S\mapsto\mathbb{N}\text{ is not surjective}.$
To have a nice example, please google Hilbert's Hotel. Consider the rooms in the Hotel the natural numbers, so they serve as indexes to count.
al-mahed is offline  
May 24th, 2015, 02:23 PM   #19
Senior Member
 
Joined: Dec 2007

Posts: 687
Thanks: 47

Quote:
Originally Posted by Tau View Post
That list has infinite cardinality and an infinite interval. The numbers on the number line are intervals, or differentials from zero and not points. This simple fact alone shows a contradiction between a set of numbers and their position on the number line. I can rewrite your list as sums of all rationals s o the notion that it is a set only of the even numbers thus is false. Similarly an infinite set is always complete
If the set $\displaystyle \mathbb{N}_{2n}$ is countable, then you could find a bijection between it and $\displaystyle \mathbb{N}$, right? Similarly to the case $\displaystyle \mathbb{N}_{2n+1}$. In any case, both $\displaystyle \mathbb{N}_{2n}$ and $\displaystyle \mathbb{N}_{2n+1}$ are countable because $\displaystyle \mathbb{N}_{2n}\mapsto\mathbb{N}$ or $\displaystyle \mathbb{N}_{2n+1}\mapsto\mathbb{N}$ are not surjective mappings.
al-mahed is offline  
May 24th, 2015, 02:59 PM   #20
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

Quote:
Originally Posted by al-mahed View Post
To have a nice example, please google Hilbert's Hotel. Consider the rooms in the Hotel the natural numbers, so they serve as indexes to count.
I've thought about it and the simple solution is that nobody is going to come for a room because everybody has one already.
Tau is offline  
Reply

  My Math Forum > Math Forums > Math

Tags
countable, logic, uncountable



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
show that M is uncountable 450081592 Real Analysis 2 November 23rd, 2011 06:34 PM
Uncountable whatlifeforme Number Theory 1 October 30th, 2011 04:53 AM
countable, uncountable wannabe1 Real Analysis 5 September 22nd, 2010 03:18 PM
Surjection, Uncountable Set vaevictis59 Applied Math 18 March 16th, 2010 09:14 AM
Sets, Countable and Uncountable Bernie Applied Math 3 September 9th, 2009 01:28 AM





Copyright © 2019 My Math Forum. All rights reserved.