Home Â» Algebra of Sets

# 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

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=Acâˆ© Bc  `

Solution:

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

`(b) (A âˆ©B)c = Acâˆª Bc  `

Solution:

`Let x âˆˆ (A âˆ©B)c â‡’ x âˆ‰  A âˆ© B    (âˆµ a âˆˆ A â‡” a âˆ‰ Ac)             â‡’ x âˆ‰  A or x âˆ‰ B             â‡’ x âˆˆ Ac and x âˆˆ Bc             â‡’ x âˆˆ Acâˆª Bc  âˆ´ (A âˆ©B)câŠ‚ (A âˆªB)c.................. (i)  Again, Let x âˆˆ Acâˆª Bc   â‡’ x âˆˆ Ac or x âˆˆ Bc              â‡’ x âˆ‰  A or x âˆ‰ B              â‡’ x âˆ‰  A âˆ© B              â‡’ x âˆˆ (A âˆ©B)c  âˆ´ Acâˆª BcâŠ‚ (A âˆ©B)c.................... (ii)  Combining (i) and (ii), we get(A âˆ©B)c=Acâˆª Bc. 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 âˆª Ac= U  `

Solution:

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

`(b) A âˆ© Ac=âˆ…  `

Solution:

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

`(c) Uc= âˆ…  `

Solution:

`Let x âˆˆ Uc   â‡” x âˆ‰ U â‡” x âˆˆ âˆ…      âˆ´ Uc= âˆ…. 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) (Ac )c A.  `

Solution:

`Let x âˆˆ (Ac )c â‡” x âˆ‰ Acâ‡”  x âˆˆ a       âˆ´ (Ac )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

Next TopicMultisets