May 24th, 2015, 11:18 AM  #1 
Member Joined: Jan 2014 Posts: 86 Thanks: 4  Countable vs uncountable vs logic
I cannot seem to understand in what sense real numbers are uncountable. No matter how many real numbers (rational or irrational) you give me I can use naturals to count them. Ε, π, and φ are three irrationals that I just counted and found to be three. What is my faulty logic?

May 24th, 2015, 11:46 AM  #2 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47 
You are overlooking that given any list, I find for you real numbers not on the list, ALWAYS. The first step to understand this, is that between two any given reals in your list you have an infinite amount of reals in the middle, always. This is not enough for being non countable since this is true for the rationals as well, but the same tools we use to show that the rationals are countable fail to be applied in the case of Reals, since now having proved that the list of rationals is countable, there are infinitely many Real numbers in between any two given rationals, and you cannot fill up this gap with rationals. 
May 24th, 2015, 12:02 PM  #3 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47 
Another aspect is that when ppl say "rationals are countable" and similar sentences, they are informally saying that all such numbers can be put on a complete list, or in bijection with the list of naturals. Of course, some real numbers are countable. The easy way to see this is as you already have done: take a countable infinite list, and add these and those guys there. Now, go further, get some infinite subset of reals which you know is countable, like e.g. $\displaystyle \pi, \pi+1, \pi+2, ...$. Now, you have naturals and also all naturals added to $\displaystyle \pi$, an enlarged list of naturals and infinite reals, such that all elements are countable. The problem of the example above is that you cannot always do that, can you? What if you get now the list $\displaystyle \pi, \pi+0.1, \pi+0.2, ...$? And the list $\displaystyle \pi, \pi+0.01, \pi+0.02, ...$? and now simultaneously all such lists for all given Real numbers? How many such lists would you need? Are they countable? Can you count how many lists such procedures generate? If not, case closed. If you think yes, now consider that between any two arbitrary numbers, in the conjunction of all such lists, you can create a new set of lists with the same size of the original conjunction of lists whose supposed element would be a list in the same size, but not only this, an entire universe of infinite lists can be infinitely created. 
May 24th, 2015, 12:04 PM  #4  
Member Joined: Jan 2014 Posts: 86 Thanks: 4  Quote:
 
May 24th, 2015, 12:13 PM  #5 
Member Joined: Jan 2014 Posts: 86 Thanks: 4  The complete list assertion is false since we are talking about infinity. I think you want to emphasize that you can construct a rule that shows exactly how to biject them. I think it's proven that no such rule of bijection can be made about reals but I'm skeptical that this proves anything about the assertion that reals are somehow uncountable. What is the counterargument about the simple observation that no matter how many reals you give me I'll always have a natural to count them with? That is what I want to know.

May 24th, 2015, 12:32 PM  #6 
Senior Member Joined: Jan 2014 From: The backwoods of Northern Ontario Posts: 390 Thanks: 70 
To determine whether two sets of numbers have the same number of elements, one must attempt to set up a onetoone correspondence between the sets. If this can be done, then the sets have the same number of elements. For example, one can easily set up a onetoone correspondence between the set of positive integers and the set of positive rationals. Yet there is an infinite set of rationals between any two positive integers. So this fact does NOT prove that they are not numerically equivalent. However, it has been PROVED that one CANNOT set up a onetoone correspondence between the postive integers and the positive reals (or the positive rationals and the positive reals). I cannot recall the proof, but when I studied it in a math course, I was convinced of its validity. Last edited by Timios; May 24th, 2015 at 12:37 PM. 
May 24th, 2015, 12:37 PM  #7 
Member Joined: Jan 2014 Posts: 86 Thanks: 4  
May 24th, 2015, 12:38 PM  #8 
Math Team Joined: Dec 2013 From: Colombia Posts: 7,649 Thanks: 2630 Math Focus: Mainly analysis and algebra 
You can count some subsets of the reals, but you can't count them all. In particular, you can't count the entire set of the reals.

May 24th, 2015, 12:41 PM  #9 
Member Joined: Jan 2014 Posts: 86 Thanks: 4  
May 24th, 2015, 12:49 PM  #10 
Senior Member Joined: Dec 2007 Posts: 687 Thanks: 47 
Now I give the most direct argument I know so far for the existence of the uncountable. This is an easytosee form of the so called diagonalization. Let $\displaystyle X_0, X_1, ...$ be the list of all subsets of naturals, that is to say, such list has all elements of the powerset $\displaystyle \mathcal{P}(\mathbb{N})$. Now, lets arrange them as this: \begin{array}{cccccc} &\textbf{0}&\textbf{1}&\cdots&\textbf{n}&\cdots \\ \hline \\ \textbf{X}_0&\phi_0(0)&\phi_0(1)&\cdots &\phi_0(n)&\cdots \\ \textbf{X}_1&\phi_1(0)&\phi_1(1)&\cdots &\phi_1(n)&\cdots \\ \vdots&\vdots&\vdots&\ddots &\vdots& \\ \textbf{X}_n&\phi_n(0)&\phi_n(1)&\cdots &\phi_n(n)&\cdots \\ \vdots&\vdots&\vdots&&\vdots&\ddots \end{array} where $\displaystyle \phi_i(n)$ is a predicate that gives a yes or no answer whether $\displaystyle n\in X_i$. Since the list has all subsets of naturals, then I define a subset $\displaystyle X^{*}$ such that $\displaystyle n\in X^{*}\iff n\not\in X_n$. Example, if in our list the 5th line, i.e., the line regarding the 5th set $\displaystyle X_5$ of our arbitrarily given list, contains the number 5, then $\displaystyle \phi_5(5)$ is true, since $\displaystyle 5\in X_5$. It should be straightforward that $\displaystyle X^{*}$ is on the list, inasmuch our assumption is that the list is complete. That means $\displaystyle X^{*}$ is in the kth position on the list. Now, fixing the number $\displaystyle k$, and studying the membership $\displaystyle k\in X_k$, we conclude that $\displaystyle k\in X^{*}\iff k\not\in X_k$, but $\displaystyle X^{*}=X_k$, then: $\displaystyle k\in X_k\iff k\not\in X_k$! This is diagonalization. the assumption of completeness of the list is the source of the contradiction. Lets see it in another angle: study the same list, but now replacing the predicates $\displaystyle \phi_i(n)$ by their results in binary form $\displaystyle 0, 1$. But in this case, lets NOT assume the list is complete. Question: is the list completable?? 

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 