*90*

# Algebra of Sets

Sets under the operations of union, intersection, and complement satisfy various laws (identities) which are listed in Table 1.

**Table: Law of Algebra of Sets **

Idempotent Laws | (a) A âˆª A = A | (b) A âˆ© A = A |

Associative Laws | (a) (A âˆª B) âˆª C = A âˆª (B âˆª C) | (b) (A âˆ© B) âˆ© C = A âˆ© (B âˆ© C) |

Commutative Laws | (a) A âˆª B = B âˆª A | (b) A âˆ© B = B âˆ© A |

Distributive Laws | (a) A âˆª (B âˆ© C) = (A âˆª B) âˆ© (A âˆª C) | (b) A âˆ© (B âˆª C) =(A âˆ© B) âˆª (A âˆ© C) |

De Morganâ€™s Laws | (a) (A âˆªB)^{c}=A^{c}âˆ© B^{c} | (b) (A âˆ©B)^{c}=A^{c}âˆª B^{c} |

Identity Laws | (a) A âˆª âˆ… = A (b) A âˆª U = U | (c) A âˆ© U =A (d) A âˆ© âˆ… = âˆ… |

Complement Laws | (a) A âˆª A^{c}= U(b) A âˆ© A ^{c}= âˆ… | (c) U^{c}= âˆ…(d) âˆ… ^{c} = U |

Involution Law | (a) (A^{c})^{c} = A |

Table 1 shows the law of algebra of sets.

### Example 1: Prove Idempotent Laws:

**Solution:**

Since, B âŠ‚ A âˆª B, therefore A âŠ‚ A âˆª A Let x âˆˆ A âˆª A â‡’ x âˆˆ A or x âˆˆ A â‡’ x âˆˆ A âˆ´ A âˆª A âŠ‚ A As A âˆª A âŠ‚ A and A âŠ‚ A âˆª A â‡’ A =A âˆª A. Hence Proved.

**Solution:**

Since, A âˆ© B âŠ‚ B, therefore A âˆ© A âŠ‚ A Let x âˆˆ A â‡’ x âˆˆ A and x âˆˆ A â‡’ x âˆˆ A âˆ© A âˆ´ A âŠ‚ A âˆ© A As A âˆ© A âŠ‚ A and A âŠ‚ A âˆ© A â‡’ A = A âˆ© A. Hence Proved.

### Example 2: Prove Associative Laws:

**Solution:**

Let some x âˆˆ (A'âˆª B) âˆª C â‡’ (x âˆˆ A or x âˆˆ B) or x âˆˆ C â‡’ x âˆˆ A or x âˆˆ B or x âˆˆ C â‡’ x âˆˆ A or (x âˆˆ B or x âˆˆ C) â‡’ x âˆˆ A or x âˆˆ B âˆª C â‡’ x âˆˆ A âˆª (B âˆª C). Similarly, if some x âˆˆ A âˆª (B âˆª C), then x âˆˆ (A âˆª B) âˆª C. Thus, any x âˆˆ A âˆª (B âˆª C) â‡” x âˆˆ (A âˆª B) âˆª C. Hence Proved.

**Solution:**

Let some x âˆˆ A âˆ© (B âˆ© C) â‡’ x âˆˆ A and x âˆˆ B âˆ© C â‡’ x âˆˆ A and (x âˆˆ B and x âˆˆ C) â‡’ x âˆˆ A and x âˆˆ B and x âˆˆ C â‡’ (x âˆˆ A and x âˆˆ B) and x âˆˆ C) â‡’ x âˆˆ A âˆ© B and x âˆˆ C â‡’ x âˆˆ (A âˆ© B) âˆ© C. Similarly, if some x âˆˆ A âˆ© (B âˆ© C), then x âˆˆ (A âˆ© B) âˆ© C Thus, any x âˆˆ (A âˆ© B) âˆ© C â‡” x âˆˆ A âˆ© (B âˆ© C). Hence Proved.

### Example3: Prove Commutative Laws

**Solution:**

To Prove A âˆª B = B âˆª A A âˆª B = {x: x âˆˆ A or x âˆˆ B} = {x: x âˆˆ B or x âˆˆ A} (âˆµ Order is not preserved in case of sets) A âˆª B = B âˆª A. Hence Proved.

**Solution:**

To Prove A âˆ© B = B âˆ© A A âˆ© B = {x: x âˆˆ A and x âˆˆ B} = {x: x âˆˆ B and x âˆˆ A} (âˆµ Order is not preserved in case of sets) A âˆ© B = B âˆ© A. Hence Proved.

### Example 4: Prove Distributive Laws

**Solution:**

