Cardinality of Integers, Positive Integers, and Rational Numbers all equal $\aleph_0$

Question

Prove that $|\mathbb{Z}|=|\mathbb{Z}^+|=|\mathbb{Q}|=\aleph_0$

I am to use cardinal addition and multiplication to reduce this to finding an injection

$\mathbb{Q}^+ \to \mathbb{Z}^+\times\mathbb{Z}^+$.

Any help would be greatly appreciated- my professor whizzed through this material in class and I've been searching online for help all day! I've read many of the other posts about this topic but they haven't helped me very much.

Answer 1

First of all , $|\mathbb{Z^+}|=|\mathbb{N}|=\aleph_0$ by definition.
Secondly, notice you can count all of $\mathbb{Z}$: $$0,1,-1,2,-2....$$ Hence $|\mathbb{Z}|=\aleph_0$.

Furthermore you can count $\mathbb{Q}$ by grouping/ordering according to the absulte value of sum |numerator+denominator| (dropping duplicates): $$0,1,-1,2,-2,\frac{1}{2},-\frac{1}{2},\frac{1}{3},-\frac{1}{3},3,-3,\frac{1}{4},-\frac{1}{4},\frac{2}{3},-\frac{2}{3},\frac{3}{2},-\frac{3}{2},4,-4....$$ Hence $|\mathbb{Q}|=\aleph_0$.

For an injection $\mathbb{Q}^+ \rightarrow \mathbb{Z}^+ \times \mathbb{Z}^+$:
Every element in $\mathbb{Q}^+$ can be uniquely represented by a reduced fraction $\frac{a}{b}$, where $a,b \in \mathbb{Z}^+$, and this is a suitable injection. Hence:
$$|\mathbb{Q}^+| \leq |\mathbb{Z}^+ \times \mathbb{Z}^+|=|\mathbb{Z}^+||\mathbb{Z}^+|=\aleph_0 \aleph_0=\aleph_0$$ Hence: $$|\mathbb{Q}|=|\mathbb{Q^+}|+|\mathbb{Q^-}|+|\{0\}|=2 \aleph_0 +1=\aleph_0$$

Answer 2

HINT: If $x\in\Bbb Q^+$ then it can be written in a unique way as a reduced fraction $\frac pq$ where $p,q\in\Bbb Z^+$.