For sets $A$ and $B$, let $f: A’ \rightarrow B’, A’ \subseteq A$ and $B’ \subseteq B,$ be called a partial function. Show that the set of all partial functions from $A$ to $B$ is a set. Use only the power set axiom, axiom of replacement, and union.

Note that this is from Tao’s Analysis text and Cartesian products have not yet been defined.

This question has been asked before here but the answers do not follow Tao’s definition of function equality. Namely two functions must have the same ranges to be considered equal (ie if $Y$ and $Y’$ are the ranges of two functions $f, g$, respectively, the functions cannot be equal even if their inverse images are equal).

  • $\begingroup$ (1) What do you mean incorrect solutions were given? Where? If you can provide links that'd be great. (2) If you want to get an answer where a specific definition for "function" is used (e.g., one where the codomain is part of the definition), then you should include that explicitly and not hope that people will guess that you want that kind of answer. $\endgroup$ – Asaf Karagila May 3 '19 at 14:43
  • $\begingroup$ Thanks I’ve edited the question. $\endgroup$ – rorty May 3 '19 at 14:47
  • $\begingroup$ Calling the answers given in that link "incorrect" is a step too far. They are unsuitable for your context, but they are not incorrect. $\endgroup$ – Asaf Karagila May 3 '19 at 14:47
  • $\begingroup$ Also, it might be worth noting that Tao's Power Set Axiom is not the standard power set axiom in set theory. Rather it states that $X^Y$ exists for any two sets $X$ and $Y$. $\endgroup$ – Asaf Karagila May 3 '19 at 14:48
  • $\begingroup$ Ah ok. Thanks I’ve edited it again. $\endgroup$ – rorty May 3 '19 at 14:50

Tao proves that if $A$ is a set, then $\{X\mid X\subseteq A\}$ is also a set.

For every fixed $Y\subseteq B$, consider the function $F(X)=Y^X$, and by Replacement, the set $\{Y^X\mid X\subseteq A\}$ exists. For each $Y\subseteq B$.

Next, define the function $G(Y)=\{Y^X\mid X\subseteq A\}$, and again by Replacement the set $\{G(Y)\mid Y\subseteq B\}$ exists.

Finally, apply the Union axiom (two times).

  • $\begingroup$ For your definition of $F(X)$, do you mean to write $Y^X$? Also for $G(Y)$ do you mean to write $X \subseteq A$? $\endgroup$ – rorty May 3 '19 at 15:59
  • $\begingroup$ I fixed the typos. Thanks! $\endgroup$ – Asaf Karagila May 3 '19 at 16:27

I'm assuming you have already read the other answer to this question, and are currently stuck on why it suffices to show the existence of the set $$\{Y^S: S \in \mathcal{P}(X)\}.$$

If we wanted to be picky and state that two partial functions are not considered to be equal if their codomains are unequal (as Tao does), we could instead revise the proof given in the link above to work for every fixed subset $Y' \subset Y$. In particular, we show the existence of the set $$\{{Y'}^S: S \in \mathcal{P}(X)\}$$ for each $Y' \subset Y$. Then it follows from the axiom of replacement on $\mathcal{P}(Y)$ that $$\{\{T^S: S \in \mathcal{P}(X)\}: T \in \mathcal{P}(Y)\}$$ is a set (by taking $P(x, y) = \text{$x \in \mathcal{P}(Y)$ and $y = \{x^S: S \in \mathcal{P}(X)\}$}$). Note that the set above is a set of sets; in particular, if we apply the axiom of union $$\bigcup \{\{T^S: S \in \mathcal{P}(X)\}: T \in \mathcal{P}(Y)\},$$ we see that the resulting set is what we wanted; the set of all partial functions from $X$ to $Y$.


Emory's answer is almost correct, you actually need to use the axiom of union two times. Here is a very small example explaining how to correct Emory's answer.

Let's take $X=Y=\emptyset$. We have $2^X=2^Y=\{\emptyset\}$ and $\emptyset^\emptyset=\{f\}$ where $f$ is the empty function from $\emptyset$ to $\emptyset$ (see example 3.3.9 from Tao's book). Hence $\{\emptyset^S:S\in 2^X\}=\{\emptyset^\emptyset\}=\{\{f\}\}$ and it follows that $\{\{T^S:S\in 2^X\}:T\in 2^Y\}=\{\{\emptyset^S:S\in 2^X\}\}=\{\{\{f\}\}\}$.

Hence $\bigcup\,\{\{T^S:S\in 2^X\}:T\in 2^Y\}=\{\{f\}\}$, you can see that you actually get a set of sets of functions instead of a set of functions. A possible correction would be $\bigcup\bigcup\,\{\{T^S:S\in 2^X\}:T\in 2^Y\}$. Another equivalent solution is $\bigcup\,\{\bigcup\,\{T^S:S\in 2^X\}:T\in 2^Y\}$.

  • 1
    $\begingroup$ You claim that my answer is somehow incorrect. Can you point out exactly where you need to apply Union for a second time? $\endgroup$ – Asaf Karagila Nov 15 '19 at 20:36
  • $\begingroup$ At the end of your answer you say that you need to use the axiom of union but you don't not say how many times you need to apply the axiom (the reader must find it), you must use this axiom two times to have a set of functions and not a set of sets of functions (see my example in the post above). But you are right your answer just state that you need to use it (not how many times) so your answer is technically correct. I will edit my post to point out that only Emory's answer is almost correct. $\endgroup$ – Voidy Nov 15 '19 at 21:17

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.