To Prove Let x âˆˆ A âˆª (B âˆ© C) â‡’ x âˆˆ A or x âˆˆ B âˆ© C â‡’ (x âˆˆ A or x âˆˆ A) or (x âˆˆ B and x âˆˆ C) â‡’ (x âˆˆ A or x âˆˆ B) and (x âˆˆ A or x âˆˆ C) â‡’ x âˆˆ A âˆª B and x âˆˆ A âˆª C â‡’ x âˆˆ (A âˆª B) âˆ© (A âˆª C) Therefore, A âˆª (B âˆ© C) âŠ‚ (A âˆª B) âˆ© (A âˆª C)............(i) Again, Let y âˆˆ (A âˆª B) âˆ© (A âˆª C) â‡’ y âˆˆ A âˆª B and y âˆˆ A âˆª C â‡’ (y âˆˆ A or y âˆˆ B) and (y âˆˆ A or y âˆˆ C) â‡’ (y âˆˆ A and y âˆˆ A) or (y âˆˆ B and y âˆˆ C) â‡’ y âˆˆ A or y âˆˆ B âˆ© C â‡’ y âˆˆ A âˆª (B âˆ© C) Therefore, (A âˆª B) âˆ© (A âˆª C) âŠ‚ A âˆª (B âˆ© C)............(ii) Combining (i) and (ii), we get A âˆª (B âˆ© C) = (A âˆª B) âˆ© (A âˆª C). Hence Proved

**Solution:**

To Prove Let x âˆˆ A âˆ© (B âˆª C) â‡’ x âˆˆ A and x âˆˆ B âˆª C â‡’ (x âˆˆ A and x âˆˆ A) and (x âˆˆ B or x âˆˆ C) â‡’ (x âˆˆ A and x âˆˆ B) or (x âˆˆ A and x âˆˆ C) â‡’ x âˆˆ A âˆ© B or x âˆˆ A âˆ© C â‡’ x âˆˆ (A âˆ© B) âˆª (A âˆª C) Therefore, A âˆ© (B âˆª C) âŠ‚ (A âˆ© B) âˆª (A âˆª C)............ (i) Again, Let y âˆˆ (A âˆ© B) âˆª (A âˆª C) â‡’ y âˆˆ A âˆ© B or y âˆˆ A âˆ© C â‡’ (y âˆˆ A and y âˆˆ B) or (y âˆˆ A and y âˆˆ C) â‡’ (y âˆˆ A or y âˆˆ A) and (y âˆˆ B or y âˆˆ C) â‡’ y âˆˆ A and y âˆˆ B âˆª C â‡’ y âˆˆ A âˆ© (B âˆª C) Therefore, (A âˆ© B) âˆª (A âˆª C) âŠ‚ A âˆ© (B âˆª C)............ (ii) Combining (i) and (ii), we get A âˆ© (B âˆª C) = (A âˆ© B) âˆª (A âˆª C). Hence Proved

### Example 5: Prove De Morganâ€™s Laws

(a) (A âˆªB)^{c}=A^{c}âˆ© B^{c}

**Solution:**

To Prove (A âˆªB)^{c}=A^{c}âˆ© B^{c}Let x âˆˆ (A âˆªB)^{c}â‡’ x âˆ‰ A âˆª B(âˆµ a âˆˆ A â‡” a âˆ‰ A^{c}) â‡’ x âˆ‰ A and x âˆ‰ B â‡’ x âˆ‰ A^{c}and x âˆ‰ B^{c}â‡’ x âˆ‰ A^{c}âˆ© B^{c}Therefore, (A âˆªB)^{c}âŠ‚ A^{c}âˆ© B^{c}............. (i) Again, let x âˆˆ A^{c}âˆ© B^{c}â‡’ x âˆˆ A^{c}and x âˆˆ B^{c}â‡’ x âˆ‰ A and x âˆ‰ B â‡’ x âˆ‰ A âˆª B â‡’ x âˆˆ (A âˆªB)^{c}Therefore, A^{c}âˆ© B^{c}âŠ‚ (A âˆªB)^{c}............. (ii) Combining (i) and (ii), we get A^{c}âˆ© B^{c}=(A âˆªB)^{c}. Hence Proved.

(b) (A âˆ©B)^{c}= A^{c}âˆª B^{c}

**Solution:**

Let x âˆˆ (A âˆ©B)^{c}â‡’ x âˆ‰ A âˆ© B (âˆµ a âˆˆ A â‡” a âˆ‰ A^{c}) â‡’ x âˆ‰ A or x âˆ‰ B â‡’ x âˆˆ A^{c}and x âˆˆ B^{c}â‡’ x âˆˆ A^{c}âˆª B^{c}âˆ´ (A âˆ©B)^{c}âŠ‚ (A âˆªB)^{c}.................. (i) Again, Let x âˆˆ A^{c}âˆª B^{c}â‡’ x âˆˆ A^{c}or x âˆˆ B^{c}â‡’ x âˆ‰ A or x âˆ‰ B â‡’ x âˆ‰ A âˆ© B â‡’ x âˆˆ (A âˆ©B)^{c}âˆ´ A^{c}âˆª B^{c}âŠ‚ (A âˆ©B)^{c}.................... (ii) Combining (i) and (ii), we get(A âˆ©B)^{c}=A^{c}âˆª B^{c}. Hence Proved.

