0
$\begingroup$

I recently came across this question as a part of exercise problems without answers and cannot figure it out. I know how to show that it is not surjective but have no idea how to do it for injectivity. I don't need a full answer a hint would be just fine. Thanks.

In order for the function to be injective, for every element of the domain (in this case B) there must be a distinct element of the codomain (in this case C) that it maps to. As the domain is larger than the codomain this means that there must be more than one element of the domain mapped to a single element of the codomain thus it is not injective.

This is what I have come up with but not sure if it is correct or even a step in the right direction.

$\endgroup$
4
  • 2
    $\begingroup$ "I know how to show that it is not surjective..." It is unclear what you mean here, since it is possible for such a function to be surjective. Do you mean in general you know how to approach proving a function can't be surjective? $\endgroup$ Nov 28, 2022 at 15:10
  • $\begingroup$ Are $B$ and $C$ supposed to be finite sets? $\endgroup$ Nov 28, 2022 at 15:12
  • $\begingroup$ @ThomasAndrews It is not specified whether they are finite or not, but I would assume they are given the context of previous exercises. And I know how to go about a proof regarding surjection in general. $\endgroup$
    – Alec
    Nov 28, 2022 at 15:15
  • 2
    $\begingroup$ Suppose there is an injective function $f:B\to C.$ How are $|f(B)| $ and $|B|$ are related ? $\endgroup$
    – Fred
    Nov 28, 2022 at 15:18

1 Answer 1

0
$\begingroup$

It depends on how rigorous you want your proof to be, and what facts about maps you are allowed to use. I'll sketch a simple proof, which only needs the knowledge that subsets are not larger than supersets, and a bijection between two sets means they are the same size:

Assume that $f:B\to C$ is injective. Then the range $R(f)$ is a subset of $C$, and $f:B\to R(f)$ is a bijection. So $|B| = |R(f)| \leq |C|$.

$\endgroup$
1
  • $\begingroup$ This would mean that we have a proof by contradiction right as we have arrived at |B|≤|C| but we know that ∣C∣<∣B∣, right? $\endgroup$
    – Alec
    Nov 28, 2022 at 15:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .