The Grammar of Mathematics: Reading and Writing Sets and Logic

0. Key points

• Mathematical prose is written using only two vocabularies: sets and logic. These are not separate subjects. The correspondences $\cap$ with “and”, $\cup$ with “or”, and $\subseteq$ with “implies” are exact.
• A proof of a set equality $A = B$ can always be split into the two inclusions $A \subseteq B$ and $B \subseteq A$ (Proposition 3.4). Whenever you are unsure how to begin a proof, return to this.
• ”$P$ implies $Q$” is not a statement of causation. If $P$ is false, the implication is true. This convention is what allows a sentence such as “every element of the empty set exceeds $\sqrt{2}$” to be handled without contradiction (Proposition 3.6).
• De Morgan’s laws wear three faces — one in propositional logic, one for sets, one for quantifiers — but there is only one law underneath (Lemma 4.3, Theorem 4.4, Corollary 5.6).
• Negating $\forall$ and $\exists$ is the mechanical operation of pushing the negation sign inward while interchanging $\forall$ and $\exists$ (Theorem 5.3). The negation of an $\varepsilon$-$\delta$ statement is produced by this procedure alone.
• “Sufficient condition” and “necessary condition” merely name the two directions of an arrow, and they say exactly what an inclusion of truth sets says (Proposition 6.3).

1. Motivation — what to rely on when intuition breaks

If the conventions of mathematical language are taught as mere etiquette, it is impossible to see why so much care is needed. This section gives one episode in which the need actually arose.

Until the first half of the nineteenth century, a function was something one pictured as a graph. “A continuous function admits a tangent line except at scattered points” was, to the mathematicians of that era, beyond doubt. Then in 1872 Weierstrass showed that a function of the form

$$W(x) = \sum_{n=0}^{\infty} a^{n} \cos(b^{n} \pi x)$$

(with $0 < a < 1$, with $b$ an odd natural number, and with $ab > 1 + \tfrac{3}{2}\pi$) is continuous at every real $x$ and yet differentiable at no point whatsoever. Something that cannot be drawn stood there as a formula. At that moment it became necessary to fix the meanings of “continuous” and “differentiable” by sentences rather than by pictures.

Around the same time Cantor began comparing the sizes of infinite sets, and the word “set” itself came under pressure to be made precise. By the end of the nineteenth century a style had been established: write a mathematical assertion as a finite string of symbols, and decide its truth from the written form alone. The vocabulary used in that style is the vocabulary of sets and logic.

By the end of this article you will be able to answer questions as elementary as the following.

1. In a class containing no students at all, is “every student in the class is at least three metres tall” true or false?
2. “If $x = 2$ then $x^2 = 4$” is true, yet its converse is false. Why? What exactly is $x^2 = 4$ to $x = 2$?
3. “For every real number there is a larger real number” and “there is a real number larger than every real number” — where, written in symbols, do these differ?

Note

This is the first of six chapters. The vocabulary set up here is used in every later chapter. The proof patterns themselves — proof by contradiction, mathematical induction, contraposition — are treated in Proof techniques (the principle of mathematical induction（Theorem 3.2）［Techniques of Proof］, the validity of proof by contradiction（Proposition 6.2）［Techniques of Proof］), and the comparison of sizes of infinite sets is taken up in Cardinality and infinity.

2. Propositions and logical connectives

2.1. Propositions

Definition 2.1（Proposition）

A proposition is an assertion that is determined to be exactly one of true or false. When a proposition $P$ is true we say that its truth value is $\mathrm{T}$; when it is false, that its truth value is $\mathrm{F}$.

The phrase “determined to be exactly one of” is doing real work. “This sentence is false” is contradictory whether taken as true or as false, so it is not a proposition. "$x + 1 = 3$" is not a proposition either, since its truth is undetermined until we say what $x$ is; assertions containing variables are treated as predicates in Definition 5.1.

Remark 2.2

Strictly speaking, describing a proposition as “an assertion determined to be true or false” is not a complete definition, since it does not explain what an assertion is. Mathematical logic first defines formulas as strings of symbols by finitely many rules, and then separately specifies a procedure that assigns truth values to them. This article works at the practical level just short of that. The move into formalization itself is discussed in Incompleteness theorems.

2.2. Four connectives and truth tables

Definition 2.3（Logical connectives）

Given propositions $P$ and $Q$, we define the new propositions $\lnot P$ (not $P$), $P \land Q$ ($P$ and $Q$), $P \lor Q$ ($P$ or $Q$), $P \implies Q$ (if $P$ then $Q$), and $P \iff Q$ ($P$ and $Q$ are equivalent) by the following table.

$P$	$Q$	$\lnot P$	$P \land Q$	$P \lor Q$	$P \implies Q$	$P \iff Q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

This table is the definition. The meaning of a connective is fixed by these four rows and not by the nuances of ordinary speech. Two points in particular depart from everyday usage.

• “Or” is not exclusive. If $P$ and $Q$ are both true, then $P \lor Q$ is true. This is unlike the everyday choice “coffee or tea”. To say that both cannot hold, write $(P \lor Q) \land \lnot(P \land Q)$.
• “Implies” is not causal. If $P$ is false, then $P \implies Q$ is true whatever $Q$ may be. “If $2 < 1$ then Mount Fuji is at sea level” is, in the mathematical sense, a true proposition.

Discomfort at the second point is natural. Read $\implies$ not as asserting a connection between $P$ and $Q$, but as asserting only that the situation ”$P$ holds while $Q$ fails” does not occur. Indeed, as Proposition 2.4 shows, $P \implies Q$ has the same meaning as $\lnot(P \land \lnot Q)$. Adopting this reading, we automatically obtain the convenient convention that an assertion about all members of a collection is true when the collection has no members (Proposition 3.6).

Proposition 2.4（Reformulations of implication）

For all propositions $P$ and $Q$, the following three propositions always take the same truth value.

$$P \implies Q, \qquad \lnot P \lor Q, \qquad \lnot Q \implies \lnot P .$$

The third is called the contrapositive of $P \implies Q$. Moreover, $\lnot(P \implies Q)$ and $P \land \lnot Q$ always take the same truth value.

Proof（Proposition 2.4）

Following the table in Definition 2.3, we write out all four combinations of truth values of $P$ and $Q$.

$P$	$Q$	$P \implies Q$	$\lnot P \lor Q$	$\lnot Q \implies \lnot P$	$P \land \lnot Q$	$\lnot(P \implies Q)$
T	T	T	T	T	F	F
T	F	F	F	F	T	T
F	T	T	T	T	F	F
F	F	T	T	T	F	F

