In proving set of positive rational numbers is countable, normally we use the way "Connecting the numbers diagonally". Connecting rational numbers "Diagonally"

In this way,we can list out all the rational numbers. But may I know what the bijective function that connects Q and N is?, since we need a bijection between two sets to show that they are having same cardinality.

Thank you.

  • $\begingroup$ Are you asking for an explicit formula for such a bijection? If so, this question has some good answers. $\endgroup$ – Wyvellum May 22 '20 at 5:00
  • $\begingroup$ Because I am just starting studying Math, and the courses I am studying are elementary. I am not sure if I can understand some deep theories. And this question arises when I learn Discrete Mathematics , and my professor did not show the bijective function. What he said is "In order to prove a set has a cardinality as natural set, we need to order the elements of that set in a sequence/list". But I would appreciate if you can give some explicit formulas, and I will try to understand them. Thank you. $\endgroup$ – Ho F May 22 '20 at 5:06
  • $\begingroup$ As an alternative, consider the Calkin-Wilf sequence $\endgroup$ – J. W. Tanner May 22 '20 at 5:18
  • $\begingroup$ OK. Thank you so much. $\endgroup$ – Ho F May 22 '20 at 5:23

The way you get a bijection is to simply skip the duplicates. The easiest way to do it is to only count the fractions in maximally cancelled form.

Note that for the purpose of this post, I assume that $0\notin\mathbb N$.

So you start with $1/1$. That is the totally cancelled form, so it gets assigned the number $1$. Next come $2/1$ and $1/2$. They are also totally cancelled, so they get assigned $2$ and $3$.

The next diagonal is where it gets interesting: $3/1$ is still totally cancelled, so we assign is the next number, $4$. But $2/2$ is not totally cancelled (numerator and denominator have a common factor $2$), therefore we skip it and do not assign it a number. If we did, we would have assigned two different numbers to the value $1=1/1=2/2$. Since we skip it, the next number considered is $1/3$, which again is totally cancelled and therefore gets assigned the next natural number, $5$.

Note that (apart from the fully-cancelled shortcut) this generally applies: Whenever for any set $X$ you have a surjection $f:\mathbb N\to X$, you can get a bijection $g:\mathbb N\to X$ by simply skipping duplicates.

Moreover note that to show that a bijection exists, you don't need to provide an explicit bijection. The Schröder-Bernstein theorem guarantees you that whenever you have an injection both ways, there does exist a bijection.

Moreover, if we have a surjection $X\to Y$, then there exists also an injection $Y\to X$ (assuming the axiom of choice, but in the case of $X=\mathbb N$, not even that is needed). The way to get that is basically the skipping process outlined above. Therefore if you can show both an injection and a surjection from 4X\to Y$ you have proved that a bijection exists.

Since the diagonal counting without skipping gives a surjection $\mathbb N\to\mathbb Q^+$ (every number is reached), and in injection $\mathbb N\to\mathbb Q^+$ is trivial, this already proves the existence of a bijection.

  • $\begingroup$ So the function needs not to be an explicit formula, as long as we can assign every elements in Natural set exactly one element in set X and make sure that the function from N to X is also surjective? $\endgroup$ – Ho F May 22 '20 at 5:22
  • $\begingroup$ @HoF: Yes, exactly, see my edit. Strictly speaking you also need to show that there exists an injection; a surjection alone only proves that there are at most as many positive rationals as naturals. But an injection is trivial (and there is no doubt that the set of rational numbers is indeed infinite). $\endgroup$ – celtschk May 22 '20 at 5:28
  • $\begingroup$ Ok, I see. Thank you $\endgroup$ – Ho F May 22 '20 at 5:36

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.