Start Sets and Subsets Algebra of Sets Functions Caretesian Product Relations Denumerable Sets Test Message Board

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}

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.

#### 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.

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= AA,            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.

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.

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.

GENERALIZED OPERATIONS

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

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

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 Ai}. In an analogous way iJ Ai consists of those elements which belong to every A i for i J. In  other words, iJ Ai = {x | x Ai for every i J}.

Theorem: Let {Ai} i I be an indexed family of sets. Then for any set B,
(iÎIAi) = iÎI (B  Ai)
(iÎIAi) = iÎI (B  Ai)

GRAPHICAL PRESENTATION

It is usual to show the sets and the relations among them with the help of  drawings.

VENN EULER DIAGRAMS

Venn Euler diagrams illustrate the relationships between sets. Usually, non-empty sets are represented by the parts of plane. We have to point out that diagrams serve only to illustrate, not to prove the real relations among the sets. Here a simple plane area presents the set.

Example 1: Let S = {a, b, c, x, y}. A point of the plane presents every element of the set S.

Example 2. If we want to represent the non empty set S without pointing out every element, then we usually imagine that a point of the outstanding part of the plane represents every element of the set S. A subset of S will be represented as a part of the part ofthe plane that represents the set S.

Example 3. The universal set U is represented by a rectangle or bythe whole plane.

On this picture, the universe is sketched and two of his subsets, A and B, are pointed out.

HASSE DIAGRAMS

The relationship between sets canbe shown by the use of Hasse diagrams. Then the set on the higher level contains the set on the lower level.

Basic Operations | Disjoint Sets | Partition | Laws | Principle of Duality  | Indexed Sets | Generalized Operations | Graphical Presentation