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