Contents / Set Theory / Naive Set Theory

Chapter 1

Naive Set Theory

Sets, membership and the double-inclusion method that follows from extensionality; why membership and inclusion are genuinely different relations; Russell's paradox derived in full, with the failing assumption located and separation shown to repair it; power sets with the count 2 to the n; Cantor's theorem by the diagonal set; and the union, intersection, distributive and De Morgan laws proved by element chasing, including arbitrary indexed families.

Introduction

Almost every object in modern mathematics is, if you push hard enough, a set. A function is a set of ordered pairs; an ordered pair is a set of sets; a natural number can be built as a set, a real number as a set of rationals, a vector space as a set with two sets of operations laid over it. The reason to care about the theory in this chapter is not that sets are interesting in themselves — for most of the chapter they will look almost insultingly simple — but that they are the substrate everything else is written on, and a substrate with a crack in it cracks everything above it.

There was a crack. The naive theory, as Cantor and Frege used it, rested on one enormously plausible principle: any property whatsoever carves out the set of things having that property. In 1901 Bertrand Russell wrote down a property — is not a member of itself — for which that principle is flatly contradictory. The resulting paradox is short enough to fit in three lines and destroyed a life's work. Section Russell's paradox and what it kills gives it in full, together with the precise diagnosis of which assumption fails, because a paradox you cannot locate is a paradox you will walk into again.

Everything else here is the working vocabulary: membership, equality, inclusion, the empty set, power sets, unions and intersections, differences and products. Two themes run through all of it. The first is extensionality: a set is nothing but its members, which makes set equality provable rather than a matter of how the set was described, and which converts every equality claim into two inclusion claims. That conversion — the double inclusion technique — is the single method used most often in this chapter and in the rest of mathematics. The second is that membership and inclusion are different relations, sharing almost no properties, and that conflating them is the most reliable source of wrong answers in the subject.

We work naively but not carelessly: axioms are named where they are used, and where the naive picture would mislead, the repair is stated. Throughout, $N = {0, 1, 2, \dots}$ , $Z$ is the integers, $Q$ the rationals and $R$ the reals.

1.1What a set is, and when two sets are equal

Membership is taken as primitive: it is not defined in terms of anything simpler, in the same way that "point" is primitive in geometry. What we do instead is say how membership behaves, and the first and most important such statement is that a set is determined by nothing except which objects are in it.

Definition 1.1 (Set and membership). A set is a collection of objects, considered as a single object in its own right. The objects belonging to a set $A$ are its elements or members, and we write

x \in A

to mean that $x$ is an element of $A$ , and $x \in / A$ to mean that it is not. For every object $x$ and every set $A$ , exactly one of $x \in A$ and $x \in / A$ holds.

That last sentence is the whole of the "well-defined" requirement stated honestly. It is not a demand that we be able to decide which of the two holds — nobody can currently decide whether the Euler–Mascheroni constant belongs to the set of rational numbers — only that one of them does hold.

Definition 1.2 (Extensionality). Two sets $A$ and $B$ are equal, written $A = B$ , precisely when they have the same elements:

A = B if and only if for every x, (x \in A ⟺ x \in B) .

Intuition. A set is a membership list and nothing more. Not how the list was compiled, not what order the names are in, not how many times a name was written down. ${1, 2, 3}$ , ${3, 2, 1}$ , ${1, 1, 2, 3, 3}$ and ${n \in Z : 0 < n < 4}$ are four descriptions of one set, in exactly the way that "the capital of France" and "the city on the Seine with the iron tower" are two descriptions of one city.

Extensionality is doing more work than it looks. It tells us that repetition and order are invisible, which is why ${a, a} = {a}$ . It tells us that two sets given by wildly different descriptions may nevertheless be the same set, so "are these equal?" is a mathematical question with a proof, not a bookkeeping question. And it hands us a proof technique, by splitting a biconditional into two implications.

Theorem 1.3 (Double inclusion). Let $A$ and $B$ be sets. Then $A = B$ if and only if both of the following hold:

every element of $A$ is an element of $B$ ;
every element of $B$ is an element of $A$ .

Proof. Suppose $A = B$ . By Definition Extensionality, for every $x$ we have $x \in A ⟺ x \in B$ . In particular, if $x \in A$ then $x \in B$ , which is (1), and if $x \in B$ then $x \in A$ , which is (2).

Conversely, suppose (1) and (2) hold, and let $x$ be arbitrary. By (1), $x \in A$ implies $x \in B$ ; by (2), $x \in B$ implies $x \in A$ . The two implications together give $x \in A ⟺ x \in B$ . Since $x$ was arbitrary, Definition Extensionality yields $A = B$ .∎

This is the workhorse of the entire subject, so it is worth naming the shape of the argument it licenses. To prove $A = B$ : take an arbitrary $x \in A$ , and reason your way to $x \in B$ ; then take an arbitrary $x \in B$ and reason your way back. Nothing else is needed, and nothing less will do — showing only (1) proves the weaker statement that $A$ is contained in $B$ , which is a different claim. Every algebraic identity in this chapter, from associativity of union to De Morgan's laws, is proved this way, and the proofs are so uniform that after three of them you can write the fourth without thinking.

Example 1.4 (Two descriptions, one set). Let $A = {n \in Z : n^{2} = n}$ and $B = {0, 1}$ . Show that $A = B$ .

Solution.

Take $x \in A$ . Then $x$ is an integer with $x^{2} = x$ , so $x^{2} - x = 0$ , that is $x (x - 1) = 0$ . A product of integers is zero only if a factor is, so $x = 0$ or $x = 1$ ; either way $x \in B$ .
Take $x \in B$ . If $x = 0$ then $x^{2} = 0 = x$ ; if $x = 1$ then $x^{2} = 1 = x$ . In both cases $x$ is an integer satisfying $x^{2} = x$ , so $x \in A$ .
Both inclusions hold, so by Theorem Double inclusion, $A = B$ .

□

Pitfall. "Same number of elements" is not "equal". ${1, 2}$ and ${5, 9}$ both have two elements and are different sets. Equality is about which objects, never about how many.

Exercises for §1.1 →

1.2Writing sets down: roster and set-builder notation

Extensionality says a set is its members; notation is the business of specifying those members on a page. There are exactly two ways, and the choice between them is the choice between listing and describing.

Definition 1.5 (Roster and set-builder notation). Roster notation specifies a set by listing its elements between braces, as in ${2, 3, 5, 7}$ ; an ellipsis stands for an unambiguous continuation, as in ${1, 2, 3, \dots, 100}$ or ${2, 4, 6, \dots}$ .

Set-builder notation specifies a set by a property. If $A$ is a set and $P (x)$ a property, then

{x \in A : P (x)}

denotes the set of exactly those elements $x$ of $A$ for which $P (x)$ holds. The variant ${f (x) : x \in A}$ denotes the set of all values $f (x)$ as $x$ ranges over $A$ .

Notation. The colon is read "such that"; many authors write a vertical bar instead, ${x \in A ∣ P (x)}$ . Both are universal and neither is more correct. The braces are part of the name of the set: ${5}$ is a set with one element, while $5$ is a number, and they are never interchangeable.

The clause $x \in A$ before the colon is not decoration, and it is the difference between safe and unsafe notation. Writing ${x : P (x)}$ with no restriction — "the set of all things with property $P$ " — is exactly the principle that Russell's paradox destroys. The restricted form always carves a new set out of a set we already have, and that restriction is what keeps it consistent. We will make this precise in Definition Separation.

Exercises for §1.2 →

1.3Sets that already surround you

Before anything is proved about sets in general, it is worth fixing the standard examples, since nearly every later illustration is drawn from them.

The number systems are nested: $N \subseteq Z \subseteq Q \subseteq R \subseteq C$ , each obtained from the last by demanding that some operation always succeed — subtraction, then division, then taking limits, then extracting roots. Intervals such as $[0, 1] = {x \in R : 0 \leq x \leq 1}$ are sets of reals defined by set-builder notation, and the difference between $[0, 1]$ and $(0, 1)$ is a difference of exactly two elements with enormous consequences in analysis.

Sets are not confined to numbers. The solution set of an equation, the set of vertices of a graph, the set of continuous functions $[0, 1] \to R$ , the set of $2 \times 2$ matrices over $Q$ , the set of prime factors of $360$ — all are sets, and in each case the elements are objects that are themselves complicated. There is no requirement that the elements of a set resemble one another. ${3, π, Q, {7}}$ is a perfectly good four-element set containing an integer, a real number, an infinite set of rationals, and a one-element set.

Example 1.6 (Counting a set given by a property). How many elements does $A = {d \in N : d \geq 1 and d ∣ 36}$ have?

Solution.

