[formal-methods] Injective, Surjective, and Bijective functions

Mikael Vejdemo-Johansson mik at stanford.edu
Sun Jun 28 10:55:31 UTC 2009


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Jun 28, 2009, at 11:04 AM, Crutcher Dunnavant wrote:
> On Sun, Jun 28, 2009 at 1:37 AM, Mikael Vejdemo-Johansson <mik at stanford.edu 
> > wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>>> On Jun 28, 2009, at 4:35 AM, Crutcher Dunnavant wrote:
>>> I find un-cited definitions un-compelling evidence.
>>>
>>> I'm perfectly willing to listen to argument, and read proofs. But  
>>> for appeals to authority, I would like citation.
>>>
>>> As to the issue at hand, it seems trivial to say that injection  
>>> abstracts to monomorphism and surjection abstracts to epimorphism.  
>>> Awody's book (Category Theory) makes this claim on page 25. What I  
>>> haven't seen anywhere, and I've looked, is a claim that it is  
>>> incorrect to say that injection and surjection are synonyms for  
>>> their more general concepts.
>>>
>>> Jason suggests that this is merely a cultural or political  
>>> distinction.
>>
>>
>> I cannot recall having ever seen a textbook or article explicitly  
>> state that it is improper to use injection and surjection in the  
>> stead of monomorphism or epimorphism. I simply do not have a  
>> citation for a statement like that. There are simple examples,  
>> however, that indicate its impropriety.
>>
>> I have never ever seen injection and surjection used in a context  
>> that is not dealing with enriched sets (concrete categories). I  
>> could agree to call it a cultural distinction. But as such it is a  
>> very strong cultural distinction.
>>
>> As for appeals to authority - where did you feel I made that? I  
>> could probably dig up a citation or three for the definitions I've  
>> been issuing, but I don't have my full mathematics library around  
>> since I'm traveling all summer, and would have to spend time in the  
>> university library digging up a book that carries it. All the  
>> definitions I have been giving are quite standard - might even be  
>> on Wikipedia.
>>
>>
> I'm learning this material for the first time. This isn't a  
> refresher for me, nor do I have a background in abstract algebra.
>
> I'm not being pedantic, I simply can't accept un-sourced  
> definitions. Its hard enough keeping up with the material I have  
> attribution for, and working my way through.
>
> But I'm going to keep at it, because there are specific things I'd  
> like to apply this material to, and I need the background.
>

I'm sorry for raising my defenses.

What will you accept as decent sources? Is Wikipedia an acceptable  
source for you?
In almost all of mathematics, there is always the option of choosing a  
definition that works for you, and any exposition will define most  
things on its own. That said, there is significant culture building,  
and many conventions most if not all mathematicians adhere to. This  
makes any single source possibly less than adequate to give a good and  
very explicit exposition of what the mathematical culture does about  
any given thing.

All this said, most any textbook on algebra or on set theory will give  
at least as an alternative definition of a function that it is a  
subset of the cartesian product Source x Target adhering to certain  
specific axioms, one of which specifies that any point in source is a  
member of exactly one pair in the function specification. And it will  
subsequently define injectivity and surjectivity with respect to this  
model or an equivalent model.

I can give you an array of suggestions for books I suspect will have  
this exposition, but without access to them personally directly, I  
will not be able to verify that the exposition I expect them to hav  
eis actually in there.

Books that may be worth looking at, though, include:
Lang - Algebra
Bourbaki - Elements of Mathematics I and II
Beachy & Blair - Abstract Algebra (this is the book I learned a lot  
from back in college)
Dummit & Foote - Abstract Algebra

Generic note on unsourced definitions, btw: Wikipedia has a very good  
reputation within mathematics. Most substantial Wikipedia articles on  
mathematical topics tend to be accurate enough that many  
mathematicians I know use Wikipedia as a quick lookup method, a first  
step before launching into a literature search, or a good place to  
recall definitions known and then forgotten. I recommend wikipediaing  
any terms I use and don't cite enough as a first approximation.

>> Actually, checking that, the idea that monomorphisms generalize  
>> injections but that the generalization is strictly larger than the  
>> initial concept, does get discussed on
>> http://en.wikipedia.org/wiki/Monomorphism
>> where among other things, it is stated:
>> It is not true in general, however, that all monomorphisms must be  
>> injective in other categories. For example, in the category Div of  
>> divisible abelian groups and group homomorphisms between them there  
>> are monomorphisms that are not injective: consider the quotient map  
>> q : Q → Q/Z. This is clearly not an injective map;  
>> nevertheless, it is a monomorphism in this category.
>>
>>
>> Also, in Barr&Wells: Category theory for the computing science, it  
>> is given as an example the case of monoids and monoid  
>> homomorphisms, a category in which the inclusion map N -> Z is an  
>> epimorphism. This map, however, is not a surjection, so forms a  
>> counterexample to the corresponding claim - that surjection is an  
>> improper synonym for epimorphism.
>>
>> Is this more compelling, or would you need me to go visit the local  
>> university library?
>
> So yes, these are more compelling arguments.
>
> However, I have an objection I can't really defend (lacking enough  
> category theory, or familiarity with either Div or monoids). You say  
> that these maps are not injective or surjective; but I think one  
> could argue that the definition of sur and injective you are  
> familiar with is best kept within Set; and that these in fact _are_  
> sur and injective examples, in their categories. This would be  
> consistent with other changes, such as "what is an object", or "what  
> does composition mean".
>
> But at this point, I really must concede. I simply don't know enough  
> to continue this discussion.
>

Simply not knowing the underlying mathematics of the examples is an  
unfortunate reason for stopping the discussion. I would hope that you  
might be persuaded to continue talking about the thoughts and doubts  
you have - I will try my best to not become defensive, so as to stay  
useful instead.

