Foundations — Sets — unique elements, set operations (union, intersection, difference)

Before you can use sets, you need a small pile of ideas: what "collection" means, what "unique" really costs, what a hash is, and the plain-English meaning of the symbols $\cup$, $\cap$, $-$, $△$, $\subseteq$, $|A|$, |, &, ^. This page builds every one of them from nothing, in an order where each idea rests on the one before it.

0. What is a "collection"?

Look at the figure. A list (top) is a row of numbered lockers — ordered, indexed, duplicates allowed. A set (bottom) is a loose bag — no numbers on it, no order, and if you drop the same marble in twice, only one stays. The parent topic is about that bag.

Why do we start here? Because every "surprise" about sets ("why is there no s[0]?", "why did my duplicate vanish?") is just one of these three answers being different from a list. Fix the three questions in your head and nothing about sets will feel strange.

See Lists — ordered, indexed collections for the ordered, indexed cousin — sets deliberately give up order to gain speed.

1. "Unique" — and why a machine needs a trick to enforce it

That sounds trivial for a human eyeballing five marbles. But imagine a million marbles. To check "do I already have this one?" the naive way is to compare against every marble you already hold. For a million marbles, adding one more could mean a million comparisons. That's painfully slow — and it's the problem the next idea solves.

2. The address trick: hashing

The picture to hold: think of a value walking up to a machine, the machine stamps a number on its forehead, and that number is used as a shelf address.

3. Hashable — which values are even allowed in a set

Why does the set demand this? The hash is the value's shelf address. If a value could change after being shelved, its hash would change too, and the set would look for it at the wrong shelf — it would "lose" its own contents.

The figure shows the rule with two doors:

• Allowed (immutable): numbers, strings, and tuples. These can never change, so their address is permanent. ✅
• Refused (mutable): lists and dictionaries. They can change, so their address is untrustworthy. ❌

{(1, 2), 3}   # OK — tuple + int, both hashable
{[1, 2], 3}   # TypeError: unhashable type: 'list'

4. Set-builder notation — reading $\{x:\dots \}$

The parent note defines every operation with a line like $\{x:x\in A\text{OR}x\in B\}$. That is set-builder notation, and here is every piece of it:

So $\{x:x\in A\text{OR}x\in B\}$ reads out loud as: "the set of all values $x$ such that $x$ is in $A$ or $x$ is in $B$." Nothing more mysterious than that sentence. Every operation below is just a different sentence after the colon.

5. AND, OR, XOR — the words behind the operations

Every set operation is one Boolean word applied to "is $x$ in $A$?" and "is $x$ in $B$?". You must know these words first.

The two overlapping circles in the figure are the master picture for the whole topic. Left circle = "in $A$", right circle = "in $B$". Each shaded region is one Boolean word:

• OR shades everything covered by either circle.
• AND shades only the overlap.
• XOR shades the two outer crescents — in one circle but not the overlap.
• $A$ but not $B$ shades only the left crescent.

Once you can point to these four regions, the symbols are just labels for them. See Boolean Logic — AND, OR, XOR for the truth tables in full.

6. The operation symbols, math ↔ Python

7. Size and containment — $|A|$, $\subseteq$, $\subset$, $\supseteq$

Two more pieces of basic set notation you will meet constantly. They don't build new sets — they ask questions about sets.

The picture: a small circle sitting entirely inside a bigger one. Every dot of the inner set is also a dot of the outer set — that is $\subseteq$. If the outer circle has at least one dot outside the inner one, the inner is a proper subset ($\subset$).

A = {1, 2}
B = {1, 2, 3}
A <= B    # True   (A is a subset of B)
A < B     # True   (proper: B has the extra 3)
B <= A    # False  (B is not inside A)
A <= A    # True   (every set is a subset of itself)

8. Degenerate cases you must not skip

A good foundation covers the empty and trivial inputs, so nothing surprises you later.

Identical sets are the other extreme:

A | A   # A itself   (union of a set with itself changes nothing)
A & A   # A itself   (everything shared)
A - A   # set()      (nothing left after removing all)
A ^ A   # set()      (nothing is in exactly one)

The first line, $A\cup A=A$, is idempotence: doing the union again adds no new element, because $A$ already contains everything it contains.

Prerequisite map

Equipment checklist