How many maps from $f: A \to A$ satisfy $f \circ f = f$?

Question

I'm self-study working through a textbook intro to Category Theory. Suppose I have a set $A = \{1,2\}$, and I want to find how many maps $f: A \to A$ satisfy $f \circ f = f$.

I can enumerate the possible mappings $f: A \to A$ as pairs $(a,b)$ where $f(a) = b$:

1. $\{(1, 1), (2, 1)\}$
2. $\{(1, 1), (2, 2)\}$
3. $\{(1, 2), (2, 1)\}$
4. $\{(1, 2), (2, 2)\}$

For each of these four mappings, I can then run $f$ and $f \circ f$ to test if it satisfies $f \circ f = f$:

1. $\{1,2\} \to \{1,1\} \to \{1,1\}$. Works.
2. $\{1,2\} \to \{1,2\} \to \{1,2\}$. Works.
3. $\{1,2\} \to \{2,1\} \to \{1,2\}$. Works because $\{2,1\} = \{1,2\}$, order doesn't matter in sets.
4. $\{1,2\} \to \{2,2\} \to \{2,2\}$. Works.

Is this right? I don't know about my argument for the third mapping. Is it appropriate to say that $f \circ f = f$ because the resultant set is the same? Or do I actually have to map each element individually to the same element in order to claim $f \circ f = f$?

I suppose what I'm confused about is whether for $f \circ f = f$ to hold, I need $f \circ f = f$ for each element in $A$, or just for the overall set $A$.

Answer 1

Let $A$ be a set of cardinal $n$.

A map $f:A\to A$ satisfies $f\circ f = f$ iif $f(f(x)) = f(x)$ for all $x\in A$, so iff $f(y) = y$ for all $y\in f(A)$. Thus, those points are fixed. One can still choose the images of the other points (as long as they are in $f(A)$).

Let's make a partition of all such $f$ by checking the cardinal of their images $f(A)$. This cardinal $k$ lies in $\{1,\ldots,n\}$. We choose $k$ points among $n$, that is $\binom{n}{k}$ choices, for the elements of $f(A)$. If we note them $(y_1,\ldots,y_k)$, let's note $(x_1,\ldots,x_{n-k})$ the remaining points. We must have $f(y_j) = y_j$ for $j\in\{1,\ldots,k\}$, so that is fixed, but we can choose $f(x_j)$ for $j\in\{1,\ldots,n-k\}$. It has to be in $f(A) = \{y_1,\ldots,y_k\}$, which makes for $k^{n-k}$ choices.

Thus, the number of map $f:A\to A$ such that $f\circ f = f$ is $$\sum_{k=1}^n\binom{n}{k} k^{n-k}. $$

Answer 2

For a finite set A with n elements, you can explicitly calculate the number of idempotent maps of A to itself.

Hint. Find a bijection between the set of idempotents and the pairs consisting of a subset T of A and a map from A\T to T.

Hint 2. Define T as the set of fixed points (=image) of an idempotent map.

If you want to know more (values, generating function, connection to other sequences), check out OEIS/A000248.