Sets in Python: set, frozenset, and Operations

The previous articles in this series presented set theory in mathematical language: what a set is, how Venn diagrams and operations work, and the notions of cardinality. Now it is time to see that theory in action in Python.

The good news: you do not need to import any special library. Python implements mathematical sets natively with the set type, mapping directly onto the concepts we have already studied, including the notation for membership, inclusion, and the operations of union, intersection, and difference.

The set type

#

In Python, a set is created with braces {} separating the elements, or with the set() constructor receiving any iterable:

A = {1, 2, 3}
B = set([3, 1, 2])

print(A)      # {1, 2, 3}
print(A == B) # True

Two mathematical properties apply automatically:

Uniqueness: repeated elements are silently ignored:

C = {1, 2, 2, 3, 3, 3}
print(C)      # {1, 2, 3}
print(len(C)) # 3

No order: Python does not guarantee any iteration order, just as \(\{1,2,3\} = \{3,2,1\}\) mathematically:

print({1, 2, 3} == {3, 2, 1}) # True

For this reason, in the output comments of this article, the elements of a set appear in an order chosen for readability (numbers in ascending order). When you run the code, Python may display them in another order: the set is the same.

The empty set: set(), not {}

#

empty      = set()
dictionary = {}

print(type(empty))      # <class 'set'>
print(type(dictionary)) # <class 'dict'>

Set comprehension notation

#

The mathematical set-builder definition \(C = \{x \in \mathbb{N} \mid x \text{ is even and } x < 10\}\) has an almost literal translation in Python:

C = {x for x in range(1, 10) if x % 2 == 0}
print(C)  # {2, 4, 6, 8}

The structure {expression for variable in iterable if condition} is called a set comprehension and follows exactly the logic of mathematical set-builder notation.

powers = {2**n for n in range(10) if 2**n < 100}
print(powers)  # {1, 2, 4, 8, 16, 32, 64}

Membership and inclusion

#

Python offers operators that map directly onto the mathematical symbols:

naturals = {1, 2, 3, 4, 5}
evens    = {2, 4}

print(3 in naturals)      # True  — 3 ∈ naturals
print(6 not in naturals)  # True  — 6 ∉ naturals
print(evens <= naturals)  # True  — evens ⊆ naturals
print(evens < naturals)   # True  — evens ⊂ naturals (proper subset)
print(naturals >= evens)  # True  — naturals ⊇ evens
print(set() <= naturals)  # True  — ∅ ⊆ A for any A

The last line confirms in code the property \(\emptyset \subseteq A\) for any set \(A\).

{1, 2}.issubset([1, 2, 3])  # True — works with a list
{1, 2} <= [1, 2, 3]         # TypeError — requires a set

Operations between sets

#

The four fundamental operations have dedicated operators:

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print(A | B)  # {1, 2, 3, 4, 5, 6}  — A ∪ B
print(A & B)  # {3, 4}              — A ∩ B
print(A - B)  # {1, 2}              — A − B
print(B - A)  # {5, 6}              — B − A
print(A ^ B)  # {1, 2, 5, 6}        — A Δ B

{1, 2, 3}.union([3, 4, 5])  # {1, 2, 3, 4, 5} — works
{1, 2, 3} | [3, 4, 5]       # TypeError — requires a set

A = {1, 2, 3}
A |= {4, 5}    # equivalent to A.update({4, 5})
print(A)       # {1, 2, 3, 4, 5}

A &= {2, 3, 4} # equivalent to A.intersection_update({2, 3, 4})
print(A)       # {2, 3, 4}

Disjointness

#

To check whether two sets are disjoint (\(A \cap B = \emptyset\)):

print({1, 2}.isdisjoint({3, 4}))  # True
print({1, 2}.isdisjoint({2, 3}))  # False

frozenset: the immutable set

#

Python offers a second kind of set: frozenset. The difference is that frozenset is immutable: its elements cannot be added or removed after creation.

fs = frozenset({1, 2, 3})
# fs.add(4)  # AttributeError: 'frozenset' object has no attribute 'add'

Why does this matter? Because a frozenset can be an element of another set, something impossible with a mutable set:

