Introduction
The algebra of sets is for developing the fundamental properties of set operations.
The algebra of sets is the analog of the algebra of numbers. The algebra of union, intersection and complement operations satisfies various laws (identities), which we will see further in this article.
For the basic introduction of sets, see The Theory of set.
Law of Algebra of sets
Here we will see different laws of the algebra of sets under the various set operations.
Commutative laws
Commutative means that if the operands' order is changed, it doesn't make any difference in the result.
For any of the two finite sets, A and B,
- A U B = B U A
- A ∩ B = B ∩ A
Let’s prove the above identities to get a clear picture of the law.
To Prove: A ∪ B = B ∪ A
A ∪ B = B ∪ A
A ∪ B = {x: x ∈ A or x ∈ B}
= {x: x ∈ B or x ∈ A}
A ∪ B = B ∪ A
Hence Proved.
To Prove: A ∩ B = B ∩ A
A ∩ B = B ∩ A
A ∩ B = {x: x ∈ A and x ∈ B}
= {x: x ∈ B and x ∈ A}
A ∩ B = B ∩ A
Hence Proved.
Distributive Laws
The distributive law asserts that equality is always true in algebra.
- A ∪ (B ∩ C ) = (A ∪ B ) ∩ (A ∪ C )
- A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
To Prove: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
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.
To Prove: A ∩ (B ∪ C ) = (A ∩ B ) ∪ (A ∩ C )
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).... (1)
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).... (2)
Combining (1) and (2), we get A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∪ C)
Hence Proved.
Idempotent Laws
To prove: A ∪ A = A
As, 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.To prove: A ∩ A = A
As, 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.
Associative Laws
Associativity is a valid rule for replacing the expressions in logical proofs. For any of the three finite sets A, B, and C;
(i) (A U B) U C = A U (B U C)
(ii) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Thus, union and intersection are associative.
To prove : (A U B) U C = A U (B U C)
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.To prove : (A ∩ B) ∩ C = A ∩ (B ∩ C)
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.
De Morgan's Law
De Morgan's Law in mathematics consists of a pair of transformation rules in boolean algebra that relates the intersection and union of sets through complements.
For any of the two finite sets A and B;
(i) A – (B U C) = (A – B) ∩ (A – C)
(ii) A - (B ∩ C) = (A – B) U (A – C)
De Morgan's Laws can also be written or modified as:
(i) (A U B)’ = A' ∩ B'
(ii) (A ∩ B)’ = A' U B'
To prove : (A U B)' = A' ∩ B'
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.
To prove : (A ∩ B)' = A' U B'
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.
Identity Law
For any subset A of universal set U, the following identities hold:
- A ∪ ∅ = A
- A ∩ U = A
Complement Law
For any subset A of universal set U, the following identities hold:
- A ∪ A′ = U
- A ∩ A′ = ∅
More laws of the algebra of sets:
For any of the two finite sets A and B;
(i) A – B = A ∩ B'
(ii) B – A = B ∩ A'
(iii) A – B = A ⇔ A ∩ B = ∅
(iv) (A – B) U B = A U B
(v) (A – B) ∩ B = ∅
(vi) A ⊆ B ⇔ B' ⊆ A'
(vii) (A – B) U (B – A) = (A U B) – (A ∩ B)
234+ registered 
