Talk:Injective function

Template:Vital article

I don't like the title

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'. — Preceding unsigned comment added by 80.229.247.11 (talk) 06:02, 14 April 2006 (UTC)

---

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

80.203.114.197 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. 70.58.35.214 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

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. 204.77.35.12 (talk) 16:58, 31 January 2009 (UTC)

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

Notation

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

Number of injective functions

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 think an edit is required, opinions?

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)

Relations

Injective relation redirects to this article. A function is a particular type of relation and the injective property is the same for both. Inclusive language could define injective for a relation, then apply the same condition for an injective function. The influence of software pushes mathematics toward relations, though the general theory has had a century and a half to develop. As textbooks such as those by Gunther Schmidt become known, the narrow focus on univalent relations (functions) will be broadened. — Rgdboer (talk) 23:38, 5 September 2018 (UTC)

38 sources for "every injection from a nonempty set has a left inverse without choice"

I didn't except anyone would dispute this point, so to prevent stubbornness or edit-warring, here are 38 sources (17 links) explaining that choice isn't needed for left inverses of nonempty injections, or to choose ONE element from a single set, or even one element from each set in a finite family of nonempty sets, even if those are infinite since it follows from a deduction rule of first-order logic:

1. Math.SE: "That is, there is no need for the Axiom of Choice in order to select an element form finitely many nonempty sets. In particular, you do not need the Axiom of Choice to show that you can choose a real number (a single set)."

2-6. MO: See answers 1-4 + Mummert's comment ("I think your first point is the main one for the question. It's alluding to the "existential elimination" inference rule, which says that from the assumption ∃xA(x), you can assert A(c) for some new constant c. The soundness of the rule is a direct consequence of the way semantics for first-order logic are defined."); 4: "The Axiom of Choice does not allow to "choose" a choice function, it only says that a choice function exists. To show that a choice function for a single nonempty set exists, you do not need to "choose" an element in the set, it is enough to show that at least one element exists (i.e. the set is nonempty). Every element in the set will give a different choice function."

7. Annoying Precision: "On the other hand, every monomorphism in Set (edit: with non-empty domain!) is split with no set-theoretic assumptions"

8. Choice function: "If X is a finite set of nonempty sets, then one can construct a choice function for X by picking one element from each member of X. This requires only finitely many choices, so neither AC or ACω is needed."

9-10. MO: In addition to answer 1, see JDH's comment.

11-16. Math.SE: See answers 1-5 (and many of the comments): 1: "Knowing that S is non-empty, there do exist such x, and so we can declare the symbol x to denote an element of S, and the rest of our argument is then a function of x."; 2: "The ability to give a name to some arbitrary element of a nonempty set is known as "existential instantiation". This is an inference rule of the underlying logic, not part of the theory, and so it is included not only in ZFC, but also in ZF, and in appropriate forms it is also included in PA and every other first-order theory."; 4: "The axiom of choice, as said, allows us to choose from infinitely many sets at once (sometimes even when these sets are finite!). If, however, one only wishes to choose from finitely many sets then this can be done without it. It does not even matter if the sets themselves are finite or not."

17-22. Math.SE: See answers 1-6. 1: "It's a matter of the basic rules of inference allowed in proofs." 3: "the main answer is that making a single choice out of a single bin is a matter of logic. Specialized to this particular situation, if S is a set and you have proven ∃x:x∈S, then logic allows you to introduce a new constant symbol (say, a) along with the corresponding an axiom a∈S."

23. Quora: "The axiom of choice is still required to prove that a choice function exists for an infinite family of finite sets. That a choice function exists for a finite family of sets (of whatever size) can be proven in ZF without the axiom of choice."

24. Math.SE: First answer.

25-28. Math.SE: See answers 1-4.

29. Math.SE: See first answer: "No, you're not. The axiom of choice isn't relevant for making one single choice. The axiom of choice only becomes relevant when you have to make infinitely many choices."

30-32. Math.SE: See first answer + comments of Bananach and Asaf ("Choosing one element from a provably non-empty set has nothing to do with the axiom of choice, and everything to do with the inference rules of your logic.")

33. Math.SE: First answer.

34-35. Math.SE: See answers 1-2. "As you can see, no AC used here, because (morally) you don't need it to pick exactly one element from a set."

36. Quora: "just map it to some fixed, arbitrarily chosen element of A. There seems to be “choice” involved here, but in fact it is trivial: you need to pick just a single element of a single given set."

