set union/intersections/compliments

**aman_cc** · July 15th 2010, 11:58 PM

I have been thinking about this - do not know if there is any formal way to approcah this problem

Few definitions

S = Universal set
A,B,C,D,.... = Subsets of S
A' = compliment of A
+ = union on sets
. = intersection of sets

Let me take a case when there are just two subsets A and B

Now, A.B, A'.B, A.B', A'.B' - partition S into mutually exclusive and exhaustive sets.

Now any 'valid' operation on A and B (using +,.,') will represent a set in S, say X
Then this X can be representes a union of some/all of A.B, A'.B, A.B', A'.B'

For e.g A+B = A.B + A'.B + A.B'

X can be as complicated as you want. (by repeatedly applying these operators in a consistent way)

Now I have two questions
1. How do you prove the above result - in a most generalized form?
2. Will the proof / result change if
a> S has infinite elements
b> S has infinite subsets

I do have an idea but am getting mixed up. Any help/pointers plz?

**Swlabr** · July 16th 2010, 12:56 AM

I am not entirely sure what the question is here...are you basically asking, Let $S=\bigcup_{\lambda \in \Lambda}A_{\lambda}$ where $\Lambda$ is some indexing set. Then every subset of $S$ can be thought of as a product consisting only of the operations $A_i \cap A_j$ , $A_i^{\prime}\cap A_j$ , $A_i \cap A_j^{\prime}$ and $A_{i}^{\prime}\cap A_j^{\prime}$ ? I do not think this is true. Let $\Lambda = \{a, b\}$ (basically $|\Lambda| = 2$ ) and let $A_a = \{1, 2, 3\}$ and $A_b = \{3\}$ . Thus $S=A_a$ . Then, $A_a^{\prime} = \emptyset$ , $A_b^{\prime} = \{1, 2\}$ and your products will be, $A_a \cap A_b = \{3\}$ $A_a^{\prime} \cap A_b = \emptyset$ $A_a \cap A_b^{\prime} = \{1, 2\}$ $A_a^{\prime} \cap A_b^{\prime} = \emptyset$ . Thus there is no way of getting the elements $1$ or $2$ to be in a singleton set, which is a contradiction. However, I am unsure if this was actually your question... Also - use LaTeX! \cap is intersection, \cup is union, \{ is left curly bracket while \} is the right. See here. (Also, I believe that $-A$ and $\overline{A}$ are often used for $S \setminus A = A \text{ complement}$ .)

**aman_cc** · July 18th 2010, 08:49 PM

Sorry if my question was not clear. I'm not asking what you have understood.

Let me repeat it

Definitions -
S = Universal set
A,B,C,D,.... = Subsets of S
A' = compliment of A
+ = union on sets
. = intersection of sets
(this notation makes it easier to write the problem below)

Let there be 'n' subsets of S - A1, A2, A3, ...., An (any 'n' subsets will do)

Consider 2^n subsets -
A1.A2.A3...An-1.An
A1.A2.A3....An-1.An'
....
..
These 2^n subsets partition S into mutually exclusive and exhaustive sets. (This is easy to prove)

Now consider operations -
1. Union, +
2. Intersection, .
3. Compliment, '

Using the above operations and {A1,A2,A3,....,An} sets we can construct a new set, for e.g.
X = ((A1+A2)'.A3)+A7

Prove that any such, X, can be represented as union of (some or all of the 2^n) partitions we constructed above.

Will this proof change if
a> S has infinite elements
b> S has infinite subsets

**Swlabr** · July 19th 2010, 12:18 AM

Originally Posted by aman_cc

Sorry if my question was not clear. I'm not asking what you have understood.

Let me repeat it

Definitions -
S = Universal set
A,B,C,D,.... = Subsets of S
A' = compliment of A
+ = union on sets
. = intersection of sets
(this notation makes it easier to write the problem below)

Let there be 'n' subsets of S - A1, A2, A3, ...., An (any 'n' subsets will do)

Consider 2^n subsets -
A1.A2.A3...An-1.An
A1.A2.A3....An-1.An'
....
..
These 2^n subsets partition S into mutually exclusive and exhaustive sets. (This is easy to prove)

Now consider operations -
1. Union, +
2. Intersection, .
3. Compliment, '

Using the above operations and {A1,A2,A3,....,An} sets we can construct a new set, for e.g.
X = ((A1+A2)'.A3)+A7

Prove that any such, X, can be represented as union of (some or all of the 2^n) partitions we constructed above.

Will this proof change if
a> S has infinite elements
b> S has infinite subsets

It may be easier to write, but it certainly isn't easier to read!

I'm still not really understanding you though. Are you saying that these $n$ subsets are all the subsets of $S$ ? I mean, What if $S=\{1, 2, \ldots, n\}$ and $A_i:=\{i\}$ . Then the subsets which you construct are all empty...

**aman_cc** · July 19th 2010, 02:45 AM

No they are not.

In your example

$S=\{1, 2, \ldots, n\}$ and $A_i=\{i\}$

Consider
$S_1 = A_1'.A_2'.A_3'...A_{i-1}'.A_{i}.A_{i-1}'.....A_n' = \{i\}$ (Please note - Here a . represent intersection)

So out of $2^n$ such subsets only 'n' are non-empty, rest all are empty. Nevertheless we have partionioned the universal set S into mutually exclusive and exhaustive susets, namely,
$<br /> \{1\}, \{2\}, ... , \{i\}, ..., \{n\}$

Is my question making sense now?

**Swlabr** · July 19th 2010, 02:53 AM

So in general is,

$S_i:=A_1^{\prime} \cap A_2^{\prime} \cap \ldots \cap A_{i-1}^{\prime} \cap A_i \cap A_{i+1}^{\prime} \cap \ldots \cap A_n^{\prime}$ ?

Also, what do you mean by exhaustive?

**aman_cc** · July 19th 2010, 03:02 AM

Not really

The partitions which are created by 'n' subsets of S, can be represented as an 'n' digit binary number
say 0100....001
Where ever you have 1 - Take $A_i$ as such, else complement it before taking the intersection.

For the above binary it would be
$S_i =A_1^{\prime} \cap A_2 \cap \ldots \cap A_i^{\prime} \ldots \cap A_n^$

What you wrote works only in the specific example you gave. (A better way to visualize these partitios is to consider any two subsets of S and see what each of the partition as I define them is in the Venn Diagram)

By exhaustive, I mean, $\forall x \in S$ there exits a partition, $S_i$ , (infact a unqiue parition as all the partition are mutually exclusive) such that $x \in S_i$

**Swlabr** · July 19th 2010, 03:06 AM

Originally Posted by aman_cc

Not really

The partitions which are created by 'n' subsets of S, can be represented as an 'n' digit binary number
say 0100....001
Where ever you have 1 - Take $A_i$ as such, else complement it before taking the intersection.

For the above binary it would be
$S_i =A_1^{\prime} \cap A_2 \cap \ldots \cap A_i^{\prime} \ldots \cap A_n^$

What you wrote works only in the specific example you gave. (A better way to visualize these partitios is to consider any two subsets of S and see what each of the partition as I define them is in the Venn Diagram)

Isn't that what I wrote?

**aman_cc** · July 19th 2010, 03:50 AM

Well I would say no becuase in the way you enumerated

$S_i:=A_1^{\prime} \cap A_2^{\prime} \cap \ldots \cap A_{i-1}^{\prime} \cap A_i \cap A_{i+1}^{\prime} \cap \ldots \cap A_n^{\prime}$

How would you define $S_i$ for $i \notin \{1,2,..,n\}$

Sorry if this is getting more and more confusing - seems I am not able to convey the crux of the problem.

This is what it is
1. Let there be any universal set S
2. Let there be any subsets of this universal set, we call them $A_1, A_2, .... A_n$
3. Based on $A_1, A_2, .... A_n$ we define partitions (as in my post above). In general there will be $2^n$ such partitions, some of which may be $\phi$ (null set)
4. Now let X be any set whcih can be constructed from $A_1, A_2, .... A_n$ using the operators below
a> Intersection
b> Union
c> Complement
5. Prove that X can be represented as union of partitions (as we defined them in step 3 above)

Also I would write down how I think we can proceed with the proof.
Show that if there are any two subsets of S, A and B where A,B can be expressed as union of the partitions then each of the following can also be expressed as union of paritions
1. A' (or B')
2. $A \cup B$
3. $A \cup B$

Now to start with each of the subsets $A_i$ can be expressed as sum of partitions hence any X can also be.

What I am struggling with is the case when we make 'n' infinite. Not sure if my logic breaks down somewhere?

**Swlabr** · July 19th 2010, 06:51 AM

Originally Posted by aman_cc

Well I would say no becuase in the way you enumerated

$S_i:=A_1^{\prime} \cap A_2^{\prime} \cap \ldots \cap A_{i-1}^{\prime} \cap A_i \cap A_{i+1}^{\prime} \cap \ldots \cap A_n^{\prime}$

How would you define $S_i$ for $i \notin \{1,2,..,n\}$

Sorry if this is getting more and more confusing - seems I am not able to convey the crux of the problem.

This is what it is
1. Let there be any universal set S
2. Let there be any subsets of this universal set, we call them $A_1, A_2, .... A_n$
3. Based on $A_1, A_2, .... A_n$ we define partitions (as in my post above). In general there will be $2^n$ such partitions, some of which may be $\phi$ (null set)
4. Now let X be any set whcih can be constructed from $A_1, A_2, .... A_n$ using the operators below
a> Intersection
b> Union
c> Complement
5. Prove that X can be represented as union of partitions (as we defined them in step 3 above)

Also I would write down how I think we can proceed with the proof.
Show that if there are any two subsets of S, A and B where A,B can be expressed as union of the partitions then each of the following can also be expressed as union of paritions
1. A' (or B')
2. $A \cup B$
3. $A \cup B$

Now to start with each of the subsets $A_i$ can be expressed as sum of partitions hence any X can also be.

What I am struggling with is the case when we make 'n' infinite. Not sure if my logic breaks down somewhere?

Induct on the number of operations you have. That is, you want to show that if you take a union of partitions, A, and union or intersect it with one of your sets, or take its complement, and see if you get a union of partitions. The complement and union are obvious, so concentrate on intersection.

This method clearly does not depend on the number of partitions, but does depend on the number of operations you are performing (so you can't take an infinite intersection or something). If you are going to take an infinite intersection then I'm not actually sure if your result holds (think of open sets in a topological space...).

**aman_cc** · July 19th 2010, 07:02 AM

Yes - it is the infinite case that is troubling me. Anyways thanks for your patience

**Swlabr** · July 19th 2010, 07:05 AM

Originally Posted by aman_cc

Yes - it is the infinite case that is troubling me. Anyways thanks for your patience

Which infinite case - the case of infinite products (e.g. taking an infinite intersection) or the case of an infinite number of partitions (which is what your fist post seems to imply). The two cases are different.

**aman_cc** · July 19th 2010, 10:04 PM

Infact both. But as of now I was thinking more on infinite number of partitions - I don't seem to able to think or even appreciate what challenges does this offer

**Swlabr** · July 20th 2010, 04:41 AM

My method, above, covers this (I mention that it covers it in the bottom paragraph, first line).

Thread: set union/intersections/compliments

LinkBack

Thread Tools

Display

set union/intersections/compliments

Similar Math Help Forum Discussions

conclude that the closure of a union is the union of the closures.

Intersections Q

Proofs involving sets and their compliments

stats probability/compliments

intersections

Search Tags