We check each row. In row 1, $P$ is true and $Q$ is true, so $P \implies Q$ is T by row 1 of the table; $\lnot P$ is F, so $\lnot P \lor Q = \mathrm{F} \lor \mathrm{T} = \mathrm{T}$; and $\lnot Q$ is F and $\lnot P$ is F, so $\lnot Q \implies \lnot P$ is $\mathrm{F} \implies \mathrm{F} = \mathrm{T}$. In row 2, $P$ is true and $Q$ is false, so $P \implies Q$ is F, $\lnot P \lor Q = \mathrm{F} \lor \mathrm{F} = \mathrm{F}$, and $\lnot Q \implies \lnot P$ is $\mathrm{T} \implies \mathrm{F} = \mathrm{F}$. In rows 3 and 4, $P$ is false, so $P \implies Q$ is T; $\lnot P$ is true, so $\lnot P \lor Q$ is T; and $\lnot Q \implies \lnot P$ is T because its conclusion $\lnot P$ is true.

Thus the three columns $P \implies Q$, $\lnot P \lor Q$ and $\lnot Q \implies \lnot P$ agree in all four rows. The column $P \land \lnot Q$ likewise agrees with the column $\lnot(P \implies Q)$ in all four rows.

∎

The availability of the contrapositive pays off directly in the practice of proof. Proving “if $n^2$ is even then $n$ is even” head-on is awkward, but the contrapositive “if $n$ is odd then $n^2$ is odd” requires only setting $n = 2k+1$ and computing $n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k)+1$. (For how this lemma is used in the proof that $\sqrt{2}$ is irrational, see if a square is even so is its root（Lemma 7.4）［Techniques of Proof］.)

Example 2.5（Converse, inverse and contrapositive）

Let $x$ be a real number, let $P$ be "$x = 2$", and let $Q$ be "$x^2 = 4$".

• $P \implies Q$ is true, since $x = 2$ gives $x^2 = 2^2 = 4$.
• The converse $Q \implies P$ is false. Taking $x = -2$ makes $x^2 = 4$ true and $x = 2$ false, which is row 2 of the table in Definition 2.3, so $Q \implies P$ is F.
• The inverse $\lnot P \implies \lnot Q$ is also false, since for $x = -2$ the antecedent $\lnot P$ is true while $\lnot Q$ is false.
• The contrapositive $\lnot Q \implies \lnot P$ is true: if $x^2 \ne 4$ then $x$ cannot be $2$. As Proposition 2.4 guarantees, this is the same as the truth of $P \implies Q$.

The converse and the inverse are contrapositives of each other, so, as we have just seen, they share their truth value.

3. Basic notions about sets

3.1. Elements and extensionality

Definition 3.1（Set and element）

A set is a collection of objects such that, for any object $x$, whether or not $x$ belongs to it is uniquely determined. We write $x \in A$ to say that $x$ belongs to the set $A$, and call $x$ an element (or member) of $A$. Non-membership is written $x \notin A$.

There are two ways to specify a set: by listing all its elements, as in $A = \{1, 2, 3\}$, and by comprehension, that is by carving it out with a condition, as in $A = \{x \in \mathbb{N} \mid x \le 3\}$. Here $\mathbb{N} = \{1, 2, 3, \ldots\}$, and we do not include $0$.

Axiom 3.2（Principle of extensionality）

For sets $A$ and $B$ we stipulate

$$A = B \iff \forall x\,(x \in A \iff x \in B).$$

That is, a set is determined by nothing but which elements it has.

This is a stipulation, not a theorem. From it, it follows that a set has neither order nor repetition. Indeed $\{1, 2\}$ and $\{2, 1, 1\}$ both satisfy ”$x$ belongs precisely when $x$ is $1$ or $2$”, so they are equal sets by Axiom 3.2.

Definition 3.3（Subset）

For sets $A$ and $B$ we define

$$A \subseteq B \quad :\Longleftrightarrow \quad \forall x\,(x \in A \implies x \in B)$$

and say that $A$ is a subset of $B$. If moreover $A \subseteq B$ and $A \ne B$, we say that $A$ is a proper subset of $B$ and write $A \subsetneq B$.

The symbols $\in$ and $\subseteq$ are different things: $\in$ expresses membership, $\subseteq$ expresses inclusion. For $A = \{1, 2\}$, the statement $1 \in A$ is true while $1 \subseteq A$ is meaningless ($1$ is not a set); and $\{1\} \subseteq A$ is true while $\{1\} \in A$ is false, because the elements of $A$ are $1$ and $2$, not $\{1\}$.

Proposition 3.4（Set equality is double inclusion）

For sets $A$ and $B$,

$$A = B \iff (A \subseteq B \ \text{and}\ B \subseteq A).$$

Proof（Proposition 3.4）

By Axiom 3.2, $A = B$ is equivalent to “for every $x$, $x \in A \iff x \in B$”. It therefore suffices to see that, for each $x$,

$$(x \in A \iff x \in B) \quad\text{and}\quad \bigl((x \in A \implies x \in B) \ \text{and}\ (x \in B \implies x \in A)\bigr)$$

take the same truth value. Put $P$ for $x \in A$ and $Q$ for $x \in B$ and consult the table in Definition 2.3: $P \iff Q$ is T exactly in row 1 (both T) and row 4 (both F). On the other hand $(P \implies Q) \land (Q \implies P)$ is F in row 2, where $P \implies Q$ is F, and F in row 3, where $Q \implies P$ is F, while in rows 1 and 4 both implications are T and so the conjunction is T. Hence the two agree in all four rows.

Consequently “for every $x$, $x \in A \iff x \in B$” is equivalent to “for every $x$, $x \in A \implies x \in B$” together with “for every $x$, $x \in B \implies x \in A$”. By Definition 3.3 this is precisely $A \subseteq B$ and $B \subseteq A$.

∎

This proposition supplies the proof pattern used most often not only in this article but in all of mathematics. On seeing a set equality, split it into two inclusions and write each in the form “assume $x \in$ left-hand side and derive $x \in$ right-hand side”. This is called element chasing.

3.2. The empty set and power sets

Definition 3.5（Empty set and power set）

A set with no elements at all is called the empty set and is written $\emptyset$; that is, $x \notin \emptyset$ for every $x$.

For a set $A$, the set

$$\mathcal{P}(A) = \{X \mid X \subseteq A\}$$

consisting of all subsets of $A$ is called the power set of $A$.

Proposition 3.6（Basic properties of the empty set）

(1) For every set $A$ we have $\emptyset \subseteq A$.
(2) The empty set is unique: if $E$ and $E'$ are sets with no elements, then $E = E'$.

Proof（Proposition 3.6）

(1) By Definition 3.3, what must be shown is “for every $x$, $x \in \emptyset \implies x \in A$”. Take $x$ arbitrary; by Definition 3.5, $x \in \emptyset$ is false. Looking at the table in Definition 2.3, in the rows with a false antecedent (rows 3 and 4) the value of $\implies$ is T. Hence $x \in \emptyset \implies x \in A$ is true regardless of $x$, and $\emptyset \subseteq A$ holds.

(2) Suppose $E$ and $E'$ both have no elements. The same argument as in (1) gives $E \subseteq E'$ and $E' \subseteq E$: since $x \in E$ is always false, $x \in E \implies x \in E'$ is always true, and likewise $x \in E' \implies x \in E$ is always true. By Proposition 3.4, $E = E'$.

