2
$\begingroup$

Cantor digonalization method is used to prove that an open interval for real numbers $(0,1)$ is not countable. Since rational numbers also have decimal expansions, we could try to use this same method to prove that the set of rational numbers in $(0,1)$ is not countable. Explain why we could not conclude that the set of rational numbers in $(0,1)$ is uncountable using this method.

What i tried

Cantor diagonalizaton works by writing all the real numbers in the interval $(0,1)$ as an array of matrix and then finding a real number that does not belong to this set of array of matrix by making the diagonal entries of the real number different from that of the set of array of numbers in the matrix thus a contradiction. While for the set of rational numbers it can be expressed in the form of $\frac{a}{b}$ where gcd(a,b)=1, We do the same thing as for the rational numbers but i think this set of rational numbers somehow always tend to appear in the array of matrix no matter how we try thus this method of proof dosent apply for the case of rational number. But im unsure how. Could someone explain this to me. Thanks

$\endgroup$
  • 1
    $\begingroup$ When you construct the "new" real out of your lists of real, you use the fact that any decimal expansion corresponds to a real. It isn't the case for rationals. $\endgroup$ – Max Jan 26 '17 at 18:08
  • 1
    $\begingroup$ Max, did explain it. You use the method to create a number not on the list. But you have no reason to assume the new number is rational. So the method concludes that if the rationals are countable than there exists at least one number that is not rational. Which is ... valid. But not relevant. $\endgroup$ – fleablood Jan 26 '17 at 18:19
3
$\begingroup$

Its not the process but the conclusion of the process that fails. When you write real numbers in the interval (0,1) as an array of matrix and then find a number by making the diagonal entries of the real number different from that of the set of array of numbers in the matrix, the resulting number is again a real number.

When you apply the same trick to the rational numbers the resulting number may not be rational. Remember being rational means the decimal expression either terminates or repeating. How do you ensure these properties in the resulting number?

$\endgroup$
  • $\begingroup$ To be pedantic, I would say this method proves: Either the rationals are uncountable or if they are countable there exists at least one irrational number. This is a valid conclusion and valid proof. Unfortunately its a weak and wimpy result. $\endgroup$ – fleablood Jan 26 '17 at 18:24
  • $\begingroup$ I can see that the Cantor number (in the case of the list of rationals) is not terminating. But I don't see why it is impossible to create a new repeating number. $\endgroup$ – zoli Jan 26 '17 at 18:27
  • $\begingroup$ @zoli of course it is possible to get a number which is repeating, i.e.rational but not all of them are of this form. $\endgroup$ – tessellation Jan 26 '17 at 18:34
  • $\begingroup$ @zoli hypothetically, without knowing that the rationals actually are countable, we don't know that it wouldn't be. But we we can't conclude that it would, so we can't use this as an argument that the number would be rational. And if the number could be irrational... the argument is useless. (But as we know, for different reasons, that the rationals are countable, we know the new number can't be rational because all the rationals are on the list.) $\endgroup$ – fleablood Jan 26 '17 at 18:50
2
$\begingroup$

Proof that the set of decimal expansions from $(0,1=.99999.....]$ are uncountable:

If they were countable we could list them all. Then we could manipulate them all to get a number not on the list. That new number is a decimal expansion. But that contradicts that all decimal expansions were on the list.

Proof that the set of rationals in decimal representation from $(0,1=.99999.....]$ are uncountable:

If they were countable we could list them all. Then we could manipulate them all to get a number not on the list. $\color {red} {\text{ That new number is a rational in decimal representation.}}$ But that contradicts that all rationals in decimal representation were on the list.

!!!BUT!!! There is no reason to believe that bit in red is true!

So instead we'd have to write:

If they were countable we could list them all. Then we could manipulate them all to get a number not on the list. If $\color {red} {\text{ that new number is a rational in decimal representation.}}$ $\color {blue} {\text{then that would}}$ contradict that all rational in decimal representation were on the list.

And from that we can conclude the true (but wimpy) result:

Either the rationals in decimal representation for $(0,1=.99999....]$ are uncountable OR if they are countable then there exist decimal representations in $(0,1]$ that are not rational.

$\endgroup$
1
$\begingroup$

The rationals are countable.

Here is a intuitive sketch.

Make a table. Put natural numbers across the top and down the left column. the body of the table is the ratio of the number at the top of the table over the number in the right column.

This is a representation of the full set of $\mathbb Q+$

Now you can run a serpentine line that runs through every entry in the table. this maps the rationals to $\mathbb N$

More formally:

There exists an injection from $\mathbb Q\to \mathbb Z\times \mathbb N$ i.e. $\frac pq = (p,q)$

the Cartesian product of countable sets is a countable set.

$\endgroup$
  • $\begingroup$ yes, but the question is not whether the rationals are uncountable but why that "proof" that they are uncountable fails. $\endgroup$ – fleablood Jan 26 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.