Maximum and minimum cardinality of range and preimage

discrete mathematicselementary-set-theoryfunctionssolution-verification

I found the following question related to understanding of images and preimages:

Let A and B be nonempty sets and $f$ be a function $f: A \rightarrow B$. In terms of $|A|$ and $|B|$, what is the maximum possible cardinality of
$f[A]$? What is the minimum possible cardinality of $f[A]$? How about $f^{-1}[B]$?

My thoughts are the following:

  1. The maximum possible cardinality of $f[A]$ is $|B|$, since $f[A]$ is the range of the function and the function might be surjective, so it will map to all the elements of $B$
  2. Minimum cardinality of $f[A]$ is $1$, because $f[A]$ might be a function which maps all the elements to a single element of $B$.
  3. Maximum and minimum possible cardinality of $f^{-1}[B]$ is $|A|$, because we have a preimage of entire codomain, which must be an entire domain for $f$ to be a well-defined function.

I'm almost sure of my answers, but I'd be very grateful if someone could check and criticise/correct me if I'm wrong somewhere. And I also doubt about the second point – my answer states that cardinality is $1$, but the question asks me to define the cardinalities in terms of $|A|$ and $|B|$. Is this possible to do in the second point?

Best Answer

I agree with your statements 2 and 3.

For statement 1, there might be a ``trap".

Well, here are two things we know about the maximum cardinality of $f[A]$, say $|f[A]|_{MAX}$.

  1. $|f[A]|_{MAX} \le |A|$ by the definition of a function.
  2. $|f[A]|_{MAX} \le |B|$ by the fact $f[A]$ is a subset of $B$.

Since we don't know which is larger between $|A|$ and $|B|$, it is better to say $|f[A]|_{MAX} = \min\left\{ |A|, |B|\right\}$