Tao Analysis I - 3.4.7

Exercise 3.4.7

Let $X, Y$ be sets. Define a partial function from $X$ to $Y$ to be any function $f:X' \to Y'$ whose domain $X'$ is a subset of $X$, and whose codomain $Y'$ is a subset of $Y$. Show that the collection of all partial functions from $X$ to $Y$ is itself a set. (Hint: use Exercise 3.4.6, the power set axiom, the replacement axiom, and the union axiom.)

Strategy

Intuitively the idea is to recognise that a set of all function from a single $X'$ and a single $Y'$ can be formed using the power set axiom. Then we need a way to expand from a single $X'$ to all subsets of $X$, and the same for all subsets of $Y$, in order for us to account for all functions from any subset of $X$ to any subset of $Y$. 

Initially, this may suggest two uses of the union axion, but it turns out the first iteration can be done with the replacement axiom.

Solution

First consider $X$. We know from Exercise 3.4.6 which proves Lemma 3.4.10 that if $X$ is a set, then there exists a set of all subsets of $X$, the power set of $X$. Let's call this $P(X)$, and similarly, $P(Y)$ for the power set of $Y$.

$$P(X) = \{X' : X' \subseteq X\} = \{X'_1, X'_2, X_3', \ldots \}$$

$$P(P) = \{Y' : Y' \subseteq Y\} = \{Y'_1, Y'_2, Y'_3, \ldots \}$$

Now, given an $X' \in P(X)$, and a $Y' \in P(Y)$, the power set axiom tells us there exists a set of all functions from $X' \to Y'$.

$$(Y')^{X'} = \{ f: X' \to Y' \}$$

Let's apply the axiom of replacement to $P(X)$. Consider the following statement $S(X', C)$

$$S(X', C) : C = (Y')^{(X')}$$

The statement is true if C = $(Y')^{(X')}$. There is only one $C$ for a given $X'$, thus the axiom of replacement is applicable, and tells us the following set exists:

$$A = \{ (Y')^{(X_1')}, (Y')^{(X_2')}, (Y')^{(X_3')}, \ldots   \}$$

This $A$ is a set of sets. Each member set consists of all the functions from each $X_i'$ to a fixed $Y'$.

Let's remind ourselves of the Union Axiom 3.12.

Let $A$ be a set, all of whose elements are themselves sets. Then there exists a set $\bigcup A$

whose elements are precisely those objects which are of the elements of the element of $A$, thus for all objects $x$

$$ x \in \bigcup A \iff (x \in S \text{ for some } S \in A) $$

Let's apply the union axiom to our $A=\{ (Y')^{(X'_i)} \}$.

$$ B = \bigcup_{j} A =  \{ (Y'_{j})^{ (X'_i) } \}$$

Here the union is indexed by $j$ over all subsets $Y'_j \subseteq Y$. 

All functions from every $X'$ to a fixed $Y$ are contained in a member set of $A$. Since $B$ is a union of all $(Y'_{j})^{ (X'_i) }$, it contains all functions from every $X' \subseteq X$ to every $Y' subseteq Y$.

Therefore this set $B$ consists of all the partial functions from $X$ to $Y$, and is a set by the axioms that constructed it, as above. $\square$