Set theory. Is the converse true?

[omoplata]

Homework Statement

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

Homework Equations

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

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

The Attempt at a Solution

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

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

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

$A \subseteq ( \cup C )$

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

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

Therefore, $\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 $A \in 2^{\cup C}$ and go to $A \in \cup_{x \in C} \{ 2^{x} \}$. That means $A \in 2^{\cup C} \Rightarrow A \in \cup_{x \in C} \{ 2^{x} \}$ and therefore $2^{\cup C} \subseteq \cup_{x \in C} \{ 2^{x} \}$ also, which means $\cup_{x \in C} \{ 2^{x} \} = 2^{\cup C}$.

Is there something wrong with this proof?

 

[micromass]

Homework Statement

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

I don't like that notation. You should write it without the brackets;

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

With the brackets, things become, for example

$$\{2^A\}\cup\{2^B\}=\{2^A,2^B\}$$

which is not what you want...

Anyway...

Homework Equations

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

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

The Attempt at a Solution

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

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

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

$A \subseteq ( \cup C )$

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

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

Therefore, $\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 $A \in 2^{\cup C}$ and go to $A \in \cup_{x \in C} \{ 2^{x} \}$. That means $A \in 2^{\cup C} \Rightarrow A \in \cup_{x \in C} \{ 2^{x} \}$ and therefore $2^{\cup C} \subseteq \cup_{x \in C} \{ 2^{x} \}$ also, which means $\cup_{x \in C} \{ 2^{x} \} = 2^{\cup C}$.

Is there something wrong with this proof?

The proof is correct. However, you can't go backwards. The crucial step that you did, is this:$$\exists x \in C: A \subseteq x~~\Rightarrow~~A \subseteq ( \cup C )$$

This is valid (and you may want to prove this in more detail), but the converse is not (you may want to give a counterexample!).

 

[omoplata]

Oh, I think I understand now. There may be a $y \in C$ such that $y \nsubseteq 2^{y}$. So $A \subseteq (\cup C) \nRightarrow A \subseteq y$. So I can't go backwards?

Sorry about the notation.

 

[micromass]

There may be a $y \in C$ such that $y \nsubseteq 2^{y}$.

This makes no sense
Can you try and come up with a specific example that shows that the implication does not hold?

 

[omoplata]

Oops, I meant "There may be a $y \in C$ such that $A \nsubseteq 2^{y}$."

I'll try to think of a specific example. I'll post if I can't find one.

 

[omoplata]

The empty set?

 

[micromass]

The empty set?

What would you take empty? Can you elaborate?

 

[omoplata]

OK. I have a counterexample. Let $C = \{\{a\},\{b\}\}$ and $A = \{\{a, b\}\}$. So $A \subseteq (\cup C)$, but $\nexists x \in C : A \subseteq x$.

I think I was completely wrong in posts 3, 5 and 6.

 

[micromass]

Yes, if you meant A={a,b}. Be careful with that notation...

 

[omoplata]

Oh, OK. A = {a,b}. I had actually misunderstood the definition of $\cup C$. Thanks.