1
$\begingroup$

Given two finite sets $A$ and $B$, what is the formula to find the number of pairs of mappings $f, g$ such that $g \circ f = 1_A$?

  • 0
    I am just beginning to learn category theory, and am focusing only on finite sets (following the Lawvere and Schanuel text) -- so yes, they are finite.2012-07-22

2 Answers 2

5

We look at the problem when $A$ and $B$ are finite. Suppose that $A$ has $a$ elements, and $B$ has $b$ elements.

A function $f$ has the desired property iff $f$ is injective. Thus we need $a \le b$. For any given $f$, the function $g$ is determined on $f(A)$, but not on the rest of $B$.

There are $b(b-1)(b-2)\cdots (b-a+1)$ injections from $A$ to $B$. For every such injection, the value of $g$ on the complement of $f(A)$ is arbitrary, so there are $a^{b-a}$ choices for $g$. Multiply. The total number of ordered pairs $(f,g)$ with the desired property is $b(b-1)(b-2)\cdots(b-a+1)(a^{b-a}),$ or equivalently $\frac{b!}{(b-a)!}a^{b-a}$.

1

A function $f\colon A\to B$ has a left inverse, $g\colon B\to A$ such that $g\circ f = 1_A$, if and only if $f$ is one-to-one.

Given a one-to-one function $f\colon A\to B$, then the values of a left inverse $g\colon B\to A$ of $f$ on $f(A)$ are uniquely determined; the values on $B-f(A)$ are free.

I'm going to assume first that the sets are finite.

Therefore: the number of ordered pairs $(f,g)\in \{a\colon A\to B\}\times\{b\colon B\to A\}$ such that $g\circ f = 1_A$ is:

  • $0$ if $|A|\gt |B|$ (no injections from $A$ to $B$);
  • if $|A|\leq |B|$, same $|A|=n\leq m=|B|$, then there are $\frac{m!}{(m-n)!}$ ways of mapping $A$ to $B$ in a one-to-one manner; and there are $n^{m-n}$ ways of mapping $B-f(A)$ to $A$ (choose which of the $n$ things in $A$ each of the $m-n$ things in $B-f(A)$ is mapped to). So the number of pairs is $\frac{n^{m-n}m!}{(m-n)!}.$

Though not necessary, I had already written much of what is below, so here goes:

For infinite sets the situation is a bit more complicated, but the analysis is the same. The number of sets of size $|A|$ contained in $|B|$ (necessary for embeddings) is either $|B|$ if $|A|\lt |B|$, or is $2^{|A|}$ when $|A|=|B|$; then you need to count the number of bijections between two sets of cardinality $|A|$. This is $2^{|A|}$ (I believe). Thus, there are $|B|2^{|A|}$ one-to-one functions from $A$ to $B$ when $|A|\leq|B|$. Then you should have $2^{|B|}$ ways to complete "most" of those functions to full left inverses $B\to A$. So I'm going to hazard a guess that the number of pairs would be $0$ if $|A|\gt |B|$, and $|B|2^{|A|}2^{|B|} = 2^{|B|}$ if $|A|\leq |B|$ and $|A|$ is infinite.

I'll leave it for someone who knows more cardinal arithmetic than I (Asaf? Andres?) to correct that if I'm wrong.

Finally, if $A$ is finite and $B$ is infinite, there are $|B|$ possible 1-to-1 function $A\to B$, and then $2^{|B|}$ ways of mapping the complement of the image back to $A$, so that would also give $2^{|B|}$ pairs in this case.

  • 1
    @Ben: Oh, yes; thinking about the infinite case turned me around for some strange reason.2012-07-23