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

[Mikael Vejdemo-Johansson]

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

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?


> 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-----