Metadata Card

• Prerequisites: Chapter 1 — Propositional Logic
• Estimated time: 45 minutes
• Core difficulty: Beginner
• Completion marker: Master the representation and operations of sets, understand Venn diagrams and set identities

Your Progress

In the previous step, you learned to use logical symbols for precise judgment. The Librarian leads you up to the second floor — here the stone doors bear circular symbols and curly braces. Each symbol points to a group of objects.

Your Task

"Find all students with scores above 80" — this kind of operation happens millions of times per day in databases. What you're really doing is one thing: finding a subset that satisfies a condition from within a set. Understanding sets means understanding the essence of data filtering, classification, and combination.

Chapter Layers

• Required reading: Basic set concepts, subsets, union, intersection, complement
• Optional reading: Set identities and algebraic proofs

Breakthrough · Origin Story

You're writing a program to manage user lists. List A contains administrators, List B contains all active users. You want to find users who are both administrators and active, you also want the union of all administrators and active users, and you want users marked as deleted who are not in the active list. These operations are unified mathematically as set operations — you've been using them intuitively in programming; now it's time to systematize that understanding.

A set is a collection of well-defined objects. Represented with curly braces:

• A =
• B = {x | x is even, x > 0} — this is set-builder notation, read as "all x such that..."

An object either belongs to a set (∈) or does not (∉). There is no middle ground. This simple idea is precisely the foundation of computer data structures — hash tables tell you whether a key exists, binary search tells you whether something is in a sorted array — these are all concrete implementations of the "belongs to" judgment.

Subset: A ⊆ B means every element of A is also an element of B. The empty set ∅ is a subset of every set.

Operations:

Operation	Symbol	Result
Union	A ∪ B	Elements in A or B
Intersection	A ∩ B	Elements in A and B
Difference	A \ B	Elements in A but not in B
Complement	Aᶜ	Elements in the universe U not in A

A real-world scenario: You have a set U of all users, and a set B of users who purchased a certain product. You want to "push ads to active users who haven't purchased":

You can recognize your own SQL habits from this pseudocode. SELECT * FROM users WHERE active=1 AND user_id NOT IN (SELECT user_id FROM buyers) — the JOIN, UNION, EXCEPT operations you write every day are all set operations at their core. Understanding sets is understanding the essence of data filtering.

active_users = U ∩ recently_logged_in
push_target = active_users \ B

In SQL terms: SELECT * FROM active_users WHERE user_id NOT IN (SELECT user_id FROM buyers). SQL's JOIN, UNION, EXCEPT, and INTERSECT are all direct mappings of set operations.

Set identities are the set-theoretic version of logical equivalences. For example, De Morgan's laws in set theory are:

• (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
• (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

There are two ways to verify: draw a Venn diagram (intuitive) or use logical proof (rigorous). The latter approach: to prove two sets are equal, show that each is a subset of the other.

Common Pitfalls

• Confusing elements and subsets. {1} is a set containing the integer 1, while 1 is an element. {1} ⊆ 1 is false, because the elements of 1 are {1} (a set), and 1 is not an element of this set.
• The empty set is not "nothing". ∅ = {}, but {∅} is a set containing the empty set — it is not empty.
• In computer science, set elements are usually required to be hashable. In mathematics, sets can contain anything, but in programming not every type can go into a HashSet.

Challenge Questions

• Given A = {1, 2, 3}, B = {2, 3, 4}, C = {1, 3, 5}, find (A ∪ B) ∩ C.
• Prove that A \ (B ∪ C) = (A \ B) ∩ (A \ C).
• Implement set difference in Python using the set type, and compare the similarities and differences between mathematical set difference and programming set difference.

Traveler's Notes

Set theory gives you a language for describing "which things". Logic handles truth values, sets handle elements — the two are tightly connected through the "belongs to" relation, forming the foundation for all subsequent mathematical discussion.

→ Next stop: With logic and sets in hand, you can now verify whether a proposition always holds — this leads to the third floor: proof methods.