[formal-methods] Fwd: Conceptual Mathematics, I.1.6

[Jason Dusek]

  Forwarding the worked solution to the list.

--
Jason Dusek




---------- Forwarded message ----------
From: Jason Dusek <jason.dusek at gmail.com>
Date: 2009/6/13
Subject: Re: [formal-methods] Conceptual Mathematics, I.1.6
To: Josh Myer <josh at joshisanerd.com>


 This problem takes place in the category of sets. We would
 like to know, how many functions are there `f : A → A` such
 that `f ∘ f = f`?

 For some set `A`, we have the set of all subsets of `A`,
 denoted by `℘(A)`. Naturally, the powerset of `A` includes `∅`
 and `A`.

   For each set `X ∈ ℘(A)`, we have a unique set of functions
   `Fₓ`, all of them `A → A`, that take all the elements of `X`
   to themselves and the other elements of `A` to some elements
   of `X`. These functions satisfy `f ∘ f = f`. Naturally, the
   number of functions `f ∘ f = f` in `A → A` is going to be
   the sum of the cardinality of these sets `Fₓ`.

     What is the cardinality of each such set of functions? It
     boils down to: "How many different ways are there to take
     the elements of `A` not in `X` to elements of `X`?"

       For every element in `A` not in `X`, we can map it into
       `X` in `|X|` ways. There are thus `|X| ^ |A\X|`
       functions in `Fₓ`. For `∅`, we have 0 such functions;
       for `A`, we have just one such function (`|A|^0 = 1`).

 So the cardinality of `Fₓ` depends solely on the cardinality
 of `|X|` and `|A|`. For each cardinality `c ∈ {0..|A|}` we
 have `|A| choose c` sets of that cardinality; thus the sum of
 the `|Fₓ|` are:

   sum with `c` ranging from 0 to `|A|` of:

     (|A| choose c) * (c ^ (|A| - c))

 I need to browse my identities and revisit this later.

--
Jason Dusek

⊂ ∈ ∉ ℘ ∘ →