[formal-methods] [mik at stanford.edu: Re: Conceptual Mathematics, I.1.6]

[Josh Myer]

This one is spoiler-free, but it does contain hints.  If you have a
math degree (or a perverse hobby in algebras).

(Mikael asks all the right leading questions here, it's good stuff.)
--
/jbm

----- Forwarded message from Mikael Vejdemo-Johansson <mik at stanford.edu> -----

From: Mikael Vejdemo-Johansson <mik at stanford.edu>
To: Josh Myer <josh at joshisanerd.com>
Subject: Re: [formal-methods] Conceptual Mathematics, I.1.6
Date: Sun, 14 Jun 2009 00:00:25 +0200

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

On Jun 13, 2009, at 11:51 PM, Josh Myer wrote:
>Conceptual Mathematics: Article I, Session 1, Exercise 6:
>
> How many maps f : A -> A satisfy (f o f) = f?
>
>The answer is, as a first approximation, a metric fucktonne.  I'm
>having a hard time pinning down a better approximation.  Does anyone
>have a closed form in terms of |A| for this?  I'd be happy to talk it
>through in email, but don't want to spoil other people's answering
>processes.  (However, I feel no compunction about bursting folks' "1:
>identity!" bubble.)
>
>I need to bust out my combinatorics text and maybe TAoCP to look for
>the right kind of generating function; I think that's where the answer
>to this lies.  Generating functions always were a little magic...


One keyword you'll want to consider is 'projection'. Another is  
'idempotent', but idempotent endomorphisms tend to be named projections.

Consider what you can say about f knowing f.f=f by arguing about  
elements in its image.

If you've already seen epimorphisms, consider that a morphism in a  
nice category factors as an epimorphism followed by a monomorphism:  
surjection onto its image, and then the inclusion of the image into  
the range.

Also, please forward this to the list if you consider it to be  
valuable info for everyone else.

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






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

iEYEARECAAYFAko0IX0ACgkQtUmpDMB8zM2UsACgg4Q3zCva2/tvpL/0BvWsQDxG
7yUAoIpJniy1I8hncmK9tEO5n9j5mO+5
=KkYp
-----END PGP SIGNATURE-----


----- End forwarded message -----