set union/intersections/compliments

Apr 2009
678
140
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?
 
May 2009
1,176
412
I am not entirely sure what the question is here...are you basically asking, Let \(\displaystyle S=\bigcup_{\lambda \in \Lambda}A_{\lambda}\) where \(\displaystyle \Lambda\) is some indexing set. Then every subset of \(\displaystyle S\) can be thought of as a product consisting only of the operations \(\displaystyle A_i \cap A_j\), \(\displaystyle A_i^{\prime}\cap A_j\), \(\displaystyle A_i \cap A_j^{\prime}\) and \(\displaystyle A_{i}^{\prime}\cap A_j^{\prime}\)? I do not think this is true. Let \(\displaystyle \Lambda = \{a, b\}\) (basically \(\displaystyle |\Lambda| = 2\)) and let \(\displaystyle A_a = \{1, 2, 3\}\) and \(\displaystyle A_b = \{3\}\). Thus \(\displaystyle S=A_a\). Then, \(\displaystyle A_a^{\prime} = \emptyset\), \(\displaystyle A_b^{\prime} = \{1, 2\}\) and your products will be, \(\displaystyle A_a \cap A_b = \{3\}\) \(\displaystyle A_a^{\prime} \cap A_b = \emptyset\) \(\displaystyle A_a \cap A_b^{\prime} = \{1, 2\}\) \(\displaystyle A_a^{\prime} \cap A_b^{\prime} = \emptyset\). Thus there is no way of getting the elements \(\displaystyle 1\) or \(\displaystyle 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 \(\displaystyle -A\) and \(\displaystyle \overline{A}\) are often used for \(\displaystyle S \setminus A = A \text{ complement} \).)
 
Last edited:
  • Like
Reactions: aman_cc
Apr 2009
678
140
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
 
May 2009
1,176
412
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 \(\displaystyle n\) subsets are all the subsets of \(\displaystyle S\)? I mean, What if \(\displaystyle S=\{1, 2, \ldots, n\}\) and \(\displaystyle A_i:=\{i\}\). Then the subsets which you construct are all empty...
 
Apr 2009
678
140
No they are not.

In your example

\(\displaystyle S=\{1, 2, \ldots, n\} \) and \(\displaystyle A_i=\{i\} \)

Consider
\(\displaystyle 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 \(\displaystyle 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,
\(\displaystyle
\{1\}, \{2\}, ... , \{i\}, ..., \{n\} \)

Is my question making sense now?
 
May 2009
1,176
412
So in general is,

\(\displaystyle 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?
 
Apr 2009
678
140
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 \(\displaystyle A_i\) as such, else complement it before taking the intersection.

For the above binary it would be
\(\displaystyle 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, \(\displaystyle \forall x \in S\) there exits a partition, \(\displaystyle S_i\), (infact a unqiue parition as all the partition are mutually exclusive) such that \(\displaystyle x \in S_i\)
 
May 2009
1,176
412
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 \(\displaystyle A_i\) as such, else complement it before taking the intersection.

For the above binary it would be
\(\displaystyle 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?
 
Apr 2009
678
140
Well I would say no becuase in the way you enumerated

\(\displaystyle 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 \(\displaystyle S_i\) for \(\displaystyle 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 \(\displaystyle A_1, A_2, .... A_n\)
3. Based on \(\displaystyle A_1, A_2, .... A_n\) we define partitions (as in my post above). In general there will be \(\displaystyle 2^n\) such partitions, some of which may be \(\displaystyle \phi\) (null set)
4. Now let X be any set whcih can be constructed from \(\displaystyle 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. \(\displaystyle A \cup B\)
3. \(\displaystyle A \cup B\)

Now to start with each of the subsets \(\displaystyle 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?
 
Last edited:
May 2009
1,176
412
Well I would say no becuase in the way you enumerated

\(\displaystyle 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 \(\displaystyle S_i\) for \(\displaystyle 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 \(\displaystyle A_1, A_2, .... A_n\)
3. Based on \(\displaystyle A_1, A_2, .... A_n\) we define partitions (as in my post above). In general there will be \(\displaystyle 2^n\) such partitions, some of which may be \(\displaystyle \phi\) (null set)
4. Now let X be any set whcih can be constructed from \(\displaystyle 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. \(\displaystyle A \cup B\)
3. \(\displaystyle A \cup B\)

Now to start with each of the subsets \(\displaystyle 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...).
 
  • Like
Reactions: aman_cc