I've been asked to prove the following property:
If $f$ and $g$ are injective then $F3$ is bijective, where $F3$ is given by $A×B→f(A)×g(B), (x,y)⟼(f(x),g(y))$
Here's what I have so far…
To prove that this is bijective, we must show that it is both injective and surjective:
Injectivity:
- We must prove that if $(f(x), g(x)) = (f(y), g(y))$, then $x = y$
- Suppose that $(f(x), g(x)) = (f(y), g(y))$
- By the equality of ordered pairs, we know that $f(x) = f(y)$ and that $g(x) = g(y) $
- $f$ is injective according to the hypothesis and $f(x) = f(y)$, implying that $x = y$
Surjectivity:
???
I'm not too sure how to prove the surjective nature of the cross product and am therefore stuck. I was thinking of finding the inverse in order to show surjectivity, but am not too show how to proceed.
Best Answer
Suppose $f: A \to X$ is injective. And $g:B\to Y$ is injective.
Note if we define $H:A\times B \to X\times Y$ via $H(a,b) = (f(a),g(b))$ then $H$ is might NOT be surjective. But that was not the question that was asked.
We aren't defining $H:A\times B \to X \times Y$; we are defining $F3:A\times B \to f(A)\times f(B)$. And $f(A)\times f(B) $ is not the same codomain as $X \times Y$ would be. We do have $f(A)\times f(B)\subset X\times Y$ but it could be that that $f(A)\times f(B) \subsetneq X\times Y$, a proper subset.
If $f$ is not surjective then there will be some $x \in X$ where there is no $a\in A$ so that $f(a) =x$. But then $x \in X$ but $x$ is NOT in $f(A)$. And $f(A)\subsetneq X$.
So if $f$ or $g$ are not both surjective then $f(A)\times f(B) \subsetneq X\times Y$.
Now... the proof that $F3: A\times B \to f(A)\times f(B)$ is downright trivial!
If $(x,y) \in f(A)\times f(B)$ then $x \in f(A)$ and $y \in f(B)$.
But if $x \in f(A) \subset X$ then there is an $\alpha \in A$ so that $f(\alpha) = x$. And if $y \in f(B)$ then there is a $\beta \in A$ so that $f(\beta) = y$.
And so ..... $F3(\alpha, \beta) = (f(\alpha), f(\beta)) = (x,y)$.
So $F3$ is surjective.