1

Let $\mathbb{G} =\{ a^b + \sqrt{c}: a,b,c\in \mathbb Q \}$

I guess the set $\mathbb{G}$ is countable set, but I can't show it properly. How to start the proof?

David
  • 4,201
J.Exactor
  • 215
  • Hint: This one is solved in a similar way to how you would usually prove countability of $\Bbb Q$ in the first place. In fact, assuming that you have a concrete counting of the rationals is a very good place to start. – Arthur Oct 14 '15 at 07:30
  • Use countable union of countable set is countable. – David Oct 14 '15 at 07:35

2 Answers2

2

You have a function $f \colon (a, b, c) \mapsto a^b + \sqrt c \colon \mathbb{Q}^3 \twoheadrightarrow \mathbb{G} \subseteq \mathbb{C}$, where $f$ maps $\mathbb{Q}^3$ onto $\mathbb{G}$.

In general: if $f\colon X \twoheadrightarrow Y$ is a surjection, then $|Y| \le |X|$ i.e. cardinality of $Y$ $\le$ cardinality of $X$. Here, $\mathbb{G}$ is a surjective image of $\mathbb{Q}^3$ which is countable, so $\mathbb{G}$ is countable too.

I'm assuming you know/don't have to prove that (*) $\mathbb{Q}$ is countable, and that (* *) if $X, Y$ are countably infinite, then so is $X \times Y$ (thus, given (*), $\mathbb{Q}^3$ is countably infinite).

BrianO
  • 16,579
1

The proof is basically the same as for $\mathbb Q$ being countable. You start with an enumerations $a_j$, $b_k$ and $c_l$ (for $a$, $b$ and $c$) in your formula and iterate the triples by first taking those where $j+k+l=0$ then $j+k+l=1$, then $j+k+l=2$ and so on. For each level you have finitely many triples and by this construct all triples will be enumerated.

skyking
  • 16,654