Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Set theory and set operations

Clear, exam-focused notes on set theory and set operations: definitions, laws (with proofs), formulas, worked problems and common exam pitfalls for engineering students.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Sets are the basic language for many topics you will meet in Computer Engineering: they describe collections of values (states, memory addresses, variable domains), index domains for sums and loops, inputs and outputs of functions, and vertices/edges in graphs. Understanding set operations and laws makes reasoning about programs, relations, functions and proofs much easier.

Key ideas

Start with the simplest concepts and build up.

  • Set: a collection of distinct objects called elements or members. We write "a ∈ A" to mean element a is in set A, and "a ∉ A" otherwise. (Defined here.)
  • Empty set: ∅ is the unique set with no elements. (Defined here.)
  • Universal set: U is the set of all elements under current discussion; complements are taken relative to U. Always state U when you use complements.
  • Subset: A ⊆ B means every element of A is also an element of B. If A ⊆ B but A ≠ B, write A ⊂ B (a proper subset). (Defined here.)
  • Equality of sets: A = B iff A ⊆ B and B ⊆ A. To prove two sets equal, use membership proof both ways. (Exact statement.)

Basic operations (define before using):

  • Union: A ∪ B = {x | x ∈ A or x ∈ B}. "or" is inclusive.
  • Intersection: A ∩ B = {x | x ∈ A and x ∈ B}.
  • Set difference: A \ B = {x | x ∈ A and x ∉ B}.
  • Complement: A^c = U \ A = {x ∈ U | x ∉ A}.
  • Power set: P(A) or 2^A is the set of all subsets of A. For finite A, |P(A)| = 2^{|A|}. (Assume finite for the count statement.)
  • Cartesian product: A × B = {(a,b) | a ∈ A, b ∈ B}. If A, B are finite, |A × B| = |A|·|B|.
  • Disjoint: A and B are disjoint if A ∩ B = ∅.
  • Symmetric difference: A Δ B = (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B).

Important laws (exact statements; each holds for sets with the usual definitions):

  • Commutative: A ∪ B = B ∪ A, A ∩ B = B ∩ A.
  • Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C).
  • Identity: A ∪ ∅ = A, A ∩ U = A.
  • Domination: A ∪ U = U, A ∩ ∅ = ∅.
  • Idempotent: A ∪ A = A, A ∩ A = A.
  • Complement laws: A ∪ A^c = U, A ∩ A^c = ∅.
  • Double complement (involution): (A^c)^c = A.
  • De Morgan's laws (exact): (A ∪ B)^c = A^c ∩ B^c, (A ∩ B)^c = A^c ∪ B^c.
  • Distributive laws (exact): A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
  • Absorption: A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A.
  • Set difference with union/intersection: A \ (B ∪ C) = (A \ B) ∩ (A \ C), A \ (B ∩ C) = (A \ B) ∪ (A \ C).
  • Difference identities: A \ ∅ = A, A \ A = ∅.

Proof-style method universities expect (example: prove distributive law): use membership method. To prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C):

  1. Let x ∈ A ∩ (B ∪ C). Then x ∈ A and x ∈ (B ∪ C). So x ∈ A and (x ∈ B or x ∈ C). By logic, (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C). So x ∈ (A ∩ B) or x ∈ (A ∩ C). Hence x ∈ (A ∩ B) ∪ (A ∩ C). This shows A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C).
  2. Now let x ∈ (A ∩ B) ∪ (A ∩ C). Then x ∈ (A ∩ B) or x ∈ (A ∩ C). In either case x ∈ A and (x ∈ B or x ∈ C). So x ∈ A ∩ (B ∪ C). This gives the reverse inclusion. Conclude equality.

Venn diagram instructions (what to draw and label):

  • To show two-set relations draw a rectangle labelled U then draw two overlapping circles labelled A (left) and B (right). Shade regions by name: left-only (A \ B), right-only (B \ A), intersection (A ∩ B), outside both (U \ (A ∪ B)).
  • For three sets A, B, C draw three overlapping circles forming 8 regions inside U; label each region with the logical description of membership (e.g. A ∩ B ∩ C, (A ∩ B) \ C, etc.). Use this to count elements by inclusion–exclusion when needed (see related topic Inclusion–exclusion principle).

When using complements, always state the universal set U.

Formulas

A ∪ B = {x | x ∈ A or x ∈ B} — A ∪ B is the union of A and B; no units; applies to any sets A, B.

A ∩ B = {x | x ∈ A and x ∈ B} — A ∩ B is the intersection; no units; applies to any sets.

A \ B = {x | x ∈ A and x ∉ B} — set difference; no units.

A^c = U \ A — complement of A relative to U; no units; requires chosen universal set U.

