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, 11:18 AM   #1
Tau
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?
Tau is offline  
 
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.
al-mahed is offline  
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.
al-mahed is offline  
May 24th, 2015, 12:04 PM   #4
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

Quote:
Originally Posted by al-mahed View Post
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.
At the limit rationals become irrationals. Huge ratios are the same thing as numbers with a huge number of decimals.The difference becomes infinitesimal and undetectable. Also, if we talk about an interval, there is but one gap which is the difference of the two numbers. You cannot speak about numbers as points and as lenghts or intervals at the same time, isn't that inconsistent?
Tau is offline  
May 24th, 2015, 12:13 PM   #5
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

Quote:
Originally Posted by al-mahed View Post
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.
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.
Tau is offline  
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 one-to-one 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 one-to-one 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 one-to-one 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.
Timios is offline  
May 24th, 2015, 12:37 PM   #7
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

Quote:
Originally Posted by Timios View Post
Yet there is an infinite set of integers between any two positive rationals.
Integers? Maybe you meant reals? If you meant reals, again I claim I have an infinite set of naturals to count them with.
Tau is offline  
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.
v8archie is offline  
May 24th, 2015, 12:41 PM   #9
Tau
Member
 
Joined: Jan 2014

Posts: 86
Thanks: 4

Quote:
Originally Posted by v8archie View Post
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.
If you substitute the word "reals" with "naturals" in your sentence, the new sentence is also true.
Tau is offline  
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 easy-to-see 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}{c|ccccc}
&\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 5-th line, i.e., the line regarding the 5-th 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 k-th 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??
al-mahed 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.