# The Grammar of Mathematics: Reading and Writing Sets and Logic

> A precise treatment of elements, subsets, power sets, unions, intersections and complements, together with truth tables, the negation rules for quantifiers, and necessary versus sufficient conditions, organized around proofs of De Morgan's laws.
> https://rikai.mugen-giken.com/en/mathematics/foundations/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$ (<Ref to="prop-double-inclusion" />). 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 (<Ref to="prop-empty-subset" />).
- De Morgan's laws wear three faces — one in propositional logic, one for sets, one for quantifiers — but there is only one law underneath (<Ref to="lem-demorgan-logic" />, <Ref to="thm-demorgan" />, <Ref to="cor-demorgan-family" />).
- Negating $\forall$ and $\exists$ is the mechanical operation of pushing the negation sign inward while interchanging $\forall$ and $\exists$ (<Ref to="thm-quantifier-negation" />). 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 (<Ref to="prop-truth-set" />).

## 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?

<Aside type="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](/en/mathematics/foundations/proof-techniques) (<Ref to="mathematics/foundations/proof-techniques#thm-induction" text="the principle of mathematical induction" />, <Ref to="mathematics/foundations/proof-techniques#prop-contradiction" text="the validity of proof by contradiction" />), and the comparison of sizes of infinite sets is taken up in [Cardinality and infinity](/mathematics/foundations/cardinality-and-infinity).
</Aside>

## 2. Propositions and logical connectives

### 2.1. Propositions

<Definition id="def-proposition" title="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}$.

</Definition>

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 <Ref to="def-predicate" />.

<Remark id="rem-proposition-informal">

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](/mathematics/foundations/incompleteness-theorems).

</Remark>

### 2.2. Four connectives and truth tables

<Definition id="def-connectives" title="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 |

</Definition>

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 <Ref to="prop-implication-forms" /> 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 (<Ref to="prop-empty-subset" />).

<Proposition id="prop-implication-forms" title="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.

</Proposition>

<Proof of="prop-implication-forms">

Following the table in <Ref to="def-connectives" />, 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.

</Proof>

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 <Ref to="mathematics/foundations/proof-techniques#lem-even-square" text="if a square is even so is its root" />.)

<Example id="ex-converse" title="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 <Ref to="def-connectives" />, 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 <Ref to="prop-implication-forms" /> 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.

</Example>

## 3. Basic notions about sets

### 3.1. Elements and extensionality

<Definition id="def-set" title="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$.

</Definition>

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 id="ax-extensionality" title="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.

</Axiom>

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 <Ref to="ax-extensionality" />.

<Definition id="def-subset" title="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$.

</Definition>

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 id="prop-double-inclusion" title="Set equality is double inclusion">

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

</Proposition>

<Proof of="prop-double-inclusion">

By <Ref to="ax-extensionality" />, $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 <Ref to="def-connectives" />: $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 <Ref to="def-subset" /> this is precisely $A \subseteq B$ and $B \subseteq A$.

</Proof>

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 id="def-empty-powerset" title="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$.

</Definition>

<Proposition id="prop-empty-subset" title="Basic properties of the empty set">

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

</Proposition>

<Proof of="prop-empty-subset">

(1) By <Ref to="def-subset" />, what must be shown is "for every $x$, $x \in \emptyset \implies x \in A$". Take $x$ arbitrary; by <Ref to="def-empty-powerset" />, $x \in \emptyset$ is false. Looking at the table in <Ref to="def-connectives" />, 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 <Ref to="prop-double-inclusion" />, $E = E'$.

</Proof>

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 id="ex-powerset" title="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 <Ref to="prop-empty-subset" />, and that $A$ itself occurs because $A \subseteq A$.

</Example>

<Theorem id="thm-powerset-card" title="Cardinality of a power set">

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

</Theorem>

<Proof of="thm-powerset-card">

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 (<Ref to="def-set" />), 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 <Ref to="ax-extensionality" /> 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.

</Proof>

<Remark id="rem-powerset-infinite">

Even when $A$ is infinite, one can prove that $\mathcal{P}(A)$ is "strictly larger" than $A$ (<Ref to="mathematics/foundations/cardinality-and-infinity#thm-cantor-power" text="Cantor's theorem" />). 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](/mathematics/foundations/cardinality-and-infinity) for details. An alternative proof of <Ref to="thm-powerset-card" /> by induction on $n$ is treated as an example in [Proof techniques](/en/mathematics/foundations/proof-techniques).

