I'm trying to prove that for any cardinal numbers $a,b,c$, the following holds: $a ^ {b + c} = a ^ b a ^ c$ i.e. that there exists a bijective function $ f : A ^ {B \:\: \cup \:\: C} \rightarrow A^B \times A^C $

This is only part of the proof sketch I have (proving $f$ is injective), and I'd like to know if is well written, since I believe it has flaws.

Let $f: \{ g \:\:\: | g:B \cup C \rightarrow A \} \rightarrow \{ \langle g,h\rangle | \:\:\: g: B \rightarrow A \wedge h : C \rightarrow A \}$ such that

$f ( g_{b} \cup g_{c}) = \langle g_{b},g_{c}\rangle$.


$f( g_{b1} \cup g_{c1}) = f ( g_{b2} \cup g_{c2} ) \implies \langle g_{b1},g_{c1}\rangle = \langle g_{b2},g_{c2}\rangle$ and therefore $f$ is injective.


  1. Does that prove that $f$ is injective? I think it does not, since $f ( g_{b} \cup g_{c} ) = f ( g_{c} \cup g_{b}) \implies \langle g_{b},g_{c}\rangle = \langle g_{c},g_{b}\rangle (\bot)$
  2. Is there an alternative way to define $f$? It's difficult for me to define it in terms of properties of elements of its domain.

Side note:

The title says "kinds" because the function domain and image sets are sets of sets, but I may be mistaken using that word, if so, please edit accordingly.

  • $\begingroup$ In ZF(C), the most common axiomatization of set theory, all sets are sets of sets, so I’ve just put a description of $f$ in the title. $\endgroup$ – Brian M. Scott Nov 8 '11 at 5:23
  • 1
    $\begingroup$ What do you mean by $g_b\cup g_c$? Are you trying to say that $f:g\mapsto\langle g\upharpoonright B,g\upharpoonright C\rangle$? That function is indeed injective. It won’t be surjective, however, unless $B\cap C=\varnothing$. $\endgroup$ – Brian M. Scott Nov 8 '11 at 5:25
  • $\begingroup$ Rather than $g_{b}\cup g_{c}$, I would write simply $g$, and map it to $\langle g|_B,g|_C\rangle$, where $g|_B$ is the restriction of $g$ to $B$, and $g|_C$ the restriction to $C$. To prove injectivity, your notation is not very nice, so instead you should us $f(g) = f(h)$ and note that this yields $g|_B=h|_B$ and $g|_C = h|_C$. Etc. P.S. Use \langle and \rangle for $\langle$ and $\rangle$ rather than < and >; the spacing is off for the latter. $\endgroup$ – Arturo Magidin Nov 8 '11 at 5:27
  • 2
    $\begingroup$ Is the union in $A^{B\cup C}$ meant to be disjoint union? Otherwise, the desired bijection need not exist. $\endgroup$ – Arturo Magidin Nov 8 '11 at 5:28
  • $\begingroup$ For the argument to work as stated, we probably need to ask that $B$ and $C$ are disjoint. Why not define $\phi(g)$ as the ordered pair $(g_B,g_C)$? A lot fewer symbols. (The $\phi$ is because somehow $f$ sounds like something of the same family as $g$.) The injectivity should be easy. From $(g_B, g_C)$ we can reconstruct $g$. $\endgroup$ – André Nicolas Nov 8 '11 at 5:34

You can think of $g : B \cup C \to A$ as a couple of functions $g_B : B \to A$ and $g_C : C \to A$ such that for all $x \in B \cap C$, $g_B(x) = g_C(x)$. Therefore, letting $f : \Gamma \to \Delta$ (with $$ \Gamma = \{ g \,\, | \,\, g : B \cup C \to A \}, \qquad \Delta = \{ \langle g_B, g_C\rangle \, \, | \, \, g_B : B \to A, \, \, g_C : C \to A \} $$ obviously), you can see that a natural way to do this is to restrict the domain of $g : B \cup C \to A$ to just $B$ (or $C$), hence the map $f$ could naturally be defined by $g_B(x) = g(x)$ for all $x \in B$, $g_C(x) = g(x)$ for all $x \in C$ and $f(g) = \langle g_B, g_C \rangle$. In this manner the notation is more clear and more obviously well-defined.

This function $f$ is injective because of the following. Suppose that $f(g_1) = \langle g_B^1, g_C^1 \rangle = \langle g_B^2, g_C^2 \rangle =f(g_2)$. Thus for all $x \in B \cup C$, $x$ is either in $B$ or $C$, suppose $B$. Thus $g_1(x) = g_B^1(x) = g_B^2(x) = g_2(x)$. The case $x \in C$ is similar. Therefore $g_1 = g_2$.

