Sets & Membership

A set is a bag, and that's almost the whole story

Forget every fancy thing you've heard. A set is a collection of objects, called its elements or members. That's it. The objects can be numbers, letters, other sets, wolves — the set doesn't care what they are, only which ones are inside. This is not a warm-up; this is the whole damn foundation.

A set has exactly three personality traits, and they're all about what it refuses to track:

• No order. $\{1, 2, 3\}$ and $\{3, 1, 2\}$ are the same set. A bag doesn't know which rock you dropped in first.
• No duplicates. $\{1, 1, 2\}$ is just $\{1, 2\}$. Either a thing is in the bag or it isn't; "in twice" is meaningless.
• No opinions. The only question a set will answer is: are you in me or not? That question has a symbol, and you'll write it ten thousand times before you die.

That symbol is $\in$. We write $x \in A$ for "$x$ is an element of $A$", and $x \notin A$ for "$x$ is not". So $2 \in \{1, 2, 3\}$ is true and $5 \notin \{1, 2, 3\}$ is true. Membership is the only primitive. Everything else in set theory gets defined out of $\in$. Everything. The whole fucking edifice. Remember that the way you remember your own name.

Two ways to name a bag

You can describe a set by roster notation — just list the elements between braces:

$A = \{2, 4, 6, 8\}.$

That's great until your set is infinite or huge. For that we use set-builder notation, which says "the set of all $x$ such that some condition holds":

$A = \{\, x \mid x \text{ is an even number and } 2 \le x \le 8 \,\}.$

Read the bar $\mid$ as "such that". The left side is the template (what shape the elements take); the right side is the filter (which ones survive). This is just the quantifier machinery from the Logic stratum wearing braces — $x \in A$ literally means "the filter is true for $x$".

Here's the standard cast of infinite sets you'll see forever — tattoo them on the inside of your skull:

• $\mathbb{N} = \{0, 1, 2, 3, \dots\}$ — the natural numbers.
• $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ — the integers.
• $\mathbb{Q}$ — the rationals, all fractions $p/q$.
• $\mathbb{R}$ — the reals, the whole continuous line.
• $\emptyset$ — the empty set, the bag with nothing in it. More on this bastard in a minute.

Subset: one bag fits inside another

Now the second relation, and it's the one that powers every proof in this stratum. We say $A$ is a subset of $B$, written $A \subseteq B$, when every element of $A$ is also an element of $B$. Stated precisely — and this is the definition, carve it into the goddamn lab wall:

$A \subseteq B \quad \text{means} \quad \forall x\,(x \in A \implies x \in B).$

Stare at that. $A \subseteq B$ is an implication wearing a subset costume. That means every subset proof is just an implication proof: assume $x \in A$, do some honest work, conclude $x \in B$. We will beat that single move to death in the proofs lesson, so internalize it now. If I have to remind you of this in office hours — and I don't have office hours because this is a particle accelerator — I will be deeply disappointed in both of us.

Drag the regions around and watch what $\subseteq$ looks like — when $A$'s circle sits entirely inside $B$'s, every point of $A$ is a point of $B$:

The empty set is a subset of everything

Here's a fact that feels like a scam until you see why it's airtight: $\emptyset \subseteq B$ for every set $B$. The empty set is a subset of literally everything, including itself. Every student I've ever shown this to says "that can't be right." Every one of them was wrong.

Why? Run the definition. $\emptyset \subseteq B$ means $\forall x\,(x \in \emptyset \implies x \in B)$. But there is no $x$ with $x \in \emptyset$ — the bag is empty. So the hypothesis $x \in \emptyset$ is never true, which means the implication is never tested, which means it never fails. An implication with a false hypothesis is vacuously true. The empty set passes the subset exam by never showing up to be questioned. That's not a trick; that's logic cashing a check it wrote in the quantifiers lesson.

A bag containing an empty bag is not empty

Now the classic head-on collision. Is $\{\emptyset\}$ the same as $\emptyset$? No. Absolutely not. And if you nod along too fast you'll get burned for the rest of your mathematical life.

$\emptyset$ is the empty bag — zero elements. $\{\emptyset\}$ is a bag with one element inside it, and that element happens to be the empty bag. One is empty; the other contains something. So $\emptyset \in \{\emptyset\}$ is true, and $\{\emptyset\}$ has size one, not zero. Sets can contain sets. A set can contain other sets as elements, and this is exactly how mathematicians build numbers, pairs, functions, and the entire universe out of nothing but braces and the empty set.

The power set: every possible sub-bag

Last piece of equipment — and it's a hell of a piece. Given a set $A$, its power set $\mathcal{P}(A)$ is the set of all subsets of $A$. Not the elements — the subsets. For $A = \{a, b\}$:

$\mathcal{P}(A) = \{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\} \,\}.$

Four subsets. Notice $\emptyset$ and $A$ itself always make the list — and if you forget either of them on an exam, the ghost of Cantor will personally haunt you. Now the gorgeous part: if $A$ has $n$ elements, $\mathcal{P}(A)$ has $2^n$ elements. Here's the proof, and it's a thing of beauty. To build a subset of $A$, walk down the elements one at a time and flip a switch for each: in or out. Two choices per element, $n$ elements, independent choices — so $2 \cdot 2 \cdots 2 = 2^n$ total subsets. Every subset is one setting of $n$ on/off switches. That $2^n$ is going to detonate again in the cardinality lesson, where it proves there are infinitely many sizes of infinity. File it away.