# Giving injective formulas for a function f: $\mathbb{N} \rightarrow L$ given a set $L = \{(a,b)\mid a,b ∈ \mathbb N\}$

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

• 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. – Mark Wildon Nov 30 '13 at 16:41
• @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... – Thomas Andrews Nov 30 '13 at 16:45
• is it possible to do something like 2(a,b)? could you apply binary operation to coordinates, or is that invalid? – gticecream8 Nov 30 '13 at 16:49
• I could swear that this question was posted last night. – Asaf Karagila Nov 30 '13 at 17:00
• @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? – 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.

• 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. – gticecream8 Nov 30 '13 at 21:26
• What do you think a function is, @gticecream8? Why is $f(n)=2n$ a function, but $f(n)=(n,1)$ is not a function? – Thomas Andrews Dec 1 '13 at 2:55
• 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) – gticecream8 Dec 1 '13 at 4:50
• 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. – Mark Wildon Dec 1 '13 at 18:30
• 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. – user36546 Dec 2 '13 at 1:35