Let $f:A\to B$ be a map, then the map induced by $f$ is defined as $f^{\to}:\mathrm{P}(A)\to \mathrm{P}(B),\ X\mapsto f(X).$ Here $\mathrm{P}(A)$ denotes the power set of $A.$ We know that $f^{\to}$ satisfys the following propeties:

Property: $\bf 1) $ $f^{\to}(X)=\emptyset\Longleftrightarrow\ X=\emptyset;$

$\bf 2)$ $f^{\to}(X\cup Y)=f^{\to}(X)\cup f^{\to}(Y);$

$\bf 3)$ $f^{\to}(X\cap Y)\subset f^{\to}(X)\cap f^{\to}(Y).$

One may wonder if the properties above could ensure that a function $F:\mathrm{P}(A)\to \mathrm{P}(B)$ is induced by some map $f:A\to B.$ It's very possibly that there could be some counterexamples.

Question: $\bf 1)$ Given a function $F:\mathrm{P}(A)\to \mathrm{P}(B)$ satisfying the properties above, can we always find some map $f:A\to B$ such that $F=f^{\to}?$

$\bf 2)$ If not, can we strengthen the requirements of $F$ to guarantee that $F$ is induced by some map $f:A\to B?$

EDIT: Now I've found proper conditions to ensure that $F$ is induced by a map $f:A\to B:$

Conditions: $\bf 1)$ $F(\emptyset)=\emptyset;$

$\bf 2)$ If $(X_i)_{i\in I}$ is a family of sets in $\mathrm{P}(A),$ then $F\bigg(\displaystyle\bigcup_{i\in I}X_i\bigg)=\bigcup_{i\in I} f(X_i);$

$\bf 3)$ If $X\in \mathrm{P}(A)$ is a singleton, then $F(X)\in \mathrm{P}(B)$ is also a singelton.

We have the following theroem:

Theorem 1: If map $F:\mathrm{P}(A)\to \mathrm{P}(B)$ satisfies all three conditions above, then there exists an $\pmb{ unique}$ map $f:A\to B,$ such that $F=f^{\to}.$


No. Define F(X) = F for all X subset E.
The reader is expected to distinguish which F, F is.
Assume f:E -> Y and let f' be the induced map.
Let x be a point in E. Then f'({x}) is a singleton.
So F /= f' if F is multipoint.
Again be sure to distinguish painday's double useage of F.

A simpler counter example is for F to map
every subset of E to the empty set.

  • $\begingroup$ Thanks for pointing out, and I have corrected the misuse of symbols now. $\endgroup$ – painday Apr 16 '18 at 3:22

Proof of the theorem 1: Since $F$ satisfies the last condition, now we can define a relation $f$ on set $A\times B$ as $$f:=\left\{(x,y)|\ x\in A,\ y\in F(\left\{x\right\})\right\}.$$ We can easily check that $f$ is actually a map between $A$ and $B,$ since $F(\left\{x\right\})$ is a singleton.

Now take an arbitrary set $X\in \mathrm{P}(A),$ then if $X=\emptyset,$ then according the the first condition, we have $F(X)=\emptyset=f^{\to}(X).$ If $X\neq\emptyset,$ then applying the second condition and the third condition we obtain that $$F(X)=\displaystyle\bigcup_{x\in X} F(\left\{x\right\})=\bigcup_{x\in X} f^{\to}(\left\{x\right\})=f^{\to}(X).$$

Now we see that $F=f^{\to}.$ It's easy to check that the map $f$ is unique.


Theorem 2: Let $F:\mathrm{P}(B)\to \mathrm{P}(A)$ be a map, and if $F$ satisfies the conditions below, then there exists some map $f:A\to B,$ such that $F=f^{\leftarrow}.$

$\bf 1)$ $F(B)=A;$

$\bf 2)$ $x,y\in B,\ x\neq y\Longrightarrow F(\left\{x\right\})\cap F(\left\{y\right\})=\emptyset;$

$\bf 3)$ If $(X_i)_{i\in I}$ is a family of sets in $\mathrm{P}(B),$ then $\displaystyle F\bigg(\bigcup_{i\in I}X_i\bigg)=\bigcup_{i\in I} F(X_i). $

Proof: First we define the set $W:=\left\{x\in B|\ F(\left\{x\right\})\neq\emptyset\right\},$ and $V:=\left\{F(\left\{x\right\}|\ x\in W\right\},$ then applying to the first and the last condition we obtain the relation $$A=\displaystyle\bigcup_{x\in B}F(\left\{x\right\})=\bigcup_{x\in W}F(\left\{x\right\})=\bigcup V.$$ Now define a relation on set $A\times Z$ to be $$p:=\left\{(x,y)|\ x\in A,\ y\in Z,\ x\in y\right\},$$ then we can use the second condition to check that $p$ is actually a map between $A$ and $Z.$

Define a map $g:Z\to B,\ F(\left\{x\right\})\to x,$ then applying the second condition we see that $g$ is well-defined.

Finally, let $f:=g\circ p,$ then we can easily check that $F=f^{\leftarrow}.$



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.