Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 · Sets, Relations and Functions

Sets and Set Operations

Learn what a set is, how to write sets, and how union, intersection, difference, complement and power sets work, with Python code that checks every law.

A set is a collection of distinct objects, called elements or members. Order does not matter and repeats do not count: {1, 2, 3} and {3, 2, 1, 1} are the same set. Almost every object in mathematics and computer science can be built from sets, which is why this chapter starts here.

You write x ∈ A for "x is an element of A" and x ∉ A for the opposite. Two sets are equal exactly when they have the same elements. This is the principle of extensionality, and it is the first axiom you will meet in the ZFC lesson.

Ways to describe a set

You can list elements, A = {2, 4, 6}, or use set-builder notation, E = {n ∈ ℕ : n is even}, read "the set of natural numbers n such that n is even". Set-builder notation is a predicate in disguise: the set holds every object that makes the predicate true. Python's comprehensions mirror it closely.

Python Set-builder notation in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Some special sets: the empty set ∅ has no elements, a singleton has one, and a universe U is the context from which you draw elements. A ⊆ B (subset) means every element of A is in B. If also A ≠ B, A is a proper subset, written A ⊂ B. Note ∅ ⊆ A for every A, and A ⊆ A.

Do not confuse ∈ and ⊆. We have 2 ∈ {1, 2} and ⊆ {1, 2}, but 2 ⊆ {1, 2} is not a meaningful claim and ∈ {1, 2} is false. Also ∅ and {∅} differ: the first has no elements, the second has one.

The basic operations

For sets A and B inside a universe U:

Operation Symbol Elements
Union A ∪ B in A or in B (or both)
Intersection A ∩ B in both A and B
Difference A \ B in A but not in B
Complement Aᶜ in U but not in A
Symmetric difference A Δ B in exactly one of A, B

Each operation is the set version of a connective from propositional logic: union is "or", intersection is "and", complement is "not". That link is why the laws of sets look exactly like the laws of logic.

Python The operations on small sets

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Laws of set algebra

Set operations obey identities you can prove by element chasing (show each side is a subset of the other).

  • Commutative: A ∪ B = B ∪ A, A ∩ B = B ∩ A
  • Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C)
  • Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
  • De Morgan: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
  • Identity and domination: A ∪ ∅ = A, A ∩ U = A, A ∪ U = U, A ∩ ∅ = ∅
  • Complement: A ∪ Aᶜ = U, A ∩ Aᶜ = ∅, (Aᶜ)ᶜ = A

A sample proof of the first De Morgan law. Take x ∈ (A ∪ B)ᶜ. Then x is not in A ∪ B, so x is not in A and not in B, i.e. x ∈ Aᶜ ∩ Bᶜ. Every step is reversible, so the sets are equal.

Testing is not proof, but you can check a law on every combination of subsets of a small universe. If a law fails, you get a counterexample at once.

Python Checking laws on all subsets of a small universe

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Power sets and cardinality

The power set P(A) is the set of all subsets of A. If A has n elements, P(A) has 2ⁿ elements: each element is either in a subset or out. For A = {a, b}, P(A) = {∅, {a}, {b}, {a, b}}. The Cartesian product A × B is the set of ordered pairs (a, b), and has |A|·|B| elements. Both ideas become important when we count infinite sets in Cardinality and Countable Sets.

The inclusion-exclusion rule counts a union: |A ∪ B| = |A| + |B| − |A ∩ B|. For three sets, add back the triple intersection: |A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.

Python Power set, product and inclusion-exclusion

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a problem says "at least one" or "none of", think complement and inclusion-exclusion. Counting what you do not want and subtracting from the total is often shorter.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which statement is true?

    {2} is a set whose only element, 2, lies in {1, 2}, so it is a subset. The others confuse membership with inclusion or claim the empty set has an element.
  2. 2. How many elements does the power set of a 5-element set have?

    Each of the 5 elements is either in or out of a subset, giving 2^5 = 32 subsets.
  3. 3. Which law is De Morgan's law for sets?

    The complement of a union is the intersection of the complements. The others are commutativity, a false identity (A ∩ ∅ = ∅) and a false complement law (A ∪ Aᶜ = U).
  4. 4. If |A| = 6, |B| = 5 and |A ∩ B| = 2, what is |A ∪ B|?

    By inclusion-exclusion, 6 + 5 − 2 = 9.

Summary

  • A set is determined by its elements; order and repeats do not matter.
  • Set-builder notation is a predicate, and Python comprehensions mirror it.
  • Union, intersection, difference, complement and symmetric difference correspond to or, and, and-not, not and xor.
  • Set laws (commutative, distributive, De Morgan) can be proved by element chasing and checked by brute force on small universes.
  • |P(A)| = 2^|A|, |A × B| = |A|·|B|, and inclusion-exclusion counts unions.

Next: Relations and Their Properties