Let $|A|>1$ and $|B|>1$.

Show $\pi: A \times B \to A$ defined by $ \pi (a,b)=a$ is a surjection, but not an injection.

My attempt:

Surjection: For any $(a,b) \in A \times B, \exists a \in A$ such that $\pi (a,b)=a$. Thus, $\pi$ is surjective. Is this correct?

Not injective: Suppose $(a,b)$ and $(a_1, b_1) \in A \times B$ and $ \pi (a,b)=\pi (a_1, b_1)$, then $a=a_1$. I know this is wrong, because I am suppose to show that it is NOT injective.

Any help is appreciated.

  • 1
    $\begingroup$ Hey, just note that $(a,b_1)$ and $(a,b_2)$ for any $b_1,b_2$ differents implies that such function is not injective since the projection of these elements are the same $\endgroup$ – L.F. Cavenaghi Mar 21 '17 at 0:52

For surjective, you should say: For any $a \in A$ there exists $(x,y) \in A \times B$ such that $\pi (x,y)=a$, namely $x = a$ and $y$ is any element in B (which we know exists since $|B|>1$ ). Thus, $\pi$ is surjective.

For not injective, take $(a,b)$ and $(a,b')$ with $b \not = b'$. We know such different $b$ and $b'$ exists since $|B|>1$. Since both $\pi(a,b) = \pi(a,b') = a$, we have two different elements mapping to the same element. So it is not injective.

  • $\begingroup$ $b \neq b'$ because $ \pi (a,b)=a$ and $pi (a, b')=a$? Does this make sense? $\endgroup$ – Lily Mar 21 '17 at 0:56
  • $\begingroup$ @Lily No, not because of it. Just take $b$ and $b'$ to be different, but pair them up with the same $a$. Since both $(a,b)$ and $(a,b')$ map to $a$, we have two different elements mapping to the same element. So it is not injective. $\endgroup$ – Bram28 Mar 21 '17 at 0:58
  • 2
    $\begingroup$ @Lily: you are again (see your surjective proof) mixing up what you want to prove and what you are assuming. You can assume $b \neq b'$ because you were given $|B| \gt 1$. This gives you two different elements in the domain with the same image, violating the definition of injective. $\endgroup$ – Ross Millikan Mar 21 '17 at 0:59

The first proof is not correct, for if $B$ is empty, then $\pi$ is not surjective...but your proof never uses the nonemptiness of $B$.

  • 1
    $\begingroup$ But B is not empty. That's why the problem indicated that |B|>1. Right? $\endgroup$ – Lily Mar 21 '17 at 0:54
  • $\begingroup$ That's right...but your proof never used the fact that $B$ was nonempty, so your proof, if correct, would also prove the statement when $B$ WAS empty...and THAT statement is not true, so the proof cannot be correct. $\endgroup$ – John Hughes Mar 21 '17 at 0:56

We have a function $\pi: A \times B \rightarrow A$ defined as $\pi(a,b) = a$. Some additional terminology, just to be perfectly clear:

  • The domain of $\pi$ is $A \times B$
  • The codomain of $\pi$ is $A$
  • The range of $\pi$ is a subset of the codomain, and is the set of all points that the domain gets mapped to, i.e. $\{\pi((a,b)) : (a,b) \in A \times B\}$.

A point worth noting is that saying a function is surjective is equivalent to saying that its range is exactly equal to its codomain.

Proof of surjectivity: consider any arbitrary $y \in Range(\pi)$. As you mentioned, we want to show there exists an $(a,b) \in Domain(\pi) = A \times B$ such that $\pi((a,b)) = y$ in order to show that our function is surjective. Since $Range(\pi) \subseteq Codomain(\pi) = A$, since $y \in Range(\pi)$, then $y \in A$. Notice that $f((y,b)) = y$, for any $b \in B$. Therefore any element of the form $(y,b)$ where $b \in B$ gets mapped to $y$. Since our choice of $y \in Range(\pi)$ was arbitrary (i.e. we did not assume anything about $y$ other than it is in the range), we have proven our claim for all $y \in Range(\pi)$. Therefore $\pi$ is subjective.

Proof that $\pi$ is not injective: we can directly show that $\pi$ is not injective by producing two elements $x, x^\prime$ in the domain such that $\pi(x) = \pi(x')$ but $x \not = x^\prime.$ Pick any $a \in A.$ Now pick two different elements $b, b^\prime \in B$. Important: this is where we use the assumption that |B| > 1. If we did not have this assumption, for example if there were only one element in $B$, we would not be able to pick two different elements from it. Then set $x = (a, b)$ and set $x^\prime = (a, b^\prime)$. Therefore, $\pi(x) = \pi(x^\prime) = a$ but $x \not = x^\prime.$


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.