Mathematics.

set algebra

Set Identities

Set Theory20 minDifficulty2 out of 10

You should know: set basics, venn diagrams

Overview

Set identities are the algebraic laws that govern union, intersection, and complement, mirroring the laws of ordinary arithmetic (and Boolean algebra) with ∪ playing the role of + and ∩ the role of ×. They include commutativity, associativity, distributivity, idempotence, and De Morgan's laws, and they hold for every choice of sets drawn from a common universe. Because these identities can be proved once and reused everywhere, they let mathematicians manipulate complicated set expressions symbolically instead of re-checking membership by hand each time.

Intuition

Each identity is a statement that two descriptions of a region in a Venn diagram always pick out the same set of points, no matter how A, B, C are drawn. De Morgan's laws, for instance, say 'everything outside (A or B)' is the same as 'outside A AND outside B' — shading the Venn diagram both ways produces an identical picture. Because these laws hold for arbitrary sets, they act like algebraic tools: you can substitute one side of an identity for the other inside a larger expression to simplify it, exactly as you'd factor or expand in ordinary algebra.

Formal Definition

Definition

For sets A, B, C within a universal set U, the algebra of sets satisfies:

A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
Distributivity of ∩ over ∪
A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
Distributivity of ∪ over ∩
(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc(A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c
De Morgan's laws
A∖B=A∩BcA \setminus B = A \cap B^c
Set difference in terms of intersection and complement

Worked Examples

  1. Compute the left side: A ∪ B = {1,2,3}, so its complement in U is {4}.

    (A∪B)c={1,2,3,4}∖{1,2,3}={4}(A \cup B)^c = \{1,2,3,4\} \setminus \{1,2,3\} = \{4\}

  2. Compute the right side: Aᶜ = {3,4}, Bᶜ = {1,4}, so Aᶜ ∩ Bᶜ = {4}.

    Ac∩Bc={3,4}∩{1,4}={4}A^c \cap B^c = \{3,4\} \cap \{1,4\} = \{4\}

Answer: Both sides equal {4}, confirming the identity for this example.

Practice Problems

Difficulty 2/10

State the De Morgan's law for the complement of a union, (A ∪ B)ᶜ.

Difficulty 3/10

Which identity correctly expresses A ∪ (B ∩ C)?

Difficulty 5/10

Simplify (Aᶜ ∪ Bᶜ)ᶜ using set identities.

Quiz

De Morgan's law states that (A ∩ B)ᶜ equals:
Which law is illustrated by A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)?
A ∩ (Aᶜ ∪ B) simplifies to:

Summary

  • Set algebra obeys commutative, associative, and distributive laws, just like ordinary arithmetic with ∪ as '+' and ∩ as '×'.
  • De Morgan's laws convert complements of unions/intersections into intersections/unions of complements: (A∪B)ᶜ=Aᶜ∩Bᶜ and (A∩B)ᶜ=Aᶜ∪Bᶜ.
  • These identities let complex set expressions be simplified symbolically, the same way Boolean algebra simplifies logic circuits.

References

  1. WebsiteWikipedia — Algebra of sets