1

This is a question I got in my homework, and it reads as follows (translated):

Consider the function $f:P(\mathbb N) \to P(\mathbb N)$, given by $f(A)=A \setminus \{1\}$.

Prove that $|f^{-1}(\{A\})| \in \{0,2\}$ for all $A \in P(\mathbb N)$

This is how I attempted to solve it, and the problems I faced:

If $f(A)=A \setminus \{1\}$, then the inverse function is $f^{-1}(A)=A\cup \{1\}$.

Now we are faced with 2 cases: either $\{1\}$ is in $A$, or not.

If $1$ is not in $A$, then $f^{-1}(\{A\})=\{A\} \cup \{1\}=\{A,1\}$ and then $|f^{-1}({A})|=2$.

I'm pretty sure A wouldn't look like $\{1, \dots \}$, but I'm not certain.

But what if $1$ is in $A$ originally?

I thought the inverse function wouldn't care and would still return $\{A\}\cup \{1\}$, resulting in $|f^{-1}({A})|=2$. But my friend wasn't so sure and now neither am I.

I don't know if I make a mistake somewhere, or if the teacher was trolling and added a $0$ for no reason, so I'm asking here for help.

Kenny Wong
  • 32,192
Yaniv Polischuk
  • 83

1 Answers1

1

Firstly, $f$ is not bijective, so it does not have an inverse! It does not make sense to talk about the "inverse function" $f^{-1}$.

The notation $f^{-1}$ actually denotes a preimage:

If $S \in P(\mathbb N)$, then $f^{-1}(S) = \{ B \in P(\mathbb N) : f(B) \in S \}$.

In other words, if $S$ is a subset of the codomain, then $f^{-1}(S)$ is the set consisting of all elements of the domain that are mapped by $f$ into $S$.

Note that $f^{-1}(S)$ is not necessarily the same size as $S$!

Anyway, let's go ahead and calculate. \begin{align} f^{-1}(\{ A \}) &= \{ B \in P(\mathbb N) : f(B) \in \{ A \} \} \\ &= \{ B \in P(\mathbb N) : f(B) = A \} \\ &= \{ B \in P(\mathbb N) : B \setminus \{ 1 \} = A \} \end{align}

Now consider the two cases you mentioned.

Case 1: $1 \notin A$. In this case, $B \setminus \{ 1 \} = A$ is true if and only if $B = A$ or $B = A \cup \{ 1 \}$. So $$ f^{-1}(\{ A \}) = \{ A, A \cup \{ 1 \} \}.$$

Case 2: $1 \in A$. In this case, there exists no $B$ such that $B \setminus \{ 1 \} = A$ is true. So $$ f^{-1}(\{ A \}) = \{ \}.$$

Kenny Wong
  • 32,192