**Sets**

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

SetSet

*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*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

**empty**

set.set

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.

*Equality of A and B is denoted by A=B.*

Two sets

Two sets

**A and B are equal**if and only if A and B have the same members.*We*

say that. We write A Í B as an abbreviation for

say that

**A is a subset of B**if and only if every member of A is also a member of B**.**

A is a subset of B

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]

*That is,*

P(A) denote the set of all subset of A, we shall call P(A),

P(A) denote the set of all subset of A, we shall call P(A),

**the power set of A.**

*P*(A) = {B : B Í A}

Example 1:

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

_{1}, a

_{2}, …, a

_{n}}, then

*P*(A) consists of f , the n sets {a

_{i}} containing single element,

nC

_{2}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

_{1}+ nC

_{2}+ ……….+ nC

_{n}= (1+1)

^{n}= 2

^{n}.

** **

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:

- A ÈA = A (Idempotent)

- A È B = B ÈA (Commutative)

- A È f = A

- (A È B) È C = A È (B È C) (Associative)

- A È B = B if and only if AÍ B

- A Í (A È B) and B Í (A
_{ }È B)

Given sets A and B, their

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:

- A Ç A = A (Idempotent)

- A Ç B = B Ç A (Commutative)

- A Ç f = f

- (A Ç B) Ç C = A Ç (B Ç C) (Associative)

- A Ç B = A if and only if A Í B

- (A Ç B) Í A and (A Ç B) Í B

**distributive law**.

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

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

**:**

Proof

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

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

*(A\B) È (B\A).*

The

The

**symmetric difference,**AD B**,**of sets A and B is the set*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.

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

_{1}, b

_{1}) and (a

_{2}, b

_{2}) are regarded as equal if and only if a

_{1}= a

_{2}and b

_{1}= b

_{2}. Thus, if A

consists of m elements a

_{1}, a

_{2}, … , a

_{m}and B consists of n elements b

_{1}, b

_{2}, … ,b

_{n}, then A ´ B consists of mn elements (a

_{i}, b

_{j}),

1 £ i £ m, 1 £ j £ n.

**In this section we shall discuss the motivation of Boolean algebra. From the Section 6.1.2, Algebra of Sets, it is interesting to**

6.1.4 Motivation of Boolean Algebra

6.1.4 Motivation of Boolean Algebra

observe that, if A is any set, then the binary operations, Ç and È on the set

*P*(A) satisfy the following properties

- Commutative law,

- Associative law,

- Absorption law,

- Idempotent property and

- 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**

absorption law, idempotent property and distributive law and uninary operation "

*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.algebraic structure.

## No comments:

Post a Comment