Let $S$ be the set of all possible functions mapping $\{\sqrt 2, \sqrt 3, \sqrt 5, \sqrt 7 \}$ to $\Bbb Q$, find the cardinality of $S$.

At first I wanted to use the theorem that for any sets $A$ and $B$, the cardinality of the set of all functions mapping $A$ to $B$ is $\vert B \vert ^ {\vert A \vert}$, but in the proof of this theorem when $A$ and/or $B$ is infinite, words like "$\aleph_0$ possibilities of each elements in $A$ mapping to $B$" are used. While my instructor thought we can’t definitely say which cardinal number $\vert B \vert ^ {\vert A \vert}$ actually is.

So without using the above theorem, is there any other way to prove the question? i.e from proving bijection of $S$ to $\Bbb Q$?

  • $\begingroup$ can you find a bijection from $S$ to $\Bbb Q^4$? $\endgroup$ – J. W. Tanner Jul 19 '19 at 22:13
  • $\begingroup$ @J.W.Tanner That is the question needed to solve. If we can find a bijection of $S$ to $\Bbb Q$, and since $\vert \Bbb Q ^4 \vert = \vert \Bbb Q \vert$, the problem will be solved. But I don't know how to constrct a bijection from $S$ to $\Bbb Q$ $\endgroup$ – WaterBro Jul 19 '19 at 22:38
  • 2
    $\begingroup$ I'm confused about your comment here and your comment to the answer of @HennoBrandsma. First, you say you already know a bijection between $\mathbb Q$ and $\mathbb Q^4$. Second, the answer gives you a bijection between $\mathbb Q^4$ and $S$. Third, the composition of those two bijections a bijection between $\mathbb Q$ and $S$. Which of these steps gives you trouble? $\endgroup$ – Lee Mosher Jul 19 '19 at 22:51
  • $\begingroup$ @LeeMosher Henno edited his answer, but I am still confused about the bijection between $S$ and $\Bbb Q ^4$, If we want to turn irrational number into rational number we have to do even exponential function but even exponential function are not injective, how can we construct such function that is bijective, a detailed one with calculation process. $\endgroup$ – WaterBro Jul 19 '19 at 23:06
  • 1
    $\begingroup$ You are not asked to "turn" an irrational number into a rational number. You are asked to write down a function from one set to another set. $\endgroup$ – Lee Mosher Jul 19 '19 at 23:08

It's clearly in bijective correspondence with $\Bbb Q^4$: if $f$ is such a function, map it to $(f(\sqrt{2}),f(\sqrt{3}),f(\sqrt{5}),f(\sqrt{7})) \in \Bbb Q^4$. The function $f$ is completely determined by these 4 rational values, and all tuples define such a function.

The square $A^2$ of a countable set $A$ is countable, and we can apply this twice to the countable set $\Bbb Q$ to get that $S\simeq \Bbb Q^4$ is countable (and infinite, so of size $\aleph_0$).

  • $\begingroup$ Well, this is what I cannot solve. I know that the cardinality of cartesian product of two countable set equals $\aleph_0$, while the bijection between my $S$ with $\Bbb Q$ cannot be constructed. It is clearly to say they are bijective, but a formal proof is needed to show that and this is the main part for this question actually. $\endgroup$ – WaterBro Jul 19 '19 at 22:42
  • 1
    $\begingroup$ @WaterBro That bijection is the most obvious map, really. $\endgroup$ – Henno Brandsma Jul 19 '19 at 22:45
  • $\begingroup$ I misunderstand the question. So for this question, we are not going to find a mapping from those four irrationals to $\Bbb Q$, right? There $f$ can be a function like ${\sqrt 2}^2+a, {\sqrt 3}^2+b, {\sqrt 5}^2+c, {\sqrt 7}^2+d$, where $a,b,c,d$ is any rational number satisfying ${\sqrt 2}^2+a\neq{\sqrt 3}^2+b\neq {\sqrt 5}^2+c\neq{\sqrt 7}^2+d$, then the function $f$ is one-to-one correspond to $\{a,b,c,d\} \in \Bbb Q ^4$, am I understanding correct? $\endgroup$ – WaterBro Jul 19 '19 at 23:24

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.