3
$\begingroup$

This is a follow up to my previous question about existence and uniqueness of piecewise functions. Suppose we are given two functions $f:S \rightarrow T$ and $g:T \rightarrow U$. How does one prove from ZFC set theory that there is a unique function $h:S \rightarrow U$ which is the composition of those two functions?

$\endgroup$
2
$\begingroup$

I'm using the definition $A \to B = \{f \in P(A \times B) | \forall x \in A \exists ! y \in B (x, y) \in f\}$. That is, a function is a set of input-output pairs such that every input corresponds to a unique output.

Define $h = \{(x, y) \in S \times U | \exists z \in T ((x, z) \in f \land (z, y) \in g)\}$. I claim that $h$ forms a function $h : S \to U$.

First, we must prove that $h$ is a set at all. But we know that $h$ is a set because $S \times U$ is a set (by other axioms) and we can pick $h$ out as a subset of $U$ using the axiom schema of separation.

Now, we must prove that $h$ is a function (proving uniqueness). Suppose we have $(x, y) \in h$ and $(x, y') \in h$. Then take $z \in T$ such that $(x, z) \in f$ and $(z, y) \in g$. And take $z' \in T$ such that $(x, z') \in f$ and $(z', y') \in g$. Then since $f$ is a function, $z = z'$. So we see that $(z, y) \in g$ and $(z, y') \in g$. Then since $g$ is a function, we have $y = y'$.

Now, we prove that $h \subseteq S \times U$. Suppose we have $(x, y) \in h$. Then take $z \in T$ such that $(x, z) \in f$ and $(z, y) \in g$. Since $f \subseteq S \times T$, we see that $x \in S$. And since $g \subseteq T \times U$, we see that $y \in U$. Then $(x, y) \in S \times U$.

Finally, we prove existence. Suppose we have $x \in S$. Then take some $z \in T$ such that $(x, z) \in f$. Then take some $y \in U$ such that $(z, y) \in g$. Then $(x, y) \in h$.

Thus, we see that $h : S \to U$.

Note that we do not ever need the axiom schema of replacement, the axiom of foundation, or the axiom of choice in proving this theorem.

$\endgroup$
2
  • $\begingroup$ I don't think you need to prove $h \subseteq S \times U$, or can justify it just by noting its definition is $h = \{(x,y) \in S \times U|...\}$ $\endgroup$
    – aschepler
    May 8 '21 at 19:48
  • $\begingroup$ @aschepler Good point. $\endgroup$ May 8 '21 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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