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

[Mikael Vejdemo-Johansson]

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

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

On Jun 26, 2009, at 4:55 PM, Crutcher Dunnavant wrote:
> Hmm.
>
> The book doesn't establish any property of injective or surjective  
> which make them defined only on sets.
>


Definition
f:S -> T is injective iff f(x) = f(y) => x = y for all _ELEMENTS_ x, y  
of S.

Do note that having _ELEMENTS_ is among the defining characteristics  
for sets. Having an operation meaning, roughly, "x is an element of S"  
fulfilling valid axioms inspired by the usual element-operation from  
set theory is how you arrive at axiomatizations of set theory.

OTOH, being defined on _SETS_ means that the property is automatically  
defined on Sets-with-structure, and hence on a very large portion of  
mathematical structures. But, for instance, injectivity is kinda weird  
if you try and use it in a partially ordered set (as opposed to  
between partially ordered sets). And this is the reason why  
monomorphisms appear.

> On Fri, Jun 26, 2009 at 7:20 AM, d p chang <pchang at macrovision.com>  
> wrote:
> Jason Dusek <jason.dusek at gmail.com> writes:
>
> >   The notion of injection and surjection apply specifically to sets
>
> this does include 'infinite' sets? i'm only doing the reading along  
> from
> home, but at one point it was talking about sets in finite terms and i
> always thought of things like Z (sorry, can't find teh fancy curly
> glyph) being 'the set of integers'.
>

The definitions certainly make sense for infinite sets as well. 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. For finite sets, the existence of an injection is enough to  
establish an ordering relation for cardinalities - but this map gives  
us an isomorphic (and therefore equally large) copy of Z embedded  
strictly inside (and therefore smaller than) Z.

> \p
> ---
> Satire Should, Like a Polished Razor Keen, Wound With a Touch That's
> Scarcely Felt or Seen. - Lady Mary Wortley Montague
>
>
>
> -- 
> Crutcher Dunnavant <crutcher at gmail.com>
> _______________________________________________
> formal-methods mailing list
> formal-methods at lists.noisebridge.net
> https://www.noisebridge.net/mailman/listinfo/formal-methods

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

iEYEARECAAYFAkpE9ssACgkQtUmpDMB8zM3IuACaA8wRGBd+2djVybu83L81qt5M
6VUAn3ME4YI8y5Su64tAJqEypqEqWsjW
=XSUZ
- -----END PGP SIGNATURE-----
Mikael Vejdemo-Johansson, Dr.rer.nat
Postdoctoral researcher
mik at math.stanford.edu

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

iEYEARECAAYFAkpE9z8ACgkQtUmpDMB8zM3pmQCfdvhA+BPCLsYTcqaAOXj0mjpZ
t2oAniH63I7AyOXK/i2XIBm3yTEF67vJ
=yR37
-----END PGP SIGNATURE-----