Inverse function, power set.

1.5k Views Asked by At

How to prove, that for every function $F: P(\mathbb N) \rightarrow P(\mathbb N)$, where:
$F(\mathbb N)=\mathbb N$
$F(\emptyset)=\emptyset$
$F(\bigcup \Xi)=\bigcup\{F(X)|X\in\Xi\}$ for every $\ \Xi\subset P(\mathbb N)$
$F(X\cap Y)=F(X)\cap F(Y)$ for every $X,Y \subset \mathbb N$
There is exactly one function $f: \mathbb N \rightarrow \mathbb N$, so, that $F(X)=f^{-1}(X)$, for every $X \subset \mathbb N$.

It may be useful not note, that $X=\bigcup\{\{x\}|x\in X\}$.

1

There are 1 best solutions below

2
On BEST ANSWER

Note that since any two singletons are disjoint, their images under $F$ must also be disjoint (since $A\cap B=\emptyset$ is what it is to be disjoint and $F$ preserves intersections and the empty set). Note also that you can easily map any singleton to the empty set (since $\emptyset$ is self-disjoint).

So an $F$ with these properties will give a partition of $\mathbb{N}$ as $\{F(\{x\}):x\in\mathbb{N}\}$, since by one of the properties above $F$ preserves coverings (and we've already established that the covering sets are pairwise disjoint). So every member of $\mathbb{N}$ will be in $F(\{y\})$ for some $y$, and will be in exactly one such set. We can thereby define $f(x)$ to be the unique $y$ such that $x\in F(\{y\})$. It is easy to see that $F$ is exactly $f^{-1}$ as desired.