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

[Mikael Vejdemo-Johansson]

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

On Jun 28, 2009, at 4:28 PM, d p chang wrote:
> Mikael Vejdemo-Johansson <mik at stanford.edu> writes:
>> Quantifiers don't commute.
>
> ah. i never really thought of it that way before (i sort of thought of
> it as 'scope' where it probably doesn't make sense either).
>

Scope makes perfect sense. The difference between the forms is:

Forall y {
   Exists x {
     f(x) = y
   }
}

as compared to

Exists x {
   Forall y {
     f(x) = y
   }
}

In one case, you state that every element in y is in the image of f.

In the other you state that there is some x such that each y is given  
as f(x).

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






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

iEYEARECAAYFAkpHnycACgkQtUmpDMB8zM3vNwCfVPAiK/Gxk8dMELg1ikj3SDvm
ixgAnRd+i/IBqKePFV4GbkWZ2AsZjGCh
=LYar
-----END PGP SIGNATURE-----