Talk:Injective function

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Foundations, logic, and set theory

Sorry, are the number of injective functions from X to Y (m in X, n in Y) n^m? I thought that was functions in general. What about (n!/((n-m)!)) ?

Physicproducer (talk) 00:26, 21 November 2012 (UTC)

I don't like the title 'injections are invertible'. To me invertible means to have an inverse, (what the paragraph I am critisising calls a 'full inverse').

I would prefer something like 'injections have left inverses' or maybe 'injections are left-invertible'. Then the section on bijections could have 'bijections are invertible', and the section on surjections could have 'surjections have right inverses'.

I don't like that the main heading of this article is "Injective function" and not "One-to-one function". I am not a PHD or anything, but it seems to me that one-to-one function is the term that is used within highschool and college mathematics, not "Injective function". Psyadam 20:23, 29 March 2007 (UTC)Adam Henderson, March 29, 2007

Perhaps in high-school, but the formal term injection is quite regular in even introductory college courses. --Jeff Wheeler (talk) 22:41, 15 December 2010 (UTC)

I added the paragraph in the first screen with the ugly notice in parenthesis, in hopes that someone of greater mathematical expertise will soon happen upon it and fix/remove the notice and accompanying text, while providing some explanation in the article that clarifies a possible misunderstanding that readers (especially new to the subject) might have in understanding an injection.

I'm attempting to address the following question a student reader might have:

"What if a function is defined as:
F(x) : A -> B
where A = {1} and B = {a,b,c,d}
and the function F is defined as:
1 -> a
1 -> b
1 -> c
1 -> d

Then isn't this 'function' F an injection according to the mathematical rule invoked to determine the property of injection?"

The problem here (as I understand it) is that a mathematical function cannot be designated as having multiple outputs, unless they are specified as an ordered set. So in the example given,
1 -> (a,b,c,d)
would be the appropriate way to define the desired function, with F(x) : A -> BxBxBxB serving as the function's context (or perhaps a better revision, F(x) : A -> {a}x{b}x{c}x{d}).

Austinflorida 20:13, 23 April 2007 (UTC)

Yep. They don't even have to be ordered or numbered, you can have a variable amount of outputs in the form of an unordered set (set operators like "union" works like this). Of course, they will then map the parameter to the set of sets, so the argument is the same.

Being a comp sci kiddie, I don't have the hubris to change it, but it looks right to me. Maybe except for the counter-intuitive bit :P 11:52, 29 April 2007 (UTC)

I removed the paragraph on the first screen with the ugly notice in parentheses. Although correct, it badly disrupted the flow of the article, and the issue of whether a function can have multiple outputs is already answered on the first page of the article function, which is conspicuously liked to in this article. Besides, if a student conceives of a multivalued "function" such as the one described by Austinflorida as being injective, they will be absolutely correct, so there's no real danger of confusion here. If it's still an issue, a link to the article Multivalued function would probably be more appropriate than an exposition on the page such as the one provided here. 10:53, 30 April 2007 (UTC)

All examples given by functions were bijective, so I replaced exp's codomain R+ by R. I hope that's okay. Tendays 11:20, 28 October 2007 (UTC)

Inverses and intuitionism[edit]

Hello, User:Chinju has added a statement about absence of inverses for injectives in intuitionistic systems. By {0,1}, do you mean the open interval (0,1)? Also, do you have a handy reference for this? Thanks Sam Staton (talk) 07:47, 23 May 2008 (UTC)

I don't have a reference, but constructivist analysis might be a better link than intuitionistic logic. I think Chinju meant the two-point set {0,1}, though what's written applies equally well to (0,1). Algebraist 13:52, 26 May 2008 (UTC)
Thanks (I had misread the sentence). I understand this has to do with indecomposability, as now linked; correct me if I'm wrong. Sam Staton (talk) 15:52, 27 May 2008 (UTC)

I don't know that this is such an important point to include here; intuitionism is an extreme minority view within mathematics, and we don't want to discuss it in every mathematics article as if it is a common viewpoint. That is: the mathematics community has soundly rejected intuitionism over the last 50 years, so we don't want to give a biased picture of contemporary mathematics by discussion intuitionism at every possible point. It is difficult to find a mathematics text that mentions intuitionism at all, apart from texts specifically about it and texts in proof theory. I don't think any generic undergraduate analysis text that covers inverse functions even mentions intuitionism.

Finding the right balance (how often to mention these minority views) is somewhat difficult. I will try to pare down what is here without completely removing it; the article on intuitionism can discuss these things in more detail. I think this article is likely of interest to particularly young readers, so giving everything due weight is important. — Carl (CBM · talk) 16:49, 27 May 2008 (UTC)

