Image of a discrete function

Question

I am a bit confused about identifying the image of a discrete function. I understand that the image of a function is the subset of its codomain, but what does it mean exactly puzzles me. Based on the question below, how are you supposed to find the image of the function ?

Let $A = \mathcal{P}(\{1, 2, 3, 4\})$. Let $f$ be the following function.

$f : A → A$ defined by $f(X) = \{1, 2, 3, 4\} − X$

What is the image of $f$ ?

Answer 1

The image is the set of all values taken by the function. Here $f$ maps a set to its complement. Every element of the power set is the complement of some element of the power set, so the image is just the power set. That is, if $X\in\mathscr{P}(\{1,2,3,4\})$ then $f(X^c)=X,$ so $X$ is in the image of $f$.

Answer 2

If $f:A\to B$ is a function then the image of $f$ is the set $\{f(a)\mid a\in A\}\subseteq B$.

Applying that on your example $f:A\to A$ we find that the image of $f$ is $A$.

This because for every $X\in A$ we can find an element $Y\in A$ with $f(Y)=X$.

In words: $f$ is a surjective function.

Just take $Y:=\{1,2,3,4\}-X\in A$ and discover that indeed $f(Y)=X$.

Answer 3

I guess you're having a problem with notation. Here is what you could do to try to get the hang of things:

• $A$ is the power set of $\left\{1,2,3,4\right\}$; That is $A$ is the set of all subsets of $\left\{1,2,3,4\right\}$. You can write all of these explcitly if you want (there are 16 of them: $$A=\Big\{\normalsize\varnothing,\ \left\{1\right\},\ \left\{2\right\},\left\{3\right\},\left\{4\right\},\left\{1,2\right\},\ldots,\left\{1,4\right\},\left\{2,3\right\},\ldots\left\{1,2,3,4\right\}\Big\}.$$ This is not necessary but you should definitely do it it you're not comfortable with the description "$A=\mathcal{P}(\left\{1,2,3,4\right\})$.

• Now look at your function $f(X)=\left\{1,2,3,4\right\}-X$. In words, $f(X)$ is the complement of $X$, where $X$ is a subset of $\left\{1,2,3,4\right\}$. Again, if you're having difficulties, try to calculate a few random values. For example, let's take a random element $X$ of $A$, say $X=\left\{1,3,4\right\}$. Then $$f(X)=\left\{1,2,3,4\right\}-\left\{1,3,4\right\}=\left\{2\right\}$$ Cool, so $\left\{2\right\}$ is in the image of $f$. In symbols, I will denote the image of $f$ by $Im(f)$, so $$Im(f)=\left\{\{2\},\ldots\right\}$$ You can then keep computing $f(X)$ for all 12 possibilities of $X$; here are a few other random values: $$f(\left\{2\right\})=\left\{1,3,4\right\},\quad f(\left\{1,3\right\})=\left\{2,4\right\},\quad f(\left\{2,4\right\})=\left\{1,3\right\}...$$ so $$Im(f)=\left\{\{2\},\{1,3,4\},\{1,3\},\{2,4\},\ldots\right\}$$ This should give you the whole of $Im(f)$. It is not too much work because $A$ is small. But if $A$ were a little larger things would get exponentially more time-consuming. (For example, if $A$ were $\left\{1,2,3,4,5,6\right\}$ there would be 64 computations to make!)

So you might have noticed something I did above: $f(\{1,3,4\})=\{2\}$, while $f(\{2\})=\{1,3,4\}$, that is, $f$ is just permuting $\{1,3,4\}$ and its image, $\{2\}$, and similarly $f$ is just permuting $\{1,3\}$ and its image $\{2,4\}$. So you may ask yourself if $f$ is always just permuting $X$ and $f(X)$., that is, if $X=f(f(X))$. To do this, compute $$f(f(X))=\{1,2,3,4\}-f(X)=\{1,2,3,4\}-(\{1,2,3,4\}-X)),$$ and verify that the right-hand side is equal to $X$ (it is "the complement of the complement").

So after you verify that $X=f(f(X))$ for all $X$, you can conclude that every $X\in A$ is the image of some $Y\in A$; namely $Y=f(X)$. Therefore $A\subseteq Im(f)$, whereas $Im(f)$ is a subset of the codomain $A$ of $f$, i.e.., $Im(f)\subseteq A$. By definition of equality of sets (or ZFC, or an axiom of Naïve Set Theory if you will), $Im(f)\subseteq A$ and $A\subseteq Im(f)$ means precisely that $Im(f)=A$.

The latter determination of $Im(f)$ was formal, without any "computations", and in fact works if we replace $A$ by any set, as large as it is.