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)

Printable View

- Sep 22nd 2008, 07:47 AMGoldendoodleMomPower 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 AMPlato
Here is a bit of notation. $\displaystyle 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 $\displaystyle C$ under $\displaystyle f$.

Now it is clear that we have $\displaystyle \overrightarrow f :P(S) \to P(T)$, so we must prove that if $\displaystyle f\mbox { is injective then } \overrightarrow f \mbox{ is also injective}$

Of course to do that you must show $\displaystyle \overrightarrow f (C) = \overrightarrow f (D) \Rightarrow \quad C = D$. - Sep 22nd 2008, 08:35 AMGoldendoodleMomPower Sets
The proof is regarding the cardinality of the sets and power sets. Does that change the strategy?

- Sep 22nd 2008, 08:43 AMPlato
No it does not.

Here is the rest of it.

If $\displaystyle \overrightarrow f (C) = \overrightarrow f (D)$ then

$\displaystyle \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.