A divisor of $36 = 2^{2} \cdot 3^{2}$ has the form $2^{a} 3^{b}$ with $0 \leq a \leq 2$ and $0 \leq b \leq 2$ .
That gives $3 \cdot 3 = 9$ choices, and distinct pairs $(a, b)$ give distinct divisors by uniqueness of prime factorisation.
Explicitly, $A = {1, 2, 3, 4, 6, 9, 12, 18, 36}$ , which has $9$ elements.

□

Exercises for §1.3 →

1.4Nothing: the empty set

A collection is allowed to be empty, and the set with no elements turns out to be the most heavily used set in mathematics — it is the default answer, the base case of a hundred inductions, and the value of any intersection of sets with nothing in common.

Definition 1.7 (Empty set). The empty set is the set with no elements. It is written $\emptyset$ or ${}$ , and it is characterised by

x \in / \emptyset for every object x .

The definite article in "the empty set" is a claim, not a courtesy, and extensionality is what justifies it.

Theorem 1.8 (Uniqueness of the empty set). There is at most one set with no elements: if $E$ and $E^{'}$ both have no elements, then $E = E^{'}$ .

Proof. We verify the condition in Definition Extensionality. Let $x$ be an arbitrary object. Since $E$ has no elements, $x \in E$ is false; since $E^{'}$ has no elements, $x \in E^{'}$ is false. Two false statements are equivalent, so $x \in E ⟺ x \in E^{'}$ holds. As $x$ was arbitrary, extensionality gives $E = E^{'}$ .∎

The proof is worth pausing over because it is the first appearance of an argument style that trips people up: both sides of the biconditional are false, and the biconditional is therefore true. Nothing was checked about any actual element, because there are none to check. The same style — a universally quantified statement about the members of an empty collection is automatically true — is called vacuous truth, and it returns immediately in Proposition The empty set is contained in everything.

Pitfall. $\emptyset$ , ${\emptyset}$ and ${0}$ are three different sets. The first has no elements. The second has exactly one element, namely $\emptyset$ , so it is not empty — a box containing an empty box is not an empty box. The third has one element, the number $0$ . Only the first satisfies $∣ X ∣ = 0$ .

Example 1.9 (Empty or not?). Determine which of the following are empty: $A = {x \in R : x^{2} < 0}$ , $B = {x \in R : x^{2} = 2}$ , $C = {x \in Q : x^{2} = 2}$ , $D = {\emptyset}$ .

Solution.

$A$ is empty: squares of reals are non-negative, so no real satisfies $x^{2} < 0$ .
$B$ is not empty: $2$ and $- 2$ belong to it, so $∣ B ∣ = 2$ .
$C$ is empty: the classical irrationality of $2$ says no rational squares to $2$ .
$D$ is not empty: it has one element. Its cardinality is $1$ , not $0$ .

□

Remark. $B$ and $C$ differ only in the ambient set the elements are drawn from, and one is empty while the other has two elements. This is a reminder that in ${x \in A : P (x)}$ the set $A$ carries real information; suppressing it is the beginning of the trouble in the next section.

Exercises for §1.4 →

1.5Russell's paradox and what it kills

Naive set theory, as practised before 1901, ran on a single generative principle: any property determines a set. It is hard to overstate how natural this is. If you can say what it is to be a prime, there ought to be the set of primes; if you can say what it is to be a group, there ought to be the set of groups. Frege built the foundations of arithmetic on it. Written out, it is the following schema.

Definition 1.10 (Unrestricted comprehension). Unrestricted comprehension is the principle that for every property $P$ there exists a set

R = {x : P (x)}

whose elements are exactly the objects satisfying $P$ ; that is, for every object $x$ ,

x \in R ⟺ P (x) .

Note the quantifier: every property, with no ambient set to draw from. Russell's observation is that one particular, entirely unexotic property makes the principle contradict itself.