</Remark>

## 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 id="def-operations" title="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**.

</Definition>

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.

<Figure caption="Two sets A and B inside a universal set U. The four regions cut out by the boundaries are numbered.">

<svg viewBox="0 0 480 270" width="100%" role="img" aria-label="A Venn diagram: two overlapping circles A and B drawn inside a rectangle representing the universal set, with the four regions numbered">
  <rect x="10" y="10" width="460" height="250" rx="10" fill="none" stroke="currentColor" stroke-width="1.5" />
  <text x="26" y="34" fill="currentColor" font-size="17" font-style="italic">U</text>
  <circle cx="190" cy="140" r="95" fill="var(--sl-color-accent)" fill-opacity="0.10" stroke="currentColor" stroke-width="1.5" />
  <circle cx="290" cy="140" r="95" fill="var(--sl-color-accent)" fill-opacity="0.10" stroke="currentColor" stroke-width="1.5" />
  <text x="135" y="78" fill="currentColor" font-size="18" font-style="italic" text-anchor="middle">A</text>
  <text x="345" y="78" fill="currentColor" font-size="18" font-style="italic" text-anchor="middle">B</text>
  <text x="152" y="148" fill="currentColor" font-size="19" text-anchor="middle">①</text>
  <text x="240" y="148" fill="currentColor" font-size="19" text-anchor="middle">②</text>
  <text x="328" y="148" fill="currentColor" font-size="19" text-anchor="middle">③</text>
  <text x="58" y="60" fill="currentColor" font-size="19" text-anchor="middle">④</text>
</svg>

</Figure>

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$.

<Aside type="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.
</Aside>

### 4.2. The distributive law

<Theorem id="thm-distributive" title="Distributive law">

For $A, B, C \subseteq U$,
$$
A \cap (B \cup C) = (A \cap B) \cup (A \cap C).
$$

</Theorem>

<Proof of="thm-distributive">

By <Ref to="prop-double-inclusion" /> we prove two inclusions.

($\subseteq$) Let $x \in A \cap (B \cup C)$. By <Ref to="def-operations" />, $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, <Ref to="prop-double-inclusion" /> gives the equality.

</Proof>

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 <Ref to="exr-distributive" />.

### 4.3. De Morgan's laws

<Lemma id="lem-demorgan-logic" title="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.

</Lemma>

<Proof of="lem-demorgan-logic">

Following the table in <Ref to="def-connectives" />, 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.

</Proof>

<Theorem id="thm-demorgan" title="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}.
$$

</Theorem>

<Proof of="thm-demorgan">

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 <Ref to="def-operations" />, and <Ref to="lem-demorgan-logic" /> 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$, <Ref to="ax-extensionality" /> 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 <Ref to="lem-demorgan-logic" /> 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 <Ref to="ax-extensionality" /> gives $(A \cap B)^{c} = A^{c} \cup B^{c}$.

</Proof>

The first half of <Ref to="thm-demorgan" /> can also be checked using the four regions of the figure following <Ref to="def-operations" />. 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 id="ex-demorgan-concrete" title="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$.

</Example>

<Remark id="rem-difference-not-associative">

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.

</Remark>

## 5. Predicates and quantifiers

### 5.1. Predicates

<Definition id="def-predicate" title="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$.

</Definition>

"$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}$ (<Ref to="mathematics/foundations/proof-techniques#thm-sqrt2" text="irrationality of the square root of 2" />) and true with domain $\mathbb{R}$ (<Ref to="mathematics/foundations/what-is-a-number#thm-sqrt2-exists" text="existence of √2" />).

<Definition id="def-quantifiers" title="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**.

</Definition>

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 <Ref to="prop-empty-subset" />.

### 5.2. How to form negations

<Theorem id="thm-quantifier-negation" title="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).
$$

</Theorem>

<Proof of="thm-quantifier-negation">

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 <Ref to="def-quantifiers" />, 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 <Ref to="def-quantifiers" /> 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 <Ref to="def-connectives" /> 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))$.

</Proof>

