1
$\begingroup$

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.

  • 0
    First off, you have the definition of *onto* wrong. It should be that for every $y$ in the *codomain*, there is a value $x$ in the *domain* for which $f(x) = y$.2012-03-11
  • 0
    Does your natural numbers contain $0$?2012-03-11
  • 3
    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?2012-03-11
  • 0
    @RahulNarain First, I fixed the typo. To your second point, that helps, but it seems like cheating. This is exactly the point that is causing me confusion. It's too abstract for me.2012-03-11
  • 3
    @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.2012-03-11
  • 0
    @ArturoMagidin I understand the point you're making, but I think you are begging the question. I'll assume that the set of your home phone numbers has 1 element in it. The natural numbers are infinite, right?2012-03-11
  • 0
    What difference does it make if the (co)domain is infinite or not?2012-03-11
  • 2
    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?2012-03-11
  • 3
    @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.2012-03-11
  • 3
    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.2012-03-11
  • 0
    @RahulNarain Yes, I agree that there is no largest natural number. This must be true, because as you pointed out in the trivial proof, for an arbitrary natural number choice $n$, add 1 to get a larger number $m$. I think that the best thing for me is to take your earlier comment as the gospel. That is, I can live with this somewhat slippery mathematical definition of functions (and other concepts) if I assume that all functions (read sets) are always instantiated at all times, even if *the number of such instantiations is infinite.* But wow, mind==blown.2012-03-11
  • 0
    @ArturoMagidin I completely agree. The concept of infinite sets and functions defined on infinite domains is something I haven't come across in programming ma and pa's invoice systems. Seriously, I have struggled with this concept. Can you recommend a source for learning how to understand the concept of infinity in mathematics?2012-03-11
  • 2
    You need to get more comfortable with functions (particularly, disassociate the notion of "function" with the notion of 'algorithm'/'recipe'/'evaluation'); and with infinite sets in general (which take a *lot* of getting used to). But I think what is really standing in your way is thinking of mathematical-functions as if they were "functions" in the sense of computer programs ("called subroutines").2012-03-11
  • 2
    Yes, you should never think about mathematical objects as being *instantiated*. They just *exist*. And their existence is completely independent of how easy or hard it is for you to *find* them. (P.S. This is going to blow your mind even more when you study analysis, and learn that there exist real numbers that cannot be computed at all. The set of real numbers is far larger than the set of possible programs that compute a real number.)2012-03-11
  • 0
    @RahulNarain I don't want this to devolve into a philosophical discussion, but I must say I find your answer that mathematical objects "just exist" to be deeply unsettling. The claim that knowledge of mathematics is *a priori* seems to be the prevalent view and has gone unquestioned this quarter by my classmates, perhaps because unlike me, they have studied math for years and are used to the idea. But this idea, and the related idea that mathematical abstractions like sets and functions exist independent of reality is ... unsettling. How do you cope with this?2012-03-11
  • 1
    Well, there's no way to talk about this without talking about philosophy! Perhaps it will give you a little consolation (or perhaps it will have the opposite effect!) to learn that the "Platonism" I espoused in my comment is by no means a universally accepted viewpoint among mathematicians (see [Wikipedia's article on the philosophy of mathematics](https://en.wikipedia.org/wiki/Philosophy_of_mathematics#Contemporary_schools_of_thought)).2012-03-11
  • 0
    That said, you don't *have* to believe in mathematical truths being independent of reality. But you do have to believe that they are independent of *you* -- that just because *you* didn't check that there is some $x$ for which $f(x)$ would be, say, $2012$ doesn't mean that there isn't one. That is, whether $f$ is onto or not has nothing to do with how many $x$s you can plug into $f$ and collect the values of $f(x)$. So it must be about all the values of $f(x)$ which are *in principle* possible, right? And that's all of them, all at once.2012-03-11
  • 0
    Cool, thanks. My math class has ended and I have moved on to a course on algorithms. We recently covered loop invariants, which are somewhat analogous to strong induction. Except for the fact that to prove a loop invariant, you need a terminating condition ... reminded me of this post and my mental dissonance regarding infinite sets and functions.2012-03-29

1 Answers 1

6

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$...)

  • 0
    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.2012-03-11
  • 0
    Actually, I'm a lawyer :)2014-10-17