∎

An assertion that is automatically true because its antecedent never holds — as in the proof of (1) — is said to be vacuously true. The claim mentioned at the outset, that in a class with no students every student is at least three metres tall, has the same structure and is true: since not a single student can be produced as a counterexample, there is no way to make the assertion false.

Example 3.7（Writing out a power set）

Let $A = \{1, 2, 3\}$. We enumerate the subsets exhaustively, grouped by their number of elements.

• $0$ elements: $\emptyset$
• $1$ element: $\{1\}, \{2\}, \{3\}$
• $2$ elements: $\{1,2\}, \{1,3\}, \{2,3\}$
• $3$ elements: $\{1,2,3\}$

Therefore

$$\mathcal{P}(A) = \bigl\{\, \emptyset,\ \{1\},\ \{2\},\ \{3\},\ \{1,2\},\ \{1,3\},\ \{2,3\},\ \{1,2,3\} \,\bigr\}$$

and the number of elements of $\mathcal{P}(A)$ is $1 + 3 + 3 + 1 = 8 = 2^{3}$. Note that $\emptyset$ occurs by part (1) of Proposition 3.6, and that $A$ itself occurs because $A \subseteq A$.

Theorem 3.8（Cardinality of a power set）

If $A$ is a finite set with $n$ elements, then $\mathcal{P}(A)$ has $2^{n}$ elements.

Proof（Theorem 3.8）

Label the elements of $A$ as $a_1, a_2, \ldots, a_n$ (so that $a_i \ne a_j$ whenever $i \ne j$). Let

$$S = \{(\varepsilon_1, \ldots, \varepsilon_n) \mid \text{each } \varepsilon_i \text{ is } 0 \text{ or } 1\}$$

be the set of all $0$-$1$ strings of length $n$. Define a map $\chi$ from $\mathcal{P}(A)$ to $S$ by setting, for $X \subseteq A$,

$$\chi(X) = (\varepsilon_1, \ldots, \varepsilon_n), \qquad \varepsilon_i = \begin{cases} 1 & (a_i \in X) \\ 0 & (a_i \notin X) \end{cases}$$

For each $i$ exactly one of $a_i \in X$ and $a_i \notin X$ holds (Definition 3.1), so $\chi(X)$ is uniquely determined.

We show that $\chi$ is injective. Suppose $X, Y \subseteq A$ satisfy $\chi(X) = \chi(Y)$. Every $x \in A$ equals $a_i$ for some $i$, and since the $i$-th entries agree, "$a_i \in X$" and "$a_i \in Y$" either both hold or both fail. For $x \notin A$, the inclusions $X \subseteq A$ and $Y \subseteq A$ give $x \notin X$ and $x \notin Y$. Hence $x \in X \iff x \in Y$ for every $x$, and Axiom 3.2 yields $X = Y$.

We show that $\chi$ is surjective. Given $(\varepsilon_1, \ldots, \varepsilon_n) \in S$, put $X = \{a_i \mid \varepsilon_i = 1\}$. Then $X \subseteq A$, and by construction $a_i \in X$ holds exactly when $\varepsilon_i = 1$, so $\chi(X) = (\varepsilon_1, \ldots, \varepsilon_n)$.

Therefore $\mathcal{P}(A)$ and $S$ have the same number of elements. The elements of $S$ are formed by choosing each entry independently from $2$ possibilities, so there are $2 \times 2 \times \cdots \times 2 = 2^{n}$ of them. Hence $\mathcal{P}(A)$ has $2^{n}$ elements.

∎

Remark 3.9