# Attempt with a mutable set
{{1, 2}}       # TypeError: unhashable type: 'set'

# With frozenset it works
{frozenset({1, 2}), frozenset({3})}  # OK

This allows us to represent the power set \(\mathcal{P}(A)\), whose elements are sets (a concept introduced in the first article of this series, where the Hasse diagram and the decision tree illustrate its structure):

from itertools import combinations

A = {1, 2, 3}
power_set = {frozenset(sub)
             for r in range(len(A) + 1)
             for sub in combinations(A, r)}

print(len(power_set))  # 8 = 2³  ✓
print(power_set)
# {frozenset(), frozenset({1}), frozenset({2}), frozenset({3}),
#  frozenset({1, 2}), frozenset({1, 3}), frozenset({2, 3}),
#  frozenset({1, 2, 3})}

The construction is a set comprehension, like those in the Set comprehension notation section, only with two for clauses. They read in the order they appear, like nested loops: the first goes through the sizes r from 0 to 3; the second, for each r, goes through the combinations of r elements of A generated by combinations(A, r).

Cardinality with len()

#

The cardinality \(|A|\) of a set is obtained with len():

A = {1, 2, 3}
print(len(A))         # 3  — |A| = 3
print(2 ** len(A))    # 8  — |𝒫(A)| = 2³ = 8

Why set is so fast: hashability

#

The x in A operation on a set has constant cost on average (\(O(1)\)), regardless of the size of the set. In a list, the same test requires going through the elements one by one: \(O(n)\).

import time

big_set  = set(range(1_000_000))
big_list = list(range(1_000_000))

start = time.perf_counter()
_ = 999_999 in big_set
print(f"set:  {time.perf_counter() - start:.2e} s")  # ~1e-05 s

start = time.perf_counter()
_ = 999_999 in big_list
print(f"list: {time.perf_counter() - start:.2e} s")  # ~1e-02 s

The exact times vary from machine to machine; what holds steady is the difference of about three orders of magnitude, and it grows along with the size of the collection.

This is possible because Python computes a hash (a numeric fingerprint) of each element when inserting it. On lookup, it computes the hash of the sought value and goes straight to the position, without traversing anything.

The connection to the theory: in mathematics, elements only need to be well defined. However, for Python to implement this with the speed we saw above, the language imposes a practical restriction: the element must be immutable (hashable). That is why:

{[1, 2]}    # TypeError: unhashable type: 'list'
{(1, 2)}    # OK — a tuple is immutable
{"text"}    # OK — a string is immutable

Lists are mutable: their contents can change at any moment, which would break the hash invariant. Strings and numbers are immutable and therefore hashable and accepted as elements. So are tuples, as long as all of their elements are hashable: {(1, [2])} raises TypeError.

The same mechanism explains the cost of operations between sets. The intersection traverses the smaller of the two sets and tests each element in the other; the difference traverses \(A\) and tests each element in \(B\); the union has to copy both. Since each test costs \(O(1)\) on average, the total cost is proportional to the number of elements traversed:

The values are those from the TimeComplexity page of the official Python wiki, which also lists the worst case of each operation.

From identities to code

#

The three previous articles established results that, seen as equations, may look abstract. With set in hand, it is possible to run them directly, which serves both to consolidate intuition and to test conjectures before proving them formally.

Complement

#

The article on operations defines the complement of \(A\) as \(\bar{A} = U - A\): everything that is in the universe but not in \(A\). Python does not offer a native complement operator, and the reason is straightforward: a set does not carry the universe with it. You have to define it explicitly:

U = set(range(1, 11))   # universe: {1, 2, ..., 10}
A = {1, 3, 5, 7, 9}    # odd numbers

complement_A = U - A
print(complement_A)     # {2, 4, 6, 8, 10}

The limitation has nothing to do with hashing: a set stores only its own elements, with no reference to the larger context it sits in, and a universe such as \(\mathbb{N}\) would not even fit in memory. In mathematics, the universe \(U\) can stay implicit; in code, it has to be explicit.

De Morgan’s laws

#

The same article proves the two identities:

With the universe already defined, both can be checked directly:

U = set(range(1, 11))
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

