Let $L = \{(a,b)\mid a,b ∈ \mathbb N\}$

$L$ is the set of all lattice points in the first quadrant (all points in first quadrant whose coordinates are natural numbers make $L$)

a. Give a formula that makes the function f: $\mathbb{N} \rightarrow L$ injective. (Where Natural numbers is the domain and $L$ is the codomain)

Just confused as to how there could be a binary operation or formula that leads from and element from the domain of $\mathbb{N}$ to form two elements in the codomain of L, since L is the set of lattice points $(a,b)$ containing two elements. For example, if I tried to do $f(x) = 2x$, it would be 2 times any element from the domain $\mathbb{N}$, but that would create another element in the domain of $\mathbb{N}$. I need a formula that uses elements in $\mathbb{N}$ to create elements in the domain of $L$, while also having that formula be injective

  • $\begingroup$ Yes, you somehow need to extract two natural numbers out of each $n \in \mathbb{N}$. One way to do this is to write $n = 2^{a-1} m$ where $m$ is odd. Then use $a$ as the first natural number associated to $n$, and $m$ as the second. $\endgroup$ – Mark Wildon Nov 30 '13 at 16:41
  • 2
    $\begingroup$ @MarkWildon That's overkill, since you just want injective. You are giving an injective and surjective function. There are much simpler functions which are injective... $\endgroup$ – Thomas Andrews Nov 30 '13 at 16:45
  • $\begingroup$ is it possible to do something like 2(a,b)? could you apply binary operation to coordinates, or is that invalid? $\endgroup$ – gticecream8 Nov 30 '13 at 16:49
  • $\begingroup$ I could swear that this question was posted last night. $\endgroup$ – Asaf Karagila Nov 30 '13 at 17:00
  • 1
    $\begingroup$ @ThomasAndrews Isn't $f: \Bbb N \to \Bbb N^2$, $f=\{(n,(a,m))\mid n=2^{a-1}m, \textrm{ with } m \textrm{ odd}\}$ only injective? $\endgroup$ – user36546 Nov 30 '13 at 19:31

Just to clear up my earlier comment: as Thomas Andrews points out, there are many, much simpler, injections from $\mathbb{N}$ to $\mathbb{N}^2$. For example, $n \mapsto (n,1)$ is fine. In words: use $n$ as the first coordinate and fix the second coordinate at $1$.

I somehow misread the question as asking for a bijection $\mathbb{N} \rightarrow \mathbb{N}^2$, but my comment doesn't work for this because $m$ is always odd. This could be fixed by defining

$$ n \mapsto (a,\frac{m+1}{2}) $$

where $n = 2^{a-1} m$ and $m$ is odd. There are many other, probably simpler, ways to do this.

  • $\begingroup$ Thank you! But is that a formula or just a mapping? so for example, f(x)↦ (n,1) or f(x)↦ (1,n) are both formulas that are injective, correct? I sort of understand it but could you explain the injective part a little? Such as just slightly explain why it is injective/how you know it is injective. $\endgroup$ – gticecream8 Nov 30 '13 at 21:26
  • $\begingroup$ What do you think a function is, @gticecream8? Why is $f(n)=2n$ a function, but $f(n)=(n,1)$ is not a function? $\endgroup$ – Thomas Andrews Dec 1 '13 at 2:55
  • $\begingroup$ It is a function but it's not a formula, since you can't solve for (n,1) but you can solve for 2n. you can only plug numbers into (n,1). For 2n, you can plug in a number for n then solve. I need a formula for the injective function (n,1) $\endgroup$ – gticecream8 Dec 1 '13 at 4:50
  • 1
    $\begingroup$ Dear gticecream8: let $g(n) = (n,1)$. I claim that this is both a formula for $g(n)$, and a specification of a function $g : \mathbb{N} \rightarrow \mathbb{N}^2$. To solve for $(n,1)$ just note that the unique element of $\mathbb{N}$ that maps to $(n,1)$ is $n$ itself. $\endgroup$ – Mark Wildon Dec 1 '13 at 18:30
  • 1
    $\begingroup$ Note that $n \mapsto (n,1)$ does not associate natural numbers with natural numbers, but associates natural numbers with ordered pairs. You might want to graph it in the three-dimensional space, assigning some $(y,z)$ for each $x$. This function is as one-to-one as $n \mapsto n$ is. The function $n \mapsto(n,n^2)$ is likewise injective. $\endgroup$ – user36546 Dec 2 '13 at 1:35

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.