Even when $A$ is infinite, one can prove that $\mathcal{P}(A)$ is “strictly larger” than $A$ (Cantor's theorem（Theorem 7.1）［濃度と無限］). This is the counterpart of $2^n > n$ in the finite case, but its proof rests on the diagonal argument rather than on counting. See Cardinality and infinity for details. An alternative proof of Theorem 3.8 by induction on $n$ is treated as an example in Proof techniques.

4. Operations on sets

4.1. Definitions and their correspondence with connectives

From here on we fix a set $U$ containing all objects under consideration and call it the universal set. Every set we handle is a subset of $U$.

Definition 4.1（Union, intersection, difference, complement）

For $A, B \subseteq U$ we define

$$\begin{aligned} A \cup B &= \{x \in U \mid x \in A \ \text{or}\ x \in B\} &&(\text{union}) \\ A \cap B &= \{x \in U \mid x \in A \ \text{and}\ x \in B\} &&(\text{intersection}) \\ A \setminus B &= \{x \in U \mid x \in A \ \text{and}\ x \notin B\} &&(\text{difference}) \\ A^{c} &= \{x \in U \mid x \notin A\} &&(\text{complement}) \end{aligned}$$

When $A \cap B = \emptyset$ we say that $A$ and $B$ are disjoint.

As the definitions make plain, the operations on sets are restatements of the logical connectives. The following table of correspondences is the backbone of the whole article.

Sets	Condition on $x$	Logic
$A \cap B$	$x \in A$ and $x \in B$	$\land$
$A \cup B$	$x \in A$ or $x \in B$	$\lor$
$A \setminus B$	$x \in A$ and $x \notin B$	$\land$ with $\lnot$
$A^{c}$	$x \notin A$	$\lnot$
$A \subseteq B$	if $x \in A$ then $x \in B$	$\implies$
$A = B$	$x \in A$ and $x \in B$ are equivalent	$\iff$

Because of this correspondence, each identity proved in logic hands us an identity about sets. We carry out that procedure explicitly below.

Two sets A and B inside a universal set U. The four regions cut out by the boundaries are numbered.

The four regions of the figure are: ① is $A \setminus B$, ② is $A \cap B$, ③ is $B \setminus A$, and ④ is $A^{c} \cap B^{c}$. Any $x \in U$ lies in exactly one of these four, according to the combination of whether $x \in A$ and whether $x \in B$.

Caution

A Venn diagram is a tool of discovery, not a proof. Once three or more sets are involved, the planar circles can no longer separate all the ways they may intersect (drawing four sets as four circles fails to produce some of the $2^4 = 16$ regions that ought to be present). Use a diagram to form a guess, and write the proof by element chasing.

4.2. The distributive law

Theorem 4.2（Distributive law）

For $A, B, C \subseteq U$,

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

Proof（Theorem 4.2）

By Proposition 3.4 we prove two inclusions.

($\subseteq$) Let $x \in A \cap (B \cup C)$. By Definition 4.1, $x \in A$ and $x \in B \cup C$. From the latter, $x \in B$ or $x \in C$.

• Case $x \in B$: combined with $x \in A$ this gives $x \in A \cap B$, hence $x \in (A \cap B) \cup (A \cap C)$.
• Case $x \in C$: combined with $x \in A$ this gives $x \in A \cap C$, hence $x \in (A \cap B) \cup (A \cap C)$.

In either case $x \in (A \cap B) \cup (A \cap C)$, so $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$.

($\supseteq$) Let $x \in (A \cap B) \cup (A \cap C)$. Then $x \in A \cap B$ or $x \in A \cap C$.

• Case $x \in A \cap B$: here $x \in A$ and $x \in B$. From $x \in B$ we get $x \in B \cup C$, so $x \in A \cap (B \cup C)$.
• Case $x \in A \cap C$: here $x \in A$ and $x \in C$. From $x \in C$ we get $x \in B \cup C$, so $x \in A \cap (B \cup C)$.

In either case $x \in A \cap (B \cup C)$, so $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$.

Both inclusions being established, Proposition 3.4 gives the equality.

∎

The other distributive law, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, is proved by the same pattern. So that you can work it through yourself, it has been left to Exercise 7.2.

4.3. De Morgan’s laws

Lemma 4.3（De Morgan's laws (propositional form)）

For all propositions $P$ and $Q$, the propositions $\lnot(P \lor Q)$ and $\lnot P \land \lnot Q$ always take the same truth value. Likewise $\lnot(P \land Q)$ and $\lnot P \lor \lnot Q$ always take the same truth value.

Proof（Lemma 4.3）

Following the table in Definition 2.3, we write out the four cases.

$P$	$Q$	$P \lor Q$	$\lnot(P \lor Q)$	$\lnot P \land \lnot Q$	$P \land Q$	$\lnot(P \land Q)$	$\lnot P \lor \lnot Q$
T	T	T	F	F	T	F	F
T	F	T	F	F	F	T	T
F	T	T	F	F	F	T	T
F	F	F	T	T	F	T	T

For instance in row 2, $P$ is T and $Q$ is F, so $P \lor Q$ is T and its negation is F; on the other side $\lnot P$ is F, so $\lnot P \land \lnot Q$ is F, and the two agree. In the same row $P \land Q$ is F, its negation is T, and $\lnot P \lor \lnot Q = \mathrm{F} \lor \mathrm{T} = \mathrm{T}$, so these agree as well. The remaining three rows are as tabulated.

The column $\lnot(P \lor Q)$ agrees with the column $\lnot P \land \lnot Q$, and the column $\lnot(P \land Q)$ agrees with the column $\lnot P \lor \lnot Q$, in all four rows.

∎

Theorem 4.4（De Morgan's laws (set form)）

For $A, B \subseteq U$,

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

Proof（Theorem 4.4）

We prove the first identity. Take $x \in U$ arbitrary and put $P$ for the proposition "$x \in A$" and $Q$ for "$x \in B$". Using the definitions in Definition 4.1, and Lemma 4.3 at the fourth line, the following equivalences hold in turn.

$$\begin{aligned} x \in (A \cup B)^{c} &\iff x \notin A \cup B && (\text{definition of complement}) \\ &\iff \lnot(x \in A \ \text{or}\ x \in B) && (\text{definition of union}) \\ &\iff \lnot(P \lor Q) \\ &\iff \lnot P \land \lnot Q && (\text{De Morgan, propositional form}) \\ &\iff x \notin A \ \text{and}\ x \notin B \\ &\iff x \in A^{c} \ \text{and}\ x \in B^{c} && (\text{definition of complement}) \\ &\iff x \in A^{c} \cap B^{c} && (\text{definition of intersection}). \end{aligned}$$

Since $x \in (A \cup B)^{c} \iff x \in A^{c} \cap B^{c}$ for every $x \in U$, Axiom 3.2 gives $(A \cup B)^{c} = A^{c} \cap B^{c}$.

The second identity is proved by the same chain: $x \in (A \cap B)^{c} \iff \lnot(P \land Q)$, and by the second half of Lemma 4.3 we have $\lnot(P \land Q) \iff \lnot P \lor \lnot Q$, which says $x \in A^{c}$ or $x \in B^{c}$, that is $x \in A^{c} \cup B^{c}$. Hence Axiom 3.2 gives $(A \cap B)^{c} = A^{c} \cup B^{c}$.

∎

The first half of Theorem 4.4 can also be checked using the four regions of the figure following Definition 4.1. Tabulating, for each region, whether a point lies in each side, we obtain the following (○ means “belongs”, × means “does not belong”).

Region	$x \in A$	$x \in B$	$A \cup B$	$(A \cup B)^{c}$	$A^{c}$	$B^{c}$	$A^{c} \cap B^{c}$
①	○	×	○	×	×	○	×
②	○	○	○	×	×	×	×
③	×	○	○	×	○	×	×
④	×	×	×	○	○	○	○

The column $(A \cup B)^{c}$ agrees with the column $A^{c} \cap B^{c}$ in all four rows. What makes this check a proof is that the four regions exhaust $U$.

Example 4.5（Checking with concrete sets）

Let $U = \{1,2,3,4,5,6,7,8,9,10\}$, let $A$ be the set of even numbers in $U$, and let $B$ the set of multiples of $3$ in $U$; that is,

$$A = \{2,4,6,8,10\}, \qquad B = \{3,6,9\}.$$

First compute the left-hand side. Since $A \cup B = \{2,3,4,6,8,9,10\}$,

$$(A \cup B)^{c} = \{1,5,7\}.$$

Now the right-hand side. We have $A^{c} = \{1,3,5,7,9\}$ and $B^{c} = \{1,2,4,5,7,8,10\}$, so picking out the common elements,

$$A^{c} \cap B^{c} = \{1,5,7\}.$$

The two agree. Reading off the meaning: the numbers that are neither even nor multiples of $3$ are not “the primes up to $6$ together with $1$ and $7$” but, correctly, “the natural numbers at most $10$ divisible by neither $2$ nor $3$”, namely $1, 5, 7$.

Remark 4.6

Not every operation shares the properties of arithmetic. Set difference is not associative. Taking $A = B = C = \{1\}$,

$$(A \setminus B) \setminus C = \emptyset \setminus \{1\} = \emptyset, \qquad A \setminus (B \setminus C) = \{1\} \setminus \emptyset = \{1\},$$

and these differ. Hence the unparenthesized notation $A \setminus B \setminus C$ is not permissible. The analogy ”$\cup$ and $\cap$ are associative, so $\setminus$ must be too” breaks down here.

5. Predicates and quantifiers

5.1. Predicates

Definition 5.1（Predicate）

Fix a set $X$. If for each $a \in X$ a proposition $P(a)$ is determined, then $P$ is called a predicate (or condition) on $X$, and $X$ is called the domain of $P$.

"$x + 1 = 3$" becomes a predicate on $\mathbb{N}$ once we fix $\mathbb{N}$ as the domain: $P(2)$ is true, $P(5)$ is false, and so on — truth is decided only after a value is substituted for $x$. Note that leaving the domain unstated changes the truth value. “There exists $x$ with $x^2 = 2$” is false with domain $\mathbb{Q}$ (irrationality of the square root of 2（Theorem 7.5）［Techniques of Proof］) and true with domain $\mathbb{R}$ (existence of √2（Theorem 5.6）［What Is a Number? From the Naturals to the Reals, and Why 1 = 0.999… Is True］).

Definition 5.2（Universal and existential quantifiers）

For a predicate $P$ on $X$ we define the following two propositions.

• $\forall x \in X,\ P(x)$: true if and only if $P(a)$ is true for every element $a$ of $X$.
• $\exists x \in X,\ P(x)$: true if and only if there is at least one $a \in X$ for which $P(a)$ is true.

We call $\forall$ the universal quantifier and $\exists$ the existential quantifier, and refer to them collectively as quantifiers.

Let us record the values when the domain is empty. If $X = \emptyset$, then $\forall x \in \emptyset,\ P(x)$ is true: were it false, there would have to be some $a \in \emptyset$ with $P(a)$ false, but $\emptyset$ has no elements. On the other hand $\exists x \in \emptyset,\ P(x)$ is false: before asking whether $P(a)$ is true, there is no $a$ with $a \in \emptyset$ at all. This is a restatement of the vacuous truth seen in Proposition 3.6.

5.2. How to form negations

Theorem 5.3（Negation of quantifiers）

Let $X$ be a set and $P$ a predicate on $X$. Then

$$\lnot\bigl(\forall x \in X,\ P(x)\bigr) \iff \exists x \in X,\ \lnot P(x),$$$$\lnot\bigl(\exists x \in X,\ P(x)\bigr) \iff \forall x \in X,\ \lnot P(x).$$

Proof（Theorem 5.3）

We prove the first equivalence.

($\Longrightarrow$) Suppose $\lnot(\forall x \in X, P(x))$ is true. Assume for contradiction that the conclusion $\exists x \in X,\ \lnot P(x)$ is false. By Definition 5.2, this says that there is no $a \in X$ making $\lnot P(a)$ true. Then for every $a \in X$ the statement $\lnot P(a)$ is false, that is, $P(a)$ is true. By Definition 5.2 this means $\forall x \in X, P(x)$ is true, contradicting the assumption $\lnot(\forall x \in X, P(x))$. Hence $\exists x \in X,\ \lnot P(x)$ is true.

($\Longleftarrow$) Suppose $\exists x \in X,\ \lnot P(x)$ is true, and pick an element $a \in X$ with $\lnot P(a)$ true. If $\forall x \in X, P(x)$ were true, then since $a \in X$ we would get that $P(a)$ is true, contradicting the truth of $\lnot P(a)$. Hence $\forall x \in X, P(x)$ is false, that is, $\lnot(\forall x \in X, P(x))$ is true.

The second equivalence follows by applying the first to the predicate $\lnot P$. Indeed, the first gives $\lnot(\forall x \in X, \lnot P(x)) \iff \exists x \in X, \lnot\lnot P(x)$, and since $\lnot \lnot P(x)$ and $P(x)$ take the same truth value (applying $\lnot$ twice in the table of Definition 2.3 returns the original value), we obtain $\lnot(\forall x \in X, \lnot P(x)) \iff \exists x \in X, P(x)$. Negating both sides and removing the double negation again yields $\forall x \in X, \lnot P(x) \iff \lnot(\exists x \in X, P(x))$.

∎

Combining this theorem with the last assertion of Proposition 2.4 ($\lnot(P \implies Q)$ is $P \land \lnot Q$) lets us push a negation mechanically inward through a formula of any length. There are only three steps.

1. Change a leading $\forall$ into $\exists$ and a leading $\exists$ into $\forall$, moving the $\lnot$ one step inward.
2. Replace $\lnot(P \land Q)$ by $\lnot P \lor \lnot Q$, and $\lnot(P \lor Q)$ by $\lnot P \land \lnot Q$ (Lemma 4.3).
3. Replace $\lnot(P \implies Q)$ by $P \land \lnot Q$ (Proposition 2.4).

flowchart TB
S0["¬ ∀ε ∃δ ∀x ( P ⟹ Q )"] --> S1["∃ε ¬ ∃δ ∀x ( P ⟹ Q )"]
S1 --> S2["∃ε ∀δ ¬ ∀x ( P ⟹ Q )"]
S2 --> S3["∃ε ∀δ ∃x ¬( P ⟹ Q )"]
S3 --> S4["∃ε ∀δ ∃x ( P ∧ ¬Q )"]

Forming the negation of an ε-δ statement. At each stage the negation sign moves one step inward and a quantifier is interchanged.

Example 5.4（Negating the definition of continuity）

A real-valued function $f$ is continuous at a point $a$ when

$$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \mathbb{R},\ \bigl(|x - a| < \delta \implies |f(x) - f(a)| < \varepsilon\bigr)$$

holds. We form the negation by the three steps above, using Theorem 5.3 in the first three stages and Proposition 2.4 in the last.

$$\begin{aligned} &\lnot\Bigl(\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x,\ (|x-a| < \delta \implies |f(x)-f(a)| < \varepsilon)\Bigr) \\ &\iff \exists \varepsilon > 0,\ \lnot\Bigl(\exists \delta > 0,\ \forall x,\ (\cdots)\Bigr) && (\text{negation of a quantifier}) \\ &\iff \exists \varepsilon > 0,\ \forall \delta > 0,\ \lnot\Bigl(\forall x,\ (\cdots)\Bigr) && (\text{negation of a quantifier}) \\ &\iff \exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x,\ \lnot\bigl(|x-a| < \delta \implies |f(x)-f(a)| < \varepsilon\bigr) && (\text{negation of a quantifier}) \\ &\iff \exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x,\ \bigl(|x-a| < \delta \ \land\ |f(x)-f(a)| \ge \varepsilon\bigr) && (\text{negation of an implication}). \end{aligned}$$

Put into words: there exists some $\varepsilon > 0$ such that, however small one takes $\delta > 0$, one can find a point $x$ lying within distance $\delta$ of $a$ whose value nevertheless deviates by at least $\varepsilon$.

Let us use this. We show that

$$f(x) = \begin{cases} 0 & (x \le 0) \\ 1 & (x > 0) \end{cases}$$

is not continuous at $a = 0$. Take $\varepsilon = \tfrac{1}{2}$. Let $\delta > 0$ be arbitrary and choose $x = \delta/2$. Then $|x - 0| = \delta/2 < \delta$, and since $x > 0$ we have $f(x) = 1$ while $f(0) = 0$, so

$$|f(x) - f(0)| = |1 - 0| = 1 \ge \tfrac{1}{2} = \varepsilon .$$

As $\delta$ was arbitrary, the negation above holds. Hence $f$ is not continuous at $0$.

5.3. The order of quantifiers

Remark 5.5（The order must not be interchanged）

When a $\forall$ and an $\exists$ follow one another, their order changes the meaning. With domain $\mathbb{R}$:

• $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$ is true, because $y$ may be chosen after $x$ is given; take $y = x + 1$.
• $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$ is false, because $y$ must be fixed first, and then choosing $x = y$ makes $y > x$ fail. Using Theorem 5.3, its negation is $\forall y,\ \exists x,\ y \le x$, and $x = y$ indeed satisfies the condition.

The same phenomenon occurs for the continuity of Example 5.4. In continuity, $\delta$ may be chosen in response to both $\varepsilon$ and the point $a$; but moving $\forall a$ inside $\exists \delta$ to obtain

$$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall a,\ \forall x,\ \bigl(|x-a| < \delta \implies |f(x)-f(a)| < \varepsilon\bigr)$$

forbids $\delta$ to depend on $a$. This is the definition of uniform continuity, a stronger condition than continuity at each point. A single difference in the order of symbols produces an entirely different notion.

5.4. Generalization to families of sets

Corollary 5.6（De Morgan's laws (for families of sets)）

Let $\Lambda$ be a non-empty set and suppose that for each $\lambda \in \Lambda$ a set $A_{\lambda} \subseteq U$ is given. Defining

$$\bigcup_{\lambda \in \Lambda} A_{\lambda} = \{x \in U \mid \exists \lambda \in \Lambda,\ x \in A_{\lambda}\}, \qquad \bigcap_{\lambda \in \Lambda} A_{\lambda} = \{x \in U \mid \forall \lambda \in \Lambda,\ x \in A_{\lambda}\},$$

we have

$$\Bigl(\bigcup_{\lambda \in \Lambda} A_{\lambda}\Bigr)^{c} = \bigcap_{\lambda \in \Lambda} A_{\lambda}^{c}, \qquad \Bigl(\bigcap_{\lambda \in \Lambda} A_{\lambda}\Bigr)^{c} = \bigcup_{\lambda \in \Lambda} A_{\lambda}^{c}.$$

Proof（Corollary 5.6）

We prove the first identity. Take $x \in U$ arbitrary. At the second line we use the second half of Theorem 5.3 (the one turning $\lnot \exists$ into $\forall \lnot$).

$$\begin{aligned} x \in \Bigl(\bigcup_{\lambda} A_{\lambda}\Bigr)^{c} &\iff \lnot\bigl(\exists \lambda \in \Lambda,\ x \in A_{\lambda}\bigr) && (\text{definitions of union and complement}) \\ &\iff \forall \lambda \in \Lambda,\ \lnot(x \in A_{\lambda}) && (\text{negation of a quantifier}) \\ &\iff \forall \lambda \in \Lambda,\ x \in A_{\lambda}^{c} && (\text{definition of complement}) \\ &\iff x \in \bigcap_{\lambda \in \Lambda} A_{\lambda}^{c} && (\text{definition of intersection}). \end{aligned}$$

Since the equivalence holds for every $x \in U$, the two sides are equal by Axiom 3.2. The second identity is obtained by using, at the second line of the same chain, the first half of Theorem 5.3 (the one turning $\lnot \forall$ into $\exists \lnot$).

∎

The case where $\Lambda$ has two elements is Theorem 4.4. Thus Lemma 4.3, Theorem 4.4 and Corollary 5.6 are three manifestations of a single rule, which fits into one sentence: negation interchanges $\land$ with $\lor$, $\forall$ with $\exists$, and $\cap$ with $\cup$.

6. Necessary conditions, sufficient conditions, equivalence

Definition 6.1（Necessary and sufficient conditions）

For propositions $P$ and $Q$ such that $P \implies Q$ is true, we say that

• $P$ is a sufficient condition for $Q$, and
• $Q$ is a necessary condition for $P$.

When both $P \implies Q$ and $Q \implies P$ are true, that is when $P \iff Q$ is true, we say that $P$ is a necessary and sufficient condition for $Q$, and that $P$ and $Q$ are equivalent.

The way to remember this is: the side the arrow leaves is sufficient, the side it enters is necessary. Since asserting $P$ alone already yields $Q$, the condition $P$ is “sufficient”; and since $P$ cannot hold if $Q$ fails (the contrapositive, Proposition 2.4), the condition $Q$ is “necessary”.

Example 6.2（Numbers whose square is 4）

Consider three conditions on a real number $x$. $P$: $x = 2$; $Q$: $x^2 = 4$; $R$: $|x| = 2$.

• $P$ is a sufficient condition for $Q$, since $x = 2$ gives $x^2 = 4$. It is not a necessary one: $x = -2$ satisfies $Q$ but not $P$, so $Q \implies P$ is false.
• $Q$ is a necessary condition for $P$. This is nothing but a restatement of the truth of $P \implies Q$, read as: in order for $x = 2$, one must at least have $x^2 = 4$.
• $R$ is a necessary and sufficient condition for $Q$. If $|x| = 2$ then $x^2 = |x|^2 = 4$. Conversely, if $x^2 = 4$ then $x^2 - 4 = (x-2)(x+2) = 0$, so $x = 2$ or $x = -2$, and in either case $|x| = 2$.

Note that the sentence ”$x = 2$ is a sufficient condition for $x^2 = 4$” treats the condition $x = 2$ as the stronger one. A strong condition (one satisfied by few numbers) is a sufficient condition; a weak condition (one satisfied by many) is a necessary condition. The next proposition makes this intuition exact.

Proposition 6.3（Truth sets and their correspondence with logic）

Let $X$ be a set and let $P$, $Q$ be predicates on $X$. Define the truth set

$$[P] = \{x \in X \mid P(x) \ \text{is true}\}$$

(taking $X$ as the universal set). Then the following hold.

$$\begin{aligned} &\text{(1)}\quad \bigl(\forall x \in X,\ (P(x) \implies Q(x))\bigr) \iff [P] \subseteq [Q], \\ &\text{(2)}\quad [P \land Q] = [P] \cap [Q], \quad [P \lor Q] = [P] \cup [Q], \quad [\lnot P] = [P]^{c}. \end{aligned}$$

Proof（Proposition 6.3）

(1) By Definition 3.3, $[P] \subseteq [Q]$ means “for every $x$, $x \in [P] \implies x \in [Q]$”. By the definition of a truth set, $x \in [P]$ is equivalent to ”$x \in X$ and $P(x)$ is true”, and $x \in [Q]$ is equivalent to ”$x \in X$ and $Q(x)$ is true”. Restricting the domain to $X$ makes $x \in X$ automatic, so the condition coincides with “for every $x \in X$, $P(x) \implies Q(x)$”.

(2) Take $x \in X$ arbitrary. By definition, $x \in [P \land Q]$ says ”$P(x) \land Q(x)$ is true”, that is ”$P(x)$ is true and $Q(x)$ is true” (Definition 2.3), which is equivalent to $x \in [P]$ and $x \in [Q]$, that is to $x \in [P] \cap [Q]$ (Definition 4.1). Since the equivalence holds for every $x \in X$, Axiom 3.2 gives $[P \land Q] = [P] \cap [Q]$. The claims for $\lor$ and $\lnot$ follow by exactly the same procedure, since $\lor$ is the very definition of $\cup$ and $\lnot$ that of the complement.

∎

By (1), ”$P$ is a sufficient condition for $Q$” is the same as "$[P] \subseteq [Q]$". In Example 6.2 we have $[P] = \{2\}$ and $[Q] = \{2, -2\}$, so $[P] \subsetneq [Q]$, and the conclusion that $P$ is sufficient but not necessary is visible at a glance as an inclusion. The slogan “a sufficient condition is a small set, a necessary condition a large one” refers to exactly this inclusion.

Tip

When writing a definition one must check that it is well defined. For example, “for a rational number $p/q$ set $f(p/q) = p + q$” is not a definition, since $1/2 = 2/4$ while the prescribed values, $3$ and $6$, disagree. This procedure of verifying independence of the choice of representative is treated head-on in Relations and equivalence relations (this very example is examined in a 'definition' that is not well defined（Example 5.6）［関係と同値関係］).

Remark 6.4（The limits of naive set theory）

If, as in Definition 3.1, one supposes that writing down a condition produces a set, the theory collapses. Suppose we form the set

$$R = \{x \mid x \notin x\}$$

from the condition "$x \notin x$". If $R \in R$, then $R$ satisfies the condition, so $R \notin R$. Conversely, if $R \notin R$, then $R$ satisfies the condition, so $R \in R$. Either way we get a contradiction (Russell, 1901).

Modern axiomatic set theory (ZFC) abandons the principle that a set may be formed from an arbitrary condition, and permits only carving out a subset of an already existing set $A$ by a condition (the axiom schema of separation). This is why comprehension has always been written in the form $\{x \in U \mid \cdots\}$ in this article, with the domain $U$ made explicit. The question of what an axiom system does and does not guarantee leads on to Incompleteness theorems (the first incompleteness theorem（Theorem 5.1）［ゲーデルの不完全性定理］). And how far back one must define the meanings of the symbols before an equation such as "$0.999\ldots = 1$" is settled is taken up in What is a number?.

7. Exercises

Exercise 7.1Easy

Let $A = \{\emptyset, \{\emptyset\}\}$.

(1) Write out $\mathcal{P}(A)$ and check that the number of its elements agrees with Theorem 3.8.
(2) Decide, with reasons, whether each of the following four assertions is true or false: $\emptyset \in A$, $\emptyset \subseteq A$, $\{\emptyset\} \in A$, $\{\emptyset\} \subseteq A$.

Solution

(1) The elements of $A$ are $\emptyset$ and $\{\emptyset\}$, two in number. Listing the subsets by their number of elements: with $0$ elements, $\emptyset$; with $1$ element, $\{\emptyset\}$ and $\{\{\emptyset\}\}$; with $2$ elements, $\{\emptyset, \{\emptyset\}\} = A$. Hence

$$\mathcal{P}(A) = \bigl\{\, \emptyset,\ \{\emptyset\},\ \{\{\emptyset\}\},\ \{\emptyset, \{\emptyset\}\} \,\bigr\}$$

which has $4 = 2^{2}$ elements, in agreement with Theorem 3.8.

(2)

• $\emptyset \in A$ is true, since $\emptyset$ is listed as an element of $A$.
• $\emptyset \subseteq A$ is true, since by part (1) of Proposition 3.6 the empty set is a subset of every set.
• $\{\emptyset\} \in A$ is true, since the second element of $A$ is $\{\emptyset\}$.
• $\{\emptyset\} \subseteq A$ is true: the only element of $\{\emptyset\}$ is $\emptyset$, and $\emptyset \in A$ holds, so the condition of Definition 3.3 is met.

All four come out true in this example, but only because of the special circumstance that $\emptyset$ is both “an element of $A$” and “the content of a set all of whose elements belong to $A$”. In general, regard $\in$ and $\subseteq$ as unrelated.

Exercise 7.2Standard

For $A, B, C \subseteq U$, prove

$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$

by element chasing.

Solution

Following Proposition 3.4, we prove two inclusions.

($\subseteq$) Let $x \in A \cup (B \cap C)$. By Definition 4.1, $x \in A$ or $x \in B \cap C$.

• Case $x \in A$: from $x \in A$ we get $x \in A \cup B$ and $x \in A \cup C$, hence $x \in (A \cup B) \cap (A \cup C)$.
• Case $x \in B \cap C$: then $x \in B$ and $x \in C$. From $x \in B$ we get $x \in A \cup B$, and from $x \in C$ we get $x \in A \cup C$. Hence $x \in (A \cup B) \cap (A \cup C)$.

In either case $x$ lies in the right-hand side, so $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$.

($\supseteq$) Let $x \in (A \cup B) \cap (A \cup C)$, that is $x \in A \cup B$ and $x \in A \cup C$. We split according to whether $x \in A$.

• Case $x \in A$: then immediately $x \in A \cup (B \cap C)$.
• Case $x \notin A$: from $x \in A \cup B$ and $x \notin A$ it follows that $x \in B$ (by the definition of $\lor$, if $x \in A$ is false then $x \in B$ is true). Likewise $x \in A \cup C$ and $x \notin A$ give $x \in C$. Hence $x \in B \cap C$, and so $x \in A \cup (B \cap C)$.

In either case $x$ lies in the left-hand side, so $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$.

From the two inclusions, Proposition 3.4 gives the equality.

Exercise 7.3Standard

A real sequence $(a_n)_{n \in \mathbb{N}}$ converges to a real number $\alpha$ when

$$\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \in \mathbb{N},\ \bigl(n \ge N \implies |a_n - \alpha| < \varepsilon\bigr)$$

holds.

(1) Write the negation of this assertion with all quantifiers brought to the front.
(2) Show that the sequence defined by $a_n = (-1)^{n}$ converges to no real number $\alpha$.

Solution

(1) We use Theorem 5.3 three times, then Proposition 2.4 once.

$$\begin{aligned} &\lnot\bigl(\forall \varepsilon > 0,\ \exists N,\ \forall n,\ (n \ge N \implies |a_n - \alpha| < \varepsilon)\bigr) \\ &\iff \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N},\ \lnot\bigl(n \ge N \implies |a_n - \alpha| < \varepsilon\bigr) \\ &\iff \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N},\ \bigl(n \ge N \ \land\ |a_n - \alpha| \ge \varepsilon\bigr). \end{aligned}$$

