7
$\begingroup$

I'm studying real analysis and I know from previous courses that there are countably infinite rationals but uncountably infinite irrationals. However, I haven't done a formal proof about uncountability of irrationals.

I've been thinking about which irrationals are "unique" (in terms of being able to be expressed in terms of other irrationals / rationals), and for this informal thought, I've come up with the following situation which I'll describe formally:

Suppose we define equivalence classes on irrationals, such that

$$[r] = \{ p + r : \forall p \in \mathbb{Q} \}$$

Or stated in other words,

$$x \in [y] \lor y \in [x] \rightarrow x - y \in \mathbb{Q}$$

How many such distinct equivalent classes would exist? Countably infinite? uncountably infinite?

$\endgroup$
2
  • 3
    $\begingroup$ You are heading towards issues with the axiom of choice and non-measurable sets here, but there must be an uncountably infinite number of these equivalence classes (every real number is one such $r$ plus a rational number so if there were countably infinite such equivalence classes there would be a countably infinite number of real numbers). $\endgroup$
    – Henry
    Sep 2, 2020 at 7:54
  • 5
    $\begingroup$ Each equivalence class is countable. If you would have a countable number of equivalence classes, the set of real numbers would be countable. $\endgroup$
    – Wuestenfux
    Sep 2, 2020 at 7:56

3 Answers 3

8
$\begingroup$

Since the equivalence relation you are considering on $\mathbb{R}$ -- a very classical one, as users have pointed out above -- is none other than the congruence modulo the additive subgroup $\mathbb{Q}$, the cardinality of the quotient set $\mathbb{R}/\mathbb{Q}$ is by definition the index $(\mathbb{R}\colon\mathbb{Q})$ and -- as elementary group theory teaches us -- must therefore satisfy the cardinal relation: $$|\mathbb{R}|=(\mathbb{R}\colon\mathbb{Q})|\mathbb{Q}| \tag{*}.$$

On the right hand side we behold a product of two cardinals, at least one of which is infinite, namely $|\mathbb{Q}|=\aleph_0$. Elementary cardinal theory then tells us that the product of the two will be equal to the larger of the two (by reasons of multiplicative absorption of infinite cardinals). Were this larger cardinal to be equal to $\aleph_0$, we would reach the conclusion that $|\mathbb{R}|=\aleph_0$. On the other hand, any decent course of analysis should have taught us in its opening classes focused on the elementary construction of $\mathbb{R}$ that the cardinal relation $|\mathbb{R}|=2^{\aleph_0}$ holds.

Since by virtue of one of Cantor's famous theorems $2^{\mathbf{x}}>\mathbf{x}$ is valid for any cardinal $\mathbf{x}$, the above made assumption leads to a contradiction. Therefore, the larger of the two cardinals in question on the right hand side of relation $(^{*})$ above must be the index $\left(\mathbb{R} \colon \mathbb{Q}\right)$ and we can finally conclude that $|\mathbb{R}|=\left(\mathbb{R} \colon \mathbb{Q}\right)$.

So not only is this cardinality of equivalence classes uncountably infinite, we actually know which uncountable infinity it is: the power of the continuum.

$\endgroup$
8
  • 4
    $\begingroup$ I think you mean "cardinality of the continuum" rather than "power of the continuum". The latter can be misinterpreted as $|2^\mathbb{R}|$. $\endgroup$
    – abhi01nat
    Sep 2, 2020 at 9:00
  • 1
    $\begingroup$ @abhi01nat There is a certain classical terminological tradition of referring to the cardinality of a set as the ''power'' of that set (and by extension of referring to two sets having the same cardinality as ''equipotent''). With this grounding in mind, usage of the syntagm ''power of the continuum'' is not only justified but is moreover common practice. Needless to say, one can just as well opt for the perfectly synonymous ''cardinality of the continuum'', the two being interchangeable. (to be cont.) $\endgroup$
    – ΑΘΩ
    Sep 2, 2020 at 9:20
  • $\begingroup$ @abhi01nat (cont.) As to that risk of misinterpretation which you mention I would say there is no need for worry, since speaking of ''the power'' of the continuum is something different linguistically, semantically, lexically etc from speaking of ''the powerset'' of the continuum. $\endgroup$
    – ΑΘΩ
    Sep 2, 2020 at 9:22
  • $\begingroup$ you can write \tag{*}\label{*} and then \eqref{*}, if you want $\endgroup$ Sep 2, 2020 at 9:30
  • $\begingroup$ I was not aware, thanks for clarifying! $\endgroup$
    – abhi01nat
    Sep 2, 2020 at 9:33
4
$\begingroup$

Every class is of the form $[x]_{\sim}=x+\mathbb{Q}$ where $x$ is irrational, so $[x]$ is countable. Since $\sim$ is an equivalence relation, $\mathbb{R}/_{\sim}$ is a decomposition into disjoint sets, therefore there must exist uncountably many equivalence classes. Your construction is not new and it is sometimes used to construct counterexamples in topology/set theory. There is for example the Dowker's Example in topological dimension theory.

$\endgroup$
1
1
$\begingroup$

"However, I haven't done a formal proof about uncountability of irrationals."

(Rudin PMA) Theorem 2.14. Let $A$ be the set of all sequences whose elements are the digits $0$ and $1$. This set $A$ is uncountable.

The elements of $A$ are sequences like $1, 0, 0, 1, 0, 1, 1, 1, ... $

You can look the proof up by finding the book for free with a google search.


Define $f:A \to \mathbb{R}$ by for example $f( (1,0,1,0,0,1,1,1,0,0,1,...)) \to 0.10100111001...$, so $f$ takes any sequence of $A$, concatenates the sequence and places it after a "$0.$". Then $f$ is well-defined and injective, so $f(A)$ is therefore uncountable.

Therefore $\mathbb{R} \supset A$ is uncountable.

Also, the union of two countable sets is countable, (e.g. by Rudin's PMA Theorem 2.12).

We also know that the rational numbers $\mathbb{Q}$ are countable.

Therefore, if the irrational numbers $\mathbb{R} \setminus \mathbb{Q}$ were countable, then $\mathbb{R} = \mathbb{Q} \cup (\mathbb{R} \setminus \mathbb{Q})$ would be countable, contradicting the fact that $\mathbb{R}$ is uncountable.

Therefore $\mathbb{R} \setminus \mathbb{Q}$ is uncountable.

$\endgroup$
1
  • $\begingroup$ An upvote and a vote to delete. lol $\endgroup$ Sep 2, 2020 at 11:31

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.