2
$\begingroup$

I am trying to prove that $\mathbb{Q}$ and $\mathbb{Q} \times \mathbb{Q}$ have the same cardinality so I must construct a bijection between the sets.

I have supposed there exists a function $f: \mathbb{Q} \to \mathbb{Q} \times \mathbb{Q}$ where $f$ is 1-1 and onto but I'm not sure where to begin proving this.

I doubt explicitly defining this function would be of much use, (much like how Cantor's Diagonalisation argument requires no formula as such, as it is tedius) I'm simply interested in seeing if it is possible to map every $q \in \mathbb{Q}$ to a $(r, s) \in \mathbb{Q} \times \mathbb{Q}$ and testing whether it is 1-1 and onto.

I think I could use something similar to Cantor's Diagonalisation argument for a bijection from $\mathbb{N} \to \mathbb{Q}$ but I can't wrap my head around it for my case.

$\endgroup$
8
  • 3
    $\begingroup$ The cardinality of $\mathbb Q$ and $\mathbb Q \times \mathbb Q$ is the same so there must exist such a bijection. $\endgroup$
    – Simon S
    Commented Nov 9, 2015 at 1:31
  • 1
    $\begingroup$ There's a bijection between $\mathbb{Q}$ and $\mathbb{Q}^n$ in fact $\endgroup$ Commented Nov 9, 2015 at 1:32
  • 1
    $\begingroup$ You can use a similar diagonalization argument by putting the rationals on the sides of the "square" (since they are countable), much like you would put the integers on the sides of the "square" when proving the rationals are countable. $\endgroup$ Commented Nov 9, 2015 at 1:34
  • 2
    $\begingroup$ @SimonS: Well, that seems a bit circular, given the definition of cardinality... $\endgroup$
    – user98602
    Commented Nov 9, 2015 at 1:35
  • 1
    $\begingroup$ @SimonS: I'm aware there's a bijection between them. My point was that "The cardinality of $A$ and $B$ is the same" is defined to mean that there's a bijection $f: A \to B$, so one can't really invoke this in pursuit of a bijection. $\endgroup$
    – user98602
    Commented Nov 9, 2015 at 3:36

2 Answers 2

9
$\begingroup$

For an explicit construction,

You should know from the literature that there exists a bijection $f~:~\mathbb{Q}\to \mathbb{N}$. Further, you should know that there exists a bijection $g~:~\mathbb{N}\to\mathbb{N}\times\mathbb{N}$. Finally, there is a bijection $h~:~\mathbb{N}\times\mathbb{N}\to\mathbb{Q}\times\mathbb{Q}$

We have then $h\circ g\circ f$ is a bijection from $\mathbb{Q}\to\mathbb{Q}\times\mathbb{Q}$

$\endgroup$
3
  • $\begingroup$ I'm studying for an exam, so if this question is asked, I would first prove there exists bijections from $\mathbb{Q} \to \mathbb{N}$, $\mathbb{N} \to \mathbb{N} \times \mathbb{N}$, and $\mathbb{N} \times \mathbb{N} \to \mathbb{Q} \times \mathbb{Q}$ and then compose those functions and use the proof that the composition of bijections is bijective? That process seems quite long, is that the best way you can think of? $\endgroup$ Commented Nov 9, 2015 at 1:51
  • 1
    $\begingroup$ @TristanBatchler: What's really being said here is twofold: 1) $\Bbb Q$ is countable, 2) the product of two countable sets is countable. I think this is a fairly intuitive idea. It would be a hassle to write down an actual bijection $\Bbb Q \to \Bbb Q \times \Bbb Q$. $\endgroup$
    – user98602
    Commented Nov 9, 2015 at 1:53
  • $\begingroup$ Thanks for clarifying. I understand now. :) $\endgroup$ Commented Nov 9, 2015 at 1:58
2
$\begingroup$

Yes, just define an injection of $\mathbb{Q} \hookrightarrow \mathbb{N}$ and an injection $\mathbb{Q} \times \mathbb{Q} \hookrightarrow \mathbb{N}$ by $f(q) \to p_1^rp_2^s$ where $p_1$ and $p_2$ are prime and $q = \frac{r}{s}$ in lowest terms. Do the same for $\mathbb{Q} \times \mathbb{Q}$.

Then note an injection of an infinite set into $\mathbb{N}$ can be made into a bijection (if such an injection exists, which it does in this case), and then take composites.

$\endgroup$
11
  • 1
    $\begingroup$ An injection of an infinite set into $\mathbb{N}$ is a bijection? Or do you mean that if an infinite set has an injection into $\mathbb{N}$, then it has a bijection with it? $\endgroup$ Commented Nov 9, 2015 at 1:36
  • $\begingroup$ this answer is wrong. $\endgroup$
    – syusim
    Commented Nov 9, 2015 at 1:36
  • $\begingroup$ @JasonDeVito Just order the elements in the image of $f$ and then list their indices and map to $\mathbb{N}$ by these indices $\endgroup$ Commented Nov 9, 2015 at 1:37
  • $\begingroup$ the map $\mathbb{N} \to \mathbb{N}$ given by $n \mapsto 2n$ is injective but not bijective since 1 is not in its image, so it can't be surjective. Revise or delete this answer. $\endgroup$
    – syusim
    Commented Nov 9, 2015 at 1:38
  • 1
    $\begingroup$ @Anthony: Thanks for your clarification. You've got the +1 from me now. $\endgroup$ Commented Nov 9, 2015 at 1:47

You must log in to answer this question.

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