Start
Sets and Subsets
Algebra of Sets
Functions
Caretesian Product
Relations
Denumerable Sets
Test
Message Board
Basic Operations| Disjoint Sets| Partition| Laws| Principle of Duality  | Indexed Sets| Generalized Operations| Graphical Presentation

 

 ALGEBRA OF SETS

 

BASIC OPERATIONS

As we have introduced meaning of the terms set, subset, null set and universal set, we can learn how to build new sets using the sets we already know. The way we do it is called set operations.

The set operations are: union, intersection, difference and complement. They are called Boolean operations.

Let A and B be subsets of the universal set U. Then we can look at the set C U that contains all elements of set A and all elements of set B and nothing else. In other words, x C implies two statements: x A or xB. Shortly, we describe set C with

C = { x | xU, x A or xB}

Union

The union of sets A and B is the set of all elements which belong to A, to B or to both. It is denoted by A B,

AB={x | x U, xA or x B}.

The conjunction “or” permits that x is an element in set A and an element in set B. We can say that x is an element of the set AB because of the three reasons:
if xA, then xA B;
if xB, then x AB;
if xA and x B, then xA B.

In the other words, we can observe the set C U, which contains all elements of set A and all elements of set B, but no other elements. C = AB.

The union of sets is the smallest subset of U, which embraces sets A and B as its subsets.

Intersection

However, sets A and B also define a set of elements that are common to both of them.

The intersection of sets A and B is the set of elements that are common to sets A and B. It is denoted by A B and is also a subset of U.

AB ={x | x U, xA and x B}

Thus, for sets A, B U completely defined is the set D, which consists of those and only those elements of U that are in A and in B at the same time.

Set D is the intersection of sets A and B.

D= A B.

 

Difference

The difference of sets A and B is the set of elements which belong to A, but do not belong to B. It is denoted by A – B or A \ B.

A \ B = {x | x U, x A and x B}

 

Complement Set

Let U be the universal set and A U, A U set whose elements are all points inside the figure that is a part of the square that represents the universal set U. Condition A U implies that there exists at least one element b U which is not in A. That element is somewhere outside of the drawn figure. Take a look to the all elements of set U which are not in A. They form a set which is called the complement of A regarding U and is denoted by AC . If we denote the set of all Blondies by U and by P the sentence “Mary belongs to the set of Blondies who do not speak French”, then the set of Blondies who do not speak French is a complement of the set of Blondies who speak French. So, AC is a set of those elements b in U which are not in A. It is denoted by

AC = {b | b U, bA}     

Back to Top.

 

DISJOINT SETS

If sets A and B have no common elements i.e. no element of A is inB and no element of B is in A, then A and B are disjoint.

In that case, set D is a set with no elements. The intersection ofsets A and B is the null set.

Example: Suppose A and B are not comparable. If they are disjoint,they can be represented by the diagram on the left. If they are notdisjoint, they can be represented by the diagram on the right.

 

Back to Top

 

POWER SET AND PARTITION OF SET

Sometimes, for a better understanding of the characteristics of a set, it is useful to know some of its parts.

Let A be a non-empty set. A power set of the set A is the set of all subsets of  A. A partition of the set A is a collection of non-empty disjoint subsets of A, whose union is A.

Example for a partition of a set: Let X denote the set of all employees of one big company divided in several departments. We can say that employees are elements of disjoint subsets because each employee belongs to a different department. The union of those subsets is the set of all employees of the company. Each department has a chief. We can say that the chief is a representative of a subset.

Let U be any non empty set and let P(U) denote the set of all subsets of U. Set P(U) is called the power set of the set U . Elements of the set P(U) are subsets of the set U.

We say that non-empty sets Ai, Ai P(U) make a partition of a set U if U= Ai, Ai Aj= , for i j. Sets Ai are called the members of the partition. Each Ai is called an equivalence class of U.

Suppose that U has only one element, i.e. U={a}. Such a set is called a one member set. In that case, P(U) is a two member set, because it contains only the set U and the null set, P(U)={ , U}.

Take a look at this example for a power set: if we have a two member set U={a, b}, a b, then P(U)={ ,{a},{b}, U}. We have to point out that a is not an element of the set P(U), but the set {a }, which contains a as a single element, is subset of U and under these circumstances is element of P(U). The power set of a two member set has 2 2=4 elements. Generally, the power set of a set with n elements consists of 2n members.

Take a look at an example for the partition of a set: let S = {1, 2, 3, 4, 5, 6}. Then the elements of the partition of S are: A1={1, 2}; A2 = {3, 4, 5}; A3= {6} or A1={1}; A2={2, 3}; A3={4}; A4={5, 6}or A 1={1,2,3}; A2={4,5,6}, etc.

Take a look to the set of all natural numbers N. Then one of its partitions is the set of odd and even numbers, i.e., {2N, 2N0+1}. Here, the elements are A1={2N} and A2={2N0 +1}. We know that N=2N (2N0+1).

Axiom of pair: If A and B are sets, then there exists a set F, that contains the set A and set B.

Axiom of specification: Let U be any set and P any statement. Then there exists a subset A U whose elements are those and only those elements from U that fulfill this statement P. Then U = {a | a  A, P(a ) is true}

According to the axiom of specification, there is a set that contains only A and B. That set is called a pair and is denoted by {A, B}.

Axiom of power set: For each set A there exists a set P(A), which is called the power set of the set A and whose elements are subsets of A.

Back to Top

LAWS OF THE ALGEBRA OF SETS

The power set of non-empty set U, set P(U), together with operations union, intersection, difference and complement ( , , c) and their characteristics is called algebra of sets. Let A, B, C be subsets of universal set U.

Then follows the laws of the algebra of sets:

1. Commutative Laws
A B=B A,           A B=B A

