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

[Mikael Vejdemo-Johansson]

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

On Jun 28, 2009, at 4:58 AM, d p chang wrote:
> Mikael Vejdemo-Johansson <mik at stanford.edu> writes:
>> 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.
>
> ok.
>
> hmmm... i was thinking that one would have to prove that f(x) was
> defined as well (ie, f was 'closed' over Z). other than falling back  
> on
> 2*x == x+x, i'm not nearly 'math person' enough to think of these  
> things
> myself (understanding someone else's explanation is easier :-)
>

If f is a function from A to B, we assume by definition that f(a) is  
defined for every a in A, and takes on a unique value. There is the  
concept of partial function, but that's a completely different mess to  
get involved in.

>> Suppose 2n = 2m for n,m in Z. Can we conclude that n=m?
>
> yes
>

Your arguments for answering yes here will constitute a proof that  
(2*) is injective.

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






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

iEUEARECAAYFAkpHLJ4ACgkQtUmpDMB8zM2tMgCXRVR+oupvbcdXb4I6/1oh/qFJ
vACbBmIgPQ9M+tfG3fOzrhub35qK4f8=
=poVL
-----END PGP SIGNATURE-----