The Blog of Scott Aaronson If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.
Come up with the best mnemonic device for remembering which is injective and which is surjective.
This entry was posted
on Tuesday, March 17th, 2009 at 6:35 am and is filed under Contests.
You can follow any responses to this entry through the RSS 2.0 feed.
Both comments and pings are currently closed.
Inclusions are injective, and “sur-” means “on”.. glossed as “covering”.
Do people really have a problem with this? The only tricky bit I find is remembering which is right- and which is left-cancellable, and that has as much to do with notational conventions as anything else.
I find this one pretty easy. If A –> B is an injection, then A goes into B. “Sur” means “on” or “over” in French, and also shows up in English words like “surcoat”, “surcharge” and “surmount”. So just picture A on top of B, covering it completely.
The one that did give me trouble for a while was epimorphism and monomorphism. Any clever tricks for this?
The mnemonic devices people come up with specifically to help themselves remember things aren’t always useful to everyone else. They often sound weird when repeated to others, but more importantly, they only need to cover the part that the creator has difficulty with. For example, if the words “injective” and “surjective” are already firmly planted in your head, even if you can’t remember which is which, then all you need is something to attach to one of the words, perhaps to just one part of one of the words.
For me, I always just remembered what “injective” didn’t mean. The idea of an injection (as with a syringe or needle) didn’t seem compatible with the idea of getting everywhere, so that was enough for me. Also, I quickly latched on to the (for good reason) rarely used “into”/”onto” terminology, and the similarity between “into” and “injection” made it mostly a non-issue. But while this might work for some, it might not for others.
Since the primary target of the mnemonic device is going to be students who are having difficulties, it’s also important that the mnemonic does not damage the student’s just-forming comprehension of the idea. That’s another potential problem with the metaphor of the injective function as injecting its domain into its codomain. It’s only an accurate metaphor in the sense that it doesn’t mesh with the concept of a surjective function very well.
One way of overcoming this problem is to make the mnemonic device so abstract or bizarre that it doesn’t contain any conceptual content that could possibly interfere with useful metaphors. In this sense, “Sur, I’m on to you!” is fantastic. “Sir Jective hits everything with his sword” is also pretty good. Though oddly enough, I’ve encountered a couple students who have been thrown off by my using the word “hits” (without reference to knights of any name) to describe surjectivity, as in “this function hits everything in the codomain”.
The ideal mnemonic device (and sorry, I don’t actually have one) would do this one better and actually help understanding. Something that would combine the ability to remember the words with a helpful metaphor. I’ve always used soda vending machines (with button presses as inputs and soda flavors as outputs) to describe the difference between injective and noninjective functions because it’s a context in which the students are very willing to accept two inputs mapping to the same output. It’s not useful for surjectivity, however, because that depends very strongly on a what codomain you specify. It also has some other weaknesses that I won’t go into here. I’m still looking for an ideal function metaphor in which something very natural corresponds to the idea of having a specified codomain, but I’m getting off-track here.
I was hoping that by writing down what my ideal mnemonic device would be (funny, helpful for remembering the words as well as their associations, and helpful for comprehension (or at least not harmful)), I would be able to come up with one, but that was not to be today. Perhaps these thoughts will help someone else.
David Speyer: I always found epimorphism and monomorphism easier, mainly because I took Greek. “mono” means one, which should be familiar (e.g. monotonous); that’s 1-1. “epi” is a Greek preposition meaning “on,” as in “epicycles” which are cycles on other cycles or “epidermis” which is the top layer of skin, the skin on all the other skin. So epi is onto.
“mono-” means one, so one-to-one is natural for “monomorphism”. “epi-” means all, so onto is natural for “epimorphism”. (Now if only this helped remember the category theoretic definitions, which I have to rebuild from scratch every time.)
The symbol for meet looks like half an “M”. The symbol for join looks like a pointy “J” that is too long on the left.
Forget the counting and whole numbers if you can. I’ve never seen them outside of high school math classes, and even then, they’re not important. (On a side note, for years, teachers told me that some people don’t include 0 as a natural number, but I’ve never actually encountered someone who did this. Have any of you?)
If you imagine “range” as in “the target is within range of our weapons”, then it makes sense as the set of everything you can “hit” with the function. Helps to differentiate range from codomain, but not so much with the word “codomain” itself.
If you can remember to think of things as pointing upward (i.e. the graph represents the upper edge of some solid object), then a function that forms a “cave” (or maybe just half of one) is concave. This is weak to some (in the same way that “righty-tighty, lefty-loosey” drove me bonkers as a kid) because it depends on an arbitrary direction. As far as polygons are concerned, this is a much better mnemonic device as we naturally fill in polygons as solid objects (or at least more naturally than filling “down” graphs).
I think what one should do in these scenarios is to memorize the most important of the terms, and remember that one.
Injective is more important than surjective, because any function can be made surjective by just changing its codomain. (Technically, you could change the domain to make any function injective, but it’s much less natural and it might require the axiom of choice.)
As for convex vs concave, I remembered that convexity is the more important concept, and so should be associated with a smiley face (the mouth of a smiling face is a convex function).
What about the question of whether “injective” and “surjective” are good words to use at all? They sound more impressive than “one-to-one” and “onto”, but if people need mnemonics to remember them, it’s probably a good idea to not use them, right?
For convex and concave, I remember that a conVex function can look like a V, and a concave function can look like the entrance to a cave.
I’m with John, Garreth, Mihai and several others on this – I don’t really see the need to construct mnemonics, since it’s reasonably obvious that one is into and the other is onto. For that, I find the englishified counterparts MUCH more confusing; onto is easy enough, but when does one-to-one mean injective, and when does it mean bijective??
This is my response, also, to svat: injective, surjective, bijective have very clear, easily distinguishable meanings that are obvious with the smallest doses of Romance language knowledge (which will serve you well in other ways as well) – and not subject to the author-by-author randomness that, for instance, one-to-one is.
Well, as many people have said, if you speak a language that comes from Latin, then the words actually make sense. That said, the way I actually remember it is just by knowing that x^2 is not injective, and x^3 is surjective.
If I had to come with an mnemonic, well, you can give an injection to a cat. And you have Schrödinger’s cat, which we can say is in two places at the same time, which is what the elements of your range cannot do for injective functions. And then, surjective is the other one. It is not logical at all, but weird and stupid enough to make it easy to remember.
This is another excellent illustration of why a knowledge of foreign languages should (still) be required to get a Ph.D. in mathematics.
The idea of learning these terms without knowing (or, at the very least, simultaneously learning) their etymologies is…well, grotesque. (Like learning quantum mechanics the traditional way, except worse.)
As others have noted, the term “one-to-one” is awful. In addition to being kindergarten-sounding, it’s confusing: although a “function” is a “correspondence”, a “one-to-one function” (injection) is not the same as a “one-to-one correspondence” (bijection).
I do not now why so many people suggest that knowing a Latin language makes it easier to remember which is which. Certainly not in Spanish, the words “injective” or “surjective” don’t evoke any meaning by themselves. (I also learned them by remembering the important one, namely injective.) But certainly they are much better than the “informal” counterparts: “onto” does not mean anything at all (how is this intuitive?), and “one to one” seems to be referring to a bijection.
As for the poster claiming that knowing Latin should be a prerrequisite for earning a Ph.D in mathematics… well, that’s plain stupid. Sure it could help on certain occasions, but it’s a really unimportant thing.
Thanks for the mono-/epi- help! So these are the Greek roots analogous to in-/sur-. I don’t know Greek but, now that I know they are supposed to work that way, it shouldn’t be hard to figure out which is which.
I always remembered “e to the x is convex”. It rhymes, you see.
“As for the poster claiming that knowing Latin should be a prerrequisite for earning a Ph.D in mathematics…well, that’s plain stupid.”
I did not say Latin. I said “foreign languages”. Maybe you are unaware, but at least in the U.S. it is a tradition that mathematics graduate students are required to pass reading exams in two out of of three of French, German, and Russian — a tradition that, unfortunately, is in the process of dying out. My intention was to polemicize in favor of retaining this tradition. (I’m not the only one who thinks this. Paul Halmos also makes this argument in his memoir _I Want To Be A Mathematician_.)
The language I was thinking of was mainly French, not Latin. (Indeed, from the point of view of Latin, “surjective” is a bastardization; it should have been “superjective” — cf. Spanish “suprayectiva”.)
1. I have had plenty of trouble learning certain opposite words, including AM and PM as a child. But I never had any trouble with injective and surjective. The following has always seemed like a natural progression:
(1 to 1, onto) -> (into, onto) -> (injective, surjective)
2. I first learned the words convex and concave with lenses, where cave concave is easy.
But, how do these relate to functions? x^2 is concave if viewed from the top, and convex if viewed from below. Is there any reason why viewed from the top is the right way to think? I have always wondered about this. I suspect it is just bad terminology, although probably too late to get rid of now. What’s wrong with “curving upward” for convex.
Does anyone know the back story on how this unfortunate term got ingrained into math?
3. I have been busy and haven’t had a chance to read the “should children vote?” discussion. I bet a lot of nutcakes chimed in on that one. I look forward to finding out if Scott is one of them.
There are so many things it would be nice to learn, such as French, German, and Russian. Personally, I’d be happier with a good knowledge of combinatorics, probability, and statistics. You only have so much time to master stuff.
For better or for worse, most science is done in English. Personally, I’m glad, because it is what I speak. And, it really ticks them off in France, where they used to outlaw reading scientific papers in English.
The number of spoken languages in the world is rapidly shrinking. In a few decades most of the world will probably speak one of a half dozen languages. On one hand, that is a bummer, culture is being lost. I hope as much as possible is being recorded. But on the other hand, being a speaker of an oddball language is a huge disadvantage. English speakers all inherited it from family that at some time “got on board with the major language”, usually unwillingly. We are lucky because we are on board with a winner.
It is a very interesting fact that such a huge part of the world speaks Indo-European languages, particularly English and Spanish. Presumably at some prehistoric time, some proto IE speakers got a lot of clout. A plausible guess is that at was the first crew, perhaps from Kazakhstan, that got in cahoots with horses as a military team, enabling them to take over a huge area. A few thousand years later, when technology was ripe to allow large scale colonization, speakers of two IE languages, English and Spanish, were the best at it.
Halmos is a contradictory character. He is one of the best math writers ever. I own several of his books; they are great. But I think he is the guy who wrote “applied math is bad math”, or similar crap. I suspect he holds computer science beneath contempt. As anyone who has worked in both knows, pure math is semi recreational and lots easier than applied math. When you get to heaven, check out where Archimedes, Newton, Gauss, Euler, etc., have their tents pitched.
“That’s pretty neat, but where do they still do this?”
From what I hear it’s pretty much down to elite places like Princeton, Harvard, etc. Perhaps a few lesser schools still require one language.
“Halmos is a contradictory character. He is one of the best math writers ever. I own several of his books; they are great. But I think he is the guy who wrote “applied math is bad math”, or similar crap.”
Oh, dear. Come on — you can’t read an essay by title alone. Yes, Halmos (who is deceased) did write an article titled “Applied Mathematics is Bad Mathematics”. The title is deliberately provocative, in order to catch your attention. You should read the article; it doesn’t say what you think.
KaoriBlue: Every program I applied to had the language requirement.
John Armstrong: In undergrad I was taught that monomorphism and epimorphism were synonyms for injective and surjective respectively. I now know this isn’t true. On the other hand, it was true in every case I discussed in undergrad.
I find it an interesting example of the way the mind works that no one has said anything about it being hard to recall what bijective means. It can hardly be that the term is more immediately transparent. (Bi means two. What has that to do with anything=?)