# Math Help - Counting and Bijections

1. ## Counting and Bijections

Hello, all! I've spent the last 2 hours trying to do this question, and my paper is still blank!

Question:

For integers m and n, let A[m,n] = ${m \le x \le n}$ where x is an integer.

(a) List all the members of the set [-2,4]
(b) For $m \le n$, write down a formula in terms of m and n, for the size of the set A[m,n]. Justify your answer by giving an explicit $f:N_k \to A[m,n]$, for an appropriate value of k.

My attempts:

(a) {-2, -1, 0, 1, 2, 3, 4}

(b) I'm thinking the formula will be n-m? ButI have no real idea, to be honest.

2. Originally Posted by WWTL@WHL
Hello, all! I've spent the last 2 hours trying to do this question, and my paper is still blank!

Question:

For integers m and n, let A[m,n] = ${m \le x \le n}$ where x is an integer.

(a) List all the members of the set [-2,4]
(b) For $m \le n$, write down a formula in terms of m and n, for the size of the set A[m,n]. Justify your answer by giving an explicit $f:N_k \to A[m,n]$, for an appropriate value of k.

My attempts:

(a) {-2, -1, 0, 1, 2, 3, 4}
correct

(b) I'm thinking the formula will be n-m? ButI have no real idea, to be honest.
did you check your formula for the set you did above? did you notice it came up one short? the formula is n - m + 1

3. Originally Posted by WWTL@WHL
Question:
For integers m and n, let A[m,n] = ${m \le x \le n}$ where x is an integer.
(a) List all the members of the set [-2,4]
(b) For $m \le n$, write down a formula in terms of m and n, for the size of the set A[m,n]. Justify your answer by giving an explicit $f:N_k \to A[m,n]$, for an appropriate value of k.
My attempts:
(a) {-2, -1, 0, 1, 2, 3, 4}
(b) I'm thinking the formula will be n-m? ButI have no real idea, to be honest.
Let us assume that in all cases we will consider m<n.
You are correct with the answer to part (a).

For part (b) count the number is part (a). Is it (m-n)+1?
If $N_{n - m + 1} = \left\{ {0,1,2, \cdots ,n - m} \right\}$ then define
$f:N_{n - m + 1} \mapsto A\left[ {m,n} \right] \mbox{ as } f(k) = k + m$

4. Originally Posted by Jhevon
did you check your formula for the set you did above? did you notice it came up one short? the formula is n - m + 1
Thanks for the reply. I didn't even think about applying it to the set in part (a)! Of course, the set has 7 elements, and n-m is just 6.

Originally Posted by plato

For part (b) count the number is part (a). Is it (m-n)+1?
If then define
Thanks to you too. So if , then we can define f to be the bijection .

But I don't understand where the f(k) = k+m bit comes from. Furthermore, I don't see why it is useful. Of course, I'm not saying it isn't, it's just that I fail to see why - but I am hopeless at this stuff. The reason I'm saying this is because I can't see a way to find a numerical value for k, or don't you have to?

Thanks once again guys, more help will be appreciated greatly.

5. Originally Posted by WWTL@WHL
I can't see a way to find a numerical value for k, or don't you have to?
The k is a variable, any member of the set $A{m,n}$. Just the way x is a variable in the usual notation f(x). That is to say that $k \in A\left[ {m,n} \right]$.

6. I see! Thank you

Can I be a bit cheeky and ask for help on another question? It's a very short one...

Question:
Give an example of an injection $f : N \to N$ that is not a bijection. ( $N$ is meant to be the set of Natural Numbers, btw.)

My thinking:
My first inclination is that you can't.

By definition, an injection is where every y in Y is value f(x) for at most one x in X.

So would I be right in saying that an injection $g : f(x) = 2x$ is such an injection. If I am right, how would I go about writing this in 'proper' notation?

7. Originally Posted by WWTL@WHL
I see! Thank you

Can I be a bit cheeky and ask for help on another question? It's a very short one...

Question:
Give an example of an injection $f : N \to N$ that is not a bijection. ( $N$ is meant to be the set of Natural Numbers, btw.)

My thinking:
My first inclination is that you can't.

By definition, an injection is where every y in Y is value f(x) for at most one x in X.

So would I be right in saying that an injection $g : f(x) = 2x$ is such an injection. If I am right, how would I go about writing this in 'proper' notation?
An injection $f: A \to B$ is a function that has values $f(a) ~ \forall ~ a \in A$ but there is not necessarily $f^{-1}(b) ~ \forall ~ b \in B$. In other words, we must be able to use all of A, but we don't necessarily use all of B.

So your example is correct: you are using all the natural numbers as your domain, and only the even natural numbers are used as your range. But to make this an injective function we can't use the set $\{ f(a) | a \in A \}$ because then we'd have a one to one function. So an injective version of this function will be:
$f: \mathbb{N} \to \mathbb{N} : x \mapsto 2x$
whereas the bijective version is
$f: \mathbb{N} \to \mathbb{N_E} : x \mapsto 2x$
where $N_E$ is the set of even whole numbers.

-Dan

8. Thanks a lot Dan!

I understood what you said completely. I think (or hope) I understand the concept behind it, it's just the notation I'm not used to. I've only started covering this stuff at university, so it all seems a bit alien to me at the moment.

A huge thank you once again to you, Plato and Jhevon!

9. Originally Posted by WWTL@WHL
Can I be a bit cheeky and ask for help on another question?

So would I be right in saying that an injection $g : f(x) = 2x$ is such an injection. If I am right, how would I go about writing this in 'proper' notation?
First, when asking a second, follow-up question it is best to start a new thread.

As to 'proper' notation, that is always defined by your textbook/instructor.
I see that Dan has given you a possible answer.
Here is another: $f = \left\{ {\left( {n,2n} \right):n \in N} \right\}$.
In some foundation courses that is the preferred notation because it points to a function as a set of ordered pairs.

10. I see. 'Ordered pairs' is not something I've covered, but I do know (roughly) what the notation means.

I will take a look through my textbook anyway.