If $A\preceq B$ and $C \preceq D$ then $C^A \preceq D^B$

Question

I was hoping I could get a little supervision on "prettying-up" this proof. I think the logic is correct, but the presentation is probably cumbersome...and I have a clarification question at the end.

The claim to prove:

If $A\preceq B$ and $C \preceq D$ then $C^A \preceq D^B$

I use the following n0tation:

Let $f$ represent the injective function from $A$ to $B$ $\quad f: A \xrightarrow{1-1}B$

Let $g$ represent the injective function from $C$ to $D$ $\quad g:C \xrightarrow{1-1} D$

$h \in C^A \iff h: A \to C$

---

Construct the following function $\Phi: C^A \to D^B$ with a mapping rule that satisfies the following formula:

For non-empty sets...

$\forall a \in A \Big (g \circ h(a) =\Phi(h)\circ f(a)\Big) \ \land \ \forall x \in B\setminus f[A]\Big(\Phi(h)(x)=d_0\Big)$ where $d_0$ is an element within the range of $g$. (i.e. $d_0 \in g[C]$)

I am uncertain how to turn the above FOL statement into a piecewise function presentation...my best guess is:

$$\Phi(h)(b)=\begin{cases} g\circ h(a),&\text{if }b=f(a)\text{ for some }a\in A\\ d_0,&\text{if } b \in B\setminus f[A] \end{cases}$$

Injectivity: Let $\Phi(h_1) = \Phi(h_2)$. Remembering that $\Phi(h)$ is a function in $D^B$:

$\Phi(h_1) = \Phi(h_2)\rightarrow \forall b \in B [ \Phi (h_1)(b)=\Phi (h_2)(b) ]$

Because of this, note that $f[A] \subseteq B$, which implies that $\forall a \in A [\Phi(h_1)f(a)=\Phi(h_2)f(a)]$

By definition of our function $\Phi$, $\quad g \circ h(a) =\Phi(h)\circ f(a)$. Thus:

$\forall a \in A [\Phi(h_1)f(a)=\Phi(h_2)f(a)] \rightarrow \forall a \in A [g \circ h_1(a)=g \circ h_2(a)]$

$g$ is an injective function and therefore $g(c_1)=g(c_2) \rightarrow c_1=c_2$. We then see that, $\forall a \in A [h_1(a)=h_2(a)]$. But that is the definition of function equality, so $h_1=h_2$ $\square$

---

Extraneous cases: $\color{red}{\text{ this reasoning is incorrect }}$

If $A$ or $B = \emptyset$, then the injective function that satisfies $A \preceq B$ is the empty function (same idea for $C$ or $D$).

W.L.G. suppose $A$ is the empty set. Then $C^A = \emptyset$. Regardless of what $D^B$ equals, there exists an injective function that maps $\emptyset \to D^B$...namely, $\emptyset$. The argument can be similarly repeated for any of the other sets equaling the empty set.

---

Clarification Side Note: I was a little surprised when I didn't require the injectivity of $f$ to demonstrate the injectivity of $\Phi$. After some thinking, I believe the injectivity of $f$ is implicitly required in the statement $\forall a \in A \Big (g \circ h(a) =\Phi(h)\circ f(a)\Big)$ in order for the domain of $\Phi$ to equal $C^A$. If $f$ is not injective, there could, depending on $C$'s cardinality, be functions in $C^A$ that do do not satisfy the relevant criteria to be admitted into $\Phi$.

For this demonstration, suppose $A \prec C$ and the injective function's name is $h_\alpha$. Let $f$ be non-injective. Then $h_\alpha$ cannot be admitted into $\Phi$'s domain because, due to $g$'s injectivity, there will exist an $a \in A$ such that $g \circ h(a) \neq \Phi(h)\circ f(a)$. To be slightly more formal, I think it is the case that:

$$f \text{ not injective, } h_\alpha \text{ is injective, and } A \prec C \rightarrow f[A] \prec h_\alpha[A]$$

If I could receive some further input on this final point, it would be greatly appreciated!

Answer 1

Assume for now that $A,B,C$, and $D$ are non-empty. Let $B_0=f[A]$ and $D_0=g[C]$, and fix $d_0\in D_0$. For each $b\in B_0$ denote by $f^{-1}(b)$ the unique $a\in A$ such that $b=f(a)$. For $h\in C^A$ define a function $\Phi(h):B\to D$ as follows:

$$\Phi(h)(b)=\begin{cases} (g\circ h\circ f^{-1})(b),&\text{if }b\in B_0\\ d_0,&\text{if }b\in B\setminus B_0\,. \end{cases}$$

Clearly $\Phi:C^A\to D^B$. To show that $\Phi$ is injective, suppose that $h_1$ and $h_2$ are distinct elements of $C^A$. Then there is an $a\in A$ such that $h_1(a)\ne h_2(a)$. Let $b=f(a)$. Then

$$\Phi(h_i)(b)=(g\circ h_i\circ f^{-1})(b)=(g\circ h_i)(a)=g\big(h_i(a)\big)$$

for $i=1,2$. Now $h_1(a)\ne h_2(a)$, and $g$ is injective, so

$$\Phi(h_1)(b)=g\big(h_1(a)\big)\ne g\big(h_2(a)\big)=\Phi(h_2)(b)\,,$$

and therefore $\Phi(h_1)\ne\Phi(h_2)$, i.e., $\Phi$ is injective.

Now we consider the edge cases in which one or more of $A,B,C$, and $D$ is empty. Recall that $X^\varnothing=\{\varnothing\}$ for all sets $X$, and $\varnothing^X=\varnothing$ for all non-empty sets $X$.

• If $A=\varnothing$, then $C^A=\{\varnothing\}$, which clearly injects into any non-empty set. However, it is possible that $B\ne\varnothing=D$, in which case $D^B=\varnothing$, and the result fails.
• If $B=\varnothing$, then $A=\varnothing$, $C^A=\{\varnothing\}=D^B$, and the result holds.
• If $C=\varnothing\ne A$, then $C^A=\varnothing$, and the result holds. If $C=\varnothing=A$, then $C^A=\{\varnothing\}$, and the result holds iff $B=\varnothing$.
• If $D=\varnothing$, then $C=\varnothing$. If $A\ne\varnothing$, then $B\ne\varnothing$, $C^A=D^B=\varnothing$, and the result holds. If $A=\varnothing$ and $B\ne\varnothing$, however, the result fails.

---

To see why you need the injectivity of $f$, suppose that there are distinct $a_1,a_2\in A$ and $b\in B$ such that $f(a_1)=f(a_2)=b$. Let $h$ be any function from $A$ to $C$ such that $h(a_1)\ne h(a_2)$. Then $\Phi(h)(b)$ is not well-defined: is it $g\big(h(a_1)\big)$, or is it $g\big(h(a_2)\big)$? These are different, since $g$ is injective.