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

[d p chang]

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

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

yes

\p
---
An optimist is someone that has never had much experience
		- Richard Schultz