4. Sets, Relations, and Functions

Level: Beginner You'll use this for: databases, type systems, deduplication, and reasoning about API contracts.

Sets

A set is an unordered collection of distinct elements. Core operations:

admins = {"alice", "bob"}
active = {"alice", "carol"}
print(admins & active)   # {'alice'}          -> active admins
print(admins - active)   # {'bob'}            -> inactive admins
print(admins | active)   # {'alice','bob','carol'}

How to compute these by hand: list both sets, then scan for membership.

admins = {alice, bob}      active = {alice, carol}

Intersection (A ∩ B): keep an element only if it's in BOTH lists.
  alice -> in admins? yes. in active? yes.  -> keep
  bob   -> in admins? yes. in active? no.   -> drop
  carol -> in admins? no.                    -> drop
  result: {alice}

Difference (A - B): keep an element from A only if it's NOT in B.
  alice -> in active? yes -> drop
  bob   -> in active? no  -> keep
  result: {bob}

Union (A ∪ B): every element that appears in either list, no duplicates.
  result: {alice, bob, carol}

A hash-set implementation does exactly this scan, just in O(1) per membership check instead of scanning a list — which is why the data-structure choice mentioned in the common mistake below matters.

Relations and functions

A relation is any set of pairs (a foreign key relationship, a graph edge). A function is a relation where every input maps to exactly one output — this constraint is why a database primary key must be unique, and why a hash function must be deterministic (same input → same output, always).

• Injective (one-to-one): different inputs never collide on the same output. A perfect hash function would be injective; real hash functions aren't (hence collisions, Ch. 26).
• Surjective (onto): every possible output is reachable from some input.
• Bijective: both — this is what makes a function invertible. Encryption must be bijective (you must be able to decrypt); hashing must not be invertible by design (one-way).

Real-life engineering ties

• SWE: SQL JOIN/UNION/INTERSECT are literally set operations; DISTINCT is "convert to a set."
• AI: train/validation/test splits must be disjoint sets — a leaking overlap between train and test sets is one of the most common, most silent causes of an ML model that looks great in evaluation and fails in production.
• Network: IP address ranges are sets; CIDR blocks are set membership tests (Ch. 25).
• Security: allowlists/denylists are sets; "is this IP in the blocklist" is a set-membership query, and the data structure backing that query (hash set vs. sorted array vs. bloom filter) is a real performance/security tradeoff at scale.

More real-life examples:

• Redis's native SET type and operations like SINTERSTORE/ SUNIONSTORE are used in production to answer questions like "which users are both online and in this user's friend list" — a live intersection query at scale.
• Google Chrome's Safe Browsing and many CDNs use Bloom filters — a probabilistic, space-efficient set-membership structure — to check "have we seen this URL/hash before" without storing every value explicitly.
• Database foreign-key constraints formally encode a relation between two tables; a "dangling foreign key" bug is a relation whose function property (every child row maps to exactly one valid parent) has been violated.
• API contract/type systems (OpenAPI schemas, TypeScript types) define the set of valid inputs and outputs a function may accept and return — a type error is really a set-membership violation caught at compile time.

Common mistake

Treating a list where you need a set — leads to accidental O(n) membership checks (and, in security-critical allowlist code, accidental duplicate/near-duplicate entries that create bypass gaps).