# Would my proof that $\mathbb{Q} \sim\mathbb{N}$ count?

So I saw that $$\mathbb{Q}\sim\mathbb{N}$$ and I tried to prove it.

The official proof was a function using prime factors.

I'm learning and in doing so I try to prove each theorem and corollary or example before I read the one in the script or book. But mine was a little funky as I tried long and hard to think of something, but unfortunately couldn't come up with anything better.

Would this work:

Every number in $$\mathbb{Q}$$ can be interpreted as two integers $$a$$ and $$b$$. Then we can devise a function $$f: \mathbb{Q} \rightarrow \mathbb{N}$$ where $$a$$ is the first digit and $$b$$ is appended.

For example $$f(5/4) = 54$$ or $$f(1/1) = 11$$.

Is such a function even allowed? Would it be injective and bijective?

Also, if this is an allowed function. Would $$0/4$$ and $$0/1$$ count as two different rational numbers or the same? ( I was struggling finding a definition for the zero numbers if they count as different).

Sorry if this is complete nonsense!

• $\frac{11}1$, $\frac{1}{11}$. Commented Dec 27, 2019 at 16:18
• $1/1=2/2$ but $f(1/1)=11$ and $f(2/2)=22$ so this isn't even a function, however you could define it that $a, b$ have to be coprime that would solve the issue and say that $f(0)=0$ and ignore the case $0/b$ Commented Dec 27, 2019 at 16:22
• This is neither injective not surjective, assuming you fix it as kingW3 suggests. Then 22 is not in the image, and f(54/11)=f(541/1)=5411$. – jgon Commented Dec 27, 2019 at 16:26 • Finding a bijection is indeed hard as none of a+b, ab, a/b, a^n, are bijective, I think you can't make a bijective function with elementary operations but thinking instead of numbering rational numbers might be easier to think about. Commented Dec 27, 2019 at 16:45 • Use $\sim$ for$\sim\$. Commented Dec 27, 2019 at 18:16

As you probably know by now, your $$f$$ is not injective (if it were a function), but most importantly, it is actually not a function as it is not well defined.

That is, as you pointed out, $$0=\frac{0}{1}=\frac{0}{4}=\frac{0}{n}$$. Thus, $$f(0)$$ could actually be any integer, so $$f$$ is not even a function.

If you want a explicit bijection you can have a look here. It shows a bijection from rationals to naturals, but it is easy to modify it to get integers of course.

• Thank you for taking the time and the link, I'll check it out, it's a different proof from the one in my book, but it uses one I've used before (Z to N). That's super cool! Commented Dec 27, 2019 at 16:47

I like Cantor's pairing function. You can look it up and get a formula. But it is utterly trivial from a geometric point of view. Roughly speaking, arrange the rationals in an array, and then just zig-zag your way from the upper left hand corner to put them in a list.

• Thanks, I've seen this a few chapters ago, I'll put it on my list to review. Awesome! Commented Dec 27, 2019 at 16:51

Here is another route. It is quite common when trying to prove that two sets $$A$$ and $$B$$ have the same cardinality that you can fairly easily find a function $$f:A \rightarrow B$$ which is an injection but not a surjection and another $$g:B \rightarrow A$$ which is also an injection but not a surjection.

Intuitively, this says that $$|A| \le |B|$$ and $$|B| \le |A|$$ so $$|A| = |B|$$.

The Schröder–Bernstein theorem deals with this case: you can deduce that the sets have the same cardinality. It is worth studying that and then you can stop once you find such a pair of injections.

Even in a fairly simple case such as yours, an explicit bijection can be rather messy.

• Thank you, in my script this was mentioned but reduced to a simple line and not further commented. I seen it more detailed in How to prove it's new edition. I will check it out. Most proofs I've seen only show an injection and not a surjection. Commented Dec 28, 2019 at 6:59