0

Construct an Injection between the set of rationals $\mathbb{Q}$ and the set of all integers $\mathbb{Z}$ .

Answer:

Define $ f: \mathbb{Q} \to \mathbb{N} \ $ by $ \ f\left(\frac{p}{q}\right)=|p-q|+1 \ $ , where $ \gcd(p,q)=1$

Clearly $f$ is an injection.

Next, define $ g: \mathbb{N} \to \mathbb{Z}$ by $ g(n)=n $

Then $ g $ is also an injection.

Lorenzo B.
  • 2,252
MAS
  • 10,638
  • This isn't a duplicate it's a proof verification request. I've added the appropriate tag. – Rob Arthan Apr 28 '18 at 18:41
  • Is my work correct ? – MAS Apr 28 '18 at 18:44
  • 2
    $p/(p+1)$ and $(p+1)/p$ are both sent to $|p-(p+1)|+1=2$. –  Apr 28 '18 at 18:45
  • oh sorry my fault – MAS Apr 28 '18 at 18:47
  • I think the easiest way to write a correct proof is look for a way to enumerate or list the rationals, and then use this enumeration to define a bijection with $\mathbb{N}$ in the natural way. The injection into $\mathbb{Z}$ then follows just like you did. Finding an explicit function defined in one case seems as too much work, to me. If you really want an explicit function, check the link by Dietrich Burde. – Václav Mordvinov Apr 28 '18 at 18:51

1 Answers1

1

Your $f$ is not an injection. There are many pairs of coprime numbers $p, q$ with the same value for $|p - q|$ (famously so when $p$ and $q$ are both prime and $|p-q|= 2$: such pairs are called twin primes). For a specific example, with your definition of $f$, $f(5/3) = 3 = f(13/11)$.

Rob Arthan
  • 48,577