My Math Forum > Math Countable vs uncountable vs logic

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

 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:
 Originally Posted by al-mahed 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?

May 24th, 2015, 12:13 PM   #5
Member

Joined: Jan 2014

Posts: 86
Thanks: 4

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

 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.
May 24th, 2015, 12:37 PM   #7
Member

Joined: Jan 2014

Posts: 86
Thanks: 4

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

 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

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

 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??

 Tags countable, logic, uncountable

,

### logic is countable or uncountable

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top