Theorem 1.11 (Russell's paradox). Unrestricted comprehension is inconsistent.

Proof. Apply Definition Unrestricted comprehension to the property $P (x)$ given by " $x \in / x$ ", which says that $x$ is not a member of itself. It yields a set

R = {x : x \in / x}

with the defining property that for every object $x$ ,

x \in R ⟺ x \in / x . (*)

Now $R$ is itself an object, so we may take $x = R$ in $(*)$ . This gives

R \in R ⟺ R \in / R .

Write $p$ for the statement $R \in R$ . We have derived $p ⟺ \neg p$ . If $p$ is true then $\neg p$ is true, so $p$ is false; if $p$ is false then $\neg p$ is true, so $p$ is true. Each case yields its own negation, so both $p$ and $\neg p$ hold, a contradiction. The contradiction was derived from the comprehension principle alone, using no further assumption, so that principle is inconsistent.∎

Intuition. The barber version: in a village the barber shaves exactly those men who do not shave themselves. Who shaves the barber? If he shaves himself, he is one of the men who shave themselves, whom he does not shave. If he does not, he is one of the men who do not shave themselves, whom he does shave. The resolution there is easy — no such barber exists, and the story was a lie. The resolution in set theory is exactly the same shape and much more expensive: no such set exists, and the principle that promised us one was the lie.

Locating the failure precisely matters more than the paradox itself. Three assumptions were in play: that the property " $x \in / x$ " is a legitimate property, that a property determines a set, and that classical logic applies. The property is unimpeachable — it is built from membership and negation, the two most basic ingredients available. Abandoning classical logic is a heavy price with no compensating benefit here. So the assumption that fails is the middle one: a property, on its own, does not determine a set.

Definition 1.12 (Separation). The axiom schema of separation (or restricted comprehension) replaces unrestricted comprehension with: for every set $A$ and every property $P$ , there exists a set

{x \in A : P (x)},

whose elements are exactly those $x \in A$ satisfying $P (x)$ .

Separation cannot build something out of nothing; it can only carve a subcollection out of a set already in hand. Run Russell's argument against it and watch it fail harmlessly: given a set $A$ , separation produces $R_{A} = {x \in A : x \in / x}$ , and asking whether $R_{A} \in R_{A}$ now yields $R_{A} \in R_{A} ⟺ (R_{A} \in A and R_{A} \in / R_{A})$ . That is no longer a contradiction; it is a proof, by the same case analysis as above, that $R_{A} \in / A$ . No paradox — instead, a theorem.

Corollary 1.13 (There is no set of all sets). There is no set $U$ such that every set is an element of $U$ .

Proof. Suppose such a $U$ existed. By Definition Separation applied to $U$ and the property $x \in / x$ , the collection

R = {x \in U : x \in / x}

is a set. Being a set, $R \in U$ by the assumed universality of $U$ . Now ask whether $R \in R$ .

If $R \in R$ , then by the definition of $R$ its members satisfy $x \in / x$ , so $R \in / R$ — contradiction. If $R \in / R$ , then $R$ satisfies both conditions for membership in $R$ , namely $R \in U$ and $R \in / R$ , so $R \in R$ — contradiction. Both cases are impossible, so no such $U$ exists.∎

Remark. The cost of the repair is that the universe of sets is not itself a set. Collections too large to be sets — the sets, the ordinals, the groups — are called proper classes; they can be talked about, but never used as elements. Zermelo–Fraenkel set theory is essentially the list of the constructions we are allowed: separation, pairing, union, power set, infinity, replacement. Every one of them builds a new set from sets already present. Nothing in this chapter beyond this section needs the axioms by name, but every construction we perform is one of them.

Example 1.14 (Diagnosing an illegitimate definition). Is ${S : S is a set and ∣ S ∣ = 1}$ , the collection of all one-element sets, a set?

Solution.

It is defined by unrestricted comprehension, with no ambient set, so it is not automatically legitimate.
It is in fact a proper class. If it were a set $C$ , then $⋃ C$ would be a set, and $⋃ C$ contains $x$ for every object $x$ , since ${x} \in C$ for every $x$ . That makes $⋃ C$ a set of all sets, contradicting Corollary There is no set of all sets.
So no: the collection is too large to be a set.

□

Exercises for §1.5 →

1.6Membership as a relation

We have used $\in$ constantly; now we examine it as an object of study. A relation is a thing that either holds or fails between two objects, and the useful questions to ask about any relation are the standard ones: is it reflexive, symmetric, antisymmetric, transitive? For most relations you meet — equality, $\leq$ , congruence mod $n$ , divisibility — the answers are yes to several. For $\in$ the answers are no across the board, and that is precisely what distinguishes it from the inclusion relation of the next section.

Notation. The membership relation $\in$ holds between an object $x$ and a set $A$ exactly when $x$ is one of the objects collected in $A$ . It is the only primitive relation of set theory: every other notion in this chapter — equality, inclusion, union, intersection, power set — is defined from $\in$ together with logic.

Intuition. Membership is a one-level relation: it sees only the outermost braces. Asking $x \in A$ is asking whether $x$ appears in the top-level list of $A$ , never whether $x$ appears somewhere nested deeper. In $A = {1, {2, 3}}$ the top-level list has two entries, $1$ and ${2, 3}$ . The number $2$ is buried one level down, so $2 \in / A$ , even though $2$ is written inside the braces of $A$ on the page.

Example 1.15 (Reading membership off nested braces). Let $A = {1, {1}, {{1}}}$ . Decide whether each of $1 \in A$ , ${1} \in A$ , ${{1}} \in A$ , ${1, {1}} \in A$ holds, and give $∣ A ∣$ .

Solution.

The top-level entries of $A$ are the three objects $1$ , ${1}$ and ${{1}}$ . These are pairwise distinct: a number, a set whose element is a number, and a set whose element is a set. So $∣ A ∣ = 3$ .
$1 \in A$ : yes, it is the first entry. ${1} \in A$ : yes, the second. ${{1}} \in A$ : yes, the third.
${1, {1}} \in A$ : no. This two-element set is not one of the three listed entries, so it is not a member — although we will see in Section Subsets and inclusion that it is a subset.

□

Exercises for §1.6 →

1.7Membership has none of the usual properties

Relations that behave well tend to be reflexive and transitive, and it is tempting to assume $\in$ is too, especially since $\subseteq$ (coming next) is both. The temptation must be resisted explicitly, with counterexamples, because the error is invisible once it is made.

Proposition 1.16 (Membership is neither reflexive, symmetric, antisymmetric nor transitive).

There is a set $A$ with $A \in / A$ , so $\in$ is not reflexive.
There are sets $A, B$ with $A \in B$ and $B \in / A$ , so $\in$ is not symmetric.
There are sets $A \neq = B$ with $A \in B$ and $B \in A$ , so $\in$ is not antisymmetric.
There are sets $A, B, C$ with $A \in B$ and $B \in C$ but $A \in / C$ , so $\in$ is not transitive.

Proof. For (1), take $A = \emptyset$ . By Definition Empty set, no object at all is a member of $\emptyset$ , and in particular $\emptyset \in / \emptyset$ .

For (2), take $A = 1$ and $B = {1}$ . Then $A \in B$ , while $B \in / A$ because $A$ is a number and has no elements at all.

For (3), antisymmetry would say that $A \in B$ and $B \in A$ force $A = B$ . Suppose $A = {B}$ and $B = {A}$ with $A \neq = B$ ; then $A \in B$ and $B \in A$ while $A \neq = B$ , so antisymmetry fails. (In Zermelo–Fraenkel set theory the axiom of foundation rules such a pair out, but nothing in the definition of $\in$ itself excludes it: antisymmetry is not a property of the relation, it is an extra axiom.)

For (4), take $A = 1$ , $B = {1}$ and $C = {{1}}$ . Then $A \in B$ since $1$ is the sole element of ${1}$ , and $B \in C$ since ${1}$ is the sole element of $C$ . But the only element of $C$ is ${1}$ , and $1 \neq = {1}$ — one is a number, the other a set — so $A \in / C$ .∎

Part (4) is the one that does damage in practice. The chain $1 \in {1} \in {{1}}$ does not collapse; each $\in$ steps exactly one level of braces, and two steps land you two levels away, not one. Contrast this with the inclusion relation, which is transitive precisely because it is a statement about all elements rather than about one level of structure.

Remark. The axiom of foundation (or regularity) asserts that every non-empty set has an element disjoint from it; a consequence is that no set is a member of itself and there are no cycles $A_{1} \in A_{2} \in \dots \in A_{n} \in A_{1}$ . So in the standard universe $x \in x$ never happens — which, incidentally, means Russell's $R = {x : x \in / x}$ would have had to be the set of all sets, another way of seeing that it is too big to exist.

Exercises for §1.7 →

1.8Subsets and inclusion

Inclusion is the relation that compares two sets wholesale, and unlike membership it is exactly as well behaved as one could hope.

Definition 1.17 (Subset). Let $A$ and $B$ be sets. We say $A$ is a subset of $B$ , or that $A$ is included in $B$ , written $A \subseteq B$ , if every element of $A$ is an element of $B$ :

A \subseteq B means for every x, (x \in A ⟹ x \in B) .

We write $A \neq \subseteq B$ when this fails, that is, when some $x$ has $x \in A$ and $x \in / B$ . Such an $x$ is a witness to the failure.

The definition tells you immediately how to prove and how to disprove an inclusion, and the asymmetry between the two is worth stating. To prove $A \subseteq B$ you must argue about an arbitrary element: "let $x \in A$ ; then ... ; hence $x \in B$ . " To disprove it you need only exhibit one witness. One object settles a negative; no finite number of objects settles a positive, unless $A$ happens to be finite and you check them all.

Proposition 1.18 (The empty set is contained in everything). For every set $A$ , we have $\emptyset \subseteq A$ . Moreover $\emptyset$ is the only set contained in every set.

Proof. By Definition Subset, $\emptyset \subseteq A$ means: for every $x$ , if $x \in \emptyset$ then $x \in A$ . Fix any $x$ . The hypothesis $x \in \emptyset$ is false, by Definition Empty set. An implication with a false hypothesis is true, whatever its conclusion — this is the truth table of $⟹$ , and it is what vacuous truth names. So the implication holds for this $x$ , and since $x$ was arbitrary, it holds for all $x$ . Hence $\emptyset \subseteq A$ .

For the second claim, suppose $S \subseteq A$ for every set $A$ . Taking $A = \emptyset$ gives $S \subseteq \emptyset$ , and every element of $S$ would then be an element of $\emptyset$ ; since $\emptyset$ has none, $S$ has none, so $S = \emptyset$ by Theorem Uniqueness of the empty set.∎

Intuition. Why should "every element of $\emptyset$ lies in $A$ " count as true when there is nothing to check? Because the only way it could be false is for some element of $\emptyset$ to lie outside $A$ , and there is no element of $\emptyset$ to serve as the counterexample. A statement with no possible counterexample is true. Compare: "every unicorn in this room is purple" cannot be refuted, because refuting it requires producing a non-purple unicorn in this room.

Theorem 1.19 (Inclusion is a partial order). For all sets $A$ , $B$ , $C$ :

Reflexivity. $A \subseteq A$ .
Antisymmetry. If $A \subseteq B$ and $B \subseteq A$ , then $A = B$ .
Transitivity. If $A \subseteq B$ and $B \subseteq C$ , then $A \subseteq C$ .
Singletons. ${x} \subseteq A$ if and only if $x \in A$ .

Proof. (1) Let $x \in A$ . Then $x \in A$ . The implication $x \in A ⟹ x \in A$ holds trivially for every $x$ , so $A \subseteq A$ .

(2) The hypothesis $A \subseteq B$ says every element of $A$ lies in $B$ , and $B \subseteq A$ says every element of $B$ lies in $A$ . These are exactly conditions (1) and (2) of Theorem Double inclusion, which gives $A = B$ .

(3) Let $x \in A$ be arbitrary. Since $A \subseteq B$ , we get $x \in B$ . Since $B \subseteq C$ , we get $x \in C$ . Thus every element of $A$ is an element of $C$ , which is $A \subseteq C$ .

(4) Suppose ${x} \subseteq A$ . Since $x \in {x}$ , the inclusion applied to this element gives $x \in A$ . Conversely suppose $x \in A$ , and let $y \in {x}$ be arbitrary; the only element of ${x}$ is $x$ , so $y = x$ and hence $y \in A$ . Thus ${x} \subseteq A$ .∎

Parts (1)–(3) say that $\subseteq$ is a partial order — "partial" because two sets need not be comparable at all: ${1, 2}$ and ${2, 3}$ satisfy neither inclusion. Part (2) is the formal statement that double inclusion works, and it is why almost every equality proof in the rest of the chapter is presented as two inclusions. Part (4) is the bridge between the two relations, and the cleanest statement of how they differ: $x \in A$ and ${x} \subseteq A$ say the same thing, while $x \subseteq A$ and ${x} \in A$ say something else entirely.

Example 1.20 (Proving and disproving inclusions). Let $A = {n \in Z : 6 ∣ n}$ and $B = {n \in Z : 3 ∣ n}$ . Show $A \subseteq B$ and show $B \neq \subseteq A$ .

Solution.

For the inclusion, let $n \in A$ . Then $n = 6 k$ for some integer $k$ , so $n = 3 (2 k)$ with $2 k \in Z$ , hence $3 ∣ n$ and $n \in B$ . As $n$ was arbitrary, $A \subseteq B$ .
For the failure, we need one witness. Take $n = 3$ : it lies in $B$ since $3 ∣ 3$ , and it does not lie in $A$ since $3 = 6 k$ has no integer solution. So $B \neq \subseteq A$ .
Together these say the inclusion $A \subseteq B$ is strict.

□

Exercises for §1.8 →

1.9Proper subsets

Inclusion as defined allows $A = B$ ; often we want to say a set sits strictly inside another.

Definition 1.21 (Proper subset). $A$ is a proper subset of $B$ , written $A ⊊ B$ , if $A \subseteq B$ and $A \neq = B$ . Equivalently, every element of $A$ lies in $B$ and there is at least one element of $B$ that does not lie in $A$ .

Pitfall. The symbol $\subset$ is genuinely ambiguous in the literature: some authors use it for ordinary inclusion, exactly as $\subseteq$ , and others reserve it for proper inclusion. Use $\subseteq$ and $⊊$ , which nobody misreads, and when you meet $\subset$ in a text, check its conventions before assuming either meaning.

The two characterisations in the definition agree because failing to be equal, given $A \subseteq B$ , can only happen through the other inclusion failing: by Theorem Inclusion is a partial order part (2), if $B \subseteq A$ also held we would have $A = B$ . So $A ⊊ B$ if and only if $A \subseteq B$ and $B \neq \subseteq A$ , and the latter is exactly the existence of a witness in $B ∖ A$ .

Proper inclusion is transitive — if $A ⊊ B ⊊ C$ then $A \subseteq C$ by transitivity of $\subseteq$ , and $A \neq = C$ because an element of $B ∖ A$ lies in $C$ but not $A$ — and irreflexive, since $A \neq = A$ is false. It is therefore a strict partial order, with $\subseteq$ related to it exactly as $\leq$ is to $<$ .

Exercises for §1.9 →

1.10Elements versus subsets

This is the section that decides whether the rest of the subject will make sense. Two relations, written with similar symbols, are constantly confused, and the confusion is not a matter of sloppy notation — it produces genuinely wrong answers about cardinalities, power sets and proofs.

The difference in one line: $x \in A$ says $x$ is one of the entries in $A$ 's list; $X \subseteq A$ says every entry of $X$ 's list also appears in $A$ 's list. Membership compares an object with a set; inclusion compares a set with a set. They have no properties in common: $\subseteq$ is reflexive, antisymmetric and transitive, and by Proposition Membership is neither reflexive, symmetric, antisymmetric nor transitive, $\in$ is none of the three.

It is possible for an object to stand in both relations to the same set, and possible for it to stand in exactly one. All four combinations are realisable, and knowing an example of each is the fastest way to keep them apart.

Example 1.22 (All four combinations). Find, for the object $x$ and set $A$ in each case: (a) $x \in A$ and $x \subseteq A$ ; (b) $x \in A$ but $x \neq \subseteq A$ ; (c) $x \subseteq A$ but $x \in / A$ ; (d) neither.

Solution.

(a) Both. Take $A = {\emptyset, {\emptyset}}$ and $x = {\emptyset}$ . Then $x \in A$ , since ${\emptyset}$ is listed as an entry. And $x \subseteq A$ , since the only element of $x$ is $\emptyset$ , which is also an entry of $A$ .
(b) Member but not subset. Take $A = {1, 2}$ and $x = 1$ . Then $1 \in A$ . But $1 \subseteq A$ is not even a sensible claim about a number, and read literally it is false: $1$ is not a set with all its elements in $A$ .
(c) Subset but not member. Take $A = {1, 2}$ and $x = {1}$ . Every element of ${1}$ , namely $1$ , lies in $A$ , so ${1} \subseteq A$ . But the entries of $A$ are $1$ and $2$ , and ${1}$ is neither, so ${1} \in / A$ .
(d) Neither. Take $A = {1, 2}$ and $x = {3}$ : it is not an entry of $A$ , and its element $3$ is not in $A$ .

□

Pitfall. Every set satisfies $A \subseteq A$ , but $A \in A$ essentially never holds. Writing ${1, 2} \in {1, 2, 3}$ is a common slip for ${1, 2} \subseteq {1, 2, 3}$ , and the first is false while the second is true.

Exercises for §1.10 →

1.11Sets inside the rest of mathematics

The element/subset distinction is not a curiosity of set theory; it is the distinction between a point and a subspace, a vector and a subgroup, a number and an interval, and it appears wherever mathematics has structure.

In linear algebra, a vector $v$ is an element of $R^{3}$ , while the line $span (v)$ is a subset, indeed a subspace. The statement " $v$ is a subspace" is a type error. In group theory, $g \in G$ is an element and $⟨ g ⟩ \subseteq G$ is the subgroup it generates; in topology, a point $p$ belongs to a space $X$ and an open neighbourhood $U \subseteq X$ contains it. In each case the object and the one-element set around it are different, and Theorem Inclusion is a partial order part (4) is the translation between them.

Where the distinction genuinely blurs is in the von Neumann construction of the natural numbers, which is worth seeing once because it shows sets doing real work. Define

0 = \emptyset, n + 1 = n \cup {n} .

So $1 = {\emptyset} = {0}$ , $2 = {0, 1}$ , $3 = {0, 1, 2}$ , and in general $n = {0, 1, \dots, n - 1}$ . Each natural number is the set of all smaller natural numbers, so $∣ n ∣ = n$ : the number is its own cardinality. And here, exceptionally, the two relations coincide in a useful way — $m \in n$ and $m ⊊ n$ both say exactly $m < n$ .

Example 1.23 (Computing inside the von Neumann numbers). With $0 = \emptyset$ and $n + 1 = n \cup {n}$ , write out $3$ in full braces, and determine $∣3∣$ , the number of subsets of $3$ , and whether $1 \in 3$ and $1 \subseteq 3$ .

Solution.

$0 = \emptyset$ , $1 = {\emptyset}$ , $2 = {\emptyset, {\emptyset}}$ , and $3 = {\emptyset, {\emptyset}, {\emptyset, {\emptyset}}}$ , that is ${0, 1, 2}$ .
$∣3∣ = 3$ , its elements being $0$ , $1$ and $2$ .
The number of subsets is $2^{3} = 8$ .
$1 \in 3$ holds, since $1$ is listed among $0, 1, 2$ . And $1 \subseteq 3$ holds, since the only element of $1$ is $0$ , which is in $3$ . Both, as promised, because $1 < 3$ .

□

Exercises for §1.11 →

1.12Working with subsets

Two kinds of question come up constantly: deciding whether a proposed inclusion holds, and counting subsets of a given shape. Both are drill, and both reward doing a few by hand.

Example 1.24 (Which inclusions hold?). Let $A = {1, 2, {1, 2}}$ . Decide each of: ${1, 2} \subseteq A$ , ${1, 2} \in A$ , ${{1, 2}} \subseteq A$ , ${1, {1}} \subseteq A$ .

Solution.

${1, 2} \subseteq A$ : the elements $1$ and $2$ are both entries of $A$ , so yes.
${1, 2} \in A$ : the entries of $A$ are $1$ , $2$ and ${1, 2}$ , and the third is exactly this set, so yes. This is a set that is simultaneously a member and a subset.
${{1, 2}} \subseteq A$ : its sole element is ${1, 2}$ , which by (2) is an entry of $A$ , so yes.
${1, {1}} \subseteq A$ : this requires ${1} \in A$ , and the entries of $A$ are $1$ , $2$ , ${1, 2}$ — none equals ${1}$ . So no.

□

Exercises for §1.12 →

1.13The power set

Having compared sets by inclusion, we now gather all the subsets of a set into a single object. This is the first construction in the chapter that genuinely increases size, and the axiom that permits it is separate from all the others for exactly that reason.

Definition 1.25 (Power set). The power set of a set $A$ , written $P (A)$ or $2^{A}$ , is the set whose elements are precisely the subsets of $A$ :

P (A) = {X : X \subseteq A} .

That is, for every set $X$ ,

X \in P (A) ⟺ X \subseteq A .

The displayed biconditional is the only fact about power sets ever used, and it is a translation device: it converts a membership statement about $P (A)$ into an inclusion statement about $A$ , and back. Every proof in this section is that translation applied once or twice.

Pitfall. Every element of $P (A)$ is a set, even when the elements of $A$ are not. For $A = {1, 2}$ we get $P (A) = {\emptyset, {1}, {2}, {1, 2}}$ ; the number $1$ is not an element of $P (A)$ , though the set ${1}$ is. Writing $1 \in P ({1, 2})$ is the classic error.

Two elements are present no matter what $A$ is: $\emptyset \in P (A)$ by Proposition The empty set is contained in everything, and $A \in P (A)$ by reflexivity of inclusion. In particular $P (A)$ is never empty — even $P (\emptyset) = {\emptyset}$ has one element, which is the cleanest illustration that a set of one empty thing is not empty.

Example 1.26 (Small power sets). Write out $P (\emptyset)$ , $P ({a})$ and $P (P (\emptyset))$ , and give the size of each.

Solution.

The only subset of $\emptyset$ is $\emptyset$ itself, so $P (\emptyset) = {\emptyset}$ , of size $1$ .
The subsets of ${a}$ are $\emptyset$ and ${a}$ , so $P ({a}) = {\emptyset, {a}}$ , of size $2$ .
$P (\emptyset) = {\emptyset}$ is a one-element set, so its power set is ${\emptyset, {\emptyset}}$ , of size $2$ .

□

Exercises for §1.13 →

1.14How big the power set is

For finite sets the size of $P (A)$ is determined by the size of $A$ , and the formula is the reason for the alternative notation $2^{A}$ .

Notation. A set $A$ is finite with cardinality $∣ A ∣ = n$ if its elements can be listed as $a_{1}, \dots, a_{n}$ without repetition; equivalently, if there is a bijection between $A$ and ${1, 2, \dots, n}$ . A set that is not finite is infinite.

Theorem 1.27 (The power set of a finite set). If $A$ is finite with $∣ A ∣ = n$ , then $P (A)$ is finite with

∣ P (A) ∣ = 2^{n} .

Proof. List the elements of $A$ as $a_{1}, \dots, a_{n}$ without repetition. Let $B_{n}$ be the set of binary strings $(ε_{1}, \dots, ε_{n})$ with each $ε_{i} \in {0, 1}$ . Define a map $Φ : P (A) \to B_{n}$ by sending a subset $X \subseteq A$ to its indicator string, whose $i$ -th entry is

ε_{i} = {10 if a_{i} \in X, if a_{i} \in / X .

$Φ$ is injective. Suppose $Φ (X) = Φ (Y)$ . Then for each $i$ , $a_{i} \in X$ holds exactly when $a_{i} \in Y$ does. Since every element of $A$ is some $a_{i}$ , and $X$ and $Y$ are subsets of $A$ , the sets $X$ and $Y$ have the same elements, so $X = Y$ by Definition Extensionality.

$Φ$ is surjective. Given a string $(ε_{1}, \dots, ε_{n})$ , put $X = {a_{i} : ε_{i} = 1}$ . This is a subset of $A$ , and its indicator string is the given one, so $Φ (X)$ is the given string.

Hence $Φ$ is a bijection and $∣ P (A) ∣ = ∣ B_{n} ∣$ . A string in $B_{n}$ is built by choosing each of the $n$ entries independently from a two-element set, so $∣ B_{n} ∣ = 2^{n}$ by the multiplication principle.∎

Intuition. Building a subset is $n$ independent yes/no decisions, one per element: is $a_{1}$ in? is $a_{2}$ in? Every pattern of answers gives a different subset and every subset arises from exactly one pattern, so there are as many subsets as patterns, which is $2 \times 2 \times \dots \times 2$ .

Corollary 1.28 (Subsets by size). If $∣ A ∣ = n$ , the number of subsets of $A$ with exactly $k$ elements is $(k n)$ , and consequently

k = 0 \sum n (k n) = 2^{n} .

Proof. A $k$ -element subset of $A$ is a choice of $k$ of the $n$ listed elements with order disregarded, and the number of such choices is $(k n)$ by definition of the binomial coefficient. Every subset has exactly one size $k$ with $0 \leq k \leq n$ , so sorting $P (A)$ by size partitions it into the classes counted by $(0 n), (1 n), \dots, (n n)$ . Summing the sizes of the parts gives $∣ P (A) ∣$ , which is $2^{n}$ by Theorem The power set of a finite set.∎

Figure 1.29. The power set of

{a, b, c}

ordered by inclusion: a cube standing on the corner

\emptyset

, with the level

k

holding the

(k 3)

subsets of size

k

. Each edge joins a set to one obtained by adding a single element, so the

2^{3} = 8

vertices are exactly the

8

indicator strings and a path from bottom to top is a choice of which element to add first.

Exercises for §1.14 →

1.15Power sets computed

Iterating the power set operation produces very large sets very quickly, and the towers are worth computing once so the growth is not a surprise.

Example 1.30 (A tower of power sets). Let $A = {1, 2, 3}$ . Compute $∣ P (A) ∣$ , $∣ P (P (A)) ∣$ , and the number of elements of $P (P (A))$ that have exactly two elements.

Solution.

$∣ A ∣ = 3$ , so $∣ P (A) ∣ = 2^{3} = 8$ by Theorem The power set of a finite set.
Applying the theorem again to the eight-element set $P (A)$ gives $∣ P (P (A)) ∣ = 2^{8} = 256$ .
A two-element element of $P (P (A))$ is a two-element subset of the eight-element set $P (A)$ , and there are $(2 8) = 28$ of these by Corollary Subsets by size.

□

Exercises for §1.15 →

1.16The power set and inclusion

The power set operation converts inclusion into membership, and it does so order-preservingly: bigger sets have bigger power sets, and the correspondence is exact in both directions.

Proposition 1.31 (Power sets respect inclusion). For all sets $A$ and $B$ , the following are equivalent:

$A \subseteq B$ ;
$A \in P (B)$ ;
$P (A) \subseteq P (B)$ .

Proof. (1) $⟺$ (2) is Definition Power set applied with $X = A$ .

(1) $⟹$ (3). Assume $A \subseteq B$ and let $X \in P (A)$ be arbitrary. Then $X \subseteq A$ , and combining with $A \subseteq B$ gives $X \subseteq B$ by transitivity of inclusion, Theorem Inclusion is a partial order part (3). Hence $X \in P (B)$ , and since $X$ was arbitrary, $P (A) \subseteq P (B)$ .

(3) $⟹$ (1). Assume $P (A) \subseteq P (B)$ . Since $A \subseteq A$ by reflexivity, $A \in P (A)$ , so the assumed inclusion gives $A \in P (B)$ , which by Definition Power set is $A \subseteq B$ .∎

The step that makes (3) $⟹$ (1) work is applying the hypothesis to the single largest element of $P (A)$ , namely $A$ itself. This is a standard move: a statement about all subsets is often cracked open by feeding it the whole set, or the empty set, or a singleton.

Exercises for §1.16 →

1.17Cantor's theorem: the power set is always bigger

For a finite set $2^{n} > n$ , so the power set is strictly larger. The remarkable fact, and the beginning of the theory of infinite cardinalities, is that this remains true for infinite sets — with the same one-line proof, which needs no notion of counting at all. The argument compares sizes by asking whether a map can hit everything.

Notation. A function $f : A \to B$ is a surjection, or is onto, if every $b \in B$ equals $f (a)$ for at least one $a \in A$ . If a surjection $A \to B$ exists we say $B$ is no larger than $A$ ; if none exists, $B$ is strictly larger.

Theorem 1.32 (Cantor's theorem). For every set $A$ there is no surjection $f : A \to P (A)$ .

Proof. Let $f : A \to P (A)$ be any function. We produce a subset of $A$ that is not in the image of $f$ . Define the diagonal set

D = {x \in A : x \in / f (x)} .

This is a legitimate set by Definition Separation: it is carved out of the set $A$ by a property, namely $x \in / f (x)$ , which makes sense because $f (x)$ is a subset of $A$ and $x$ is an element of $A$ . By construction $D \subseteq A$ , so $D \in P (A)$ .

Suppose, for contradiction, that $D = f (a)$ for some $a \in A$ . Ask whether $a \in D$ .

If $a \in D$ , then by the defining property of $D$ we have $a \in / f (a)$ . But $f (a) = D$ , so $a \in / D$ — contradiction.
If $a \in / D$ , then $a$ fails the defining property, so $a \in f (a)$ . But $f (a) = D$ , so $a \in D$ — contradiction.

Both alternatives are impossible, so no such $a$ exists. Hence $D$ is an element of $P (A)$ outside the image of $f$ , and $f$ is not a surjection. Since $f$ was arbitrary, no surjection $A \to P (A)$ exists.∎

The resemblance to Theorem Russell's paradox is not an accident: both hinge on the self-referential set ${x : x \in / something built from x}$ . The difference is what the argument is allowed to conclude. Russell had a set $R$ that was forced to be a member of itself and not, and the conclusion was that the theory was broken. Cantor has a set $D$ that would be $f (a)$ for some $a$ , and the conclusion is merely that no such $a$ exists — one hypothesis, the surjectivity of $f$ , is available to blame. A contradiction with something to blame is a theorem; a contradiction with nothing to blame is a paradox.

Figure 1.33. Cantor's diagonal for a candidate list

f (x_{1}), \dots, f (x_{5})

of subsets of

A = {x_{1}, \dots, x_{5}}

. A dot at column

j

of row

i

means

x_{j} \in f (x_{i})

; the muted line marks the diagonal cells

x_{i} \in f (x_{i})

. The set

D

along the top takes exactly the columns where the diagonal has no dot, so

D

disagrees with row

i

at position

i

for every

i

and therefore appears nowhere in the list.

Corollary 1.34 (No largest cardinality). There is no set $A$ such that every set injects into $A$ ; equivalently, for every set $A$ there is a strictly larger set.

Proof. Given any set $A$ , form $P (A)$ . The map $x \mapsto {x}$ from $A$ into $P (A)$ is injective, since ${x} = {y}$ forces $x = y$ by extensionality, so $P (A)$ is at least as large as $A$ . By Theorem Cantor's theorem there is no surjection $A \to P (A)$ , hence in particular no bijection, so the two are not of equal size. Therefore $P (A)$ is strictly larger than $A$ , and the process $A, P (A), P (P (A)), \dots$ never terminates in a largest set.∎

Remark. Applied to $N$ , Cantor's theorem says $P (N)$ is uncountable — there is no list $S_{1}, S_{2}, S_{3}, \dots$ containing every set of natural numbers. Since $P (N)$ corresponds to the binary expansions of reals in $[0, 1]$ , this is the uncountability of $R$ , and the diagonal set is the familiar "change every digit on the diagonal" construction in disguise. Whether any cardinality lies strictly between $∣ N ∣$ and $∣ P (N) ∣$ is the continuum hypothesis, which Gödel and Cohen showed the standard axioms can neither prove nor refute.

Example 1.35 (Cantor's argument on a concrete list). Let $A = {1, 2, 3}$ and define $f (1) = {1, 3}$ , $f (2) = {2}$ , $f (3) = \emptyset$ . Compute the diagonal set $D$ and check it is missing from the list.

Solution.

$1 \in f (1) = {1, 3}$ , so $1 \in / D$ . $2 \in f (2) = {2}$ , so $2 \in / D$ . $3 \in / f (3) = \emptyset$ , so $3 \in D$ .
Hence $D = {3}$ .
The list is ${1, 3}, {2}, \emptyset$ , and ${3}$ is none of them, as guaranteed. Indeed $P (A)$ has $8$ elements while the list has at most $3$ , so at least $5$ subsets are missed.

□

Exercises for §1.17 →

1.18Union

We now turn from comparing sets to combining them. The two basic operations are union and intersection, defined by "or" and "and" respectively, and every algebraic law they satisfy is inherited from the corresponding law of logic.

Definition 1.36 (Union). The union of sets $A$ and $B$ is

A \cup B = {x : x \in A or x \in B},

the set of objects belonging to at least one of them. Membership is characterised by

x \in A \cup B ⟺ (x \in A or x \in B) .

Notation. The "or" is always inclusive: an $x$ lying in both $A$ and $B$ lies in $A \cup B$ , and lies there once, because extensionality makes repetition invisible. English "or" is often exclusive — "tea or coffee" — and mathematical "or" never is.

Exercises for §1.18 →

1.19The algebra of union

Union obeys the laws you would expect of an addition-like operation, with $\emptyset$ playing the role of zero — but with idempotence replacing anything like cancellation. All of the proofs have the same three-line form, so the first is given in full and the pattern then stated once.

Theorem 1.37 (Laws of union). For all sets $A$ , $B$ , $C$ :

Commutativity. $A \cup B = B \cup A$ .
Associativity. $(A \cup B) \cup C = A \cup (B \cup C)$ .
Idempotence. $A \cup A = A$ .
Identity. $A \cup \emptyset = A$ .
Monotonicity and absorption. $A \subseteq A \cup B$ , and $A \cup B = B$ if and only if $A \subseteq B$ .

Proof. (1) Let $x$ be arbitrary. Then $x \in A \cup B$ iff ( $x \in A$ or $x \in B$ ) iff ( $x \in B$ or $x \in A$ ) iff $x \in B \cup A$ , the middle step being the commutativity of "or". By extensionality the sets are equal.

(2) $x \in (A \cup B) \cup C$ iff (( $x \in A$ or $x \in B$ ) or $x \in C$ ) iff ( $x \in A$ or ( $x \in B$ or $x \in C$ )) iff $x \in A \cup (B \cup C)$ , using associativity of "or" in the middle. Extensionality finishes it.

(3) $x \in A \cup A$ iff ( $x \in A$ or $x \in A$ ) iff $x \in A$ .

(4) $x \in A \cup \emptyset$ iff ( $x \in A$ or $x \in \emptyset$ ). The second disjunct is always false by Definition Empty set, and " $p$ or false" is equivalent to $p$ , so this holds iff $x \in A$ .

(5) If $x \in A$ then " $x \in A$ or $x \in B$ " holds, so $x \in A \cup B$ ; hence $A \subseteq A \cup B$ . For the second claim, suppose $A \cup B = B$ . Then $A \subseteq A \cup B = B$ by what we just proved. Conversely suppose $A \subseteq B$ . We show two inclusions. If $x \in A \cup B$ then $x \in A$ or $x \in B$ ; in the first case $x \in B$ by hypothesis, and in the second directly, so $x \in B$ and $A \cup B \subseteq B$ . And $B \subseteq A \cup B$ by the first part with the roles of $A$ and $B$ exchanged, using (1). By Theorem Double inclusion, $A \cup B = B$ .∎

Associativity is what licenses writing $A \cup B \cup C$ with no brackets, and together with commutativity it says the union of a finite list does not depend on the order or the grouping — which is what makes the indexed notation of Section Unions of arbitrary families well defined.

Exercises for §1.19 →

1.20Unions computed

Example 1.38 (Counting a union). In a class of $30$ students, $18$ study French and $15$ study German, and $7$ study both. How many study at least one of the two?

Solution.

Let $F$ and $G$ be the sets of students studying each language, so $∣ F ∣ = 18$ , $∣ G ∣ = 15$ , $∣ F \cap G ∣ = 7$ .
Adding $∣ F ∣ + ∣ G ∣ = 33$ counts each of the $7$ students in both twice, so subtract the overcount once: $∣ F \cup G ∣ = 18 + 15 - 7 = 26$ .
So $26$ students study at least one, and $30 - 26 = 4$ study neither.

□

Exercises for §1.20 →

1.21Unions of arbitrary families

Union of two sets extends to any collection at all, finite or infinite, and the extension is an axiom rather than a definition made from the binary case — you cannot reach an infinite union by applying a binary operation finitely often.

Definition 1.39 (Indexed union). Let $I$ be a set and let $A_{i}$ be a set for each $i \in I$ ; we call ${A_{i}}_{i \in I}$ an indexed family. Its union is

i \in I ⋃ A_{i} = {x : x \in A_{i} for at least one i \in I},

so that $x \in ⋃_{i \in I} A_{i}$ if and only if there exists $i \in I$ with $x \in A_{i}$ . When $I = {1, 2}$ this is $A_{1} \cup A_{2}$ .

The union axiom of Zermelo–Fraenkel is precisely the assertion that this collection is a set. Note the logical shape: membership in a union is an existence statement, and so proving $x \in ⋃_{i} A_{i}$ means exhibiting one index, while proving $⋃_{i} A_{i} \subseteq B$ means handling every index at once.

Proposition 1.40 (Union over the empty family). If $I = \emptyset$ then $⋃_{i \in I} A_{i} = \emptyset$ .

Proof. By Definition Indexed union, $x \in ⋃_{i \in \emptyset} A_{i}$ holds if and only if there exists $i \in \emptyset$ with $x \in A_{i}$ . There exists no $i \in \emptyset$ at all, so the existence statement is false for every $x$ . Thus the union has no elements, and by Theorem Uniqueness of the empty set it is $\emptyset$ .∎

Unlike the analogous question for intersections in Section Intersections of arbitrary families, this causes no trouble whatsoever: an existence statement over an empty range is false, which is exactly what we want, and the answer $\emptyset$ is the identity element for union, exactly as the empty sum is $0$ .

Example 1.41 (Indexing by a finite set of divisors). For $d \in {2, 3, 5}$ let $A_{d} = {n \in Z : 1 \leq n \leq 30, d ∣ n}$ . Compute $∣ ⋃_{d} A_{d} ∣$ .

Solution.

$∣ A_{2} ∣ = 15$ , $∣ A_{3} ∣ = 10$ , $∣ A_{5} ∣ = 6$ .
The pairwise overlaps are the multiples of $6$ , $10$ and $15$ : $5$ , $3$ and $2$ elements. The triple overlap is the multiples of $30$ : $1$ element.
Inclusion–exclusion gives $15 + 10 + 6 - 5 - 3 - 2 + 1 = 22$ . So $22$ of the first $30$ positive integers are divisible by $2$ , $3$ or $5$ .

□

Exercises for §1.21 →

1.22Intersection

Where union asks for "at least one", intersection asks for "both", and the shift from "or" to "and" changes every law accordingly. Intersection is the operation that can produce the empty set out of two non-empty inputs, which union never does.

Definition 1.42 (Intersection and disjointness). The intersection of sets $A$ and $B$ is

A \cap B = {x : x \in A and x \in B},

so that $x \in A \cap B$ if and only if both $x \in A$ and $x \in B$ . If $A \cap B = \emptyset$ the sets are called disjoint; a family of sets is pairwise disjoint if any two distinct members of it are disjoint.

Note that $A \cap B$ can be formed by separation from $A$ alone — it is ${x \in A : x \in B}$ — so intersection, unlike union, needs no axiom of its own. This is the first of many places where the two operations, superficially symmetric, turn out not to be.

Exercises for §1.22 →

1.23The algebra of intersection

The laws mirror those for union, with $\emptyset$ now acting as an annihilator rather than an identity, and with the inclusion in part (5) pointing the other way.

Theorem 1.43 (Laws of intersection). For all sets $A$ , $B$ , $C$ :

Commutativity. $A \cap B = B \cap A$ .
Associativity. $(A \cap B) \cap C = A \cap (B \cap C)$ .
Idempotence. $A \cap A = A$ .
Annihilation. $A \cap \emptyset = \emptyset$ .
Monotonicity and absorption. $A \cap B \subseteq A$ , and $A \cap B = A$ if and only if $A \subseteq B$ .
Absorption across the operations. $A \cup (A \cap B) = A$ and $A \cap (A \cup B) = A$ .

Proof. (1)–(3) are the arguments of Theorem Laws of union with "or" replaced by "and" throughout, using the commutativity, associativity and idempotence of conjunction.

(4) $x \in A \cap \emptyset$ iff ( $x \in A$ and $x \in \emptyset$ ). The second conjunct is always false, and " $p$ and false" is false, so no $x$ qualifies and the intersection is empty.

(5) If $x \in A \cap B$ then in particular $x \in A$ , so $A \cap B \subseteq A$ . Now suppose $A \cap B = A$ ; then $A = A \cap B \subseteq B$ by the same argument applied with the roles exchanged. Conversely suppose $A \subseteq B$ . We have $A \cap B \subseteq A$ already; and if $x \in A$ then $x \in B$ by hypothesis, so $x \in A \cap B$ , giving $A \subseteq A \cap B$ . Double inclusion gives equality.

(6) For the first, $A \cap B \subseteq A$ by (5), so $A \cup (A \cap B) = A$ by Theorem Laws of union part (5). For the second, $A \subseteq A \cup B$ by that same part, so $A \cap (A \cup B) = A$ by (5) here.∎

Parts (5) of the two theorems together give three equivalent ways of saying $A \subseteq B$ : as an inclusion, as $A \cup B = B$ , and as $A \cap B = A$ . In a Boolean algebra this is how the order is defined from the operations, and it is why every fact about $\subseteq$ can be turned into an algebraic identity.

Exercises for §1.23 →

1.24Intersections computed

Example 1.44 (Intersecting described sets). Compute ${n \in Z : 4 ∣ n} \cap {n \in Z : 6 ∣ n}$ .

Solution.

An integer lies in both exactly when it is a multiple of $4$ and of $6$ , that is, a common multiple of $4$ and $6$ .
The common multiples of two integers are exactly the multiples of their least common multiple, and $lcm (4, 6) = 12$ .
So the intersection is ${n \in Z : 12 ∣ n}$ . It is not the multiples of $24$ : the product is not the right answer when the two numbers share a factor.

□

Example 1.45 (Nested intervals). Compute $⋂_{n \geq 1} (0, \frac{1}{n})$ .

Solution.

Suppose $x$ belongs to every $(0, \frac{1}{n})$ . Then $x > 0$ and $x < \frac{1}{n}$ for every $n \geq 1$ .
By the Archimedean property there is an $n$ with $\frac{1}{n} < x$ , contradicting $x < \frac{1}{n}$ . So no such $x$ exists.
The intersection is $\emptyset$ , even though every set in the family is non-empty and each contains the next. Shrinking non-empty open intervals need not have a common point.

□

Exercises for §1.24 →

1.25Intersections of arbitrary families

Indexed intersection is defined by the same pattern as indexed union, with "for at least one $i$ " replaced by "for every $i$ " — and the change of quantifier is exactly what makes the empty index set a genuine problem here when it was harmless there.

Definition 1.46 (Indexed intersection). For an indexed family ${A_{i}}_{i \in I}$ with $I \neq = \emptyset$ ,

i \in I ⋂ A_{i} = {x : x \in A_{i} for every i \in I} .

Proposition 1.47 (Why the empty index set is excluded). Let $I = \emptyset$ . Then the condition " $x \in A_{i}$ for every $i \in I$ " holds for every object $x$ whatsoever. Consequently $⋂_{i \in \emptyset} A_{i}$ would have to contain every set, and by Corollary There is no set of all sets it is not a set.

Proof. The condition is a universally quantified statement ranging over $I = \emptyset$ . It fails for a given $x$ only if some $i \in \emptyset$ has $x \in / A_{i}$ , and there is no $i \in \emptyset$ at all; so by vacuous truth the condition holds for every $x$ , exactly as in Proposition The empty set is contained in everything. The collection defined by the condition therefore contains every object, in particular every set, and no set has that property by Corollary There is no set of all sets.∎

The repair is a convention, and it is the right one: intersections are always taken relative to a fixed ambient set. If every $A_{i}$ is a subset of a universe $U$ , define $⋂_{i \in I} A_{i} = {x \in U : x \in A_{i} for all i \in I}$ , which for $I = \emptyset$ evaluates to $U$ . This is consistent with the general pattern — union over nothing is the smallest set, intersection over nothing is the largest — and it works precisely because $U$ is a set rather than the universe of all sets.

Exercises for §1.25 →

1.26Difference and complement

Subtraction of sets is removal of members, and it needs no new principle: it is separation applied with the property "not in $B$ ".

Definition 1.48 (Difference, complement, symmetric difference). For sets $A$ and $B$ ,

A ∖ B = {x \in A : x \in / B}

is the difference. When all sets under discussion are subsets of a fixed universe $U$ , the complement of $A$ is $A^{c} = U ∖ A$ . The symmetric difference is

A △ B = (A ∖ B) \cup (B ∖ A),

the set of objects in exactly one of the two.

Pitfall. $A ∖ B$ does not require $B \subseteq A$ . Elements of $B$ that were never in $A$ are simply ignored: ${1, 2} ∖ {2, 7} = {1}$ , and the stray $7$ changes nothing. Nor is difference commutative — $B ∖ A = {7}$ here — or associative.

Figure 1.49. Three sets in general position cut the universe into eight regions, one for each of the

2^{3}

answers to "in

A

? in

B

? in

C

? ". Every set built from

A

B

C

by union, intersection and complement is a union of some of these eight regions, so there are exactly

2^{8} = 256

such sets. The outer region, in none of the three, is

(A \cup B \cup C)^{c}

Example 1.50 (Differences and symmetric difference). For $A = {1, 2, 3, 4, 5}$ and $B = {4, 5, 6, 7}$ compute $A ∖ B$ , $B ∖ A$ , $A △ B$ and $∣ A △ B ∣$ .

Solution.

$A ∖ B = {1, 2, 3}$ : the elements of $A$ not in $B$ .
$B ∖ A = {6, 7}$ .
$A △ B = {1, 2, 3} \cup {6, 7} = {1, 2, 3, 6, 7}$ , of size $5$ .
As a check, $∣ A △ B ∣ = ∣ A ∣ + ∣ B ∣ - 2∣ A \cap B ∣ = 5 + 4 - 2 \cdot 2 = 5$ : the shared elements are removed from both counts.

□

Exercises for §1.26 →

1.27Distributive and De Morgan laws

Union and intersection each distribute over the other — a symmetry that addition and multiplication of numbers do not have, since $a + (b \cdot c) \neq = (a + b) (a + c)$ in general. And complementation exchanges the two operations, which is De Morgan's contribution. Both proofs are pure element chasing: unfold the definitions into logic, apply a law of logic, fold back up.

Theorem 1.51 (Distributive laws). For all sets $A$ , $B$ , $C$ :

A \cap (B \cup C) = (A \cap B) \cup (A \cap C), A \cup (B \cap C) = (A \cup B) \cap (A \cup C) .

Proof. For the first, take any $x$ and chase it both ways.

( $\subseteq$ ) Suppose $x \in A \cap (B \cup C)$ . Then $x \in A$ , and $x \in B$ or $x \in C$ . In the first case $x \in A$ and $x \in B$ , so $x \in A \cap B$ ; in the second $x \in A \cap C$ . Either way $x \in (A \cap B) \cup (A \cap C)$ .

( $\supseteq$ ) Suppose $x \in (A \cap B) \cup (A \cap C)$ . Then $x \in A \cap B$ or $x \in A \cap C$ . In the first case $x \in A$ and $x \in B$ , so $x \in A$ and $x \in B \cup C$ ; in the second, $x \in A$ and $x \in C$ , so again $x \in A$ and $x \in B \cup C$ . Either way $x \in A \cap (B \cup C)$ .

By Theorem Double inclusion the two sets are equal. The second identity is the same argument with "and" and "or" exchanged throughout: $x \in A \cup (B \cap C)$ says $x \in A$ or ( $x \in B$ and $x \in C$ ), which by the distributivity of "or" over "and" is equivalent to ( $x \in A$ or $x \in B$ ) and ( $x \in A$ or $x \in C$ ), that is $x \in (A \cup B) \cap (A \cup C)$ .∎

Theorem 1.52 (De Morgan's laws). Let $A$ , $B$ be subsets of a universe $U$ , and write $X^{c} = U ∖ X$ . Then

(A \cup B)^{c} = A^{c} \cap B^{c}, (A \cap B)^{c} = A^{c} \cup B^{c} .

More generally, for any non-empty indexed family ${A_{i}}_{i \in I}$ of subsets of $U$ ,

(i \in I ⋃ A_{i})^{c} = i \in I ⋂ A_{i}^{c}, (i \in I ⋂ A_{i})^{c} = i \in I ⋃ A_{i}^{c} .

Proof. Let $x \in U$ . Then $x \in (A \cup B)^{c}$ means $x \in / A \cup B$ , that is, it is not the case that ( $x \in A$ or $x \in B$ ). By the logical law $\neg (p \lor q) \equiv \neg p \land \neg q$ , this is equivalent to: $x \in / A$ and $x \in / B$ , that is, $x \in A^{c}$ and $x \in B^{c}$ , that is, $x \in A^{c} \cap B^{c}$ . Extensionality gives the first identity, and the second follows by the companion law $\neg (p \land q) \equiv \neg p \lor \neg q$ .

For the indexed version, $x \in (⋃_{i} A_{i})^{c}$ means there is no $i \in I$ with $x \in A_{i}$ , which is precisely: for every $i \in I$ , $x \in / A_{i}$ ; that is, $x \in A_{i}^{c}$ for every $i$ , which is $x \in ⋂_{i} A_{i}^{c}$ . The other identity is the same argument with the quantifiers exchanged, using that "not for all" is "there exists not".∎

Intuition. De Morgan in words: to fail to be in either of two sets is to be outside both; to fail to be in both is to be outside at least one. The complement swaps "or" with "and", exactly as negation swaps them in logic — which is no coincidence, since $\cup$ , $\cap$ and $^{c}$ are $\lor$ , $\land$ and $\neg$ acting on membership conditions.

Example 1.53 (Simplifying with the laws). Simplify $(A \cup B) \cap (A \cup B^{c})$ , working inside a universe $U$ .

Solution.

By the second distributive law read backwards, $(A \cup B) \cap (A \cup B^{c}) = A \cup (B \cap B^{c})$ .
$B \cap B^{c} = \emptyset$ , since no $x$ lies both in $B$ and outside it.
So the expression is $A \cup \emptyset = A$ by Theorem Laws of union part (4).

□

Example 1.54 (Inclusion–exclusion for three sets). In a survey of $100$ people, $50$ read newspaper $A$ , $40$ read $B$ , $30$ read $C$ , $20$ read both $A$ and $B$ , $15$ both $A$ and $C$ , $10$ both $B$ and $C$ , and $5$ read all three. How many read none?

Solution.

Inclusion–exclusion gives $∣ A \cup B \cup C ∣ = 50 + 40 + 30 - 20 - 15 - 10 + 5 = 80$ .
By De Morgan, the readers of none form $(A \cup B \cup C)^{c}$ , whose size is $100 - 80 = 20$ .
So $20$ people read none of the three.

□

Exercises for §1.27 →

1.28Ordered pairs and Cartesian products

Sets are unordered, so to do geometry, define functions or record relations we need a device that remembers order. One is available without new axioms.

Definition 1.55 (Ordered pair and Cartesian product). The ordered pair $(a, b)$ is defined by Kuratowski's construction $(a, b) = {{a}, {a, b}}$ ; its defining property is that $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ . The Cartesian product of sets $A$ and $B$ is

A \times B = {(a, b) : a \in A and b \in B} .

We write $A^{2}$ for $A \times A$ .

Proposition 1.56 (Size and distributivity of the product). For finite sets $A$ , $B$ we have $∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣$ . Moreover, for all sets $A$ , $B$ , $C$ ,

A \times (B \cup C) = (A \times B) \cup (A \times C), A \times (B \cap C) = (A \times B) \cap (A \times C) .

Proof. For the count: an element of $A \times B$ is determined by choosing a first coordinate in $∣ A ∣$ ways and a second in $∣ B ∣$ ways, and distinct choices give distinct pairs by the defining property of ordered pairs; the multiplication principle gives $∣ A ∣ \cdot ∣ B ∣$ .

For the first identity, $(x, y) \in A \times (B \cup C)$ iff $x \in A$ and ( $y \in B$ or $y \in C$ ), which by distributivity of "and" over "or" is ( $x \in A$ and $y \in B$ ) or ( $x \in A$ and $y \in C$ ), that is $(x, y) \in (A \times B) \cup (A \times C)$ . Since every element of either side is an ordered pair, extensionality applies and the sets are equal. The second identity is the same computation with "or" replaced by "and".∎

Pitfall. $A \times B$ and $B \times A$ are different sets unless $A = B$ or one of them is empty: $(1, 2) \neq = (2, 1)$ . And $∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣$ is a product, whereas $∣ A \cup B ∣ \leq ∣ A ∣ + ∣ B ∣$ is a sum — mixing the two is a standard slip in counting problems.

Example 1.57 (Counting pairs and relations). Let $∣ A ∣ = 4$ and $∣ B ∣ = 3$ . Compute $∣ A \times B ∣$ , $∣ A^{2} ∣$ , and the number of subsets of $A \times B$ .

Solution.

$∣ A \times B ∣ = 4 \cdot 3 = 12$ .
$∣ A^{2} ∣ = 4 \cdot 4 = 16$ .
A subset of $A \times B$ is a relation from $A$ to $B$ ; there are $2^{12} = 4096$ of them, by Theorem The power set of a finite set.

□

Exercises for §1.28 →

Common Mistakes

Confusing $\in$ with $\subseteq$ . $1 \in {1, 2}$ is true and $1 \subseteq {1, 2}$ is not; ${1} \subseteq {1, 2}$ is true and ${1} \in {1, 2}$ is not. The correct translation is Theorem Inclusion is a partial order part (4): $x \in A$ if and only if ${x} \subseteq A$ .
Treating $\in$ as transitive. From $1 \in {1}$ and ${1} \in {{1}}$ it does not follow that $1 \in {{1}}$ . Only $\subseteq$ chains.
Confusing $\emptyset$ with ${\emptyset}$ . The first has cardinality $0$ , the second cardinality $1$ . Consequently $P (\emptyset) = {\emptyset}$ has one element, not none.
Forgetting that $\emptyset$ and $A$ are subsets of $A$ . Both belong to $P (A)$ always; "proper subsets" excludes $A$ but never $\emptyset$ .
Writing $∣ P (A) ∣ = 2∣ A ∣$ . The formula is $2^{∣ A ∣}$ . For $∣ A ∣ = 10$ the difference is $20$ against $1024$ .
Counting a union by adding. $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ only when $A$ and $B$ are disjoint; in general subtract $∣ A \cap B ∣$ .
Proving only one inclusion. Showing $A \subseteq B$ proves containment, not equality. Every equality proof needs both directions, or an explicit chain of equalities each of which is reversible.
Using unrestricted set-builder notation. ${x : P (x)}$ with no ambient set is the form that produces Russell's paradox. Always write ${x \in A : P (x)}$ .
Assuming every collection is a set. "The set of all sets", "the set of all groups" and "the set of all one-element sets" are proper classes, and reasoning with them as sets proves false things.
Intersecting an empty family. $⋂_{i \in \emptyset} A_{i}$ is only meaningful relative to a fixed universe $U$ , where it equals $U$ . Unrestricted, it is not a set.
Assuming $A ∖ B$ requires $B \subseteq A$ , or that $∖$ is commutative. Neither holds: elements of $B$ outside $A$ are simply ignored, and $A ∖ B$ is rarely $B ∖ A$ .
Reading "or" exclusively. $x \in A \cup B$ includes the case $x \in A \cap B$ . There is no "but not both" hidden in the definition.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter