# Function which is onto and not 1-1

Here is an example of a function which I believe to be onto and not 1-1:

$f: \mathbb{N} \to \mathbb{N}$

$f(n) = \begin{cases} 0 &\text{if} \quad n=0\\ 0 &\text{if} \quad n=1\\ n-1 &\text{otherwise}\\ \end{cases}$

It is not 1-1 because f(0) and f(1) both map to 0. It is onto because for every $y$ in the codomain, there is a value $x$ in the domain for which $y=f(x)$.

Fine. But this is causing me mental dissonance because I don't understand how you can say that all codomain values are mapped given the following: In programming, $y=f(x)$ doesn't take on a value until $f$ is called.

Even then the largest values in the codomain won't be mapped until some call to $f(x)$ yields their value.

There are other places in studying math where the lack of instantiation of values doesn't seem to invalidate the definition of concepts, and I think it will help me to move forward as a student if someone can explain to me what is going on here, and why I shouldn't worry about the fact that the definition seems to assume that all functions are always simultaneously instantiated, allowing mathematicians to make claims about their values.

-
Second, maybe you can think of it this way: For every $y$ in the codomain, there is a value $x$ in the domain such that *if you called $f$ with the argument $x$*, the result *would be* $y$. Does that help? –  Rahul Mar 11 '12 at 5:32
@Noah: Do you believe that I don't have a phone number until you or someone else looks me up in the telephone directory, or is whether I do or do not have a phone number independent of someone looking it up? "Calling" the function (evaluating it) is like looking me up and dialing my number; but whether or not I have a phone does not depend on whether people call me or not. –  Arturo Magidin Mar 11 '12 at 5:41
Consider the following statement: For every natural number $n$, there is another natural number $m$ bigger than $n$. Would you agree that this statement is true? If I told you that one proof is to take $m = n+1$, should you be concerned that $m$ has no value until $n$ is chosen, and so any really large natural number doesn't necessarily have a bigger number until you evaluate $m = n + 1$ with $n$ chosen to be that number? –  Rahul Mar 11 '12 at 5:53
@g33kzor: No, I don't think you understand the point I'm making. The point is that the act of you evaluating a function should not be confused with the function, just like the act of looking up or dialing a phone number should not be confused with the number. What digits are included in my phone number does not depend on whether or not you dial it, just like whether 148432 is an element of the image of $f$ do not depend on whether or not you bother to actually compute the function at some input and get 148432. –  Arturo Magidin Mar 11 '12 at 6:03
Also, it seems to me that the domain, the codomain, the function in question, everything is completely irrelevant to your true question/confusion, which has to do with infinite sets and with functions defined on infinite domains. –  Arturo Magidin Mar 11 '12 at 6:09

You are confusing your act of finding out the value of the function at a particular element of the domain with the function. That would be like thinking that a person does not have a telephone number until you look them up in the telephone directory and dial. Whether or not you look them up in the telephone directory does not determine whether or not they have a phone number.

In mathematics, a function $f\colon X\to Y$ is a subset of $X\times Y$ such that

1. For all $x\in X$ there exists $y\in Y$ such that $(x,y)\in f$; and
2. If $x\in X$, $y,y'\in Y$ and $(x,y),(x,y')\in f$, then $y=y'$.

When this happens, we write $f(x)=y$ to signify that $(x,y)\in f$; this is unambiguous by $2$.

Now consider what happens if we "dualize" the two parts of the definition:

1. For all $y\in Y$ there exists $x\in X$ such that $(x,y)\in f$;
2. If $y\in Y$, $x,x'\in X$ and $(x,y),(x',y)\in f$, then $x=x'$.

A function that satisfies the first property is said to be "onto" or "surjective." (Note that you have the definition wrong; you are using the first property that defines a function to be a function instead of this extra condition). A function that satisfies the second property is said to be "one-to-one" or "injective.

Your function, viewed as a function $f\colon \mathbb{N}\to\mathbb{N}$ is the set $$\{(0,0), (1,0)\}\cup\{ (n+1,n)\mid n=1,2,3,4,\ldots\}.$$ As such, you are absolutely correct that the function is onto (though not for the reason you state: it's onto because for every $n\in\mathbb{N}$, the codomain, there exists $x\in\mathbb{N}$, the domain, with $f(x)=n$: if $n=0$, we can take $x=0$; if $n\gt 0$, we can take $x=n+1$), and is not one-to-one (because $f(0)=f(1)$, even though $0\neq 1$).

Now, $f$ is just a set. It is. It is not a procedure, it is not a process, it is not the act of you evaluating the function. It's a set. Its functional properties depend only on its properties as a set, and not on what we do with it. We don't "call" a functionn

(What "causes [you] mental dissonance" would likewise cause you mental dissonance when you consider the one-to-one and onto function $f\colon \mathbb{R}\to\mathbb{R}$ given by $f(x)=x$...)

-
I totally agree,the OP is probably a computer science or some other major and this is his or her first exposure to real mathematics. He/she needs to stop thinking of a function in formula or procedural terms and begin thinking in terms of naive set theory i.e. a function is a nonempty set of ordered pairs such that no 2 different ordered pairs have the same first member;a one to one function is a function with the added property that no 2 different ordered pairs have the same SECOND member and an onto function is one where the set of all second members(values) of f is equal to the codomain. –  Mathemagician1234 Mar 11 '12 at 7:00
Actually, I'm a lawyer :) –  g33kz0r Oct 17 at 1:04