If $f$ maps finite sets $A$ to $B$ and $n(A) < n(B)$, prove that $f$ cannot be onto.

Proof by contradiction:

If $f: A→B$ and $n(A) < n(B)$, $f$ is onto.

Since, by definition of a function, $a∈A$ cannot be mapped to more than one value $b∈B$. This means that $f$ is not onto since $n(A)$ cannot be less than $n(B)$, which violates the contradiction.

To me, this explanation seems simple yet complete enough to constitute a proof to the theorem. But the given solution to this problem is as follows:

If we assume that $f$ is onto, then the range is $f(A) = B$ so $n(f(A)) = n(B)$. Knowing that $n(A) ≥ n(f(A))$, yields the expression: $n(A) ≥ n(f(A)) = n(B)$. However this is a contradiction to the fact that $n(A) < n(B)$, so $f$ is not onto.

Are both proofs to this theorem deemed accurate? Should I always, when encountering these types of problems, try to prove the theorem based on the number of elements in the set versus constructing an argument by definition?

Thanks so much!

  • 1
    $\begingroup$ These seem equivalent to me. $\endgroup$ – Brian Tung Apr 22 '15 at 0:18
  • 1
    $\begingroup$ You're approach seems fine. I might just clarify it by saying that since $f$ is a function $n(f(A))\leq n(A)$ since each element of $A$ is mapped to exactly $1$ element of $f(A)$. $\endgroup$ – TravisJ Apr 22 '15 at 0:24
  • 1
    $\begingroup$ With this in mind, you have a 1-line proof: since $f$ is a function $n(f(A))\leq n(A)<n(B)$ so $f$ is not onto. This also doesn't use contradiction. $\endgroup$ – TravisJ Apr 22 '15 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.