Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Wait: are you given $f$ and $g$? Then the count is either $0$ or $1$, depending on whether the given $f$ and $g$ satisfy $g\circ f = 1_A$. Or are only the sets given? –  Arturo Magidin Jul 22 '12 at 20:34
    
Only given $A$ and $B$. –  syrion Jul 22 '12 at 20:43
    
Are $A$ and $B$ finite? –  Arturo Magidin Jul 22 '12 at 20:49
    
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. –  syrion Jul 22 '12 at 20:52

2 Answers 2

up vote 5 down vote accepted

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}$.

share|improve this answer

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.

share|improve this answer
    
Your finite case disagrees with the other answer, and I think yours is the wrong one. –  Ben Millwood Jul 23 '12 at 0:21
    
@Ben: Oh, yes; thinking about the infinite case turned me around for some strange reason. –  Arturo Magidin Jul 23 '12 at 0:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.