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.