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

[Mikael Vejdemo-Johansson]

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


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