View source for Talk:Bijection, injection and surjection

{{WikiProject banner shell|class=B|vital=yes|1=
{{WikiProject Mathematics|priority=High}}
}}
{{User:MiszaBot/config
| algo = old(365d)
| archive  = Talk:Bijection, injection and surjection/Archive %(counter)d
| counter  = 1
| maxarchivesize  = 150K
| archiveheader  = {{Automatic archive navigator}}
| minthreadstoarchive = 1
| minthreadsleft = 10
}}
{{Archive box |search=yes |bot=Lowercase sigmabot III |age=12 |units=months |auto=yes }}

== Easy way to remember which is which ==
Maybe I'm just unfortunate in this regard, but everytime I read a paper that refers to a function being injective or surjective, I have to look up which is which.  Does anyone have a mnemonic or some way to remember what each of these refer to?  Even some explanation as to the origin of the names might be helpful. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/192.160.6.253|192.160.6.253]] ([[User talk:192.160.6.253#top|talk]]) 15:23, 11 July 2005 (UTC)</small>

:-1nject1ve=(1 to 1)

:This is how I have memorised these words: if a function f:X->Y is injective, then the image of the domain X is a subset ''in'' the codomain Y but not necessarily equal to the whole codomain (or, more precisely, a function f:X->Y is injective iff the function f defines a bijection between the set X and a subset in Y); as the word "sur" means "on" in French, "surjective" means that the domain X is mapped ''onto'' the codomain Y, i.e. the whole codomain is covered by the image of the domain. As the prefix "bi" means "two", "bijective" means a function that has ''both'' properties: is both injective and surjective. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/81.20.159.197|81.20.159.197]] ([[User talk:81.20.159.197#top|talk]]) 18:07, 1 January 2007 (UTC)</small>

{{Outdent}}
Yeah I have the same problem, here is what I came up with! :D

"SURjective" = "surrounded", so:
<pre style="font-family:monospace">
          f(x3)
            |
            v
f(x1)  -->  Y  <-- f(x2)
            ^
            |
          f(x4)
</pre>

And "INJECTIVE" = "Injection", so:
<pre style="font-family:monospace">
         Y1
         Y2
 f(x) -> Y3
         Y4
         Y5
         Y6
</pre>
Hope this will help at least one person :) [[User_talk:Bluedeck#c5a2b9ac|<span style="font-family:Constantia,Centaur;font-size:smaller;white-space:nowrap;border-radius:99em;padding:0 4em;box-shadow:2px 2px 11px #ace;background:#39f;color:#fff" lang="en">Bluedeck</span>]] 05:18, 27 January 2018 (UTC)

==Simple question==
It would seem to me that the choice of codomain is arbitrary, and for a function on any domain, there is exactly one codomain (which may or
may not be computable) for which the function is surjective, right? To use computer terms, the domain and codomain for which the function is 
surjective are the sets of keys and values in the key/value pairs that make up the mapping? So any codomain for which the function is not
surjective is a less-precise superset of the codomain for which it is surjective. So why have any codomain that as described above would seem
to not uniquely identify a function. Instead I would think of a surjective codomain (and less-precise supersets if the precision is to hard to
deal with). Giving a function an imprecise non-surjective codomain doesn't seem to help or identify the function.  <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/198.60.22.24|198.60.22.24]] ([[User talk:198.60.22.24|talk]]) 14:14, 31 August 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

:You're correct that the image can be declared to be the codomain (target), but there are several important reasons this is not commonly done in mathematics.

:It is very common to define functions where the domain is also the target (codomain), or where the domain is a tuple of the target.  It is frequently the case that the easiest way to specify the image of a function is by giving the function itself, while in contrast, the target is often very easy to describe.  We usually choose the target to be the smallest group or set (ordinals, natural numbers, integers, rationals, reals, nonnegative reals, complex numbers, etc.) that contains the entire image ''and'' also whatever items the function is intended to "get at", in a semantic sense.

:For example, consider '''f(x) = x * 12 + 1''' from natural numbers to natural numbers, or '''f(a, b) = |a|<sup>b</sup> + &pi;''' from real number pairs to real numbers.  The image of the former does not include numbers like '''0''' or '''3''', and the image of the latter does not include numbers less than or equal to '''&pi;'''.  These are artefacts of the functions themselves, not of what "type" of numbers the functions return.

:Additionally, there are many functions for which we either cannot prove, or have not yet proven, what the image includes!  For example: '''f(x) = x<sup>1/2</sup>log(x)/8&pi; - |&pi;(x)-Li(x)|''' defined from naturals to reals has an image of only positive reals, if and only if the celebrated [[Riemann Hypothesis]] is true.  But being able to tell you that this function returns only real numbers is useful information, whether or not we yet know which exact values it can return.  :)  [[User:TricksterWolf|TricksterWolf]] ([[User talk:TricksterWolf|talk]]) 21:26, 25 August 2011 (UTC)

== SVG ==
I have replaced all the images with available SVG equivalents. [[User:Superm401|Superm401]] - [[User_talk:Superm401|Talk]] 22:40, 26 October 2007 (UTC)

== Minor concerns with "Properties" Section ==
I fixed a couple of minor formatting issues in this section, but I have other concerns.

On the first bullet, ''A'' = ''f''<sup>&nbsp;&minus;1</sup>(''f''(''A'')) and ''f''(''f''<sup>&nbsp;&minus;1</sup>(''B'')) = ''B'' seem ill-defined (with the exception of the injection).  This is because f is not invertible if it is not an bijection (though it can be ''reversible'' if it is an injection, which becomes an inversion if you simply restrict the domain of ''f''<sup>&nbsp;&minus;1</sup> to the image of ''f''), but in general ''f''<sup>&nbsp;&minus;1</sup> is not well-defined without additional qualifications.  There's some unconscious type-raising going on here, in other words.

On the second bullet, I'm not familiar with the function descriptions of the format ''H'' : ''A'' &rarr; ''h(A)'' : a &rarr; h(a) (though it certainly looks as though somebody's laughing at me).  Perhaps this should more closely model the description of functional decomposition given in the [[injective function]] article?

Also, depending on how these are described, it may be necessary to mention that certain aspects (such as, the existence of an injection from A to B implies a surjection exists from B to A) are not always true if AC is not assumed.  I don't think the article on injective functions is direct enough in describing this, and I may mod it slightly.  [[User:TricksterWolf|TricksterWolf]] ([[User talk:TricksterWolf|talk]]) 20:51, 25 August 2011 (UTC)

: If ''A'' is a subset of the domain of function ''f'', then ''f''<sup>&nbsp;&minus;1</sup>(''A'') denotes the [[preimage]] of ''A'' under ''f'' (which itself is a (maybe empty) set), so it is well defined. [[User:DerVanda|DerVanda]] ([[User talk:DerVanda|talk]]) 13:48, 17 March 2024 (UTC)

== Lead diagram ==
The diagram in the lead has one variable in italics and the others in regular typeface.  It would nice if someone could fix the one inconsistent image, Bijection.svg. — [[User:Anita5192|Anita5192]] ([[User talk:Anita5192|talk]]) 19:58, 14 April 2016 (UTC)

: Fixed. [[User:George Makepeace|George Makepeace]] ([[User talk:George Makepeace|talk]]) 21:13, 14 April 2016 (UTC)

== Free variables in the definition of Bijection and Surjection ==
The two logical definitions of bijection, & surjection have three free variables. While they are in a common abbreviated form, they could be improved by quantifying the domain and co-domains, since order of substitution matters here.

I suggest an existential quantification at the start, which clarifies the definitions only need to hold for particular domains, rather than all. The talk page actually contains a question from 2011, about whether or not the co-domains are arbitrary. This suggests it's a commonly needed clarification.

[[User:Whole Oats|Whole Oats]] ([[User talk:Whole Oats|talk]]) 00:09, 29 January 2018 (UTC)

== '''R'''<sup>+</sup> ==
How do Wikipedians expect the reader to guess what the crap does it denote? And why don’t simply say {{closed-open|0, +∞}} for algebraic examples and {{open-open|0, +∞}} for logarithm? [[User:Incnis Mrsi|Incnis Mrsi]] ([[User talk:Incnis Mrsi|talk]]) 11:50, 23 December 2018 (UTC)

== large pictures of each function ==
I really thought the large diagrams in the centre of the page was very helpful for visualizing what each function means. If anyone cares I would vote to return the beginning of the page back to how it was instead of keeping the diagrams small and to the side.  <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Koanarec|Koanarec]] ([[User talk:Koanarec#top|talk]] • [[Special:Contributions/Koanarec|contribs]]) 11:51, 9 April 2020 (UTC)</small> <!--Autosigned by SineBot-->

== Concerns about the definition of injection ==

I have concerns about the definition of injection. The wordy definition is not equivalent with the logical definition. Injection is defined as so: 

"The function is injective, or one-to-one, if each element of the codomain is mapped to by at most one element of the domain..."

The logical definition is

<math>\forall x,x'\in X, x\neq x' \implies f(x) \neq f(x')  </math>

Which states that for every element x and x' in codomain X the implication is true.

But the implication is true even when x and x' are equivalent but their images f(x) and f(x') are not. This can be seen from the implications identical disjunction representation <math> \neg (x\neq x') \lor f(x)\neq f(x') </math> which states that a function f is injection when <math> x=x' </math> or <math> f(x)\neq f(x') </math> is true.

This means that the logical definition of injection is saying that in injective mapping some element in codomain is mapped to more than one element in the domain, which contradicts the wordy definition.

I think this is a major issue, and should be resolved.

I suggest that the implication from the logical definition changes to double arrow <math> \iff </math>. This resolves the issue and is in agreement with the wordy definition. So the new definition should be:

<math> \forall x,x'\in X, x\neq x' \iff f(x) \neq f(x') </math>

But because this is about the very core of mathematics, there should be a consensus before changing the definition.

[[User:Otacon.w.|Otacon.w.]] ([[User talk:Otacon.w.|talk]]) 08:33, 19 November 2020 (UTC)
:The case <math>(x=x')\land (f(x)\ne f(x'))</math> cannot occur because of the definition of  a function. So, the "wordy definition" is equivalent with the logical formula, and there is no reason for changing the formulation of the article. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 09:20, 19 November 2020 (UTC)

== Properties ==

I question the validity of this section as written, because, as yet, we have not established that ''f''{{i sup|−1}} exists.—[[User:Anita5192|Anita5192]] ([[User talk:Anita5192|talk]]) 15:20, 17 March 2024 (UTC)

:An inverse function, denoted <math>f^{-1},</math> exists only if <math>f</math> is bijective. But the [[inverse image]] of a subset <math>Y</math> of the codomain is also denoted <math>f^{-1}(Y),</math> and it is defined as <math>f^{-1}(Y)=\{x\mid f(x)\in Y\}.</math> So, the section is valid, but misplaced, since its natural place is undoubtedly in [[Image (mathematics)]]: The second item is about the factorization of a function through its image. The first item is about the relations between images and inverse images. If moved there, it would deserve to be expanded to say that one has a [[Galois correspondence]], since images and preserve inclusions and satisfy <math>f\circ f^{-1}\circ f=f</math> and <math>f^{-1}\circ f\circ f^{-1}=f^{-1}</math> applied to subsets of the domain and the codomain. [[User:D.Lazard|D.Lazard]] ([[User talk:D.Lazard|talk]]) 17:05, 17 March 2024 (UTC)