1

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.

Lily
  • 395
  • 1
    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 – L.F. Cavenaghi Mar 21 '17 at 00:52

3 Answers3

6

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • $b \neq b'$ because $ \pi (a,b)=a$ and $pi (a, b')=a$? Does this make sense? – Lily Mar 21 '17 at 00:56
  • @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. – Bram28 Mar 21 '17 at 00:58
  • 2
    @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. – Ross Millikan Mar 21 '17 at 00:59
1

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$.

John Hughes
  • 93,729
  • 1
    But B is not empty. That's why the problem indicated that |B|>1. Right? – Lily Mar 21 '17 at 00:54
  • 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. – John Hughes Mar 21 '17 at 00:56
0

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.$

hausdork
  • 666