37. Math.SE: 1st answer: "One direction ... is just true without choice. If there is an injection f:X→Y, then there is always a surjection from Y onto X, … (here we used the fact that X is non-empty)."

38. Axiom of choice, at least three places in the page text: "In many cases, such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of sets is finite", "… the axiom of choice … thus implies that every finite collection of nonempty sets has a choice function. However, that particular case is a theorem of the Zermelo–Fraenkel set theory without the axiom of choice (ZF); it is easily proved by mathematical induction.[6] In the even simpler case of a collection of one set, ... the axiom of choice says that every nonempty set has an element; this holds trivially.", "For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box."

2601:42:0:4C76:7465:467D:C2F9:6CEE (talk) 07:12, 8 September 2018 (UTC)

Making The Article Easy to Read for Non-Mathematicians.

I have a degree in mathematics, so I know what an injection is.

However, the people looking up "injection" on Wikipedia are looking up "injection" because they do not know what an it is.

Currently, the article is only readable to mathematicians.

---

You can tell by using the following rule:

A Wikipedia page on a mathematical object $X$ is readable only to mathematicians if $X$ is defined in terms of $A$ $B$ and $C$ where $A$ $B$ and $C$ are mathematical terms.

If a person does not know what $X$ is, then they probably do not know what $A$ $B$ and $C$ are either.

The only way for a non-mathematician to understand mathematical thing $X$ is to define $X$ using only terms found in everyday English.

---

The follow should not be the opening line of the article. The opening line of article to be readable to both mathematicians and non-mathematicians alike.

An injective function (also known as injection, or one-to-one function) is a function which maps distinct elements of its domain to distinct elements of its codomain

Problem:

• Non-mathematicians do not know what a codomain is
• Non-mathematicians do not know what a domain is

The following is also not accessible to the general public:

every element of the function's codomain is the image of at most one element of its domain

Something like this is more readable to non-mathematicians:

An injective function is a function such that no two inputs have produce the same output.

In everyday English, the word "image" is usually you something you imagine seeing/visualizing in your mind. For example, "The author uses vivid language to create the image of a dragon in the reader's mind" An image can also be a painting, photograph/. Also, "The image of an oncoming car was still burned into her retinas" In English, an "image" is not the output of a function. In mathematics, the "image" of $sin(x)$ is $\{x\in \mathbb {R} \colon -1\leq x\leq +1\}$. In English, the image of $sin(x)$ is what you see with your eyes, which includes information other than the smallest set containing all possible output.

I am hoping that the article on injection can be split into two sections:

1. An Explanation of injections for the uninitiated
2. injections for the people well versed in such things.

Those are NOT the names I would use for the sections. Feel free to suggest some better names for the sections. However, that is how I recommend that the content be sorted.

73.153.60.76 (talk) 04:41, 11 July 2021 (UTC)

The lead contains links to the definitions of function, domain, codomain, and image. This should be enough for mathematicians. It is not realistic to expect nonmathematicians to understand the concept of an injective function without first understanding many simpler, related concepts. If they want to start from scratch, they should read a suitable textbook. Nor is it realistic to define all related terms in an article. Also, the article should not "dummy down" to layman's terms which are not accurate, mathematical terms; for example, functions do not have inputs and outputs; they have arguments and results or values. Similar for the articles for surjective function and bijection.—Anita5192 (talk) 05:39, 11 July 2021 (UTC)

Anita5192, I agree however with the IP that the first sentence was too technical, as it is not useful to introduce domains and codomains here. It is also wrong, as "elements of the domain" suggest that the domain must be a set, which is not the case, as "power set" is an injective function whose domain is not a set, even if the function is restricted to cardinal numbers.

So, I have removed "domain" and "codomain" from the first sentence, and added a very simple formula that may be clearer for many people. I have kept the second sentence, although my opinion is that it does not belong to the lead, and should be moved to the body. Also, the second paragraph does not belong to the lead of such an elementary article.

On the other hand, many fundamental things are lacking in the article, which should be mentioned in the lead. For example the inclusion map of a subset into a set, and the fact that, in many cases, an injection allows identifying its domain and its image. D.Lazard (talk) 09:13, 11 July 2021 (UTC)

Okay. I think this is better, although "function" is still used in the first sentence, and elements of set X are referred to without mentioning the set X. Hopefully the reader will get the concept from the diagrams. I made some slight modifications to the lead and I tried to clean up the surjective function article similarly. We could move all of the technical terms down into the Definition section, but I think that would make the lead more difficult to understand.—Anita5192 (talk) 16:36, 11 July 2021 (UTC)