This is an exercise you can find here, but I recall the context:
Let $X, Y$ be sets. Define a partial function from $X$ to $Y$ to be
any function $f: X' \rightarrow Y'$ with $X' \subseteq X$ and $Y'\subseteq Y$.
Show that the collection of all partial functions from
$X$ to $Y$ is itself a set.
Tao's hint is to use the following four results from set theory exposed in his textbook:
- Lemma 3.4.9. Let $X$ be a set. Then there exists a set $\{Y \, : \, Y \text{ is a subset of } X\}$. It is denoted $2^X$.
- Axiom 3.10. Power set axiom: let $X$ and $Y$ be sets. Then there exists a set, denoted $Y^X$, which consists of all the functions from $X$ to $Y$.
- Axiom 3.6. Replacement axiom.
- Axiom 3.11. Union axiom: let $A$ be a set, whose all elements are themselves sets. Then there exists a set $\bigcup A$ whose elements are those objects which are elements of elements of $A$, i.e., $x \in \bigcup A$ iff $x \in S$ for some $S \in A$.
A consequence: if one has some set $I$, and for each element $\alpha \in I$ we have one set $A_\alpha$, then we can form the union set $\bigcup_{\alpha \in I} A_\alpha$ by defining: $\bigcup_{\alpha \in I} A_\alpha := \bigcup \{ A_\alpha \, | \, \alpha \in I\}$.
There are some very complete solutions out there, e.g. here. My sketch of proof is much shorter, thus I think that there are many errors in it. Here it is:
- Let be $X' \subseteq X$ and $Y' \subseteq Y$. If both $X'$ and $Y'$ are fixed, then per the power set axiom (3.10), there exists a set $Y'^{X'}$ which consists of all the functions from $X'$ to $Y'$.
- By lemma 3.4.9, there exist a set $2^X$ which consists of all the subsets of $X$, and a set $2^Y$ which consists of all the subsets of $Y$.
- Now we fix an element $X'$ of $2^X$. Let be $Y'$ an element of the set $2^Y$, $f$ a function, and $P$ the property “$P(Y', f)$: $f$ is a function from $X'$ to $Y'$''. Per the replacement axiom, there exists a set $\{f \, | \, P(Y', f) \text{ is true for some } Y' \in 2^Y\} = \{f \, | \, f: X' \rightarrow Y' \text{ for some } Y' \in 2^Y\}$. This set is related to a fixed subset $X' \subseteq X$, so let's denote this set $S_{X'} = \{f \, | \, f: X' \rightarrow Y' \text{ for some } Y' \in 2^Y\}$.
- Now we apply the union set (3.11), especially in its second formulation. If we denote $I = 2^X$, then for each element $X' \in I$ we do have one set $S_{X'}$, which is defined above. Thus, there exists a set $\bigcup_{X' \in 2^X} S_{X'} := \bigcup \{S_{X'} \, | \, X' \in 2^X\}$. And, for every function $f$, we have $f \in \bigcup \{S_{X'} \, | \, X' \in 2^X\}$ iff there exists $X' \in 2^X$ such that $f \in S_{X'}$, i.e. if there exists $X' \subset X$ and $Y' \subset Y$ such that $f: X' \rightarrow Y'$.
- Consequently, we have proved that there exists a set which consists of the collection of all partial functions from $X$ to $Y$.
What does make this proof incomplete and/or incorrect?
Thanks!
Best Answer
The key observation is that this set is equal to $$\bigcup \{Y'^{X'}: (X', Y') \in 2^X \times 2^Y\}$$ so you can use union axiom if you have shown that $$\{Y'^{X'}: (X',Y')\in 2^X \times 2^Y\}$$ is a set. That this is actually a set follows by replacement applied to the set $2^X \times 2^Y$, in which we use power set axiom and pairing axiom.