Set theory. Is the converse true?

• Jun 10th 2011, 09:12 AM
omoplata
Set theory. Is the converse true?
1. The problem statement, all variables and given/known data

Prove that $\displaystyle \cup_{x \in C} 2^{x} \subseteq 2^{\cup C}$

2. Relevant equations

$\displaystyle \cup_{x \in C} 2^{x} = \{ A | \exists x \in C, A \subseteq 2^{x} \}$

$\displaystyle 2^{x}$ is the powerset of $\displaystyle x$. i.e. $\displaystyle 2^{x} = \{ y | y \subseteq x \}$

3. The attempt at a solution

Suppose $\displaystyle A \in \cup_{x \in C} 2^{x}$. Then,

$\displaystyle \exists x \in C, A \in 2^{x}$

$\displaystyle \exists x \in C, A \subseteq x$

$\displaystyle A \subseteq ( \cup C )$

$\displaystyle A \in 2^{\cup C}$

Therefore, $\displaystyle A \in \cup_{x \in C} 2^{x} \Rightarrow A \in 2^{\cup C}$

Therefore, $\displaystyle \cup_{x \in C} 2^{x} \subseteq 2^{\cup C}$

But I think there might be something wrong with my proof. Because why can't I start assuming $\displaystyle A \in 2^{\cup C}$ and go to $\displaystyle A \in \cup_{x \in C} 2^{x}$. That means $\displaystyle A \in 2^{\cup C} \Rightarrow A \in \cup_{x \in C} 2^{x}$ and therefore $\displaystyle 2^{\cup C} \subseteq \cup_{x \in C} 2^{x}$ also. That means $\displaystyle \cup_{x \in C} 2^{x} = 2^{\cup C}$

Is there something wrong with this proof?
• Jun 10th 2011, 09:29 AM
MoeBlee
To me that seems like odd use of the '{ }' notation.

Ordinarily, $\displaystyle \cup_{x \in C} \{ 2^{x} \}$ = {A | Ex(x in C & A in {Px})} = {A | Ex(x in C & A = Px)}.
• Jun 10th 2011, 09:41 AM
MoeBlee
But I glean that the actual problem is this:

Show {A | Ex(x in C & A in Px)} subset PUC

So, let x in C and A subset x. Show A subset UC.

Suppose z in A. So z in x in C. So z in UC.

Done.
• Jun 10th 2011, 09:48 AM
omoplata
Quote:

Originally Posted by MoeBlee
To me that seems like odd use of the '{ }' notation.

Ordinarily, $\displaystyle \cup_{x \in C} \{ 2^{x} \}$ = {A | Ex(x in C & A in {Px})} = {A | Ex(x in C & A = Px)}.

Sorry, it should be $\displaystyle \cup_{x \in C} 2^{x}$, not $\displaystyle \cup_{x \in C} {2^{x}}$. I edited the original post and corrected it.
• Jun 10th 2011, 09:54 AM
omoplata
Quote:

Originally Posted by MoeBlee
But I glean that the actual problem is this:

Show {A | Ex(x in C & A in Px)} subset PUC

So, let x in C and A subset x. Show A subset UC.

Suppose z in A. So z in x in C. So z in UC.

Done.

Thanks. Now I understand why I can't go backwards. z in UC does not imply z in x.
• Jun 10th 2011, 10:22 AM
MoeBlee
So I take it you also wanted to check whether

PUC subset {A | Ex(x in C & A in Px)} is a theorem.

But counterexample:

Let C = {{0} {1}}. Let A = {0 1}.

There, A in PUC but there is no x in C such that A in Px.