(2) Let $\alpha$ be an arbitrary real number and take $\varepsilon = 1$. Let $N \in \mathbb{N}$ be arbitrary. Assume, for contradiction, that $|a_n - \alpha| < 1$ holds for every $n$ with $n \ge N$.

Let $n_0$ be an even number at least $N$ and $m_0$ an odd number at least $N$ (one of $N, N+1$ is even and the other odd, so both exist). By assumption $|a_{n_0} - \alpha| < 1$ and $|a_{m_0} - \alpha| < 1$. The triangle inequality gives

$$|a_{n_0} - a_{m_0}| \le |a_{n_0} - \alpha| + |\alpha - a_{m_0}| < 1 + 1 = 2 .$$

But $a_{n_0} = (-1)^{n_0} = 1$ and $a_{m_0} = (-1)^{m_0} = -1$, so $|a_{n_0} - a_{m_0}| = |1 - (-1)| = 2$, and we arrive at the contradiction $2 < 2$.

Hence the assumption fails, and there exists $n$ with $n \ge N$ and $|a_n - \alpha| \ge 1$. Since $N$ was arbitrary, the negation from (1) holds and $(a_n)$ does not converge to $\alpha$. Since $\alpha$ was arbitrary too, this sequence converges to no real number.

Exercise 7.4Hard

