# Thread: topology - the lift of a function f

1. ## topology - the lift of a function f

Let X,Y be subsets of the universal set S. Suppose f:X to Y is a function. Define the lift of f to 2^X , F:2^X to 2^Y by F(A)=f(A), A in 2^X. Show the following:

a) F is one-to-one if and only if f is one-to-one.
b)F is onto if and only if f is onto.

I know that 2^X is the power set of X, meaning that 2^X is the set of all subsets of X. Similarly, 2^Y is the set of all subsets of X. But I have no experience with lifts at all. To prove a), I will first assume that F is one-to-one. Then for a1,a2 in 2^X F(a1)=F(a2) implies a1=a2. But I don't understand how the lift is relating to f, so I cannot complete the proof. Thank you for your help.

2. Originally Posted by poXGxxi
Let X,Y be subsets of the universal set S. Suppose f:X to Y is a function. Define the lift of f to 2^X , F:2^X to 2^Y by F(A)=f(A), A in 2^X. Show the following:

a) F is one-to-one if and only if f is one-to-one.
Let $\displaystyle A\subseteq X$ define $\displaystyle f[A]=\{ y\in Y | y=f(x) \text{ for some }x\in A \}$. I do not like to use $\displaystyle 2^X$ because it does not usually mean the power set, instead I shall use $\displaystyle \mathcal{P}(X)$ for the power set. Now define $\displaystyle F: \mathcal{P}(X) \to \mathcal{P}(Y)$ by $\displaystyle F(A) = f[A]$. Assume that $\displaystyle f$ is one-to-one and $\displaystyle F(A) = F(B)$ then $\displaystyle f[A] = f[ B ]$. To show $\displaystyle F$ is one-to-one we need to show $\displaystyle A=B$. Thus, let $\displaystyle a\in A$ then $\displaystyle f(a)\in f[A]$. Since $\displaystyle f[A] = f[ B ]$ it means $\displaystyle f(a) \in f[ B ]$ and so by definition $\displaystyle f(a) = f( b )$ for some $\displaystyle b\in B$. However, $\displaystyle f$ is one-to-one so $\displaystyle a=b\in B$. Thus, $\displaystyle A\subseteq B$, repeating the mirror argument shows $\displaystyle B\subseteq A$, which means $\displaystyle A=B$. Let us summarize what we did: we showed that if $\displaystyle f$ is one-to-one then $\displaystyle F$ is one-to-one.

Conversely, say $\displaystyle F$ is one-to-one, i.e. if $\displaystyle F(A)=F(B)$ then $\displaystyle A=B$. We want to show $\displaystyle f$ is one-to-one. Say that $\displaystyle f(a) = f(b)$. Now form the sets $\displaystyle \{ a \}$ and $\displaystyle \{ b \}$ which are subsets of $\displaystyle A$. Note $\displaystyle F( \{a\}) = \{ f(a)\}$ and $\displaystyle F(\{b\}) = \{ f(b) \}$. Therefore $\displaystyle F( \{a \}) = F(\{ b\})$ but by above assumptions it means $\displaystyle \{ a \} = \{ b \}$ and so $\displaystyle a=b$. Let us summarize what we did: we showed that if $\displaystyle F$ is one-to-one then $\displaystyle f$ is one-to-one.

Putting these together it means $\displaystyle f$ is one-to-one if and only if $\displaystyle F$ is one-to-one.

You try the second part.