2. Associative Laws
(A B) C=A (B C),            (A B) C=A (B C)

3. Idempotent Laws
A A=A,            A A=A

4. Distributive Laws
A (B C)=(A B) (A C),            A (B C)=(A B) (A C)

5. De Morgan Laws
A = ,            AU=U< BR> (A B)C =AC BC,            (A B)C=AC BC

6. Complement Laws
 (AC)C=A

 

1. Let us prove commutative laws:

( x) (x A B) (x A or x B) (according to definition of union ) (x B or x A)       

( x) (x A B) (x A and x B)   (according to definition of  intersection) (x B and x A)       

2. Let’s prove the associative law. Therefore, we have to prove these two statements:

a)      (A B) C A (B C),     

b)       A (B C) (A B) C.

Let’s prove a).

Let x be any element in the set (A B) C,

x (A B) C.

Then xA B and x C.

x A B implies x A and x B.

So, we have x A, x B and x C.

We can write it on this way: x A and x B C,

Therefore, xA (B C).

We see that from x (A B) C outcomes xA (B C). Statement a) is proven.

Let’s prove the statement b).

Let xA (B C). Then x A and x B C. From x B C outcomes x B and x C.

Now we have shown that x A, x B and x C.

Therefore, x A B and x C.       

Then x (A B) C. Statement b) is proven.

From (A B) C A (B C) and A (B C) (A B) C       

outcomes (A B) C=A (B C).

3. Let us prove idempotent laws:

(x) (xAA)xA or xAx A

(x) (xAA)xA and xAx A

4. Lets prove now distributive law from to , i. e. A(BC)=(AB)(A C)

We have to prove following two statements:

a)      A(BC)(AB)(AC)

b)      (AB)(AC) A(BC).

Let x A(BC). Then xA or xBC, or x is an element in both sets, xA and xBC. If xA, then x AB and xAC.

Therefore, x(AB)(A C).

If x BC, then xB and xC. Then xAB and xA C.

So, x(AB)(AC). Statement a) is proven.

Let’s prove statement b).

Let x(AB)(AC). Then        x AB and xAC.       

If xA, then xA(BC) and statement b) is proven.

If xA, then xB, because xAB, and also xC, because xAC.

That means if xA, then xB and xC, i.e. xBC.

Therefore in any case from x (AB)(AC) outcomes x A(BC) and statement b) is proven.

From A(BC)(AB)(AC) and (AB)(AC) A (BC) outcomes A(BC) (AB) (AC).

5. Let us prove De Morgan laws:

A = ,            A U=U

(A B)C =AC BC,            (A B)C=AC BC

Each of the sets A and contains A as a subset,

(A ) A and (A )

Since null set is a subset of every set, then (A ). Hence A = .

The sets U and A are always subsets of A U,

A (A  U) and U (A  U)

But every set is a subset of the universal set, (A U) U and according to the definition of equality of two sets follows A U=U.

(A B)c (according to the definition of complement) U\(A B)

(U\A) (U\B)

Ac Bc

(A B)c by the definition of complement U\(A B)

(U\A) (U\B)

Ac Bc

6. Let us prove complement laws:

On the first way let it be A Ac=S Then A S and       Ac S:      

(Ac)c (S\Ac)

A

On the second way let it be A . Then ( x) xA or x A.

x A x Ac

x (Ac)c

x Ax Ac

x (Ac)c

That was the proof.

Set operations as union and intersection are defined on the same way on any number of sets. Let F be any number of sets, i.e. F is set which elements are sets. Then union of F is

B= A F A, i.e. B= A(A F)

the smallest set, which contains all elements from all, sets A from F and nothing else.

We can say that more precisely: xB if and only if x is element of at least one member of F.

Analogous is defined the intersection of any number of sets,

D= AF  A,            D=A(AF)

as “the biggest” set that is contained in each set of F. In the other words: yD, if and only if y is element of each element A from F.

Accordingly we introduce de Morgans theorems:

( A)C= AC (A F)

( A)C= AC (A F)

Accepting the existence of union of any number of sets is so natural that we take it as an axiom.

Axiom of union: Let F be non-empty set of sets. Then exist such a set B for which is valid that xA for at least one AF xB.
 
Back to Top

 

PRINCIPLE OF DUALITY

If we interchange and and also U and in any statement about sets, then the new statement is called the dual of the original one.

Definition: If certain axioms imply their own duals, then the dual of any theorem that is a consequence of the axioms is also a consequence of the axioms.
For, given any theorem and its proof, the dual of the theorem can be proven in the same way by using the dual of each step in the original proof. Thus the principle of duality applies to the algebra of sets.
 
Back to Top

 

INDEXED SETS

Definition: An indexed family of sets {Ai}iI is a function f : I A, where the domain of f is the index set I and the range of f is a family of sets.
 
Back to Top

 

GENERALIZED OPERATIONS

For two subsets A, B  U, the following sets are defined:

A   B = {x U | x A or x B},

A   B = {x U | x A and x B},

A \ B = {x U | x A, x B}

 

Example:

Let the universal set U be the set of all natural numbers N. If A = {1, 2, 3, 4} and B = {2, 3, 5, 6} then A B = {1, 2, 3, 4, 5, 6} and A B = {2, 3}

and A\B = {1, 4} and B\A = {5, 6}.

It is obvious that

A    = A,

A    = A,

A  A = A,

A  A = A,

A  U = U,

A  U = A.

 

We denote the union and the intersection for a finite number of sets A1, A2, …, An, by

ni=1 Ai A1 A2 … An

ni=1 Ai  A1 A2 … An

Consider the indexed family of sets {Ai} i I and let J I. Then iJAi consists of those elements which belong to at least one Ai where i J.   Specifically, iJ Ai = {x | there exists an i J such  that x