For $A, B \subseteq U$ define the symmetric difference by $A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)$. Show that for $A, B, C \subseteq U$,

$$(A \bigtriangleup B) \bigtriangleup C = A \bigtriangleup (B \bigtriangleup C).$$

Solution

We first prove, as a lemma, that for $x \in U$,

$$x \in A \bigtriangleup B \iff \text{exactly one of }x \in A\text{ and }x \in B\text{ holds}.$$

By Definition 4.1, $x \in A \setminus B$ says ”$x \in A$ and $x \notin B$”, while $x \in B \setminus A$ says ”$x \in B$ and $x \notin A$”. By the definition of union, $x \in A \bigtriangleup B$ says that one of these two holds, that is, that $x$ belongs to $A$ only or to $B$ only, which is the same as “exactly one”.

Next, write $k(x) \in \{0,1,2,3\}$ for the number of the sets $A$, $B$, $C$ to which $x$ belongs, and prove the assertion

$$x \in (A \bigtriangleup B) \bigtriangleup C \iff k(x) \ \text{is odd}.$$

Applying the lemma to $A \bigtriangleup B$ and $C$, the statement $x \in (A \bigtriangleup B) \bigtriangleup C$ says that exactly one of "$x \in A \bigtriangleup B$" and "$x \in C$" holds. We split according to whether $x \in C$.