### Example 6: Prove Identity Laws.

**Solution:**

To Prove A âˆª âˆ… = A Let x âˆˆ A âˆª âˆ… â‡’ x âˆˆ A or x âˆˆ âˆ… â‡’ x âˆˆ A (âˆµx âˆˆ âˆ…, as âˆ… is the null set ) Therefore, x âˆˆ A âˆª âˆ… â‡’ x âˆˆ A Hence, A âˆª âˆ… âŠ‚ A. We know that A âŠ‚ A âˆª B for any set B. But for B = âˆ…, we have A âŠ‚ A âˆª âˆ… From above, A âŠ‚ A âˆª âˆ… , A âˆª âˆ… âŠ‚ A â‡’ A = A âˆª âˆ…. Hence Proved.

**Solution:**

To Prove A âˆ© âˆ… = âˆ… If x âˆˆ A, then x âˆ‰ âˆ… (âˆµâˆ… is a null set) Therefore, x âˆˆ A, x âˆ‰ âˆ… â‡’ A âˆ© âˆ… = âˆ…. Hence Proved.

**Solution:**

To Prove A âˆª U = U Every set is a subset of a universal set. âˆ´ A âˆª U âŠ† U Also, U âŠ† A âˆª U Therefore, A âˆª U = U. Hence Proved.

**Solution:**

To Prove A âˆ© U = A We know A âˆ© U âŠ‚ A................. (i) So we have to show that A âŠ‚ A âˆ© U Let x âˆˆ A â‡’ x âˆˆ A and x âˆˆ U (âˆµ A âŠ‚ U so x âˆˆ A â‡’ x âˆˆ U ) âˆ´ x âˆˆ A â‡’ x âˆˆ A âˆ© U âˆ´ A âŠ‚ A âˆ© U................. (ii) From (i) and (ii), we get A âˆ© U = A. Hence Proved.

### Example7: Prove Complement Laws

(a) A âˆª A^{c}= U

**Solution:**

To Prove A âˆª A^{c}= U Every set is a subset of U âˆ´ A âˆª A^{c}âŠ‚ U.................. (i) We have to show that U âŠ† A âˆª A^{c}Let x âˆˆ U â‡’ x âˆˆ A or x âˆ‰ A â‡’ x âˆˆ A or x âˆˆ A^{c}â‡’ x âˆˆ A âˆª A^{c}âˆ´ U âŠ† A âˆª A^{c}................... (ii) From (i) and (ii), we get A âˆª A^{c}= U. Hence Proved.

(b) A âˆ© A^{c}=âˆ…

**Solution:**

As âˆ… is the subset of every set âˆ´ âˆ… âŠ† A âˆ© A^{c}..................... (i) We have to show that A âˆ© A^{c}âŠ† âˆ… Let x âˆˆ A âˆ© A^{c}â‡’ x âˆˆ A and x âˆˆ A^{c}â‡’ x âˆˆ A and x âˆ‰ A â‡’ x âˆˆ âˆ… âˆ´ A âˆ© A^{c}âŠ‚âˆ…..................... (ii) From (i) and (ii), we get Aâˆ© A^{c}=âˆ…. Hence Proved.

(c) U^{c}= âˆ…

**Solution:**

Let x âˆˆ U^{c}â‡” x âˆ‰ U â‡” x âˆˆ âˆ… âˆ´ U^{c}= âˆ…. Hence Proved. (As U is the Universal Set).

(d) âˆ…^{c}= U

**Solution:**

Let x âˆˆ âˆ…^{c}â‡” x âˆ‰ âˆ… â‡” x âˆˆ U (As âˆ… is an empty set) âˆ´ âˆ…^{c}= U. Hence Proved.

### Example8: Prove Involution Law

(a) (A^{c})^{c}A.

**Solution:**

Let x âˆˆ (A^{c})^{c}â‡” x âˆ‰ A^{c}â‡” x âˆˆ a âˆ´ (A^{c})^{c}=A. Hence Proved.

## Duality:

The dual Eâˆ— of E is the equation obtained by replacing every occurrence of âˆª, âˆ©, U and âˆ… in E by âˆ©, âˆª, âˆ…, and U, respectively. For example, the dual of

It is noted as the principle of duality, that if any equation E is an identity, then its dual Eâˆ— is also an identity.

## Principle of Extension:

According to the Principle of Extension two sets, A and B are the same if and only if they have the same members. We denote equal sets by A=B.

## Cartesian product of two sets:

The Cartesian Product of two sets P and Q in that order is the set of all ordered pairs whose first member belongs to the set P and second member belong to set Q and is denoted by P x Q, i.e.,

**Example:** Let P = {a, b, c} and Q = {k, l, m, n}. Determine the Cartesian product of P and Q.

**Solution:** The Cartesian product of P and Q is