4. Sets Algebra

 

Sets Algebra

Sets under the operations of union, intersection, and complement satisfy various laws(identities) which are as:

Idempotent Laws	A ∪ A = A	A ∩ A = A
Associative Laws	(A ∪ B) ∪ C = A ∪ (B ∪ C)	(A ∩ B) ∩ C = A ∩ (B ∩ C)
Commutative Laws	A ∪ B = B ∪ A	A ∩ B = B ∩ A
Distributive Laws	A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)	A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
De Morgan's Laws	(A ∪ B)c = Ac ∩ Bc	(A ∩ B)c = Ac ∪ Bc
Identity Laws	A ∪ ∅ = A A ∪ U = U	A ∩ ∅ = ∅ A ∩ U = A
Complement Laws	A ∪ Ac = U A ∩ Ac = ∅	Uc = ∅ Φc = U
Involution Law	(Ac)c = A

Associative Laws

Commutative Laws

Distributive Laws

De Morgan's Laws

Duality

Suppose E is an equation of set algebra. The dual E^* of E is the equation obtained by replacing each occurrence of ∩, ∪, U and ∅ in E by ∪, ∩, ∅ and U respectively.

For example:

1. If the equation E is:
   A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
   then the dual equation E^* is:
   A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
2. If the equation E is:
   (U ∩ A) ∪ (B ∩ A) = A
   then the dual equation E^* is:
   (∅ ∪ A) ∩ (B ∪ A) = A

It is the fact of set algebra, called the principle of duality, that, if any equation E is an identity, then its dual E^* is also an identity.

The Inclusion-Exclusion Principle

Let A and B be any two finite sets. Then

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

To find the number of elements in the union A ∪ B, we add the number of elements in the set A and set B and then subtract the number of elements in the intersection A ∩ B. That is we include n(A) and n(B), and we exclude n(A ∩ B).

For any three finite sets A, B and C

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C)

That is we include n(A), n(B) and n(C), we exclude n(A ∩ B), n(A ∩ C) and n(B ∩ C), and we include n(A ∩ B ∩ C).

The Cartesian Product of Sets

If A and B are two sets, then the cartesian product (or cross product or direct product) of A and B is the set of all ordered pairs whose first members belongs to the set A and second member belongs to the set B and is denoted by A x B, i.e.

A x B = {(a, b) : a ∈ A and b ∈ B}

The cartesian product of A x A is denoted as A₂. For any general product

A_n = {(a₁, a₂, ... , a_n) : a_i ∈ A and i = 1, 2, ...., n}

Example: Let A = {1, 2} and B = {1, 2, 3}
then A x B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}

Previous                                 Next