I am proving the rationals (greater than 0) are countable. I have to prove a function is injective and I just wanted another opinion on whether my proof is correct or if there is an even better method of proof.
I have the following function - f : Q(greater than 0) -> Naturals
f(m/n) = 2^m 3^n (where m and n are coprime)
I have to prove that this function is injective. Proof:
For all m/n and m'/n' in Q (>0) WTS: f(m/n) = f(m'/n') implies m/n = m'/n'
f(m/n) = 2^m 3^n
f(m'/n') = 2^m' 3^n'
Suppose m != m' and n != n' for a contradiction.
By the definition of injective functions we have:
2^m 3^n = 2^m' 3^n' which is equivalent to 2^m 3^n (1- 2^(m'-m) 3^(n'-n)) = 0
Since a^b = 0 does not have a solution. We have that:
2^(m'-m) 3^(n'-n) = 1
Since 2 divides the LHS, it must divide the RHS so 2 divides 1. Which is a contradiction as n divides 1 is false for all n > 1. We can do something similar with 3 as well. So our assumption that n != n' and m != m' is incorrect. Yielding m = m' and n = n' as required.
Note: I have a feeling there is a far better way of showing this so if you have a better method please tell me :)
There are problems here. You should not suppose that $m\ne m'$ and that $n\ne n'$; what you should suppose is that $m\ne m'$ or that $n\ne n'$.
And, after writing that $2^{m'-m}3^{n'-n}=1$, you act as if the LHS is a natural number, but it doesn't have to be.
You can simply say that $2^m3^n=2^{m'}3^{n'}\implies m=m'\wedge n=n'$ by the Fundamental Theorem of Arithmetic.