• Case $x \in C$: the condition becomes $x \notin A \bigtriangleup B$, which by the lemma says that $x \in A$ and $x \in B$ either both hold or both fail. Then the number of $A$, $B$ containing $x$ is $2$ or $0$, hence even, and adding $1$ for $C$ makes $k(x)$ odd. Conversely, if $k(x)$ is odd and $x \in C$, the number of $A$, $B$ containing $x$ is even, so the condition holds.
• Case $x \notin C$: the condition becomes $x \in A \bigtriangleup B$, that is, the number of $A$, $B$ containing $x$ is $1$. The contribution of $C$ is $0$, so $k(x) = 1$, which is odd. Conversely, if $k(x)$ is odd and $x \notin C$, the number of $A$, $B$ containing $x$ is $k(x)$ itself, which is odd and at most $2$, hence $1$, so the condition holds.

The equivalence holds in both cases, which proves the assertion.

Now apply the same argument to $A \bigtriangleup (B \bigtriangleup C)$. By the lemma applied to $A$ and $B \bigtriangleup C$, the statement $x \in A \bigtriangleup (B \bigtriangleup C)$ says that exactly one of "$x \in A$" and "$x \in B \bigtriangleup C$" holds. We split according to whether $x \in A$.

• Case $x \in A$: the condition becomes $x \notin B \bigtriangleup C$, so the number of $B$, $C$ containing $x$ is $2$ or $0$, hence even. Adding $1$ for $A$ makes $k(x)$ odd. The converse holds similarly.
• Case $x \notin A$: the condition becomes $x \in B \bigtriangleup C$, so the number of $B$, $C$ containing $x$ is $1$. The contribution of $A$ is $0$, so $k(x) = 1$, which is odd. The converse holds similarly.

