Finding $\phi^{-1}({id_{P(\mathbb{N})}})$, where $\phi:(\mathbb{N}\to\mathbb{N})\to(P(\mathbb{N})\to P(\mathbb{N}))$ and $\phi(f)(A) = f^{-1}(A)$

Question

I have function $\varphi : (\mathbb{N} \to \mathbb{N}) \to (P(\mathbb{N}) \to P(\mathbb{N}))$ and $\varphi(f)(A) = f^{-1}(A)$. I have to find $\varphi^{-1}({id_{P(\mathbb{N})}})$, and I don't have any idea how to find it.

Any tips? Thanks a lot.

Answer 1

Let's take it one step at a time. For any function $g$, what is $g^{-1}(Y)$? It is $g^{-1}(Y)=\{x \mid g(x) \in Y\}$. Now apply that to $\varphi^{-1}(\text{id}_{\mathcal{P}(\mathbb{N})})$. This set is everything that is mapped by $\varphi$ to $\text{id}_{\mathcal{P}(\mathbb{N})}$, and here the "everything" means "every function $f:\mathbb{N} \to \mathbb{N}$" as that is the domain of $\varphi$.

What does it mean for a function $f:\mathbb{N}\to\mathbb{N}$ to be mapped to the identity function by $\varphi$? It means $\varphi(f)(A)=A$ for every $A\subseteq \mathbb{N}$. I'll leave it to you to determine what functions $f$ satisfy that.

Answer 2

Although it's common in type theory and in some programming languages (such as Haskell) to write the function signature as you have it, the more common way to write it in mathematics is $$\varphi: \mathbb{N}^\mathbb{N} \rightarrow P(\mathbb{N})^{P(\mathbb{N})}$$

where for sets $A, B$, the notation $B^A$ is used to denote the set of all functions $g:A \rightarrow B$.

Regarding your question:

$$\varphi^{-1}(id_{P(\mathbb{N})}) = y $$ where we know that $y \in \mathbb{N}^\mathbb{N}$, so $y : \mathbb{N} \rightarrow \mathbb{N}$. Let's discover some information about $y$. We know that

$$\varphi(y) = \varphi(\varphi^{-1}(id_{P(\mathbb{N})})) = id_{P(\mathbb{N})} \tag 1$$

so we have two pieces of information:

$$\varphi(y)(A) = A \tag 2$$ $$\varphi(y)(A) = y^{-1}(A) \tag 3$$ where (2) follows from (1), and (3) follows from definition of $\varphi$.

Thus,

$$ y^{-1}(A) = A$$

You asked for tips; does this give you enough information for what $y$ could be?