Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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? – Fred Nov 30 '13 at 19:31
up vote 2 down vote accepted

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.

share|cite|improve this answer
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. – Fred Dec 2 '13 at 1:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.