3
$\begingroup$

Suppose $X$, $Y$, and $Z$ are finite sets. If we have a function $$f : X \longrightarrow Y$$ and another $$g : Y \longrightarrow Z$$ then the composite function $g \circ f$ has the property that $$ |\mbox{Im} \, g \circ f | \leq |Y|. $$

If we replace $f$ by a formal linear combination of functions $X \longrightarrow Y$, and $g$ by a formal linear combination of functions $Y \longrightarrow Z$, then we may "compose" these formal combinations (enforcing the distributive law) to obtain a linear combination of functions $X \longrightarrow Z$, none of which have image exceeding $|Y|$ in cardinality.

My question is the converse: can any such linear combination be obtained?

  • 0
    Don't you mean $|\mbox{Im} \, (g \circ f) | \leq |Y|$?2012-01-09
  • 0
    @AlexBecker Yes, of course!2012-01-09
  • 0
    What coefficients do these formal linear combinations have? Is it just $\mathbb{Z}$ or something else?2012-01-09
  • 0
    @Ted I was thinking of coefficients from a field of characteristic zero, although any other ring would also be interesting.2012-01-09
  • 0
    If $p$ and $q$ are functions from $X$ to $Y$, then a formal linear combination $ap+bq$ is defined by $(ap+bq)(x)=ap(x)+bq(x)$, which means $Y$ has to be closed under linear combinations, which, if coefficients come from a field of characteristic zero, means $Y$ is infinite (or trivial). So I don't see how the problem makes any sense.2012-01-18
  • 0
    @Gerry: The linear combinations aren’t functions to $Y$ or $Z$, but to the set of formal $R$-linear combinations of elements of $Y$ or $Z$ (for some coefficient ring $R$).2012-01-18
  • 0
    @Brian, thanks. Time for us to start working on a solution, then.2012-01-18

0 Answers 0