I can't think of a natural way to define $ F : \Delta \to \Gamma$ right now, it'll require some thinking, I guess. I am not familiar with the usual rigor abusive context, but my problem is that I don't want to assume $B \cap C = \varnothing$. If we can assume that there is an obvious way back (i.e. you can show that this $f$ is bijective, easily). If someone could comment on this question I'm asking, I'd love to read.

  • $\begingroup$ There’s not much reason to define an $F:\Delta\to\Gamma$ unless $B\cap C=\varnothing$, in which case the desired $F$ is simply $F:\Delta\to\Gamma:\langle g,h\rangle\mapsto g\cup h$. $\endgroup$ – Brian M. Scott Nov 8 '11 at 5:31
  • $\begingroup$ Yeah... I know it would sound lame to do it if the intersection was non-empty, but ZFC theory usually scares me by its depth and generality, so I don't know if it is allowed sometimes in some contexts. I've never actually studied ZFC rigorously so I preferred to ask instead of babbling. $\endgroup$ – Patrick Da Silva Nov 8 '11 at 5:32
  • $\begingroup$ Perhaps because of this my notation seems more familiar to a mathematician that doesn't study logic or set theory because I've understood but never seen the notation $g \cup h$ for taking the "union" of two functions... $\endgroup$ – Patrick Da Silva Nov 8 '11 at 5:34
  • $\begingroup$ The functions $g$ and $h$ are just sets of ordered pairs, so their union is also a set of ordered pairs. As long as $g$ and $h$ don’t contain two pairs $\langle b,a\rangle$ and $\langle c,a\rangle$ with $b\ne c$, their union will still be a function $-$ and if $B\cap C=\varnothing$, they won’t contain such conflicting pairs. $\endgroup$ – Brian M. Scott Nov 8 '11 at 5:49
  • 1
    $\begingroup$ Thank you Brian, Pattrick and yunome for your help, I really appreciate it. $\endgroup$ – kmels Nov 8 '11 at 6:19

I’m going to assume that I’ve guessed correctly that you want to define $$f:A^{B\;\cup\;C}\to A^B\times A^C:g\mapsto \langle g\upharpoonright B,g\upharpoonright C\rangle\;.$$ If you express it this way, it’s easy to see that $f$ is injective. Suppose that $f(g_0)=f(g_1)$. Then $g_0\upharpoonright B=g_1\upharpoonright B$ and $g_0\upharpoonright C=g_1\upharpoonright C$. Now let $x\in B\cup C$ be arbitrary. If $x\in B$, then $$g_0(x)=(g_0\upharpoonright B)(x)=(g_1\upharpoonright B)(x)=g_1(x)\;,$$ and if $x\in C$, then $$g_0(x)=(g_0\upharpoonright C)(x)=(g_1\upharpoonright C)(x)=g_1(x)\;,$$ so $g_0(x)=g_1(x)$ for all $x\in B\cup C$, and hence $g_0=g_1$. It was the clumsy way in which you expressed an arbitrary element of $A^{B\;\cup\;C}$ that led you to doubt the injectivity of $f$.

Note that although this $f$ is injective, it is not surjective if $B\cap C\ne\varnothing$ and $A$ has at least two elements. To see this, suppose that $B\cap C\ne \varnothing$, and fix $x\in B\cap C$. Let $g_0\in A^B$ be arbitrary, and let $g_1\in A^C$ be any function such that $g_1(x)\ne g_0(x)$. Then $\langle g_0,g_1\rangle \ne f(h)$ for any $h\in A^{B\;\cup \;C}$.

To get bijectivity, you must assume that $B\cap C=\varnothing$. In that case $f$ as defined above is a bijection, and $$f^{-1}:A^B\times A^C\to A^{B\;\cup\;C}:\langle g,h\rangle\mapsto g\cup h\;.$$

  • $\begingroup$ Thanks for pasting the exact same argument as mine but adding $B \cap C = \varnothing$... you could've just ask me to complete my answer instead of making a new one though. (I am not arguing, I am thanking.) $\endgroup$ – Patrick Da Silva Nov 8 '11 at 6:03

I don't believe this proves $f$ is injective, for if $f(g_{b1}\cup g_{c1})=\langle g_{b1},g_{c1}\rangle$, then $f( g_{b1} \cup g_{c1}) = f ( g_{b2} \cup g_{c2} )$ and$\langle g_{b1},g_{c1}\rangle = \langle g_{b2},g_{c2}\rangle$ are really just the same statement so you haven't really proven anything.

I assume you also have the assumption that $B$ and $C$ are disjoint, for if not, surjectivity does not necessarily follow, and you want to show that $f$ is a bijection. I think the best way to go about proving injectivity is to first define $f$ by $f(g)=\langle g|_B,g|_C\rangle$, where $g|_B$ is the restriction of $g\colon B\cup C\to A$ to $B$, and likewise for $C$.

There are are two usual ways to show injectivity here. One is to show that $f(x)=f(y)\implies x=y$ or its contrapositive $x\neq y\implies f(x)\neq f(y)$.

One way to use it here is to suppose $g\neq h$ for $g,h\in A^{B\cup C}$, and then show $f(g)\neq f(h)$. Then for some $x\in B\cup C$, $g(x)\neq h(x)$. Let's also assume $x\in B$. Then $f(g)=\langle g|_B,g|_C\rangle$ and $f(h)=\langle h|_B,h|_C\rangle$. However, $g|_B\neq h|_B$ since $g(x)\neq h(x)$ for $x\in B$, so $f(g)\neq f(h)$, and $f$ is injective. The same idea works if you had chosen $x\in C$.


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.