Of course you could just decide, for yourself, that you will use  
"surjective" and "injective" instead of "epimorphic" and  
"monomorphic". However, this will clash either with classic usage of  
surjective and injective - by not being appropriate where epi's and  
mono's fail to be surjective and injective functions on the underlying  
sets - such as in the monoidal example (which I am forced to keep  
refering to, even though you feel unfamiliar with it); or by bringing  
inappropriate connotations into new domains.

For this last objection, consider a group - i.e. a set of elements  
with a binary operation, an identity, and inverses for every element  
present.

This can be viewed as a category with only one object and all  
morphisms isomorphisms.
In this category, both left and right cancellation holds for all  
arrows - however, though injectivity and surjectivity makes less sense  
as concepts for these.

Admittedly, it can be argued that if the group is in fact a group of,  
say, linear transformations of vector spaces - then injectivity and  
surjectivity will follow for those linear transformations. Thus, one  
more example:

A monoid is a set with an associative binary operation. Some sources  
give monoids an identity element, some don't. We shall give a monoid  
an identity element here. A good mental model for monoids are "Lists"  
with "concatenation" as the product and "the empty list" as the  
identity.

Now, certainly, any element in a monoid **can be viewed** as a map  
that takes elements to new elements. This is not saying that each  
element in a monoid **is** a function, only that it gives rise to a  
function in a very natural manner; namely the function that right- 
multiplies by that element.

For example, we can use the english alphabet as generators, and then  
get a function f_abc such that f_abc(xyz) = xyzabc, for instance.

This function is not going to be surjective. It might be injective,  
unless the monoid has some extra relations imposed on it.

Let us suppose that we have no extra relations. In that case, the  
function belonging to an element is going to be injective but not  
surjective. However, an element of this kind of a monoid is going to  
be both epi and mono. Without relations, it is indeed the case that if  
the concatenation of l1 with l is equal to the concatenation of l2  
with l, then l1 is going to be equal to l2.

Does all this make sense?

Also, now, note that N is the monoid with a single generator 1, and no  
relations, while Z is the monoid with two generators 1, -1 and the  
relations 1+-1=0 and 1+-1=-1+1. The monoid map taking 1 to 1 is an  
injective map on the set level, and is left cancellable, since any map  
from Z to another monoid is completely determined by the image of 1,  
which thus completely determines any map from N through this map to  
another monoid.

> On Jun 27, 2009, at 4:05 PM, d p chang wrote:
>
> > Mikael Vejdemo-Johansson <mik at stanford.edu> writes:
> >
> >> On Jun 27, 2009, at 12:11 AM, d p chang wrote:
> >>> Mikael Vejdemo-Johansson <mik at stanford.edu> writes:
> >>>> For instance, the map (*2): Z -> Z is injective (prove it!) but  
> not
> >>>> surjective (prove it!), and is an establishing map for why
> >>>> infinities
> >>>> are weird.
> >>>
> >>> i'm not sure i have the 'notation' for reasoning/expressing that  
> the
> >>> infinities are equal, but it seems like one of those questions i
> >>> associate w/ cantor and diagonals.
> >>
> >> Define |S| <= |T| iff there exists an injection S -> T.
> >>
> >> Also, define |S| = |T| iff there exists a bijection S -> T.
> >>
> >> But still, we can fit |Z| elements within |Z| elements and still  
> get
> >> gaps. This cannot happen for the finite case - any strict injection
> >> S -
> >> T (not a bijection) of finite sets is a proof that |S| < |T|, but
> >> it breaks for infinite sets.
> >
> > thanks for that.
> >
> > i'm still thinking about how (*2) over Z is injective. it seems  
> like i
> > have to reason over the function itself.
> >
>
> f is injective iff f(x) = f(y) implies x = y.
>
> Suppose 2n = 2m for n,m in Z. Can we conclude that n=m?
>
> Mikael Vejdemo-Johansson, Dr.rer.nat
> Postdoctoral researcher
> mik at math.stanford.edu
>
>
>
>
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.10 (Darwin)
>
> iEYEARECAAYFAkpGS3sACgkQtUmpDMB8zM0L2wCgkAnVqSgkaINj0unHHCcITxYn
> 4fYAn3bzXhMRtQHVXvaBsNeCc9gSRlBi
> =nSVt
> -----END PGP SIGNATURE-----
> _______________________________________________
> formal-methods mailing list
> formal-methods at lists.noisebridge.net
> https://www.noisebridge.net/mailman/listinfo/formal-methods
>
>
>
> -- 
> Crutcher Dunnavant <crutcher at gmail.com>
>
> Mikael Vejdemo-Johansson, Dr.rer.nat
> Postdoctoral researcher
> mik at math.stanford.edu
>
>
>
>
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v2.0.10 (Darwin)
>
> iEYEARECAAYFAkpHK9wACgkQtUmpDMB8zM0BaQCfexW7pR3p85565UZ8LATE41ot
> oAQAnjHrgZh7tNwSEHhe2J1dFf4BnMV0
> =Tupk
> -----END PGP SIGNATURE-----
>
>
>
> -- 
> Crutcher Dunnavant <crutcher at gmail.com>

Mikael Vejdemo-Johansson, Dr.rer.nat
Postdoctoral researcher
mik at math.stanford.edu






-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (Darwin)

iEYEARECAAYFAkpHTCYACgkQtUmpDMB8zM29VgCgjfxsYK4o9fIvqK+AfaUIOswr
x9gAnjh/RtT5lFCR87tlcuTsaWhMaluP
=95sB
-----END PGP SIGNATURE-----



More information about the formal-methods mailing list