Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 68 · Sets, Relations and Functions

Sets and Set Operations

Learn sets: membership, subsets, union, intersection, difference, complement, Venn reasoning and set identities, all tested with Python's set type.

A set is an unordered collection of distinct objects. That one sentence is the foundation of nearly everything else in discrete mathematics: relations are sets of pairs, functions are special relations, graphs are sets of vertices and edges, and a probability event is a set of outcomes. Learning to calculate with sets fluently pays off in every later chapter.

Python's built-in set type is a close match to the mathematical idea, so you can try every definition and identity on real data. In this lesson you will learn the notation, the basic operations, how to reason with Venn diagrams, and how to check set identities by testing them.

Describing a set

A set is defined by its elements. Two ways to write one down:

  • Roster notation lists the elements: {2, 3, 5, 7}.
  • Set-builder notation states a rule: {x : x is a prime below 10}.

Two facts follow from "unordered and distinct". Order does not matter, so {1, 2, 3} and {3, 1, 2} are the same set. Repetition does not matter either, so {1, 1, 2} is just {1, 2}.

The statement "x is an element of A" is written x ∈ A, and in Python that is x in A. The number of elements, |A|, is len(A). The empty set ∅ has no elements. Careful: in Python {} is an empty dictionary; the empty set is set().

Sets can contain other sets, and {∅} is a set with exactly one element (the empty set), so it is not empty. In Python, use frozenset for elements that are themselves sets, because ordinary sets are mutable and therefore not hashable.

Python Sets 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.

Subsets and equality

A ⊆ B ("A is a subset of B") means every element of A is also in B. A proper subset A ⊂ B additionally requires A ≠ B. Two sets are equal exactly when each is a subset of the other, which is the standard way of proving that two sets are the same: show A ⊆ B and B ⊆ A.

Two facts that surprise beginners: the empty set is a subset of every set (the statement "every element of ∅ is in B" is vacuously true), and every set is a subset of itself.

Python reads almost like the notation: A <= B is A ⊆ B, A < B is A ⊂ B, and A == B tests equality.

The core operations

Operation Symbol Meaning Python
Union A ∪ B in A, or in B, or both A | B
Intersection A ∩ B in both A and B A & B
Difference A \ B in A but not in B A - B
Symmetric difference A Δ B in exactly one of them A ^ B
Complement Aᶜ everything in the universe not in A U - A
Disjoint A ∩ B = ∅ no shared elements A.isdisjoint(B)

The complement only makes sense relative to a universal set U that contains everything under discussion. Python has no built-in complement operator, because it has no built-in universe: you define U yourself and compute U - A.

Python Operations on two 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.

Notice that difference is not symmetric: A - B and B - A are different sets. Union and intersection, on the other hand, are both commutative.

Four ways to combine sets

Union Everything in either set.
Intersection Only what both share.
Difference In the first but not the second.
Complement Everything in U that is outside.

Complement always needs a universe.

1 / 2

Venn reasoning and counting

A Venn diagram draws each set as a region inside the universe; overlaps show shared elements. You can read the diagram as a table of regions. With two sets A and B there are four disjoint regions: only A, only B, both, and neither. Every counting question about two sets becomes arithmetic on those four regions.

The key counting rule is inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|. Adding the sizes counts the overlap twice, so subtract it once. (Three sets and more are in Counting Principles.)

An example. In a class of 40 students, 25 take Python, 18 take SQL and 6 take neither. How many take both? The students taking at least one course number 40 - 6 = 34. So 34 = 25 + 18 - both, giving both = 9.

Python Inclusion-exclusion with a class

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.

The four regions add up to the size of the universe, and no student appears in two regions. That is what it means for the regions to be a partition, an idea developed in Power Sets and Cartesian Products.

Set identities

Just as arithmetic has laws such as a + b = b + a, sets obey a collection of identities. The most useful ones:

  • Commutative: A ∪ B = B ∪ A and A ∩ B = B ∩ A.
  • Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C), and the same for ∩.
  • Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
  • Identity and domination: A ∪ ∅ = A, A ∩ U = A, A ∪ U = U, A ∩ ∅ = ∅.
  • Complement: A ∪ Aᶜ = U and A ∩ Aᶜ = ∅; also (Aᶜ)ᶜ = A.
  • De Morgan: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.
  • Absorption: A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A.

These mirror the laws of Logical Equivalences and Laws, and the reason is not a coincidence: union corresponds to OR, intersection to AND, and complement to NOT. Membership in A ∪ B is the proposition x ∈ A ∨ x ∈ B. So any logical law becomes a set identity.

To prove an identity, show both inclusions (each side is a subset of the other), or translate to logic and use a truth table. To test a conjecture quickly, try it on many small sets. A test cannot prove an identity for all sets, but one failure is a disproof, which is how you catch mistakes such as A - (B - C) = (A - B) - C (false).

Python Testing set identities exhaustively 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.

Because the universe has only three elements, there are exactly eight subsets and 512 triples to check, so this is a complete verification for that universe. It is also strong evidence for a law, since the identities depend only on which of the regions each element falls in, and three elements already produce all the regions of a three-set Venn diagram. The failing identity has an easy counterexample, shown in the last line.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What does Python's {} create?

    Braces with no elements make an empty dictionary. The empty set is written set().
  2. 2. If |A| = 10, |B| = 7 and |A ∩ B| = 3, what is |A ∪ B|?

    Inclusion-exclusion: 10 + 7 - 3 = 14. Adding the sizes counts the three shared elements twice.
  3. 3. Which statement about the empty set is true?

    Every element of the empty set (there are none) belongs to any set B, so the subset condition holds vacuously.
  4. 4. Which identity is a correct form of De Morgan's law for sets?

    The complement of a union is the intersection of the complements: being outside both sets means being outside A and outside B. Complementing an intersection turns it into a union.
  5. 5. Why does a complement need a universal set?

    The complement is defined relative to U: Aᶜ = U \ A. Different universes give different complements of the same set.

Summary

  • A set is an unordered collection of distinct elements; write it by roster or set-builder notation, and use set() (not {}) for the empty set.
  • A ⊆ B means every element of A is in B; prove equality by showing both inclusions.
  • Union, intersection, difference, symmetric difference and complement map to |, &, -, ^ and U - A.
  • Inclusion-exclusion, |A ∪ B| = |A| + |B| - |A ∩ B|, turns Venn diagrams into arithmetic.
  • Set identities (commutative, distributive, De Morgan, absorption) mirror logical laws, and a small exhaustive test can catch false conjectures.

Next: Power Sets and Cartesian Products, where sets are used to build bigger sets.