Laws of Algebra of Set
Laws of algebra of set
THEOREM 1 (Idempotent Laws) For any set A
(i) A ∪ A = A
(ii) A ∩ A = A
PROOF (i) A ∪ A= { x : x ∈ A or x ∈ A} ={x : x ∈ A} = A
(ii) A ∩ A = {x : x ∈ A and x ∈ A} = {x : x ∈ A} = A
THEOREM 2 (Identity laws) For any set A,
(ii) A ∩ Φ = A
PROOF (i) A ∪ Φ = {x : x ∈ A or x ∈ Φ} ={ x : x ∈ A} =A
(ii) A ∩ Φ = {x : x ∈ A and x ∈ Φ} = { x : x ∈ A} =A
THEOREM 3 (Commutative Laws) For any two sets A and B
(i) A ∪ B = B ∪ A
(ii) A ∩ B = B ∩ A
PROOF(i) Let x be an arbitrary element of A ∪ B
x ∈ A ∪ B ⇒x ∈ A or x ∈ B ⇒ x ∈ B or x ∈ A ⇒ x ∈ B ∪ A
A ∪ B ⊆ B ∪ A
Similarly, B ∪ A ⊆ A ∪ B
Hence, A ∪ B = B ∪ A
Note
Recall that two sets X and Y are equal iff(if only if) X ⊆ Y and Y ⊆ X
(ii) Let x be an arbitrary element of A ∩ B
x ∈ A ∩ B ⇒x ∈ A and x ∈ B ⇒ x ∈ B and x ∈ A ⇒ x ∈ B ∩ A
A ∩ B ⊆ B ∩ A
Similarly, B ∩ A ⊆ A ∩ B
Hence, A ∩ B = B ∩ A
THEOREM 4 (Associative laws), If A, B and C are any three sets, then
(i) (A ∪ B) ∪ C = A ∪ (B ∪ C)
(ii) (A ∩ B) ∩ C = A ∩ (B ∩ C)
PROOF (i) Let x be an arbitrary element of A ∪ (B ∪ C)
x ∈ (A ∪ B) ∪ C
⇒ x ∈ (A ∪ 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)
Then, (A ∪ B) ∪ C ⊆ A ∪ (B ∪ C)
Similarly, A ∪ (B ∪ C) ⊆ (A ∪ B) ∪ C
Hence, A ∪ (B ∪ C) = (A ∪ B) ∪ C
(ii) Let x be an arbitrary element of A ∩ (B ∩ C)
x ∈ (A ∩ B) ∩ C
⇒ x ∈ (A ∩ B) and x ∈ C
⇒ (x ∈ A and x ∈ B) and x ∈ C
⇒ x ∈ A and (x ∈ B and x ∈ C)
⇒ x ∈ A and x ∈ (B ∩ C)
⇒ x ∈ A ∩ (B ∩ C)
Then, (A ∩ B) ∩ C ⊆ A ∩ (B ∩ C)
Similarly, A ∩ (B ∩ C) ⊆ (A ∩ B) ∩ C
Hence, A ∩ (B ∩ C) = (A ∩ B) ∩ C