Sets and Motivation for Boolean Algebra

Sets

We devote this section to brief some set theoretic notions, which will play an essential role in the lattice theory.

Set is a collection of well-defined objects. An object belonging to a set is called member or element of the set.

In most cases, set will be defined by means of a characteristic property of the objects belonging to the set. That is, for a given
property P(x), let {x : P(x)} denote the set of all objects x such that P(x) is true. A set with no member is said to be an empty
set. We use upper case letters such as A, B, C, etc., to denote sets and lower case letters such as a, b, c, x, y, z, etc, to denote
members of the sets. We denote the fact that x is an element of the set S by x Î S, while x is not an element of S by x Ï S.

Two sets A and B are equal if and only if A and B have the same members. Equality of A and B is denoted by A=B. We
say that A is a subset of B if and only if every member of A is also a member of B. We write A Í B as an abbreviation for
A is a subset of B.

It is interesting to observe that, for all sets A, B and C, we have
(i) A Í A [Reflexive]
(ii) A Í B and BÍ A if and only if A=B
(iii) If A Í B, B Í C then AÍ C [transitive]


P(A) denote the set of all subset of A, we shall call P(A), the power set of A.
That is, P(A) = {B : B Í A}

Example 1:
Let A = {1,2,3}
Then P(A) = {f , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}.

Let A be a finite set of n elements, say A= {a₁, a₂, …, a_n}, then P(A) consists of f , the n sets {a_i} containing single element,
nC₂ sets {a_i, a_j / i ¹ j}containing two elements, etc. In general P(A) contains nC_i subsets containing i distinct elements of A, for
1£ i £ n. Therefore the number of elements in P(A) is 1+ nC₁ + nC₂ + ……….+ nC_n = (1+1)ⁿ = 2ⁿ.

Back to top

6.1.2 Algebra of Sets

In this section we define, union of two sets, intersection of two sets, complement of a set and we brief some of their basic
properties and their operations.
Given sets A and B, their union A È B consists of all elements in A or B or both.

That is, AÈ B = {x / x Î A or x Î B}.

It is interesting to observe that the union operation on sets has properties:

1. A ÈA = A (Idempotent)
   
2. A È B = B ÈA (Commutative)
   
3. A È f = A
   
4. (A È B) È C = A È (B È C) (Associative)
   
5. A È B = B if and only if AÍ B
   
6. A Í (A È B) and B Í (A È B)
   

Given sets A and B, their intersection A Ç B consists of all objects which are in both A and B.

Thus, A Ç B = {x / x Î A and x Î B} .Two sets A and B are said to be disjoint if and only if A Ç B = f .

The intersection operation on sets has the following evident properties:

1. A Ç A = A (Idempotent)
   
2. A Ç B = B Ç A (Commutative)
   
3. A Ç f = f
   
4. (A Ç B) Ç C = A Ç (B Ç C) (Associative)
   
5. A Ç B = A if and only if A Í B
   
6. (A Ç B) Í A and (A Ç B) Í B
   

An important property connecting È and Ç is the distributive law.

(i) A Ç (B È C) = (A Ç B) È (A Ç B)
(ii) A È (B È C) = (A È B)Ç (A È C)

Proof:

A Ç (B È C) = {x / x Î A and x Î B È C}
= {x / x Î A and (x Î B or xÎ C)}
= {x / (x Î A and x Î B) or (x Î A and x Î C)}
= {x / x Î A Ç B or xÎ A Ç C}
= (A Ç B) È (A È C)

Similarly, A È (B Ç C) = (A È B) Ç (A È C) can be proved.

It is very interesting to observe that A Ç (A È B) = A, for A Í (A È B) and A Í A,
therefore, A Ç (A È B) = A.

Similarly, A È (A Ç B) = A, for (A Ç B) Í A and A Í A, hence, A È (A Ç B) = A.

Thus, for sets A and B, we have,
AÇ (AÈ B) = A; AÈ (AÇ B) = A [Absorption law].

By the difference, B\A, of the sets B and A, we mean the set of all those objects in B which are not in A.

Thus, B\A = {x : x Î B and x Ï A}.

The symmetric difference, AD B, of sets A and B is the set (A\B) È (B\A).


Let X be given set. If we deal with subset of X then we call X is a universal set. If A Í X, then the complement of A
is defined to be X\A.
Thus, = {x / x Î X and x Ï A}

It is clear that whenever we use complements, it is assumed that we are dealing only with subset of some fixed universal set X.

The following properties can be easily verified:

6.1.3 Cartesian Products

In this section we define Cartesian product of sets. Cartesian product set A ´ B of two arbitrary sets A and B is the set of
all pairs (a, b) such that aÎ A and bÎ B. That is, A ´ B = {(a,b) / a Î A and bÎ B}. Note that the sets A and B need not be
distinct in the Cartesian product.

In the product A ´ B, the element (a₁, b₁) and (a₂, b₂) are regarded as equal if and only if a₁ = a₂ and b₁ = b₂. Thus, if A
consists of m elements a₁, a₂, … , a_m and B consists of n elements b₁, b₂, … ,b_n , then A ´ B consists of mn elements (a_i, b_j),
1 £ i £ m, 1 £ j £ n.
6.1.4 Motivation of Boolean Algebra

In this section we shall discuss the motivation of Boolean algebra. From the Section 6.1.2, Algebra of Sets, it is interesting to
observe that, if A is any set, then the binary operations, Ç and È on the set P(A) satisfy the following properties

1. Commutative law,
   
2. Associative law,
   
3. Absorption law,
   
4. Idempotent property and
   
5. Distributive law.

and the uninary " - " operation on P(A) satisfies the De Morgan's law. So it is tempting to ask the question:
"Are there other sets like P(A) and binary operations like È and Ç satisfying commutative law, associative law,
absorption law, idempotent property and distributive law and uninary operation " - " satisfying De Morgan's law?".

Indeed there are many such sets and such binary and uninary operations on such sets satisfying the above mentioned laws and
property. In fact, one of the main motivations of Boolean Algebra is a search of such sets and understanding their
algebraic structure.