Hi Carl, I agree that it is important to get the right balance, and that it's tricky. I think your footnote is appropriate. But I re-added the text "in conventional mathematics" as an aside, in brackets. I don't think this adds undue weight to constructivism.
It might be inappropriate to mention constructivism in every wikipedia article, but this article is a topic in discrete mathematics and set theory, and I think it is appropriate to mention at this stage that the foundations might be questioned. For instance, when teaching, I often find that students find non-constructive principles harder to understand, and it is sometimes nice to tell the keen ones that these principles are debatable. I don't think it's fair to say that "the mathematics community has soundly rejected intuitionism over the last 50 years", since various related topics are still active research areas. Note also that many computer scientists do accept constructivism, and that injective functions and discrete maths are also a part of every undergraduate computer science course (though explicit constructivism admittedly isn't). Sam Staton (talk) 10:14, 29 May 2008 (UTC)
My research is in proof theory and computability theory, so I have spent some time learning and working with intuitionistic systems. While it is true that there is active research in constructive mathematics within mathematical logic, that's not because the principles of ordinary mathematics are being debated. The main contemporary motivations for studying intuitionistic systems are (1) they are interesting on their own, and (2) properties of intuitionistic systems can be used to obtain results about classical systems.
Outside of mathematical logic, it appears to me that the community of constructive mathematicians is on the same scale as the community of ultrafinitists, and both are very small minorities within the broader mathematics community. This is reflected in the complete lack of coverage of either intuitionism or finitism in standard undergraduate mathematics texts. I don't know the CS community well enough to know how many of them might espouse some sort of constructivism or finitism, but I haven't seen those philosophies discussed in the few computer science texts I have seen.
We would do a disservice to readers (especially students) if we gave them the impression that there is some sort of active debate within the mathematics or mathematical logic community about the validity of classical mathematics. So I don't think the "in conventional mathematics" disclaimer should be included here. The entire article (apart from the footnote) is about conventional mathematics, as are virtually all other math articles on WP. I think the footnote is reasonable, though, as a pointer for those who want to learn more. — Carl (CBM · talk) 10:51, 29 May 2008 (UTC)

Hi Carl. I agree it would be wrong if readers got the idea that there was some kind of large guerrilla group trying to rise up against conventional mathematics. (Though there is some active debate about the validity of classical mathematics, I admit it is not within the general mathematics community.)
I'd like to add a third item to your list, though: (3) constructive proofs are often more informative than non-constructive ones. I've just been in our library here, and all the "discrete maths" textbooks I looked in discuss constructivism (Rosen, Ross & Wright, Huth & Ryan, not to mention Paulson, Forster, Taylor). So I think it is quite normal to let students know about this. All the books go further, suggesting that it is best to write constructive proofs where possible. I think that many students are thus aware that there is something better about constructive proofs, and I think those people will be interested to know when something as basic as inverting an injection is non-constructive.
I'm not sure whether the footnote alone is enough. My concern is that footnotes are usually used to clarify unclear sentences, whereas the sentence, without the "(in conventional mathematics)", is not unclear. Sam Staton (talk) 18:09, 29 May 2008 (UTC)
Are you convinced those textbooks are actually discussing mathematical constructivism (e.g. intuitionism) and not just a vague sense that some classical proofs are "constructive" and others aren't? — Carl (CBM · talk) 17:10, 9 June 2008 (UTC)

Sorry to show up so late to this discussion; in response to the first (already answered) question, yes, I had been talking about the two point set, and indecomposability is exactly the right thing to link to. As for the more ongoing debate, I agree with Carl's concern about the infeasibility of discussing constructive logic (or other well-known but "non-standard" systems of math/logic) differences in every mathematics article, but in this particular case, it struck me as a reasonable thing to point out, not because I want to (falsely) suggest that there is some very large controversy over the use of classical systems, but simply to present interesting and illustrative illumination of the concept under discussion (injective functions) as viewed from other, not necessarily competing, perspectives. I had actually been a bit uncomfortable myself with giving my own parenthetical injection of intuitionistic logic so much prominence but couldn't figure out how to present it better; however, I think the current solution, with the parenthetical qualifier of "conventional mathematics" and then the footnote explaining the constructive difference, is pretty good. -Chinju (talk) 20:20, 3 June 2008 (UTC)

Though I don't know if it's fair to say that "This principle may fail in constructive mathematics, where the concepts of function and set are treated differently than in mainstream mathematics." In a sense they are treated differently, sure, but not generally due to any direct difference of definition, but only because of the inevitable effects of differences elsewhere in the system. That is, in such systems as I have in mind, a set remains a collection of elements and a function remains a mapping between such sets (as given by a binary relation satisfying the appropriate properties of "totality" and "single-valuedness"). At this level, the concepts are treated no differently. The only problem is that some binary relations which could classically be proved to be "total", in the relevant sense, could no longer could be proved "total" constructively; but that's hardly a difference in the concepts of set and function, merely a difference in the strength of the logic (to prove certain things to actually be total functions). -Chinju (talk) 20:34, 3 June 2008 (UTC)
I agree, and I've simplified the footnote. Sam (talk) 15:39, 9 June 2008 (UTC)
I don't agree. The counterexample given in the footnote is extremely subtle, as it permits the inclusion "function" f from the "set" {0,1} into the real numbers, but denies the existence of the same "function" when {0,1} is viewed as a subset of the reals rather than as an independent set. From a classical viewpoint, this inclusion map f literally is its own inverse (f and f-1 are the same set {{0,{0}},{1,{1}}}), so only a difference in the definitions of "set" and "function" could permit the "function" f to exist without the inverse of f existing simultaneously.
You may have intended to mean that the domain of f was the set of natural numbers {0,1}. In that case, the above argument doesn't hold, but a stronger one still does: a set, classically, is the collection of elements that satisfy a given property. The property "is either the image of 0 or the image of 1 under the map f" thus defines a set. In order to claim that the inverse of f doesn't exist, you would either have to claim its domain isn't a set (thus departing from the classical definition of sets) or that despite its domain existing, the function itself doesn't exist (departing from the classical definition of function, as even constructively it is possible to distinguish the real number 0 from the real number 1, as they are separated at nonzero distance). This is another facet of the subtlety of the issue.
My motivation in adding that explanatory text in the first place was to include some vague explanation, for a reader grounded only in classical math, telling why the classical principle in question may fail. I didn't want to get into so much detail in the footnote, though. Can you reword it to add some explanation? — Carl (CBM · talk) 17:10, 9 June 2008 (UTC)
Hi Carl, I'm having trouble with your comment. I don't think that the function f-1 that you mention is total. (Sure, it is constructively true that every injection has a partial inverse.) Sam (talk) 17:24, 9 June 2008 (UTC)
I see. I am so used to thinking about functions without an explicitly given codomain that I missed the terminology here that the left inverse needs to be total on the original codomain. Of course that's impossible constructively, like the example shows. My last comment was under the impression that the footnote made a stronger claim.
I went back to see what was confusing me, and I'm going to change the wording slightly to prevent this happening to anyone else, by being more explicit that the left inverse is meant to be a retraction. — Carl (CBM · talk) 18:35, 9 June 2008 (UTC)

I've never heard the phrase "information-preserving function", and a Google search confirms that the phrase is extremely rare. The claim that injective functions are sometimes called information-preserving may be technically true, but it is very misleading. Listing the phrase before "one-to-one function" (a very common phrase) is simply absurd. (talk) 16:58, 31 January 2009 (UTC)

I agree. I've removed the phrase from the intro now. (talk) 21:52, 2 February 2009 (UTC)


How frequent is the notation f: XY ? I'm a professional mathematician and I never encountered it. On the other hand I've sometimes seen . (talk) 16:07, 12 March 2012 (UTC)

I think an edit is required, opinions?[edit]

The 3rd paragraph has real problems, I think. I'm not a mathematician, or even skilled in the art but please consider the following. "A function f that is not injective is sometimes called many-to-one. However, this terminology is also sometimes used to mean "single-valued", i.e., each argument is mapped to at most one value; this is the case for any function, but is used to stress the opposition with multi-valued functions." (as of Nov 1, 2013) 1. I find "this terminology" confusing, in the second sentence. The entire first sentence is jargon laden so which "terminology" is being specified? I do know what the sentence means, but believe it WILL confuse many others...Why not say something like: "However "many-to-one" is sometimes used to mean "all-to-one", i.e. all arguments are mapped to the same single value." I also suggest removal of the "at most", since, in my ignorance, I don't believe you map can an argument to null, so it is NOT "at most one", it is "exactly one". I am not confident enough in my knowledge here to make the change. Someone help, please? 2. The second part is really terrible and must be fixed. It seems to have been written by a non-English speaker (non-native?). Opposition???? This is awful. First: WHAT is used to stress the opposition? Second "stress the opposition" is virtually incomprehensible and terrible usage (did author mean "stress the contrast" or simply "contrast x with"? (I am not clear what is supposedly "used" here). Third use of the phrase "multivalued functions" is really going to confuse anyone that knows that functions are NOT multivalued. (see Multivalued_function). It seems this clause is saying that even though it isn't saying anything, it is used anyway. I am removing the clause, perhaps someone can fix what was being communicated and add another sentence here about contrast with multivalued functions (which are not functions). Thanks.Abitslow (talk) 23:33, 1 November 2013 (UTC)