Combining this theorem with the last assertion of <Ref to="prop-implication-forms" /> ($\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$ (<Ref to="lem-demorgan-logic" />).
3. Replace $\lnot(P \implies Q)$ by $P \land \lnot Q$ (<Ref to="prop-implication-forms" />).

<Figure caption="Forming the negation of an ε-δ statement. At each stage the negation sign moves one step inward and a quantifier is interchanged.">

<Mermaid code={`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 )"]`} />

</Figure>

<Example id="ex-negate-continuity" title="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 <Ref to="thm-quantifier-negation" /> in the first three stages and <Ref to="prop-implication-forms" /> 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$.

</Example>

### 5.3. The order of quantifiers

<Remark id="rem-quantifier-order" title="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 <Ref to="thm-quantifier-negation" />, 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 <Ref to="ex-negate-continuity" />. 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.

</Remark>

### 5.4. Generalization to families of sets

<Corollary id="cor-demorgan-family" title="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}.
$$

</Corollary>

<Proof of="cor-demorgan-family">

We prove the first identity. Take $x \in U$ arbitrary. At the second line we use the second half of <Ref to="thm-quantifier-negation" /> (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 <Ref to="ax-extensionality" />. The second identity is obtained by using, at the second line of the same chain, the first half of <Ref to="thm-quantifier-negation" /> (the one turning $\lnot \forall$ into $\exists \lnot$).

</Proof>

The case where $\Lambda$ has two elements is <Ref to="thm-demorgan" />. Thus <Ref to="lem-demorgan-logic" />, <Ref to="thm-demorgan" /> and <Ref to="cor-demorgan-family" /> 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 id="def-necessary-sufficient" title="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**.

</Definition>

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, <Ref to="prop-implication-forms" />), the condition $Q$ is "necessary".

<Example id="ex-necessary-sufficient" title="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.

</Example>

<Proposition id="prop-truth-set" title="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}
$$

</Proposition>

<Proof of="prop-truth-set">

(1) By <Ref to="def-subset" />, $[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" (<Ref to="def-connectives" />), which is equivalent to $x \in [P]$ and $x \in [Q]$, that is to $x \in [P] \cap [Q]$ (<Ref to="def-operations" />). Since the equivalence holds for every $x \in X$, <Ref to="ax-extensionality" /> 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.

</Proof>

By (1), "$P$ is a sufficient condition for $Q$" is the same as "$[P] \subseteq [Q]$". In <Ref to="ex-necessary-sufficient" /> 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.

<Aside type="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](/mathematics/foundations/equivalence-relations) (this very example is examined in <Ref to="mathematics/foundations/equivalence-relations#ex-ill-defined" text="a 'definition' that is not well defined" />).
</Aside>

<Remark id="rem-russell" title="The limits of naive set theory">

If, as in <Ref to="def-set" />, 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](/mathematics/foundations/incompleteness-theorems) (<Ref to="mathematics/foundations/incompleteness-theorems#thm-first" text="the first incompleteness theorem" />). 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?](/en/mathematics/foundations/what-is-a-number).

</Remark>

## 7. Exercises

<Exercise id="exr-powerset-empty" difficulty="Easy">

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

(1) Write out $\mathcal{P}(A)$ and check that the number of its elements agrees with <Ref to="thm-powerset-card" />. <br />
(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 <Ref to="thm-powerset-card" />.

(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 <Ref to="prop-empty-subset" /> 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 <Ref to="def-subset" /> 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.

</Solution>

</Exercise>

<Exercise id="exr-distributive" difficulty="Standard">

For $A, B, C \subseteq U$, prove
$$
A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
$$
by element chasing.

<Solution>

Following <Ref to="prop-double-inclusion" />, we prove two inclusions.

($\subseteq$) Let $x \in A \cup (B \cap C)$. By <Ref to="def-operations" />, $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, <Ref to="prop-double-inclusion" /> gives the equality.

</Solution>

</Exercise>

<Exercise id="exr-negate-convergence" difficulty="Standard">

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. <br />
(2) Show that the sequence defined by $a_n = (-1)^{n}$ converges to no real number $\alpha$.

<Solution>

(1) We use <Ref to="thm-quantifier-negation" /> three times, then <Ref to="prop-implication-forms" /> 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.

</Solution>

</Exercise>

<Exercise id="exr-symmetric-difference" difficulty="Hard">

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 <Ref to="def-operations" />, $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 <Ref to="ax-extensionality" />.

</Solution>

</Exercise>

## 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 <Ref to="prop-double-inclusion" />.