description/proof of that for real numbers set and equivalence relation that \(2\) elements are equivalent iff their difference is rational, quotient set is uncountable
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of quotient set.
- The reader knows a definition of representatives set of quotient set.
- The reader admits the proposition that any finite product of countable sets is countable.
- The reader admits the proposition that any finite composition of injections is an injection.
- The reader admits the proposition that for any infinite set, if there is any injection from the set into the natural numbers set, there is a bijection from the natural numbers set onto the set.
Target Context
- The reader will have a description and a proof of the proposition that for the real numbers set and the equivalence relation that any \(2\) elements are equivalent if and only if their difference is rational, the quotient set is uncountable.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(\mathbb{R}\):
\(\sim\): \(\in \{\text{ the equivalence relations on } \mathbb{R}\}\), such that for each \(r_1, r_2 \in \mathbb{R}\), \(r_1 \sim r_2 \iff r_1 - r_2 \in \mathbb{Q}\)
\(\mathbb{R} / \sim\): \(= \text{ the quotient set }\)
//
Statements:
\(\mathbb{R} / \sim \notin \{\text{ the countable sets }\}\)
//
2: Proof
Whole Strategy: Step 1: see that \(\sim\) is indeed an equivalence relation; Step 2: take the classification map, \(g: \mathbb{R} \to \mathbb{R} / \sim\), any representatives map, \(f: \mathbb{R} / \sim \to \mathbb{R}\), and the map, \(h: \mathbb{R} \to (\mathbb{R} / \sim) \times \mathbb{Q}, r \mapsto (g (r), r - f (g (r)))\), and see that \(h\) is an injection.
Step 1:
Let us see that \(\sim\) is indeed an equivalence relation.
1) \(\forall r \in \mathbb{R} (r \sim r)\): reflexivity: \(r - r = 0 \in \mathbb{Q}\), so, \(r \sim r\).
2) \(\forall r_1, r_2 \in \mathbb{R} (r_1 \sim r_2 \implies r_2 \sim r_1)\): symmetry: \(r_1 - r_2 \in \mathbb{Q}\), so, \(r_2 - r_1 = - (r_1 - r_2) \in \mathbb{Q}\), so, \(r_2 \sim r_1\).
3) \(\forall r_1, r_2, r_3 \in \mathbb{R} ((r_1 \sim r_2 \land r_2 \sim r_3)\implies r_1 \sim r_3)\): transitivity: \(r_1 - r_2 \in \mathbb{Q}\) and \(r_2 - r_3 \in \mathbb{Q}\), so, \(r_1 - r_3 = r_1 - r_2 + r_2 - r_3 = (r_1 - r_2) + (r_2 - r_3) \in \mathbb{Q}\), so, \(r_1 \sim r_3\).
So, \(\sim\) is an equivalence relation.
Step 2:
There is the classification map, \(g: \mathbb{R} \to \mathbb{R} / \sim, r \mapsto [r]\), which is a surjection, as is mentioned in Note for the definition of quotient set.
There is a representatives map, \(f: \mathbb{R} / \sim \to \mathbb{R}\), which is an injection, as is mentioned in Note for the definition of representatives set of quotient set.
Let us define the map, \(h: \mathbb{R} \to (\mathbb{R} / \sim) \times \mathbb{Q}, r \mapsto (g (r), r - f (g (r)))\).
That is indeed valid, because as \(r, f (g (r)) \in g (r)\), \(r \sim f (g (r))\), so, \(r - f (g (r)) \in \mathbb{Q}\).
\(h\) is injective, because for each \(r_1, r_2 \in \mathbb{R}\) such that \(r_1 \neq r_2\), when \(g (r_1) \neq g (r_2)\), \(h (r_1) \neq h (r_2)\), and otherwise, \(f (g (r_1)) = f (g (r_2))\), so, \(r_1 - f (g (r_1)) \neq r_2 - f (g (r_2))\), because otherwise, \(r_1 = r_2\), a contradiction.
If \(\mathbb{R} / \sim\) was countable, \((\mathbb{R} / \sim) \times \mathbb{Q}\) would be countable, by the proposition that any finite product of countable sets is countable, so, there would be a bijection, \(h': (\mathbb{R} / \sim) \times \mathbb{Q} \to \mathbb{N}\), and \(h' \circ h: \mathbb{R} \to (\mathbb{R} / \sim) \times \mathbb{Q} \to \mathbb{N}\) would be an injection, by the proposition that any finite composition of injections is an injection, then, \(\mathbb{R}\) would be countable, by the proposition that for any infinite set, if there is any injection from the set into the natural numbers set, there is a bijection from the natural numbers set onto the set, a contradiction against that \(\mathbb{R}\) was not countable.
So, \(\mathbb{R} / \sim\) is not countable.
