0
$\begingroup$

The definition of a countably infinite set is that each element can be paired up with a natural number. The basic goal of the proof is to show that an infinite number of distinct irrational numbers can be mapped to every natural number, which would contradict the fact that every natural number can be paired up with an irrational number. This is basically achieved by shuffling numbers around to end up with a contradiction. Also, this post isn't exactly a proof yet but just the scratch work.

To start I took advantage of the fact that the rationals are countably infinite. That is, for all $a,b \in \mathbb{Z}, b \neq 0$, then $n \to a/b$ for some $n \in \mathbb{N}$ (The arrow here just indicates that a natural number is mapped to an irrational). Assume for a contradiction that every natural number can be paired up with every irrational number. In other words, for all $n \in \mathbb{N}$ we have $n \to x$ where $x$ is some irrational. Since every integer is also mapped to a rational number then we could also map every rational number to an irrational number.

Then this would also mean that $a/b$ can be mapped to $x$, so $a/b \to x$. If we think of this as an equation then "multiplying both sides" would yield $a \to bx$. Since $b$ is a non-zero integer being multiplied by $x$, an irrational integer, then $bx$ is also an irrational integer that also exists somewhere, by our assumption. But this would also mean that $a$ would also be mapped to infinitely other irrational numbers because $a/k \to y$ would turn into $a \to ky$ for every $k \in \mathbb{Z}$.

So by only moving the numbers around, we found a way to map an infinite number of irrational numbers to each natural number, which clearly isn't possible and leads to a contradiction. Thus there are uncountably many irrational numbers.

Now I'm not sure that this really is a proof. I have this feeling that something isn't quite right with it. Is this proof right or wrong?

Also, note that I have literal bare minimum experience with working the cardinality of infinite sets and things, so if there is a mistake, please try to explain it in simple terms. I only attempted this exercise as part of a "sneak peek" section in my intro-to-proofs textbook into the world of combinatorics

$\endgroup$
5
  • 1
    $\begingroup$ I'm afraid there are at least two critical errors. If $\frac{a}{b}$ is mapped to $x$, in general, this tells us nothing about where $a$ is mapped. Further, it's perfectly possible to have sets $A,B$ bijective where you can also map infinitely many elements of $A$ to each element of $B$. For an example, consider $A = \mathbb{Q}^*$, $B = \mathbb{N}$, where we map each non-zero reduced fraction to its numerator (taken to be positive). $\endgroup$ Jul 4, 2023 at 22:14
  • $\begingroup$ I do not follow this at all. Your terminology of "can be mapped" is far too vague. That a set is countable means that there is a (at leats one) bijective map $f$ from the natural numbers to that set, but then automatically there are infinitely other such maps. But when you want to show that a certain set $S$ is uncountable, you have to show that there is no bijective map $f : \mathbb N \rightarrow S$ at all. Your whole line of argument about "infinite numbers of distinct irrational numbers mapped to every natural number" is imprecise, it's unclear how that would show what is actually needed. $\endgroup$ Jul 4, 2023 at 22:14
  • $\begingroup$ Also, one should not think of a map "as an equation" and "multiply both sides". Also, what is an "irrational integer"? Etc. $\endgroup$ Jul 4, 2023 at 22:15
  • 1
    $\begingroup$ "The basic goal of the proof is to show that an infinite number of distinct irrational numbers can be mapped to every natural number, which would contradict the fact that every natural number can be paired up with an irrational number." I don't understand this... $\endgroup$ Jul 4, 2023 at 22:22
  • $\begingroup$ An infinite number of distinct rational numbers can also be mapped to each natural number. $\endgroup$
    – gnasher729
    Jul 4, 2023 at 23:18

2 Answers 2

2
$\begingroup$

The basic goal is to show that an infinite number of distinct irrational numbers can be mapped to every natural number, which would contradict the fact that every natural number can be paired up with an irrational number.

This approach doesn't work. Consider the function $f:\Bbb N\to\Bbb N$ that counts the number of trailing zeroes, i.e. $f(1)=0, f(10)=1, f(100)=2,$ etc. This maps infinitely many inputs to each output value (e.g. there are infinitely many numbers with exactly three trailing zeroes), but the existence of this mapping does not establish the impossibility of a one-to-one pairing between $\Bbb N$ and $\Bbb N$.

$\endgroup$
1
  • $\begingroup$ I knew something was fishy with this step! $\endgroup$ Jul 4, 2023 at 22:32
0
$\begingroup$

Carl already answered you, but I think it's a vision This actual model may be useful, and directly relevant, see my question:

Does the number of circles in the plane exceed the number of points?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .