What is the Relationship Between Union and Power Sets?

[Oxymoron]

I want to make sure I understand the meaning of membership and subset.

For example, if I have a set x, then is x a member/subset of the set

S = {{y},x}

I came to the conclusion that x is a member of the set S because S contains x as an element, and x is also a subset of S because S contains the set x and x is a subset of x. This doesn't sound right, I've used the same argument for two different things?? Hmmm...

But if

S = {y,{x}}

then x would NOT be a member of S because the set S does not contain the set x as an element (but it does contain the set {x} as an element and {x} \neq x). And x is also NOT a subset of S for reasons I cannot think of.

 

[Oxymoron]

Also, if I have the power set P(x), is x a member of P(x)?

If the set x is to be a member of the power set P(x) then P(x) must contain the set x. For example, let x = {a,b} then P(x) = {{},{a},{b},{a,b}}. And since if I remove the outer brackets I have {}, {a}, {b}, and {a,b} as members, and there is {a,b}! Since this will happen with whatever set x I start with, x will always be a member of P(x).

Is x a subset of P(x)?

I figured that since P(x) consists of all subsets of x and since x is a subset of itself, then x is a subset of P(x). Is it true that for every set x, x is always a subset of the power set P(x)?

 

[d_leet]

I want to make sure I understand the meaning of membership and subset.

For example, if I have a set x, then is x a member/subset of the set

S = {{y},x}

I came to the conclusion that x is a member of the set S because S contains x as an element, and x is also a subset of S because S contains the set x and x is a subset of x. This doesn't sound right, I've used the same argument for two different things?? Hmmm...

Yes x is a member of S, but x is not a subset of S, however {x} is a subeset of S.

But if

S = {y,{x}}

then x would NOT be a member of S because the set S does not contain the set x as an element (but it does contain the set {x} as an element and {x} \neq x). And x is also NOT a subset of S for reasons I cannot think of.

This is correct.

 

[d_leet]

Also, if I have the power set P(x), is x a member of P(x)?

I take it that x is a set? Then yes x belongs to P(x).

Is x a subset of P(x)?

I figured that since P(x) consists of all subsets of x and since x is a subset of itself, then x is a subset of P(x). Is it true that for every set x, x is always a subset of the power set P(x)?

P(x) is the SET of all subsets of x, so yes x is a subset of x and hence it will belong to P(x), but remember the conditions on a subset

A is a subset of B if for every element a in A a is also in B.

You should notice that none of the elements of x will belong to the power set of x and hence x is not a subset of P(X).

 

[Oxymoron]

Posted by d_leet

Yes x is a member of S, but x is not a subset of S, however {x} is a subeset of S.

Right. So {x} is a subset of S because every element of {x} is in S (namely the only element of {x} is x, and x is in S). However, not every element of x (say z) is in S because S contains only two distinct sets (namely x and {y}) and z is not one of these.

 

[d_leet]

Right. So {x} is a subset of S because every element of {x} is in S (namely the only element of {x} is x, and x is in S). However, not every element of x (say z) is in S because S contains only two distinct sets (namely x and {y}) and z is not one of these.

Also that x is not necessarily a set.

 

[Hurkyl]

You should notice that none of the elements of x will belong to the power set of x and hence x is not a subset of P(x).

That's not strictly true; if x is a transitive set, then it will be a subset of its power set. (if and only if)

 

[d_leet]

That's not strictly true; if x is a transitive set, then it will be a subset of its power set. (if and only if)

Thanks I didn't know that, is that the only case where a set will be a subset of its powerset?

 

[Oxymoron]

Posted by d_leet

I take it that x is a set?

Yes, I will always be assuming that x is a set.

 

[Oxymoron]

But what if my set was not P(x) but instead P({x})!?

P({x}) is the set of all subsets of {x}. But {x} is a set of one element, namely x, so P({x}) = {{},{x}} does it not? and x is not an member (but {x} would be!?).

Is x a subset of P({x})? No, would be my answer, because we cannot guarantee that a member of x is in P({x}) which contains only the empty set and the set containing the set x.

 

[d_leet]

But what if my set was not P(x) but instead P({x})!?

P({x}) is the set of all subsets of {x}. But {x} is a set of one element, namely x, so P({x}) = {{},{x}} does it not? and x is not an member (but {x} would be!?).

Is x a subset of P({x})? No, would be my answer, because we cannot guarantee that a member of x is in P({x}) which contains only the empty set and the set containing the set x.

Yes that would be correct again.

 

[Hurkyl]

I don't know if it will help, but (I think) if you assume the axiom of foundation, you can actually represent sets as trees. For example, the set {x, {y}} can be represented as:

   *
  / \
 /   \
x     *
      |
      |
      y

In this representation, an asterisk denotes the top of set, and all of the children of an asterisk are the elements of that set. (If x and y were themselves sets, you could substitute their trees into the above diagram)


I say "I think", because I'm pretty sure that the axiom of foundation guarantees every set can be drawn like this, but not 100% sure.

 

[Hurkyl]

Is x a subset of P({x})? No, would be my answer, because we cannot guarantee that a member of x is in P({x}) which contains only the empty set and the set containing the set x.

Technicalities again. The answer is yes if x is the empty set, or the set containing the empty set. (Or, if we reject the axiom of foundation, and allow x = {{x}} or x = {{}, {x}})

 

[Oxymoron]

Perhaps this will help: I will always assume that x is non-empty, x is not an member of itself, and y is not x.

 

[Oxymoron]

The Axiom of Foundation has not been covered in lectures yet, so I am pretty sure I am not meant to use it. However, your idea may come in handy never-the-less...I like it.

 

[Hurkyl]

Well, allowing recursion, and sets with transfinite depth is a sort of trappy thing, and not really needed for doing ordinary mathematics. So for most purposes, you're going to want to assume foundation. I mainly just want you to be aware of its necessity.

 

[Oxymoron]

What about U P(x), that is the union of the power set?

I figured that since the union is "like" bracket removal, x will not be a member. For example, take x = {1,2}. Then

U P(x) = U {{},{1},{2},{1,2}} = {} U {1} U {2} U {1,2} = ?? not sure what goes here.

 

[Oxymoron]

I was thinking, (assuming that x is not a member of itself and is non-empty), x is not a member of x BUT x is a member of {x}. So, would x be both a member AND an element of the set {{x},x}?

 

[Hurkyl]

Note that, in your particular case, U P(x) = {1, 2} = x. Can you prove the general case?

So, would x be both a member AND an element of the set {{x},x}?

Yes... but member and element are synonyms.

I think you meant to ask:

Would {x} be an element and a subset of {{x},x}?

And the answer would be yes.

 

[Oxymoron]

...you read my mind! ;)

 

[Oxymoron]

Posted by Hurkyl:

Note that, in your particular case, U P(x) = {1, 2} = x. Can you prove the general case?

No, but I am sure it is easy. Could you simply use the definition of "big"-union? The membership for the union of the power set P(X) is that x is in A_i for at least one i in the index set I. Note that A_i are the subsets of X. (so, say A_1 = {}, A_2 = {1}, A_3 = {2}, and A_4 = {1,2}). Then you could just argue that there does not exist an A_i which contains an element not in X. Therefore the union of the collection of all subsets of X (i.e. the power set of X) is exactly X.

 

[Hurkyl]

That's the idea. Now just clean it up! It's often easier to organize proofs like this as either proving:

a is in U P(x) iff a is in x

which is usually done by proving the if part and the only if part separately. I often find this more convenient than showing

x <= U P(x) and U P(x) <= x

(where <= means subset)

 

[Oxymoron]

(<=)
Suppose a is in x. Then a is in at least one of the subsets in the power set of x, since P(x) consists of all subsets of x. Then by the definition of union, a is in U P(x) because a is in at least one of the subsets. Therefore a is in U P(x).

(=>)
Suppose a is in U P(x). Then a is in at least one of the subsets of P(x). But the power set P(x) of a set x is the set of all subsets of x, therefore if a is in at least one of the subsets of P(x) is must be in x itself. Therefore a is in x.

Therefore a is in U P(x) <=> a is in x. Therefore U P(x) = x.

Does this look ok?