# Power Sets

• Sep 22nd 2008, 07:47 AM
GoldendoodleMom
Power Sets
Prove: Let S and T be sets. If there exists and injection from |S| --> |T| then there exists an injection from |P(S)|-->|P(T)|

(P(S) and P(T) represent the power sets of each)
• Sep 22nd 2008, 08:15 AM
Plato
Here is a bit of notation. $C \subseteq S \Rightarrow \quad \overrightarrow f (C) = \left\{ {t \in T:\left( {\exists x \in C} \right)\left[ {f(x) = t} \right]} \right\}$
That is called the image set of $C$ under $f$.
Now it is clear that we have $\overrightarrow f :P(S) \to P(T)$, so we must prove that if $f\mbox { is injective then } \overrightarrow f \mbox{ is also injective}$
Of course to do that you must show $\overrightarrow f (C) = \overrightarrow f (D) \Rightarrow \quad C = D$.
• Sep 22nd 2008, 08:35 AM
GoldendoodleMom
Power Sets
The proof is regarding the cardinality of the sets and power sets. Does that change the strategy?
• Sep 22nd 2008, 08:43 AM
Plato
Quote:

Originally Posted by GoldendoodleMom
The proof is regarding the cardinality of the sets and power sets. Does that change the strategy?

No it does not.
Here is the rest of it.
If $\overrightarrow f (C) = \overrightarrow f (D)$ then
$\begin{array}{lcl}
{c \in C} & \Rightarrow & {f(c) \in \overrightarrow f (C)} \\
{} & \Rightarrow & {f(c) \in \overrightarrow f (D)} \\
{} & \Rightarrow & {\left( {\exists d \in D} \right)\left[ {f(d) = f(c)} \right]} \\
{} & \Rightarrow & {d = c} \\
{} & \Rightarrow & {c \in D} \\

\end{array}$

You do the other way by switching D with C.