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

Sun Jun 28 10:04:24 UTC 2009

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.

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

>
>
>  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>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.noisebridge.net/pipermail/formal-methods/attachments/20090628/3ed5b8c3/attachment-0003.html>