12

We just learnt this today in Discrete Math, and now I'm trying to review from the textbook. However unfortunately during this lecture I was completely lost with no idea what was going on.

I know that for one-to-one, every $x$ has an unique $y$ and for onto, for all $y$ there exists an $x$ such that $f(x)=y$.

I've provided two questions to use as examples from my textbook.

  1. Suppose $f \colon \Bbb N \to \Bbb N$ has the rule $f(n) = 4n + 1$. Function $f$ is one-to-one.

  2. Suppose $f \colon \Bbb Z \to \Bbb Z$ has the rule $f(n) = 3n - 1$. Function $f$ is onto $\Bbb Z$.

Answer one or both or give a hint, I would just love any explanation to what is going on! Thanks!

dfeuer
  • 9,069
user7349
  • 143
  • 1
  • 1
  • 5
  • See if it passes the Vertical Line Test AND the Horizontal Line Test. If so, that function is 1-1. Ex: $y = x^3$ – Xoque55 Nov 14 '13 at 20:37
  • In fact, the definition of a function requires $x$ to have a unique $y$ whenever $f: X \to Y$. – Don Larynx Nov 14 '13 at 20:39
  • @DonLarynx As much I appreciate hints, we have not learnt that so I have no idea what that is. – user7349 Nov 14 '13 at 20:44
  • 4
    @DonLarynx I don't understand your hint. How does the notion of cardinality help with this question? – Trevor Wilson Nov 14 '13 at 21:08
  • 1
    The way to identify a duck goes like this: 0) know what makes a duck a duck 1) look at something 2) decide if it has all the properties of a duck. 3) Say yes/no accordingly 4) Done. The procedure with "duck" swapped with "onto function" or "1-1 function" is the same. Is your trouble at step 2 or 0? – rschwieb Nov 14 '13 at 21:10
  • 4
    Between ducks and cardinals, I hope we haven't confused the OP :) He might think we're birdbrains.... – Eleven-Eleven Nov 14 '13 at 21:21
  • 1
    @DonLarynx, your hint doesn't seem to have anything to do with anything. – dfeuer Nov 14 '13 at 21:42

3 Answers3

17

1) Let's show this function is $1-1$. To do this, we suppose $f(n_1) = f(n_2)$ and show that this forces $n_1 = n_2$.

So, if it's true that $f(n_1) = f(n_2)$, then this means that

$$4n_1 + 1 = 4n_2 + 1 \\ \Rightarrow 4n_1 = 4n_2 \\ \Rightarrow n_1 = n_2 $$

and we have demonstrated what is required. Thus, $f$ is $1-1$.

2) Let's see if the function is onto (it might not be). If it is, we should be able to choose any $m \in \mathbb{Z}$ and show that there is some $n \in \mathbb{Z}$ such that $f(n) = 3n - 1 = m$.

If this is true, then we will need $n = \dfrac{1}{3}(m + 1)$. The problem is that this might not be an integer! For example, if $m = 1$, then $n$ would need to be $\dfrac{2}{3}$, which is not an integer. Thus, there is no $n \in \mathbb{Z}$ such that $f(n) = 1$ and so the function is not onto.

EDIT: For fun, let's see if the function in 1) is onto. If so, then for every $m \in \mathbb{N}$, there is $n$ so that $4n + 1 = m$. For basically the same reasons as in part 2), you can argue that this function is not onto.

For a more subtle example, let's examine

3) $f : \mathbb{N} \to \mathbb{N}$ has the rule $f(n) = n + 2$. If it is onto, then, for every natural number $m$, there is an $n$ such that $n + 2 = m$; i.e. that $n = m - 2$. Now, we don't have the same problem as we did before, that is, we don't have to divide by anything to solve for $n$. Thus there is always an integer $n$ so that $n + 2 = m$.

BUT! If $m = 1$ (for example), then $n$ would have to be $1 - 2 = -1$ which is not a natural number, so this function is not onto either.

The point of all this is, we have to look closely at both the domain and codomain to answer these kinds of questions.

BaronVT
  • 13,613
  • Ok, so I'm starting to see the light. But let's take "1)" if we changed the last sentence to "function is onto N" that would be 'False' since the function is 1-1. Unless it could be both? – user7349 Nov 14 '13 at 21:23
  • @user7349: Yes, a function can be both one-to-one and onto. We call this a bijection; a fancy name for an invertible function. –  Nov 14 '13 at 21:24
  • 1
    A function can be $1-1$ and onto (or it can be one, but not the other, or it can be neither). I'll edit in a discussion of whether the function in 1) in onto. – BaronVT Nov 14 '13 at 21:24
  • 1
    Ok, so you're awesome! (for going beyond my original question) and your explanation(s) are great, thank you! (the fog as lifted) – user7349 Nov 14 '13 at 21:57
  • 1
    fantastic explanation – computerscienceisapain Sep 05 '21 at 03:12
3

If you want to show that a function, say $f$, is 1-to-1, then you typically consider two values $x_1,x_2$ in the domain of $f$ such that $f(x_1)=f(x_2)$. From this, if you can derive that $x_1=x_2$, then your function is 1-to-1.

Let's consider your first example. We would have $f(x_1)=4x_1+1=4x_2+1=f(x_2)$. We can then simplify to obtain $x_1=x_2$. Hence $f$ is 1-to-1.

To show that a function $f$ is not 1-to-1, it suffices to find $x_1,x_2$ in the domain of $f$ such that $x_1\neq x_2$, but $f(x_1)=f(x_2)$.

If you want to show that a function $f$ is onto, then for any $y$ in the image/range of $f$, you must find $x$ in the domain such that $f(x)=y$.

To show that a function $f$ is not onto, just find $y$ in the target set of $f$ (that is, the set at the end of your arrow $f:X\to Y$; we call it the codomain) such that there is no $x$ in the domain such that $f(x)=y$.

As Baron pointed out, the function in your second example is not onto... we'll show this as an example that something is not onto. Consider any $y\in\mathbb Z$. In order for $f$ to be onto, there must be an $x$ such that $f(x)=3x-1=y$, or $$ x = \frac{y+1}{3}. $$ Now, we can see that $x$ is not an integer (as required) for some values of $y$. Namely, if $y=1,3,4,6,$etc., then there is no $x$ such that $f(x)=y$. Thus $f$ cannot be onto.

2
  1. Another option: decompose $f$ into simpler functions that are easier to check as being one-to-one. Let $g(n)=n+1$ and $h(n)=4n$. Both $g$ and $h$ are linear functions with nonzero leading coefficient; and linear functions are one-to-one. Then $f= g\circ h$, both $g$ and $h$ are one-to-one, and a composition of one-to-one functions is also one-to-one. So $f$ is one-to-one.
David Snyder
  • 326