P(A) = {S | S ⊆ A} — power set; no units; applies to any set A.

|P(A)| = 2^{|A|} — cardinality of power set for finite A; |A| denotes the number of elements in A; no units; assumes A is finite.

A × B = {(a,b) | a ∈ A, b ∈ B} — Cartesian product; no units.

|A × B| = |A| · |B| — for finite sets A, B; no units.

A = B ⇔ (A ⊆ B and B ⊆ A) — equality condition; no units.

(A ∪ B)^c = A^c ∩ B^c and (A ∩ B)^c = A^c ∪ B^c — De Morgan's laws; require a universal set U.

Worked examples

Example 1 (set operations, numeric elements) Let U = {1,2,3,4,5,6,7}. Let A = {1,2,4,6}, B = {2,3,6,7}, C = {4,5}.

  1. Compute A ∪ B: apply definition: elements in A or B = {1,2,3,4,6,7}. Final: A ∪ B = {1,2,3,4,6,7}.
  2. Compute A ∩ B: elements common = {2,6}. Final: A ∩ B = {2,6}.
  3. Compute A \ C: elements in A but not in C = A elements {1,2,4,6} removing those in C ({4,5}) → {1,2,6}. Final: A \ C = {1,2,6}.
  4. Compute C^c = U \ C = {1,2,3,4,5,6,7} \ {4,5} = {1,2,3,6,7}. Final: C^c = {1,2,3,6,7}. (Each step: state definition then list elements.)

Example 2 (Cartesian product and power set) Let A = {a,b}, B = {0,1}. Compute A × B and P(A).

  • A × B = {(a,0),(a,1),(b,0),(b,1)}. |A × B| = 2·2 = 4.
  • P(A) = {∅, {a}, {b}, {a,b}}. |P(A)| = 2^{|A|} = 2^2 = 4.

Example 3 (theoretical proof asked in exam) Prove De Morgan's law: (A ∪ B)^c = A^c ∩ B^c. Solution (membership proof):

  1. Let x ∈ (A ∪ B)^c. Then x ∉ (A ∪ B). So x ∉ A and x ∉ B. Hence x ∈ A^c and x ∈ B^c. Therefore x ∈ A^c ∩ B^c. So (A ∪ B)^c ⊆ A^c ∩ B^c.
  2. Let x ∈ A^c ∩ B^c. Then x ∈ A^c and x ∈ B^c, so x ∉ A and x ∉ B. Therefore x ∉ (A ∪ B), so x ∈ (A ∪ B)^c. Thus A^c ∩ B^c ⊆ (A ∪ B)^c.
  3. From both inclusions conclude equality. Final: (A ∪ B)^c = A^c ∩ B^c.

Common mistakes

  • Trying to prove set equality by showing only one inclusion. Always do both directions or show element-wise equivalence.
  • Using exclusive "or" in the definition of union; union is inclusive: element may be in both.
  • Counting elements twice in Venn diagrams; use inclusion–exclusion if counting by regions.
  • Omitting the empty set as a subset: ∅ ⊆ A for every A (remember this when proving subset relations).
  • For Cartesian products, mixing up order of pairs: (a,b) ≠ (b,a) generally.

For your exam

Types of questions you will see:

  • Definitions and short notes (define subset, power set, Cartesian product, complement) — include notation and a short example.
  • Derivations/proofs: prove a law (e.g. distributive, De Morgan) using membership method; show two sets equal by two inclusions.
  • Numericals: given finite sets, compute unions, intersections, differences, complements; compute power set and cardinalities.
  • Diagrams: draw Venn diagrams with 2 or 3 sets and shade specified regions; label regions when performing counts.
  • Applications: use sets to describe domains/ranges, list relations, or form Cartesian products for small databases.

What a full-mark answer includes:

  • For definitions: the precise symbolic definition, at least one short example, correct notation (∈, ⊆, ×, P(A)).
  • For proofs: clear membership method, statements of assumptions (finite if counting), both directions of inclusion for equalities, concluding sentence.
  • For numericals: write the formula/definition before substituting numbers, list intermediate steps and the final set with elements in curly braces.
  • For diagrams: a rectangle U labelled, circles labelled A,B,(C) positioned as required, regions clearly numbered or described, and shading or labels matching the question.

Quick check

  1. If A = {1,2,3} and B = {2,3,4}, what is A ∪ B?
  2. State the condition for A = B in terms of subsets.
  3. True or False: (A \ B) ∪ (B \ A) = A Δ B (the symmetric difference).

Answers: 1. {1,2,3,4}. 2. A = B ⇔ A ⊆ B and B ⊆ A. 3. True (by definition, symmetric difference A Δ B = (A \ B) ∪ (B \ A)).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?