Showing Function is Injective/Surjective

[mikemhz]

Show that for any sets $X, Y , Z$, the canonical function:

$\varphi : (X × Y) × Z \rightarrow X × (Y × Z)$

$(\varphi((x, y), z) = (x,(y, z)))$

is a bijection.


Solution. We can do this by showing that $\varphi$ is injective and surjective..

I can do this by showing $\varphi$ has an inverse (isomorphism theorem). But I would like to know how to show that a function involving cartesian products is injective/surjective.

 

[jbunniii]

I can do this by showing $\varphi$ has an inverse (isomorphism theorem). But I would like to know how to show that a function involving cartesian products is injective/surjective.

This should be pretty straightforward. Why not start by writing out the definition of injective and surjective for this particular map, i.e., what is it you would need to show in each case?

 

[mikemhz]

Would this show that it is injective?

$x, a \in X$
$y, b \in Y$
$z, c \in Z$

$\varphi((x,y),z) = \varphi((a,b),c)$

$\varphi : (x,(y,z)) = (a,(b,c))$

$x=a, y=b, z=c$

End of proof.

How about surjective? To be honest, I'm not 100% what I need to prove in each case. I know that injective is one-to-one (each element in Y has at MOST one element from X mapped to it) and surjective is onto (each element in Y has at LEAST one element from X mapped to it), but I do not know how that translates into the notation.

 

[mikemhz]

Sooo..

$X = \left\{1, 2\right\}$
$Y = \left\{A, B\right\}$
$Z = \left\{I, J\right\}$

$X × (Y × Z) =$
$\left\{(1, (A, I)), (1, (A, J)), (1, (B, I)), (1, (B, J)), (2, (A, I)), (2, (A, J)), (2, (B, I)), (2, (B, J))\right\}$

Take any element from $X × (Y × Z)$:
e.g. $(2, (A, I))$
Show that there is an element from $(X × Y) × Z$ which maps using the function:
$\varphi((2, A), I) = (2, (A, I))$

Therefore $\varphi$ is surjective...? :)

 

[jbunniii]

Would this show that it is injective?

$x, a \in X$
$y, b \in Y$
$z, c \in Z$

$\varphi((x,y),z) = \varphi((a,b),c)$

$\varphi : (x,(y,z)) = (a,(b,c))$

$x=a, y=b, z=c$

End of proof.

Yes, that's pretty much all there is to it. You may want to include "if and only if" between the statements and write some words to explain the conclusion you are drawing, such as:

$\varphi((x,y),z) = \varphi((a,b),c)$

if and only if

$(x,(y,z)) = (a,(b,c))$

if and only if

$x=a, y=b, z=c$

if and only if

$((x,y),z) = ((a,b),c)$

Therefore $\varphi((x,y),z) = \varphi((a,b),c)$ implies $((x,y),z) = ((a,b),c)$. This shows that the function $\varphi$ is injective.

 

[jbunniii]

Therefore $\varphi$ is surjective...? :)

No, this isn't a general proof, because you used specific examples of $X$, $Y$, and $Z$. To write a general proof, start by taking an arbitrary element of $X \times (Y \times Z)$. An arbitrary element is of the form $(x,(y,z))$, where $x \in X, y \in Y, z \in Z$. Now you need to find an element of $(X \times Y) \times Z$ which is mapped by $\varphi$ to $(x,(y,z))$. That's all there is to it.