complement_A = U - A
complement_B = U - B

# First law: complement of the union = intersection of the complements
print((U - (A | B)) == (complement_A & complement_B))   # True

# Second law: complement of the intersection = union of the complements
print((U - (A & B)) == (complement_A | complement_B))   # True

Note that the cited article presented De Morgan in the context of Boolean logic (not (A or B) ↔ not A and not B). Here the same laws appear in their set-theoretic version, and they are the same algebraic structure seen from two angles.

Inclusion-Exclusion Principle

#

The article on cardinality shows that, when two sets overlap, adding their cardinalities counts the intersection twice. The correction is:

In Python, len() and the set operators let us confirm this directly:

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

pie = len(A) + len(B) - len(A & B)
print(pie == len(A | B))  # True — 4 + 4 - 2 = 6

The equality holds for any pair of finite sets, and Python can serve as a quick checker when working with concrete examples before a formal proof.

Practical applications

#

List deduplication

#

with_duplicates = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
without_duplicates = list(set(with_duplicates))
print(without_duplicates)  # [1, 2, 3, 4, 5, 6, 9]  (order not guaranteed)

with_duplicates = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
without_duplicates_ordered = list(dict.fromkeys(with_duplicates))
print(without_duplicates_ordered)  # [3, 1, 4, 5, 9, 2, 6] (order preserved)

Permission checking

#

required_permissions = {"read", "write"}
user_permissions     = {"read", "write", "execute"}

has_access = required_permissions <= user_permissions
print(has_access)  # True — required_permissions ⊆ user_permissions

Elements in common between groups

#

class_a = {"Ana", "Bruno", "Carla", "Diego"}
class_b = {"Bruno", "Carla", "Eduardo", "Fernanda"}

in_both = class_a & class_b
print(in_both)   # {'Bruno', 'Carla'}

only_in_a = class_a - class_b
print(only_in_a)    # {'Ana', 'Diego'}

When not to use set

#

The flowchart below summarizes the decision of which type to use when the collection needs unique elements:

flowchart TD
  A["I need a collection"] --> B{"Unique elements
without order?"}
  B -- "No" --> C{"Does order
matter?"}
  C -- "Yes" --> D["list"]
  C -- "No" --> E{"Does multiplicity
matter?"}
  E -- "Yes" --> F["collections.Counter"]
  E -- "No" --> G{"Key → value
association?"}
  G -- "Yes" --> H["dict"]
  G -- "No" --> D
  B -- "Yes" --> I{"Must be
immutable / hashable?"}
  I -- "No" --> J["set"]
  I -- "Yes" --> K["frozenset"]

Exercises

#

print(type(set()))  # <class 'set'>
print(type({}))     # <class 'dict'>

A, B = {2, 4}, {1, 2, 3, 4, 5}
print(A <= B)       # True — (i)  A ⊆ B
print(A < B)        # True — (ii) A ⊂ B (proper subset)
print(set() <= A)   # True — (iii) ∅ ⊆ any set

A, B = {1, 2, 3, 4}, {3, 4, 5, 6}
print(A | B)  # {1, 2, 3, 4, 5, 6}
print(A & B)  # {3, 4}
print(A - B)  # {1, 2}
print(A ^ B)  # {1, 2, 5, 6}

tags1 = ["python", "sets", "math",   "programming"]
tags2 = ["python", "sets", "graphs", "programming"]

tags1 = ["python", "sets", "math",   "programming"]
tags2 = ["python", "sets", "graphs", "programming"]

t1, t2 = set(tags1), set(tags2)
print(t1 & t2)   # {'python', 'sets', 'programming'}
print(t1 - t2)   # {'math'}
print(t1 <= t2)  # False — 'math' is not in t2

from itertools import combinations

A = {1, 2, 3}
power_set = {frozenset(sub)
             for r in range(len(A) + 1)
             for sub in combinations(A, r)}

print(len(power_set))  # 8 ✓

Next steps

#

With the theory and the Python implementation consolidated, the series moves on to other topics in Discrete Mathematics. To go deeper into the use of set and frozenset, see the official documentation of the set type and the itertools module for combinatorial operations on sets.

See you in the next article!