Hence $x \in A \bigtriangleup (B \bigtriangleup C) \iff k(x)$ is odd as well.

Therefore, for every $x \in U$,

$$x \in (A \bigtriangleup B) \bigtriangleup C \iff k(x) \ \text{is odd} \iff x \in A \bigtriangleup (B \bigtriangleup C),$$

so the two sets are equal by Axiom 3.2.

References

• Kazuo Matsuzaka, Shugo, Iso Nyumon (in Japanese), Iwanami Shoten, 1968 — Chapter 1, “Sets and maps”. A standard Japanese introduction, careful with proofs of set identities.
• Masahiko Saito, Sugaku no Kiso: Shugo, Su, Iso (in Japanese), University of Tokyo Press, 2002 — Chapter 1. Shows clearly the path from set theory to the construction of the real numbers.
• Shoichi Nakajima, Shugo, Shazo, Ronri: Sugaku no Kihon o Manabu (in Japanese), Kyoritsu Shuppan, 2012 — devotes considerable space to reading and writing formulas and to handling quantifiers.
• Shoji Maehara, Kigo Ronri Nyumon (in Japanese), Nippon Hyoron Sha, 1967 (reissued 2005) — a standard introduction treating propositional and predicate logic formally.
• P. R. Halmos, Naive Set Theory, Van Nostrand, 1960 — Chapters 1 to 5. A short classic bridging naive and axiomatic set theory.

Appendix: A list of frequently used equivalences

Consult this when a proof stalls. Here $P$, $Q$, $R$ are propositions and $A$, $B$, $C$ are subsets of $U$; only in the last two rows (negation of quantifiers) is $P$ a predicate on a domain $X$. That the two sides always take the same truth value (or, for sets, denote the same set) can be verified by a truth table or by element chasing.

Name	Logical form	Set form
Double negation	$\lnot \lnot P$ and $P$	$(A^{c})^{c} = A$
De Morgan	$\lnot(P \land Q)$ and $\lnot P \lor \lnot Q$	$(A \cap B)^{c} = A^{c} \cup B^{c}$
De Morgan	$\lnot(P \lor Q)$ and $\lnot P \land \lnot Q$	$(A \cup B)^{c} = A^{c} \cap B^{c}$
Distribution	$P \land (Q \lor R)$ and $(P \land Q) \lor (P \land R)$	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
Distribution	$P \lor (Q \land R)$ and $(P \lor Q) \land (P \lor R)$	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
Absorption	$P \land (P \lor Q)$ and $P$	$A \cap (A \cup B) = A$
Unfolding implication	$P \implies Q$ and $\lnot P \lor Q$	$A \subseteq B$ and $A^{c} \cup B = U$
Contraposition	$P \implies Q$ and $\lnot Q \implies \lnot P$	$A \subseteq B$ and $B^{c} \subseteq A^{c}$
Negation of implication	$\lnot(P \implies Q)$ and $P \land \lnot Q$	$A \nsubseteq B$ and $A \cap B^{c} \ne \emptyset$
Negation of a quantifier	$\lnot \forall x\, P(x)$ and $\exists x\, \lnot P(x)$	—
Negation of a quantifier	$\lnot \exists x\, P(x)$ and $\forall x\, \lnot P(x)$	—

Of these, only absorption is not treated in the body, so we record how to check it. If $x \in A \cap (A \cup B)$ then $x \in A$ (the first half of the definition of intersection). Conversely, if $x \in A$ then also $x \in A \cup B$, so $x \in A \cap (A \cup B)$. Hence the two are equal by Proposition 3.4.