How can I formally prove this obvious surjection?

Question

Note: I will be using $\uplus$ to represent disjoint unions. $f$ and $g$ are not explicitly defined in the question I have and are meant to be abstract.

I have some 2 surjections $C : A \mapsto B$ and $D : X \mapsto Y$, and I want to show that:

a) $f : A\times X \mapsto B \times Y$ is a surjective function too, and

b) $g : A \uplus X \mapsto B \uplus Y$ is also surjective.

I know it's kind of obvious that since A and B are domains of surjective functions, we can definitely map all values in the domains to a corresponding value in its co-domain. Formally, we want to show that $\forall a \in A$, there exists some $b \in B$ such that $f(a) = b$. Since function $C$ can at least map to one element in $B$, and so could D for mapping X to Y, part (a) seems obvious.

But is there a way to prove this formally? I have meddled with some set builder notation but it looks unclean and all it seems is that I'm writing unnecessary notations.

Also for proving the disjoint union function is surjective, I have tried letting $\forall (k, n), n \in \{0, 1\}, k\in A \lor k \in X$, we have some $l \in B \lor l \in Y$ such that $g(k,n) = (l, n)$.

But this doesn't seem to be the right way to prove it.

Answer 1

Let's start with the first problem -- saying what $f$ and $g$ are:

I believe you mean to write $$ f: A \times X \to B \times Y : (a, x) \mapsto (C(a), D(x)) $$ and for the second, I think you mean that $$ g: A \cup X \to B \cup Y : u \mapsto \begin{cases} C(u) & u \in A\\ D(u) & u \in X \end{cases}. $$ Do I have that about right? If not, please correct me. But without some definition of $f$ and $g$, the whole problem is meaningless.

Assuming so, let's proceed to the second problem, which is considerably easier once that first (unwritten) one is out of the way.

To show that $f$ is surjective, take an arbitrary element $(b, y)$ of the codomain, where $b \in B$ and $y \in Y$. Because $f$ is surjective, there's some element $q \in A$ with $C(q) = b$; similarly, there's an element $r \in X$ with $D(r) = y$ (again by surjectivity).

Now look at $f(q, r)$. By definition (which you have to write down or the whole problem is meaningless!), we have

$$ f(q, r) = (C(q), D(r)) = (b, y). $$ Hence the point $(b, y)$ is in the image of $f$.

Now: you try it for the disjoint union case. Your proof will have two cases, depending on whether the target item $s$ is in $B$ or is in $Y$. It cannot be in both, because the codomain is a disjoint union (even though I haven't used the special symbol for that).

Answer 2

I'll sketch the second question. We define $g $ as $$g(x)=\begin{cases}C(x)&\text{if }x\in A \\ D(x)&\text{if }x\in X \end{cases}.$$ Now consider an element $t\in B\uplus Y$. Then

• either $t\in B$. In this case, by hypothesis, $t=C(a)$ for some $a\in A$. But $a$ also lies in $A\uplus X$, and then $C(a)=g(a)$.
• or $t\in Y$. I think you can proceed.

Answer 3

First off, based on your comments, I believe that statements of the things that you want to prove are something like this:

Suppose that $A$, $B$, $X$, and $Y$. Further assume that there exist surjective functions $$ f: A\to B \qquad\text{and}\qquad g : X\to Y. $$ Then there exist surjective maps $A\times X \to B\times Y$, and $A\sqcup X \to B\sqcup Y$ (where $\sqcup$ denotes the disjoint union).

For the first statement, define a map $h : A\times X \to B\times Y$ by $$ h(a,x) = (f(a),g(x)). $$ We claim that $h$ is surjective. Let $(b,y) \in B\times Y$—our goal is to find some point $(b',y') \in A\times X$ such that $h(b',y') = (b,y)$. Since $f$ is surjective, there is some point $b' \in A$ such that $f(b') = b$. Since $g$ is surjective, there is some point $y' \in X$ such that $g(y') = y$. Then, by definition of $h$, we have $$ h(b',y') = (f(b'), g(y')) = (b,y).$$ Therefore $h$ is surjective.

For the second statement, let's first be very careful about the definition of the disjoint union. This is usually defined by $$ A \sqcup B := (A\times \{0\}) \cup (B\times \{1\}).$$ The reason to do this is that $A$ and $B$ might be subsets of some larger set, but the disjoint union somehow remembers the original set membership of its elements. As a basic example, $[0,1] \cup [0,1] = [0,1]$, while $[0,1]\sqcup[0,1]$ consists of two copies of the interval that are "placed next to each other."

With this in mind, define a map $k : A\sqcup X \to B\sqcup Y$ by $$ k(s,i) = \begin{cases} (f(s),0) & \text{if $i=0$, and} \\ (g(s),1) & \text{if $i=1$.} \end{cases} $$ Basically, $i$ keeps track of which set the point $s$ originally belonged to. Hence $k$ looks at $i$, determines which set $s$ belongs to, then applies the appropriate map to that point, retaining the appropriate group membership. The claim is that $k$ is surjective.

Suppose that $(t,j) \in B\sqcup Y$. There are two cases: either (1) $j=0$ or (2) $j=1$.

1. If $j=0$, then $t \in B$. By the surjectivity of $f$, there is a point $t'\in A$ such that $f(t') = t$. It therefore follows that $$k(t',0) = (f(t'),0) = (t,0). $$ Hence we have found a point $(s,i) = (t',0) \in A\sqcup X$ that is sent to $(t,j)$ by $k$.
2. If $j=1$, then $t \in Y$. By the surjectivity of $g$, there is a point $t'\in X$ such that $g(t') = t$. It therefore follows that $$k(t',1) = (g(t'),1) = (t,1). $$ Hence we have found a point $(s,i) = (t',1) \in A\sqcup X$ that is sent to $(t,j)$ by $k$.

In either case, given an arbitrary $(t,j) \in B\sqcup Y$, we can find a point $(s,i)$ such that $k(s,i) = (t,j)$. Therefore $k$ is surjective.