Sets | Libre University

Every proof so far has spoken of "the even integers" or "the primes" as collections, and none has said what a collection is, when two of them are the same, or how to build new ones from old.

The previous lesson completed the stock of proof methods with induction, and it leaned on collections throughout: the set of natural numbers where a statement fails, groups of horses, the collection of all formulas. This lesson makes those words exact. It sets up the language of sets that the rest of the course, and most of mathematics, is written in: how to describe a set, how to prove that one set lies inside another and that two sets are equal, the operations that build new sets from old and the laws they obey, power sets and Cartesian products, and unions and intersections of infinitely many sets at once. It ends with the paradox that showed the naive idea of a set to be contradictory, and with the axioms that repaired it. The lesson assumes the connectives, including the rule that a conditional with a false hypothesis is vacuously true, the quantifiers $\forall$ and $\exists$ , and induction. As before, $ℕ = {1, 2, 3, \dots}$ starts at $1$ .

Sets and membership

A set is a collection of objects, called its elements or members, and it is determined by nothing except which objects those are. " $x$ is an element of $A$ " is written $x \in A$ , and its negation $x \notin A$ . So $3 \in ℕ$ and $- 3 \notin ℕ$ , with $ℕ$ , $ℤ$ , $ℚ$ and $ℝ$ standing as before for the natural numbers, the integers, the rationals and the reals.

This is not a definition in the strict sense, since "collection" is only another word for "set". Like "point" in geometry, "set" and "is an element of" are taken as basic, and what matters is the rules they obey. The first and most important rule says what it means for two sets to be the same.

Axiom of extensionality. Two sets are equal exactly when they have the same elements: $A = B$ means $\forall x (x \in A ⟺ x \in B)$ .

A small set can be written by listing its elements between braces, in roster notation: ${2, 3, 5, 7}$ is the set of primes below $10$ . By extensionality, order and repetition in a list make no difference. ${1, 2, 2} = {2, 1}$ , since each side has exactly the elements $1$ and $2$ ; writing $2$ twice names the same element twice. Longer sets are sometimes listed with dots, as in ${1, 2, \dots, 100}$ or ${2, 4, 6, \dots}$ , when the pattern cannot be mistaken.

Elements can be anything, including other sets. The set ${1, {1, 2}}$ has exactly two elements, the number $1$ and the set ${1, 2}$ ; the number $2$ is not one of them, since it is an element of an element, not an element. A set with no elements at all is the empty set, written $\emptyset$ . By extensionality there is only one: two sets with no elements have the same elements. And ${\emptyset}$ is not empty. It has one element, which happens to be the empty set, in the way that a box containing an empty box is not an empty box.

Subsets of the real line have their own notation. For real numbers $a < b$ , the open interval $(a, b)$ is the set of reals $x$ with $a < x < b$ , and the closed interval $[a, b]$ is the set with $a \leq x \leq b$ . Mixed ones such as $[a, b)$ include one end and not the other, and $(a, \infty)$ is the set of all reals greater than $a$ . The notation $(a, b)$ also means an ordered pair, met later in the lesson, and context decides which is meant.

Set builder notation

Most sets are too large to list, and are described by a property instead, in set builder notation:

{x \in A : P (x)}

read "the set of $x$ in $A$ such that $P (x)$ ". Here $A$ is a set already known and $P (x)$ an open sentence, in the sense of the lesson on quantifiers, and the result is the set of those elements of $A$ that make $P$ true. So

{n \in ℤ : n^{2} < 10} = {- 3, - 2, - 1, 0, 1, 2, 3}

since $3^{2} = 9$ is below $10$ and $4^{2} = 16$ is not. Some books write a vertical bar for the colon, ${x \in A ∣ P (x)}$ ; the meaning is the same.

The notation comes with one rule, and every proof about such a set uses it.

The membership rule. An object $y$ belongs to ${x \in A : P (x)}$ exactly when $y \in A$ and $P (y)$ is true.

The letter $x$ is a dummy, like the $k$ in a sum: ${x \in ℝ : x^{2} = 2}$ and ${t \in ℝ : t^{2} = 2}$ are the same set, ${\sqrt{2}, - \sqrt{2}}$ . The surrounding set matters: ${x \in ℚ : x^{2} = 2}$ is empty, because the previous lesson's descent argument, or the lesson on contradiction, shows that no rational squares to $2$ .

A second form puts an expression first. For a set $A$ and an expression $f (x)$ ,

{f (x) : x \in A}

is the set of all values $f (x)$ as $x$ runs through $A$ . So ${2 k : k \in ℤ}$ is the set of even integers, and ${k^{2} : k \in ℤ} = {0, 1, 4, 9, \dots}$ is the set of perfect squares. Its membership rule has a hidden quantifier: $y \in {f (x) : x \in A}$ exactly when $\exists x \in A (y = f (x))$ . To show that $10$ is in the first set, name the witness, $k = 5$ . To show that $7$ is not, show that no witness exists: $7 = 2 k$ would make $7$ even. Several variables are allowed, and then each gets its own quantifier: $y \in {3 a + 5 b : a, b \in ℤ}$ means that there are integers $a$ and $b$ with $y = 3 a + 5 b$ .

The insistence on a surrounding set $A$ in the first form looks like pedantry, since " ${x : P (x)}$ , the set of all $x$ with property $P$ " seems just as clear. A later section shows that it is not pedantry: without the surrounding set, the notation produces a contradiction.

Subsets and equality

$A$ is a subset of $B$ , written $A \subseteq B$ , when every element of $A$ is an element of $B$ :

A \subseteq B means \forall x (x \in A \Rightarrow x \in B)

So $ℕ \subseteq ℤ \subseteq ℚ \subseteq ℝ$ , and ${2, 3} \subseteq {1, 2, 3}$ . $A$ is a proper subset of $B$ when $A \subseteq B$ and $A \neq B$ , that is, when $B$ has at least one element that $A$ lacks. Notation for this varies between books, so this course writes it out in words.

The definition is a universal conditional, and it fixes the method of proof. To prove $A \subseteq B$ , let $x$ be an arbitrary element of $A$ , unpack what membership of $A$ says about $x$ , and show from that alone that $x$ satisfies the condition for membership of $B$ . This is called element chasing, and it is the direct proof of the lesson on direct proof, applied to the statement " $x \in A \Rightarrow x \in B$ ". To disprove $A \subseteq B$ , the negation $\exists x (x \in A \land x \notin B)$ says what is needed: one element of $A$ that is not in $B$ .

For example, ${n \in ℤ : 4 ∣ n} \subseteq {n \in ℤ : 2 ∣ n}$ . Let $n$ be an element of the left side. By the membership rule, $n$ is an integer and $4 ∣ n$ , so $n = 4 k$ for some integer $k$ . Then $n = 2 (2 k)$ with $2 k$ an integer, so $2 ∣ n$ , and $n$ belongs to the right side. The reverse inclusion fails, and $2$ shows it: $2$ is an even integer and $4$ does not divide $2$ .

Keep $\in$ and $\subseteq$ apart. The first relates an object to a set that contains it; the second relates two sets. So $1 \in {1, 2}$ and ${1} \subseteq {1, 2}$ , but ${1} \notin {1, 2}$ , since the set ${1}$ is neither of the numbers $1$ and $2$ . Yet ${1} \in {{1}, 2}$ , and there ${1} ⊈ {{1}, 2}$ , since the element $1$ of ${1}$ is not an element of ${{1}, 2}$ . Whether a set is an element or a subset of another depends on the other set, and each claim is checked against its own definition.

The empty set is a subset of every set $A$ . The claim $\emptyset \subseteq A$ means $\forall x (x \in \emptyset \Rightarrow x \in A)$ . The hypothesis $x \in \emptyset$ is false for every $x$ , so each instance of the conditional is vacuously true, and so is the universal statement. A disproof would need an element of $\emptyset$ outside $A$ , and there is no element of $\emptyset$ at all.

Three properties of $\subseteq$ are used constantly. For all sets $A$ , $B$ and $C$ : $A \subseteq A$ ; if $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$ ; and if $A \subseteq B$ and $B \subseteq A$ then $A = B$ . The first holds because $x \in A \Rightarrow x \in A$ is always true. For the second, let $x \in A$ ; then $x \in B$ because $A \subseteq B$ , and then $x \in C$ because $B \subseteq C$ . The third is extensionality: together, the two inclusions say $x \in A ⟺ x \in B$ for every $x$ . The lesson on order relations names these three properties reflexivity, transitivity and antisymmetry.

The third property is the method this lesson is built round. To prove that two sets are equal, prove two subset statements, $A \subseteq B$ and $B \subseteq A$ , each by element chasing. This is a proof by double inclusion. Checking a few elements of each set is not a proof of equality, for the same reason that checking examples is not a proof of a universal statement: each inclusion is a claim about every element.

Example. Prove that ${12 a + 18 b : a, b \in ℤ} = {6 c : c \in ℤ}$ .

Call the two sides $L$ and $R$ .

First, $L \subseteq R$ . Let $y \in L$ . By the membership rule there are integers $a$ and $b$ with $y = 12 a + 18 b$ . Then $y = 6 (2 a + 3 b)$ , and $2 a + 3 b$ is an integer, so $y$ has the form $6 c$ with $c = 2 a + 3 b$ , and $y \in R$ .

Second, $R \subseteq L$ . Let $y \in R$ , so $y = 6 c$ for some integer $c$ . The task is to find integers $a$ and $b$ with $12 a + 18 b = 6 c$ , and it is enough to write $6$ itself in the form $12 a + 18 b$ : since $18 - 12 = 6$ , take $a = - c$ and $b = c$ . Then $12 a + 18 b = - 12 c + 18 c = 6 c = y$ , so $y \in L$ .

Each side is a subset of the other, so $L = R$ .

The two halves were different in kind. The first unpacked an existential hypothesis ("there are $a$ and $b$ ") and needed only algebra. The second had an existential goal, and needed a witness to be constructed. The same shape recurs whenever a set is described by a formula: showing that the formula's values lie in a set is usually routine, and showing that it reaches every element of the set is where the work is. The equation ${m a + n b : a, b \in ℤ} = {d c : c \in ℤ}$ , where $d$ is the greatest common divisor of $m$ and $n$ , is Bézout's identity from the Discrete Mathematics course, and $12$ , $18$ and $6$ are its simplest instance.

Now you. Prove that ${x \in ℝ : x^{2} - 3 x + 2 < 0} = (1, 2)$ .

Answer

Call the left side $S$ , and note that $x^{2} - 3 x + 2 = (x - 1) (x - 2)$ for every real $x$ .

First, $S \subseteq (1, 2)$ . Let $x \in S$ , so $(x - 1) (x - 2) < 0$ . A product of two real numbers is negative only when one factor is positive and the other negative. Since $x - 1 > x - 2$ , the positive factor must be $x - 1$ and the negative one $x - 2$ . So $x > 1$ and $x < 2$ , and $x \in (1, 2)$ .

Second, $(1, 2) \subseteq S$ . Let $1 < x < 2$ . Then $x - 1 > 0$ and $x - 2 < 0$ , so their product is negative, and $x \in S$ .

Each set contains the other, so $S = (1, 2)$ . This is the same as "solving the inequality", but written as two inclusions it is clear that both directions were checked: every solution lies in $(1, 2)$ , and every point of $(1, 2)$ is a solution.

Union, intersection, difference and complement

Four operations build new sets from old, and each is a connective in disguise. For sets $A$ and $B$ :

\begin{matrix} x \in A \cup B & ⟺ x \in A \lor x \in B \\ x \in A \cap B & ⟺ x \in A \land x \in B \\ x \in A ∖ B & ⟺ x \in A \land x \notin B \end{matrix}

The union $A \cup B$ collects everything in either set, with the inclusive "or", so an element of both belongs to it. The intersection $A \cap B$ keeps what the two sets share. The difference $A ∖ B$ , read " $A$ minus $B$ ", keeps what is in $A$ and not in $B$ . With $A = {1, 2, 3, 4}$ and $B = {3, 4, 5}$ these are ${1, 2, 3, 4, 5}$ , ${3, 4}$ and ${1, 2}$ , and $B ∖ A = {5}$ , so difference, unlike union and intersection, depends on the order. Two sets are disjoint when $A \cap B = \emptyset$ , that is, when they have no element in common.

The complement of $A$ is everything not in $A$ , and "everything" needs a limit. Fix a universe $U$ , a set containing every set under discussion, and define the complement of a subset $A$ of $U$ as $A^{c} = U ∖ A$ . The universe is part of the meaning: the complement of the even integers is the odd integers when $U = ℤ$ , but it also contains $\frac{1}{2}$ and $π$ when $U = ℝ$ . When no universe has been fixed, write the difference $U ∖ A$ and name the universe.

A fifth operation is less familiar but just as natural. The symmetric difference $A △ B$ is the set of elements in exactly one of $A$ and $B$ :

x \in A △ B ⟺ (x \in A) \oplus (x \in B)

where $\oplus$ is exclusive "or". With the sets above, $A △ B = {1, 2, 5}$ . A later section studies it.

These operations are pictured by Venn diagrams, with each set drawn as a region inside a rectangle standing for $U$ : the union is the area covered by either region, the intersection the overlap, the complement everything outside. The pictures are the best way to guess an identity. Whether they can prove one is a fair question.

Can a Venn diagram prove a set identity?

For identities built from $\cup$ , $\cap$ , $∖$ and complement, a complete diagram can, and the reason is the same as the reason truth tables work. Whether an element $x$ belongs to a set built from $A$ , $B$ and $C$ by these operations depends only on the three answers to "is $x$ in $A$ ?", "in $B$ ?", "in $C$ ?". There are $2^{3} = 8$ patterns of answers, and the eight regions of the standard three-circle diagram are exactly the eight patterns, including the region outside all three circles. So two expressions give the same set, for all choices of $A$ , $B$ and $C$ , exactly when they contain the same regions of the diagram. Checking regions is checking a finite list of cases that provably covers everything, which is a proof by cases in the sense of the lesson on direct proof.

Written as a table rather than a picture, this is a membership table: one column per set, one row per pattern of $\in$ and $\notin$ , and a column for each expression. It is literally a truth table, with " $x \in A$ " in place of a propositional variable, and an identity between sets holds exactly when the matching statement of logic is a tautology. That is why De Morgan's laws, the distributive laws and the rest hold for sets: each is a logical equivalence with " $x \in$ " written in front.

The method has limits. A picture that leaves out a region, for instance by drawing $B$ inside $A$ , checks only the special case where that region is empty, and a claim can hold there and fail in general. With four sets there are $16$ patterns, and four circles cannot show them all, since four circles in the plane make at most $14$ regions; John Venn, who introduced the diagrams in 1880, used ellipses for four sets. And the method does not reach statements about unions of infinitely many sets, or claims mixing sets with arithmetic, where element chasing is the only general tool. So this course proves identities by double inclusion, and uses diagrams and tables to find and check them.

For finite sets, size interacts with these operations in a simple way. Write $| A |$ for the number of elements of a finite set $A$ . If $A$ and $B$ are disjoint, then $| A \cup B | = | A | + | B |$ , since counting the union counts each element once and the two sets share none. In general the elements of $A \cap B$ are counted twice in $| A | + | B |$ , which gives

| A \cup B | = | A | + | B | - | A \cap B |

To prove it from the disjoint case, split $A \cup B$ into the disjoint sets $A$ and $B ∖ A$ , and split $B$ into the disjoint sets $B ∖ A$ and $A \cap B$ . Then $| A \cup B | = | A | + | B ∖ A |$ and $| B | = | B ∖ A | + | A \cap B |$ , and subtracting gives the formula. Of $100$ students, if $60$ study French, $45$ study German and $20$ study both, then $60 + 45 - 20 = 85$ study at least one, and $15$ study neither. The formula for three or more sets, with its alternating signs, is the subject of the Discrete Mathematics lesson on inclusion and exclusion.

The laws of set algebra

Because each operation is a connective in disguise, each law of logic from the lesson on statements and connectives becomes a law of sets. For all subsets $A$ , $B$ and $C$ of a universe $U$ :

\begin{matrix} A \cup B = B \cup A, A \cap B = B \cap A & (commutative) \\ (A \cup B) \cup C = A \cup (B \cup C), (A \cap B) \cap C = A \cap (B \cap C) & (associative) \\ A \cap (B \cup C) = (A \cap B) \cup (A \cap C), A \cup (B \cap C) = (A \cup B) \cap (A \cup C) & (distributive) \\ A \cup \emptyset = A, A \cap U = A, A \cup U = U, A \cap \emptyset = \emptyset & (identity and domination) \\ A \cup A^{c} = U, A \cap A^{c} = \emptyset, (A^{c})^{c} = A & (complement) \\ A \cup A = A, A \cap A = A & (idempotent) \\ A \cup (A \cap B) = A, A \cap (A \cup B) = A & (absorption) \end{matrix}

together with De Morgan's laws, which get a section of their own below. The associative laws make brackets unnecessary in $A \cup B \cup C$ and $A \cap B \cap C$ . Each law is proved by double inclusion, and each proof is the matching law of logic applied to the statements $x \in A$ , $x \in B$ and $x \in C$ . One example shows the pattern.

Example. Prove that for all sets $A$ , $B$ and $C$ , $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ .

First, the left side is contained in the right. Let $x \in A \cap (B \cup C)$ . Then $x \in A$ , and $x \in B \cup C$ , so $x \in B$ or $x \in C$ . If $x \in B$ , then $x \in A$ and $x \in B$ , so $x \in A \cap B$ . If $x \in C$ , then in the same way $x \in A \cap C$ . In either case $x$ belongs to $(A \cap B) \cup (A \cap C)$ .

Second, the right side is contained in the left. Let $x \in (A \cap B) \cup (A \cap C)$ . If $x \in A \cap B$ , then $x \in A$ and $x \in B$ ; since $x \in B$ , also $x \in B \cup C$ , so $x \in A \cap (B \cup C)$ . If $x \in A \cap C$ , the same argument with $C$ in place of $B$ gives $x \in A \cap (B \cup C)$ .

Each side contains the other, so they are equal.

An "or" in the hypothesis became a proof by cases, while an "or" in the conclusion needed only one of its parts to be established. That is the pattern of most identity proofs, and knowing it in advance makes them quick to write.

Now you. Prove the other distributive law: for all sets $A$ , $B$ and $C$ , $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .

Answer

First, left in right. Let $x \in A \cup (B \cap C)$ . If $x \in A$ , then $x \in A \cup B$ and $x \in A \cup C$ , so $x$ is in the right side. If $x \in B \cap C$ , then $x \in B$ , so $x \in A \cup B$ , and $x \in C$ , so $x \in A \cup C$ ; again $x$ is in the right side.

Second, right in left. Let $x \in (A \cup B) \cap (A \cup C)$ . Either $x \in A$ or $x \notin A$ . If $x \in A$ , then $x \in A \cup (B \cap C)$ . If $x \notin A$ , then $x \in A \cup B$ forces $x \in B$ , and $x \in A \cup C$ forces $x \in C$ , so $x \in B \cap C$ , and again $x \in A \cup (B \cap C)$ .

The sets are equal. The second half split on whether $x \in A$ , a case split that the hypothesis did not offer directly; the law of excluded middle supplies it.

Once the laws are proved, they can be used like the rules of algebra, and identities can be derived without chasing elements. The useful link between difference and complement is $A ∖ B = A \cap B^{c}$ (for subsets of $U$ ), which follows at once from the membership conditions. Then, for example,

A ∖ (A ∖ B) = A \cap (A \cap B^{c})^{c} = A \cap (A^{c} \cup B) = (A \cap A^{c}) \cup (A \cap B) = \emptyset \cup (A \cap B) = A \cap B

using, in turn, the link twice, De Morgan's law with $(B^{c})^{c} = B$ , the distributive law, a complement law and an identity law. Both styles are proofs. Element chasing is more robust, since it needs no list of laws and works for operations not on the list; algebra is shorter once the laws are available.

The subset relation can itself be expressed through the operations, and the result is a list of equivalent conditions.

Theorem. For all sets $A$ and $B$ , the following are equivalent: (i) $A \subseteq B$ ; (ii) $A \cup B = B$ ; (iii) $A \cap B = A$ .

Proof. We prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i), a cycle of three implications, as the lesson on direct proof recommends for such lists.

(i) $\Rightarrow$ (ii). Suppose $A \subseteq B$ . Always $B \subseteq A \cup B$ . Conversely, let $x \in A \cup B$ ; if $x \in A$ then $x \in B$ because $A \subseteq B$ , and if $x \in B$ there is nothing to show. So $A \cup B \subseteq B$ , and $A \cup B = B$ .

(ii) $\Rightarrow$ (iii). Suppose $A \cup B = B$ . Always $A \cap B \subseteq A$ . Conversely, let $x \in A$ . Then $x \in A \cup B = B$ , so $x \in A$ and $x \in B$ , that is, $x \in A \cap B$ . So $A \cap B = A$ .

(iii) $\Rightarrow$ (i). Suppose $A \cap B = A$ , and let $x \in A$ . Then $x \in A \cap B$ , so $x \in B$ . Hence $A \subseteq B$ . $□$

Set algebra looks like the algebra of numbers, with $\cup$ as addition and $\cap$ as multiplication, and the resemblance misleads in one respect: there is no cancellation. From $A \cup C = B \cup C$ nothing follows about $A$ and $B$ : take $C = U$ , and the equation holds for every $A$ and $B$ . The same goes for $A \cap C = B \cap C$ , with $C = \emptyset$ . Problem 6 shows what does allow cancellation.

De Morgan's laws

Augustus De Morgan stated his laws for statements in his Formal Logic of 1847: $\neg (P \lor Q)$ is equivalent to $\neg P \land \neg Q$ , and $\neg (P \land Q)$ to $\neg P \lor \neg Q$ . They are proved by truth table in the lesson on statements and connectives. Since union is "or", intersection "and" and complement "not", the same laws hold for subsets $A$ and $B$ of a universe $U$ :

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

In words: what lies outside the union lies outside both sets, and what lies outside the intersection lies outside at least one of them.

Example. Prove that $(A \cup B)^{c} = A^{c} \cap B^{c}$ for all subsets $A$ and $B$ of $U$ .

First, left in right. Let $x \in (A \cup B)^{c}$ , so $x \in U$ and $x \notin A \cup B$ . If $x$ were in $A$ , it would be in $A \cup B$ , so $x \notin A$ ; in the same way $x \notin B$ . Hence $x \in A^{c}$ and $x \in B^{c}$ , so $x \in A^{c} \cap B^{c}$ .

Second, right in left. Let $x \in A^{c} \cap B^{c}$ , so $x \in U$ , $x \notin A$ and $x \notin B$ . Then " $x \in A$ or $x \in B$ " is false, so $x \notin A \cup B$ , and $x \in (A \cup B)^{c}$ .

The sets are equal. The middle of each half is De Morgan's law for statements, applied to " $x \in A$ " and " $x \in B$ ".

Now you. Prove that $(A \cap B)^{c} = A^{c} \cup B^{c}$ for all subsets $A$ and $B$ of $U$ .

Answer

First, left in right. Let $x \in (A \cap B)^{c}$ , so $x \in U$ and $x \notin A \cap B$ . Then " $x \in A$ and $x \in B$ " is false, so by De Morgan's law for statements, $x \notin A$ or $x \notin B$ . In the first case $x \in A^{c}$ and in the second $x \in B^{c}$ , so either way $x \in A^{c} \cup B^{c}$ .

Second, right in left. Let $x \in A^{c} \cup B^{c}$ . If $x \in A^{c}$ , then $x \in U$ and $x \notin A$ , so $x \notin A \cap B$ , since every element of $A \cap B$ is in $A$ . If $x \in B^{c}$ , the same holds with $B$ . Either way $x \in (A \cap B)^{c}$ .

The sets are equal. Alternatively, the second law follows from the first by algebra: apply the first law to $A^{c}$ and $B^{c}$ to get $(A^{c} \cup B^{c})^{c} = A \cap B$ , then take complements of both sides.

The laws hold with any set in place of the universe, since complement is only difference from $U$ : for all sets $A$ , $B$ and $C$ ,

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

by the same proofs with " $x \in A$ " in place of " $x \in U$ ".

Symmetric difference

The symmetric difference $A △ B$ , the set of elements in exactly one of $A$ and $B$ , is the set-theoretic "exclusive or". It can be built from the other operations in two standard ways.

Example. Prove that for all sets $A$ and $B$ , $A △ B = (A \cup B) ∖ (A \cap B)$ , and deduce that $A △ B = (A ∖ B) \cup (B ∖ A)$ .

First, left in right. Let $x \in A △ B$ , so $x$ is in exactly one of $A$ and $B$ . Then $x \in A \cup B$ . And $x$ is not in both, so $x \notin A \cap B$ . Hence $x \in (A \cup B) ∖ (A \cap B)$ .

Second, right in left. Let $x \in (A \cup B) ∖ (A \cap B)$ . Then $x$ is in at least one of $A$ and $B$ , and not in both, so in exactly one, and $x \in A △ B$ .

For the second description: $x$ is in exactly one of the two sets when either $x \in A$ and $x \notin B$ , or $x \in B$ and $x \notin A$ , and those two conditions say $x \in A ∖ B$ and $x \in B ∖ A$ . So $A △ B = (A ∖ B) \cup (B ∖ A)$ , and the two sets in this union are disjoint.

Now you. Prove that intersection distributes over symmetric difference: for all sets $A$ , $B$ and $C$ , $A \cap (B △ C) = (A \cap B) △ (A \cap C)$ .

Answer

First, left in right. Let $x \in A \cap (B △ C)$ . Then $x \in A$ , and $x$ is in exactly one of $B$ and $C$ . If $x \in B$ and $x \notin C$ , then $x \in A \cap B$ and $x \notin A \cap C$ , so $x$ is in exactly one of $A \cap B$ and $A \cap C$ . If $x \in C$ and $x \notin B$ , the same holds with the roles exchanged. Either way $x \in (A \cap B) △ (A \cap C)$ .

Second, right in left. Let $x$ be in exactly one of $A \cap B$ and $A \cap C$ . Either way $x \in A$ . If $x \in A \cap B$ and $x \notin A \cap C$ , then, since $x \in A$ , it must be that $x \notin C$ ; so $x \in B$ and $x \notin C$ , and $x \in B △ C$ . The other case is the same with $B$ and $C$ exchanged. So $x \in A \cap (B △ C)$ .

The sets are equal. Union does not distribute over symmetric difference: with $A = B = C = {1}$ , the left side $A \cup (B △ C)$ is ${1} \cup \emptyset = {1}$ , while $(A \cup B) △ (A \cup C) = {1} △ {1} = \emptyset$ .

Symmetric difference has the algebra of addition with remainders mod $2$ , and the reason is a counting fact.

Proposition. For all sets $A$ , $B$ and $C$ , an object $x$ belongs to $(A △ B) △ C$ exactly when it belongs to an odd number of the sets $A$ , $B$ , $C$ . Consequently $(A △ B) △ C = A △ (B △ C)$ .

Proof. Let $x$ be any object, and let $k$ be the number of the sets $A$ and $B$ containing $x$ , so $k$ is $0$ , $1$ or $2$ . By definition, $x \in A △ B$ exactly when $k = 1$ , that is, exactly when $k$ is odd. Now $x \in (A △ B) △ C$ exactly when $x$ is in exactly one of $A △ B$ and $C$ . If $x \notin C$ , that means $x \in A △ B$ , that is, $k$ is odd, and then the number of sets among $A$ , $B$ , $C$ containing $x$ is $k$ , which is odd. If $x \in C$ , it means $x \notin A △ B$ , that is, $k$ is even, and then the number of the three sets containing $x$ is $k + 1$ , which is odd. In each case, $x \in (A △ B) △ C$ exactly when $x$ lies in an odd number of the three sets.

For associativity, note that $△$ is commutative, straight from its definition, so $A △ (B △ C) = (B △ C) △ A$ . By what was just proved, applied to $B$ , $C$ and $A$ in that order, this set consists of the objects lying in an odd number of $B$ , $C$ , $A$ . That is the same condition as before, since it does not depend on the order of the three sets. So the two sets have the same elements. $□$

With associativity in hand, symmetric difference behaves like addition. The empty set is a zero, $A △ \emptyset = A$ , and every set is its own negative, $A △ A = \emptyset$ . So equations can be solved: if $A △ X = B$ , then applying $A △$ to both sides gives $A △ (A △ X) = A △ B$ , and the left side is $(A △ A) △ X = \emptyset △ X = X$ . So $X = A △ B$ is the only solution, and it is one, by the same computation read backwards. This is the cancellation that union and intersection lacked. In the language of algebra, the subsets of $U$ form a group under $△$ , and with $\cap$ as multiplication they form a ring in which every element is its own square; this is the setting in which Boole's algebra of logic is studied today.

Power sets

The power set of a set $A$ , written $P (A)$ , is the set of all subsets of $A$ . Its membership rule is: $X \in P (A)$ exactly when $X \subseteq A$ . For $A = {1, 2, 3}$ it has eight elements,

P ({1, 2, 3}) = {\emptyset, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

namely the empty set, three sets of one element, three of two, and $A$ itself. The elements of a power set are sets, which is where the distinction between $\in$ and $\subseteq$ earns its keep: ${1} \in P (A)$ , while ${{1}} \subseteq P (A)$ . The smallest cases are worth doing once by hand. The empty set has exactly one subset, itself, so $P (\emptyset) = {\emptyset}$ , a set with one element. Then $P ({\emptyset}) = {\emptyset, {\emptyset}}$ has two.

Theorem. If a finite set $A$ has $n$ elements, then $P (A)$ has $2^{n}$ elements.

Proof. By induction on $n$ , starting at $n = 0$ , as the induction lesson allows. Let $P (n)$ be the statement that every set with $n$ elements has exactly $2^{n}$ subsets. For $n = 0$ the set is $\emptyset$ , whose only subset is $\emptyset$ , and $2^{0} = 1$ .

For the step, suppose every set with $n$ elements has $2^{n}$ subsets, and let $A$ have $n + 1$ elements. Choose an element $a \in A$ and let $A' = A ∖ {a}$ , a set with $n$ elements. Every subset $X$ of $A$ either omits $a$ or contains it, and not both. If it omits $a$ , then $X$ is a subset of $A'$ , and every subset of $A'$ arises this way. If it contains $a$ , then $X = S \cup {a}$ where $S = X ∖ {a}$ is a subset of $A'$ , and different subsets $S$ of $A'$ give different sets $S \cup {a}$ , since $S$ can be recovered by removing $a$ . So there are $2^{n}$ subsets of each kind by the inductive hypothesis, and $A$ has $2^{n} + 2^{n} = 2^{n + 1}$ subsets. By induction the theorem holds for every $n \geq 0$ . $□$

A second proof counts choices: a subset of ${a_{1}, \dots, a_{n}}$ is determined by deciding, for each $a_{i}$ in turn, whether to include it, and $n$ independent yes or no choices can be made in $2^{n}$ ways. The two proofs are the same argument; the induction is what makes "and so on for each $a_{i}$ " precise. Either way, the power set of a set of $10$ elements has $1024$ elements, and its elements are themselves sets.

Example. Prove that for all sets $A$ and $B$ , $P (A) \cap P (B) = P (A \cap B)$ .

Here the elements are sets, so let $X$ stand for one.

First, left in right. Let $X \in P (A) \cap P (B)$ . Then $X \in P (A)$ and $X \in P (B)$ , that is, $X \subseteq A$ and $X \subseteq B$ . To show $X \subseteq A \cap B$ , let $x \in X$ ; then $x \in A$ and $x \in B$ , so $x \in A \cap B$ . Hence $X \in P (A \cap B)$ .

Second, right in left. Let $X \in P (A \cap B)$ , so $X \subseteq A \cap B$ . Since $A \cap B \subseteq A$ , transitivity of $\subseteq$ gives $X \subseteq A$ , and likewise $X \subseteq B$ . So $X \in P (A)$ and $X \in P (B)$ , and $X \in P (A) \cap P (B)$ .

The sets are equal. The proof chased elements at two levels: the outer chase was over subsets $X$ , and inside it a second, ordinary chase over elements $x$ proved a subset statement.

Now you. Prove that $P (A) \cup P (B) \subseteq P (A \cup B)$ for all sets $A$ and $B$ , and show by an example that the two sets need not be equal.

Answer

Let $X \in P (A) \cup P (B)$ . If $X \in P (A)$ , then $X \subseteq A \subseteq A \cup B$ , so $X \subseteq A \cup B$ by transitivity. If $X \in P (B)$ , then in the same way $X \subseteq A \cup B$ . Either way $X \in P (A \cup B)$ .

For the example, take $A = {1}$ and $B = {2}$ . Then ${1, 2} \subseteq A \cup B$ , so ${1, 2} \in P (A \cup B)$ . But ${1, 2}$ is a subset of neither $A$ nor $B$ , so it is not in $P (A) \cup P (B)$ . Counting confirms the gap: $P (A) \cup P (B) = {\emptyset, {1}, {2}}$ has $3$ elements, while $P (A \cup B)$ has $4$ .

A subset of $A \cup B$ may take some elements from $A$ and some from $B$ , and that is exactly what $P (A) \cup P (B)$ misses. Equality holds precisely when one of $A$ and $B$ contains the other.

For infinite sets the question "how many subsets?" has a startling answer. Georg Cantor proved in 1891 that no set, finite or infinite, can be matched one to one with its power set, so $P (ℕ)$ is a larger infinity than $ℕ$ , and there is an endless ladder of larger ones. The lesson on countable and uncountable sets proves it, and the section on Russell's paradox below shows how closely the two arguments are related.

Cartesian products

In a set, order does not matter: ${a, b} = {b, a}$ . Coordinates need order, and so does most of mathematics. An ordered pair $(a, b)$ is an object with a first coordinate $a$ and a second coordinate $b$ , governed by one rule:

(a, b) = (c, d) exactly when a = c and b = d

So $(1, 2) \neq (2, 1)$ , and $(1, 1)$ is a perfectly good pair, while ${1, 1} = {1}$ . Ordered pairs can be defined from sets alone, and the lesson on functions gives the standard definition; for now the rule is all that is needed.

The Cartesian product of sets $A$ and $B$ is the set of all ordered pairs with first coordinate in $A$ and second in $B$ :

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

It is named after René Descartes, because $ℝ \times ℝ$ , written $ℝ^{2}$ , is the coordinate plane of his La Géométrie (1637). With $A = {1, 2, 3}$ and $B = {x, y}$ ,

A \times B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}

and $B \times A$ consists of the pairs the other way round, so $A \times B \neq B \times A$ here: the product is not commutative. Products of three or more sets are formed from ordered triples $(a, b, c)$ and so on. In the same way $A^{n}$ is the set of ordered $n$ -tuples of elements of $A$ . For any set $A$ , $A \times \emptyset = \emptyset$ , since there is no second coordinate to choose.

Proposition. If $A$ and $B$ are finite, then $| A \times B | = | A | \cdot | B |$ .

Proof. Let $| A | = m$ and $| B | = n$ , and list $A$ as $a_{1}, \dots, a_{m}$ . Sort the pairs by first coordinate: for each $i$ , the pairs with first coordinate $a_{i}$ are $(a_{i}, b)$ for $b \in B$ , which are $n$ different pairs, since pairs with different second coordinates differ. These $m$ rows are disjoint, since pairs with different first coordinates differ, and together they make up $A \times B$ . So $| A \times B | = n + n + \dots + n$ with $m$ terms, which is $m n$ . (The step "adding $m$ disjoint rows gives the sum of their sizes" is the disjoint case of the union formula, extended to $m$ sets by induction on $m$ .) $□$

This is the product rule of counting, and repeated, it gives $| A^{n} | = | A |^{n}$ . The lesson on functions uses it to count the functions between two finite sets.

The product interacts with the other operations in the expected way on one side. For all sets $A$ , $B$ and $C$ ,

A \times (B \cup C) = (A \times B) \cup (A \times C)

To prove it: a pair $(a, x)$ lies in the left side exactly when $a \in A$ and ( $x \in B$ or $x \in C$ ), and in the right side exactly when ( $a \in A$ and $x \in B$ ) or ( $a \in A$ and $x \in C$ ), and these conditions are equivalent by the distributive law of logic. Every element of either side is a pair, so the sets are equal. The same argument works with $\cap$ or $∖$ in place of $\cup$ . The analogous claim for unions in both coordinates at once is false, and Problem 8 shows why.

Unions and intersections of families

Two sets have a union and an intersection, and by associativity so do any finite number. Analysis and probability need more: the union of infinitely many sets at once. The tool is an indexed family of sets, a set $A_{i}$ for each $i$ in some index set $I$ . Its union and intersection are defined by the quantifiers, as the two-set versions were defined by the connectives:

x \in ⋃_{i \in I} A_{i} ⟺ \exists i \in I (x \in A_{i}) x \in ⋂_{i \in I} A_{i} ⟺ \forall i \in I (x \in A_{i})

So the union collects everything that lies in at least one $A_{i}$ , and the intersection keeps what lies in every $A_{i}$ . When $I = {1, 2}$ these are $A_{1} \cup A_{2}$ and $A_{1} \cap A_{2}$ , since "there is an $i$ among $1$ and $2$ " is an "or", and "for every $i$ among $1$ and $2$ " is an "and". When $I = ℕ$ one also writes $⋃_{n = 1}^{\infty} A_{n}$ and $⋂_{n = 1}^{\infty} A_{n}$ . The symbol $\infty$ there is notation only; there is no set $A_{\infty}$ .

Proofs about families are element chasing with a quantifier in the membership condition. To show $x$ is in a union, produce an index $i$ with $x \in A_{i}$ . To show $x$ is in an intersection, let $i$ be an arbitrary index and show $x \in A_{i}$ . To show $x$ is not in an intersection, produce one index $i$ with $x \notin A_{i}$ . Arguments about intervals of reals often need one fact about $ℝ$ , the Archimedean property: for every real number $t$ there is a natural number $n$ with $n > t$ . It is proved from the completeness of $ℝ$ in the lesson on the real numbers, and used here freely.

Example. Prove that $⋃_{n \in ℕ} [\frac{1}{n}, 2 - \frac{1}{n}] = (0, 2)$ .

Write $A_{n} = [\frac{1}{n}, 2 - \frac{1}{n}]$ , so $A_{1} = [1, 1] = {1}$ , $A_{2} = [\frac{1}{2}, \frac{3}{2}]$ , $A_{3} = [\frac{1}{3}, \frac{5}{3}]$ , and the intervals grow towards both ends of $(0, 2)$ .

First, the union is contained in $(0, 2)$ . Let $x$ be in the union. Then $x \in A_{n}$ for some natural number $n$ , so $\frac{1}{n} \leq x \leq 2 - \frac{1}{n}$ . Since $\frac{1}{n} > 0$ , this gives $0 < x < 2$ .

Second, $(0, 2)$ is contained in the union. Let $0 < x < 2$ . The task is to produce one $n$ with $\frac{1}{n} \leq x$ and $\frac{1}{n} \leq 2 - x$ , and since $x$ and $2 - x$ are both positive, it is enough to take $n$ at least as large as $\frac{1}{x}$ and as $\frac{1}{2 - x}$ . By the Archimedean property there is a natural number $n$ greater than the larger of these two numbers. Then $\frac{1}{n} < x$ and $\frac{1}{n} < 2 - x$ , so $x \in A_{n}$ , and $x$ is in the union.

The sets are equal. Each $A_{n}$ contains its end points, while the union contains neither $0$ nor $2$ . So a union of infinitely many closed intervals need not be a closed interval, a first sign that infinite operations behave differently from finite ones.

Now you. Prove that $⋂_{n \in ℕ} (- \frac{1}{n}, \frac{1}{n}) = {0}$ .

Answer

First, ${0}$ is contained in the intersection. For every natural number $n$ , $- \frac{1}{n} < 0 < \frac{1}{n}$ , so $0 \in (- \frac{1}{n}, \frac{1}{n})$ . As $n$ was arbitrary, $0$ lies in the intersection.

Second, the intersection is contained in ${0}$ . We prove the contrapositive: if $x \neq 0$ , then $x$ is not in the intersection. Let $x \neq 0$ , so $| x | > 0$ . By the Archimedean property there is a natural number $n > \frac{1}{| x |}$ , and then $\frac{1}{n} < | x |$ . So $x \notin (- \frac{1}{n}, \frac{1}{n})$ , since the members of that interval have absolute value less than $\frac{1}{n}$ . One index where $x$ fails is enough to keep $x$ out of the intersection.

The sets are equal. Each interval in the family is open, and the intersection is the closed interval $[0, 0] = {0}$ : the mirror image of the Example.

The same technique shows that $⋂_{n \in ℕ} (0, \frac{1}{n}) = \emptyset$ : a real $x$ in every interval would satisfy $x > 0$ , and then some $n > \frac{1}{x}$ gives $\frac{1}{n} < x$ , so $x \notin (0, \frac{1}{n})$ . Yet the intersection of any finite number of these intervals is the smallest of them, $(0, \frac{1}{N})$ for the largest index $N$ present, which is not empty. What holds at every finite stage can fail for the whole family, and this is the reason the lesson on the real numbers needs closed intervals in its nested interval theorem.

De Morgan's laws extend to families, with the quantifier rules of the lesson on quantifiers doing the work that De Morgan's laws for "and" and "or" did before. For subsets $A_{i}$ of a universe $U$ ,

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

For the first: an element $x$ of $U$ is outside the union exactly when $\neg \exists i (x \in A_{i})$ , which is equivalent to $\forall i (x \notin A_{i})$ , that is, $x \in A_{i}^{c}$ for every $i$ , which is membership of the intersection of the complements. Each step is an equivalence, so both inclusions are proved at once. The second law is the same argument with $\neg \forall$ turned into $\exists \neg$ . The distributive laws extend too: $B \cap ⋃_{i \in I} A_{i} = ⋃_{i \in I} (B \cap A_{i})$ , since " $x \in B$ and there is an $i$ with $x \in A_{i}$ " says the same as "there is an $i$ with $x \in B$ and $x \in A_{i}$ ".

Russell's paradox

Georg Cantor, who created the theory of sets, described a set in 1895 as any collection into a whole of definite, distinct objects of our intuition or thought. Read literally, that allows a set ${x : P (x)}$ for every property $P$ , with no surrounding set: the collection of all objects with the property. Gottlob Frege built his logical foundation of arithmetic, the Grundgesetze der Arithmetik, on a principle of exactly this kind. In 1901 Bertrand Russell found that it is contradictory.

Take the property " $x \notin x$ ", " $x$ is not an element of itself". Most sets have it: the set of even integers is not an even integer, and $\emptyset$ is not an element of $\emptyset$ . If every property defines a set, then there is a set

R = {x : x \notin x}

and its membership rule says that for every object $y$ , $y \in R$ exactly when $y \notin y$ . Now ask whether $R$ is an element of itself, by taking $y = R$ :

R \in R ⟺ R \notin R

No statement can be equivalent to its own negation. If $R \in R$ , the rule gives $R \notin R$ ; if $R \notin R$ , the rule gives $R \in R$ . Either way there is a contradiction, and there is no third case. So the assumption that every property defines a set is false.

Russell wrote to Frege on 16 June 1902, as the second volume of the Grundgesetze was going to press. Frege added an appendix to that volume, published in 1903, acknowledging that the paradox struck at the foundation of his system. The episode is one of the turning points in the history of mathematics: it showed that intuition about collections, however clear it feels, can be inconsistent, and that the rules for forming sets have to be stated explicitly.

The popular version is the village barber who shaves exactly those villagers who do not shave themselves: does he shave himself? The same reasoning shows he does if and only if he does not, and the resolution is simply that no such barber exists. That is the right reading of Russell's argument too. It is a proof, by contradiction, that no set $R$ has the property $\forall y (y \in R ⟺ y \notin y)$ .

The repair used in this lesson from the start is to form sets by a property only inside a set already known, as ${x \in A : P (x)}$ . Run Russell's argument on

R_{A} = {x \in A : x \notin x}

for an arbitrary set $A$ . Its membership rule is: $y \in R_{A}$ exactly when $y \in A$ and $y \notin y$ . Suppose $R_{A} \in A$ . Then taking $y = R_{A}$ gives $R_{A} \in R_{A} ⟺ R_{A} \notin R_{A}$ , the same contradiction. So $R_{A} \notin A$ . Nothing is contradictory any more: the argument has become a proof.

Theorem. For every set $A$ there is a set not belonging to $A$ . In particular, there is no set of all sets.

Proof. Let $A$ be a set. By the argument just given, the set $R_{A} = {x \in A : x \notin x}$ is not an element of $A$ . If there were a set $V$ containing every set, then $R_{V}$ would be a set not in $V$ , a contradiction. $□$

This is why a complement needs a universe. The "set of everything" that would make $A^{c}$ meaningful without a universe does not exist.

What does Russell's paradox have to do with Cantor's theorem?

They are the same argument. Cantor's theorem, proved in the lesson on countable and uncountable sets, says that for every set $A$ there is no function $f$ that assigns to each element $a$ of $A$ a subset $f (a)$ of $A$ in such a way that every subset is assigned to some element. The proof builds the subset

D = {a \in A : a \notin f (a)}

and shows that no element $d$ has $f (d) = D$ : if it did, then $d \in D$ would hold exactly when $d \notin f (d) = D$ , which is impossible. The set $D$ differs from each $f (a)$ at the element $a$ , like a diagonal.

Russell arrived at his paradox, by his own account, by thinking about this proof. If there were a set $V$ of all sets, then every subset of $V$ would itself be a set, hence an element of $V$ , so $P (V) \subseteq V$ . In pure set theory every object is a set, so every element $x$ of $V$ is also a subset of $V$ , and the rule $f (x) = x$ assigns to each element of $V$ a subset of $V$ ; every subset of $V$ is assigned to something, namely to itself. Cantor's theorem says that cannot happen, and his set $D$ becomes ${x \in V : x \notin x}$ , which is Russell's $R$ . Cantor's contradiction has become Russell's paradox. In Cantor's hands the argument proves that power sets are bigger; in Russell's, that some collections are too big to be sets.

The same diagonal shape appears again and again in logic. Kurt Gödel's first incompleteness theorem (1931) builds a sentence that says of itself that it is not provable, and Alan Turing's proof (1936) that no program can decide whether every program halts builds a program that does the opposite of what the supposed decider predicts about it. Each time, an object is defined by disagreeing with the entry on the diagonal of a table that was supposed to be complete.

The axioms of set theory

Russell's paradox showed that sets cannot be formed by any property whatever. Some other rule for forming sets is needed, strong enough to build everything mathematics uses and restrained enough to avoid contradiction. Ernst Zermelo proposed the first such list of axioms in 1908. Abraham Fraenkel and Thoralf Skolem each added an axiom of replacement in 1922, and John von Neumann proposed the axiom of foundation in the 1920s. The result, called Zermelo and Fraenkel set theory, or ZF, and ZFC when the axiom of choice is included, is the standard foundation of mathematics today. Informally, its axioms say:

Extensionality. Sets with the same elements are equal.

Empty set. There is a set with no elements.

Pairing. For any objects $a$ and $b$ there is a set ${a, b}$ . With $a = b$ this gives ${a}$ .

Union. For any set $F$ whose elements are sets, there is a set whose elements are exactly the elements of the elements of $F$ . With $F = {A, B}$ this is $A \cup B$ , and with $F = {A_{i} : i \in I}$ it is $⋃_{i \in I} A_{i}$ .

Power set. For any set $A$ there is a set $P (A)$ of all its subsets.

Separation. For any set $A$ and any property $P$ expressible in the language of sets, there is a set ${x \in A : P (x)}$ .

Replacement. For any set $A$ and any rule assigning an object $f (x)$ to each $x \in A$ , there is a set ${f (x) : x \in A}$ .

Infinity. There is a set that contains $\emptyset$ and, with each element $x$ , also contains $x \cup {x}$ .

Foundation. Every non-empty set $A$ has an element $x$ with $x \cap A = \emptyset$ . One consequence is that no set is an element of itself.

Choice. For every family of non-empty sets there is a way of choosing one element from each.

Every construction in this lesson comes from these axioms. Intersection and difference come from separation, as $A \cap B = {x \in A : x \in B}$ and $A ∖ B = {x \in A : x \notin B}$ , and so does a complement inside a universe. Union needs an axiom of its own, since there is no larger set given in advance to carve it out of; so does the power set. Russell's set is forbidden because separation only ever carves a subset from a set already available, which is exactly the repair of the previous section. The Cartesian product $A \times B$ comes from separation inside $P (P (A \cup B))$ , once ordered pairs are defined as sets, as the lesson on functions does. And the axiom of infinity supplies the natural numbers, as the first deeper explanation below describes.

What the axioms cannot do is prove themselves consistent. Gödel's second incompleteness theorem, of 1931, shows that a consistent system of this strength cannot prove its own consistency, so the evidence for ZF is of another kind: the axioms describe a clear picture, in which sets are built up in stages from the empty set, and more than a century of intensive use has produced no contradiction. In practice mathematicians rarely cite the axioms. They form sets as this lesson has, by separation, unions, power sets and products, confident that each step could be justified from the list if anyone asked.

How can numbers be built out of sets?

If sets are the foundation of mathematics, the natural numbers must be sets too. John von Neumann's definition of 1923 is the one used today. It starts at $0$ and builds each number as the set of all the numbers before it:

0 = \emptyset, 1 = {0} = {\emptyset}, 2 = {0, 1} = {\emptyset, {\emptyset}}, 3 = {0, 1, 2}

and in general the successor of $n$ is $n \cup {n}$ . Each number $n$ is then a set with exactly $n$ elements, and $m < n$ means simply $m \in n$ , which also gives $m \subseteq n$ . The axiom of infinity says precisely that some set contains $0$ and is closed under $x \mapsto x \cup {x}$ , and the intersection of all subsets of that set with this property is the smallest such set: the set $ω = {0, 1, 2, \dots}$ of all natural numbers.

Now induction, which the previous lesson derived from the well-ordering principle, a property of $ℕ$ this course takes as basic, becomes a theorem about sets. Let $S$ be a subset of $ω$ that contains $0$ and contains $n \cup {n}$ whenever it contains $n$ . Then $S$ is one of the sets whose intersection defined $ω$ , so $ω \subseteq S$ , and hence $S = ω$ . That is the induction axiom of Peano, derived from the axioms of sets.

The rest of the number system follows. Integers are built from pairs of natural numbers, with $(a, b)$ standing for $a - b$ and two pairs identified when they stand for the same difference; rationals are built from pairs of integers in the same way, which is the construction in the lesson on equivalence relations; and real numbers are built from sets of rationals. So every object in this course, from $\sqrt{2}$ to a function on $ℝ$ , can be modelled as a set built from $\emptyset$ in stages. Nobody thinks of $3$ as ${\emptyset, {\emptyset}, {\emptyset, {\emptyset}}}$ when adding, and nobody needs to; the point is that the foundation holds.

(This course starts $ℕ$ at $1$ , the convention of number theory and analysis; set theory starts it at $0$ . Nothing of substance depends on the choice.)

What is the axiom of choice, and why was it controversial?

For a finite family of non-empty sets, choosing one element from each needs no axiom: pick an element of the first set, then of the second, and so on, which is an induction on the number of sets. For infinite families, no finite process makes all the choices, and the axiom asserts that a choice function exists anyway. Russell's illustration: from infinitely many pairs of shoes one can choose a shoe from each pair without the axiom, by the rule "take the left one", but from infinitely many pairs of socks, where the two members of a pair are indistinguishable, no rule is available, and only the axiom supplies a choice.

Zermelo stated the axiom in 1904, to prove that every set can be well ordered, that is, given an order in which every non-empty subset has a least element, as $ℕ$ has. The proof was controversial, because the axiom asserts that something exists without saying what it is, the objection the constructivists raised against non-constructive proofs in the lesson on direct proof. It also has strange consequences. Stefan Banach and Alfred Tarski showed in 1924, using choice, that a solid ball can be cut into finitely many pieces that can be moved rigidly and reassembled into two balls of the same size as the first; the pieces are so irregular that they have no volume at all.

The question was settled as far as it can be. Kurt Gödel showed in 1938 that if ZF is consistent, it stays consistent when choice is added, and Paul Cohen showed in 1963 that it also stays consistent when the negation of choice is added. So choice can be neither proved nor refuted from the other axioms. Most mathematicians accept it, because much of mathematics depends on it: that every vector space has a basis, and many results in analysis and algebra, are equivalent to it or need it. Its most used form in practice is Zorn's lemma, stated in the lesson on order relations.

Sets now have a precise language, a method of proof and a foundation. A set on its own does nothing, though. Mathematics is mostly about processes that turn one thing into another, a number into its square or a point into its reflection, and the next lesson makes those processes precise as functions, built, like everything else, out of sets.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. In the universe $U = {1, 2, \dots, 8}$ , let $A = {1, 2, 3, 4}$ and $B = {3, 4, 5, 6}$ . List the elements of $A \cup B$ , $A \cap B$ , $A ∖ B$ , $B ∖ A$ , $A △ B$ , $A^{c}$ , $(A \cup B)^{c}$ and $A^{c} \cap B^{c}$ .

Solution

$A \cup B = {1, 2, 3, 4, 5, 6}$ , $A \cap B = {3, 4}$ , $A ∖ B = {1, 2}$ , $B ∖ A = {5, 6}$ , and $A △ B = {1, 2, 5, 6}$ , the elements in exactly one of the two sets.

$A^{c} = {5, 6, 7, 8}$ . $(A \cup B)^{c} = {7, 8}$ . Since $B^{c} = {1, 2, 7, 8}$ , $A^{c} \cap B^{c} = {7, 8}$ , the same set, as De Morgan's law requires.

2. Decide which statements are true: (a) $\emptyset \in \emptyset$ ; (b) $\emptyset \subseteq \emptyset$ ; (c) $\emptyset \in {\emptyset}$ ; (d) ${\emptyset} \subseteq {\emptyset}$ ; (e) ${1} \in {1, {1}}$ ; (f) ${1} \subseteq {1, {1}}$ ; (g) ${{1}} \subseteq {1, {1}}$ ; (h) ${{1}} \in {1, {1}}$ .

Solution

(a) False: $\emptyset$ has no elements at all. (b) True: the empty set is a subset of every set. (c) True: $\emptyset$ is the one element of ${\emptyset}$ . (d) True: every set is a subset of itself.

(e) True: ${1}$ is one of the two elements, $1$ and ${1}$ . (f) True: the only element of ${1}$ is $1$ , which is an element of ${1, {1}}$ . (g) True: the only element of ${{1}}$ is ${1}$ , which is an element of ${1, {1}}$ . (h) False: the elements of ${1, {1}}$ are $1$ and ${1}$ , and ${{1}}$ is neither, since its only element is ${1}$ while the only element of ${1}$ is $1$ , and ${1} \neq 1$ .

3. Write out $P ({a, b})$ , $P (\emptyset)$ and $P (P (\emptyset))$ in full, and find the number of elements of $P (P ({1, 2}))$ .

Solution

$P ({a, b}) = {\emptyset, {a}, {b}, {a, b}}$ , with $2^{2} = 4$ elements.

$P (\emptyset) = {\emptyset}$ , with $2^{0} = 1$ element.

$P (P (\emptyset)) = P ({\emptyset}) = {\emptyset, {\emptyset}}$ , with $2^{1} = 2$ elements.

$P ({1, 2})$ has $2^{2} = 4$ elements, so by the theorem on power sets $P (P ({1, 2}))$ has $2^{4} = 16$ elements.

4. List the elements of each set: (a) ${n \in ℤ : n^{2} \leq 5}$ ; (b) ${2 k + 1 : k \in ℤ, - 2 \leq k \leq 2}$ ; (c) ${x \in ℝ : x^{2} = - 1}$ ; (d) ${(x, y) \in ℤ \times ℤ : x^{2} + y^{2} = 1}$ ; (e) ${1, 2} \times {1, 2}$ .

Solution

(a) ${- 2, - 1, 0, 1, 2}$ , since $2^{2} = 4 \leq 5$ and $3^{2} = 9 > 5$ .

(b) The values of $2 k + 1$ for $k = - 2, - 1, 0, 1, 2$ are $- 3, - 1, 1, 3, 5$ , so the set is ${- 3, - 1, 1, 3, 5}$ .

(d) If $x^{2} + y^{2} = 1$ with integers $x$ and $y$ , then one square is $1$ and the other $0$ . So the set is ${(1, 0), (- 1, 0), (0, 1), (0, - 1)}$ , four pairs.

(e) ${(1, 1), (1, 2), (2, 1), (2, 2)}$ , four pairs, as $| {1, 2} |^{2} = 4$ requires; $(1, 2)$ and $(2, 1)$ are different.

Core

5. Let $A$ , $B$ and $C$ be sets. (a) Prove that $(A ∖ B) ∖ C = A ∖ (B \cup C)$ . (b) Prove or disprove that $A ∖ (B ∖ C) = (A ∖ B) ∖ C$ . (c) Prove that $A ∖ (B ∖ C) = (A ∖ B) \cup (A \cap C)$ .

Hint

Write each membership condition with "and", "or" and "not", and simplify with the laws of logic. For (b), try sets with a single element.

Solution

(a) For every object $x$ : $x \in (A ∖ B) ∖ C$ exactly when $x \in A$ , $x \notin B$ and $x \notin C$ . And $x \in A ∖ (B \cup C)$ exactly when $x \in A$ and $x \notin B \cup C$ , that is, $x \in A$ and not ( $x \in B$ or $x \in C$ ), which by De Morgan's law for statements is $x \in A$ , $x \notin B$ and $x \notin C$ . The conditions are the same, so each set is contained in the other and they are equal.

(b) False. Take $A = B = C = {1}$ . Then $B ∖ C = \emptyset$ , so $A ∖ (B ∖ C) = {1}$ , while $A ∖ B = \emptyset$ , so $(A ∖ B) ∖ C = \emptyset$ . Difference is not associative.

(c) For every object $x$ , $x \in A ∖ (B ∖ C)$ exactly when $x \in A$ and not ( $x \in B$ and $x \notin C$ ). By De Morgan's law for statements, the second part is ( $x \notin B$ or $x \in C$ ). So the condition is: $x \in A$ , and $x \notin B$ or $x \in C$ . By the distributive law of logic this is: ( $x \in A$ and $x \notin B$ ) or ( $x \in A$ and $x \in C$ ), which says $x \in (A ∖ B) \cup (A \cap C)$ . Each step is an equivalence, so the sets are equal. With the sets of (b), the right side is $\emptyset \cup {1} = {1}$ , as it should be.

6. Let $A$ , $B$ and $C$ be sets. (a) Show that $A \cup C = B \cup C$ does not imply $A = B$ . (b) Prove that if $A \cup C = B \cup C$ and $A \cap C = B \cap C$ , then $A = B$ . (c) Prove that if $A △ C = B △ C$ , then $A = B$ .

Hint

For (b), take $x \in A$ and split into the cases $x \in C$ and $x \notin C$ ; each case uses one of the two hypotheses. For (c), use the algebra of symmetric difference from the lesson.

Solution

(a) Take $A = {1}$ , $B = \emptyset$ and $C = {1}$ . Then $A \cup C = {1} = B \cup C$ , but $A \neq B$ .

(b) Suppose $A \cup C = B \cup C$ and $A \cap C = B \cap C$ . We show $A \subseteq B$ . Let $x \in A$ . If $x \in C$ , then $x \in A \cap C = B \cap C$ , so $x \in B$ . If $x \notin C$ , then $x \in A \cup C = B \cup C$ , so $x \in B$ or $x \in C$ , and since $x \notin C$ , $x \in B$ . In both cases $x \in B$ , so $A \subseteq B$ . The hypotheses are unchanged when $A$ and $B$ are exchanged, so the same argument gives $B \subseteq A$ , and $A = B$ .

(c) Suppose $A △ C = B △ C$ , and take the symmetric difference of both sides with $C$ . Using associativity, $C △ C = \emptyset$ and $X △ \emptyset = X$ ,

A = A △ (C △ C) = (A △ C) △ C = (B △ C) △ C = B △ (C △ C) = B

So $A = B$ . Symmetric difference cancels where union and intersection alone do not, and (b) shows that union and intersection together do.

7. Find the flaw in this proof, and show that the claim is false.

Claim. For all sets $A$ , $B$ and $C$ , if $A \subseteq B \cup C$ , then $A \subseteq B$ or $A \subseteq C$ .

Proof. Suppose $A \subseteq B \cup C$ , and let $x \in A$ . Then $x \in B \cup C$ , so $x \in B$ or $x \in C$ . If $x \in B$ , then since $x$ was an arbitrary element of $A$ , $A \subseteq B$ . If $x \in C$ , then in the same way $A \subseteq C$ . So $A \subseteq B$ or $A \subseteq C$ .

Hint

Which of $B$ and $C$ contains $x$ depends on $x$ . Compare "for every $x$ , $x \in B$ or $x \in C$ " with "every $x$ is in $B$ , or every $x$ is in $C$ ".

Solution

The claim is false. Take $A = {1, 2}$ , $B = {1}$ and $C = {2}$ . Then $A \subseteq B \cup C = {1, 2}$ , but $A ⊈ B$ because $2 \notin B$ , and $A ⊈ C$ because $1 \notin C$ .

The flaw is in the case split. Once the proof splits into cases according to whether $x \in B$ , the element $x$ is no longer arbitrary: in the first case it is an element of $A$ that happens to lie in $B$ . Concluding " $A \subseteq B$ " from that case generalises from a restricted $x$ , the misuse of "arbitrary" discussed in the lesson on direct proof. What the argument actually proves is $\forall x \in A (x \in B \lor x \in C)$ , which is just the hypothesis again. The claim needs $(\forall x \in A x \in B) \lor (\forall x \in A x \in C)$ , and a universal quantifier does not distribute over "or", as the lesson on quantifiers showed.

The correct statement in the other direction is true: if $A \subseteq B$ or $A \subseteq C$ , then $A \subseteq B \cup C$ , since $B$ and $C$ are both subsets of $B \cup C$ .

8. Let $A$ , $B$ , $C$ and $D$ be sets. (a) Prove that $(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)$ . (b) Prove that $(A \times B) \cup (C \times D) \subseteq (A \cup C) \times (B \cup D)$ , and show by an example that equality can fail.

Hint

Every element of each side is an ordered pair, so let $(x, y)$ be an arbitrary pair and compare the conditions on $x$ and $y$ . For the example, draw the sets as rectangles in the plane.

Solution

(a) Every element of either side is an ordered pair, so it is enough to compare the conditions for a pair $(x, y)$ to belong. The pair is in $(A \times B) \cap (C \times D)$ exactly when ( $x \in A$ and $y \in B$ ) and ( $x \in C$ and $y \in D$ ). Rearranging the "and"s, this is ( $x \in A$ and $x \in C$ ) and ( $y \in B$ and $y \in D$ ), that is, $x \in A \cap C$ and $y \in B \cap D$ , which is the condition for $(x, y) \in (A \cap C) \times (B \cap D)$ . So the sets are equal.

(b) Let $(x, y) \in (A \times B) \cup (C \times D)$ . If $(x, y) \in A \times B$ , then $x \in A \subseteq A \cup C$ and $y \in B \subseteq B \cup D$ , so $(x, y) \in (A \cup C) \times (B \cup D)$ . If $(x, y) \in C \times D$ , the same argument applies with $C$ and $D$ . So the inclusion holds.

For the example, take $A = B = {1}$ and $C = D = {2}$ . Then $(A \times B) \cup (C \times D) = {(1, 1), (2, 2)}$ , while $(A \cup C) \times (B \cup D) = {1, 2} \times {1, 2}$ also contains $(1, 2)$ and $(2, 1)$ . In pictures, the union of two squares on a diagonal is smaller than the square that spans both.

9. Prove that for all sets $A$ and $B$ , $P (A) \subseteq P (B)$ if and only if $A \subseteq B$ . Deduce that $P (A) = P (B)$ if and only if $A = B$ .

Hint

For the forward direction, find an element of $P (A)$ that tells you about $A$ itself.

Solution

( $\Rightarrow$ ) Suppose $P (A) \subseteq P (B)$ . Since $A \subseteq A$ , we have $A \in P (A)$ , so $A \in P (B)$ , which means $A \subseteq B$ .

( $\Leftarrow$ ) Suppose $A \subseteq B$ , and let $X \in P (A)$ , so $X \subseteq A$ . By transitivity of $\subseteq$ , $X \subseteq B$ , so $X \in P (B)$ . Hence $P (A) \subseteq P (B)$ .

For the deduction: $P (A) = P (B)$ holds exactly when $P (A) \subseteq P (B)$ and $P (B) \subseteq P (A)$ . By the first part this holds exactly when $A \subseteq B$ and $B \subseteq A$ , which by double inclusion is $A = B$ .

10. Prove that $⋂_{n \in ℕ} [0, 1 + \frac{1}{n}) = [0, 1]$ and that $⋃_{n \in ℕ} [0, 1 - \frac{1}{n}] = [0, 1)$ .

Hint

Each needs the Archimedean property in exactly one of the two inclusions. For a real number that is supposed to be kept out, find one index that excludes it; for a real number that is supposed to be let in, find one index that includes it.

Solution

The intersection. First, $[0, 1]$ is contained in it. Let $0 \leq x \leq 1$ and let $n$ be any natural number. Then $x \leq 1 < 1 + \frac{1}{n}$ , so $x \in [0, 1 + \frac{1}{n})$ . As $n$ was arbitrary, $x$ is in the intersection.

Second, the intersection is contained in $[0, 1]$ . Let $x$ be in every $[0, 1 + \frac{1}{n})$ . Taking $n = 1$ gives $x \geq 0$ . Suppose, for contradiction, that $x > 1$ . Then $x - 1 > 0$ , and by the Archimedean property there is a natural number $n > \frac{1}{x - 1}$ , so $\frac{1}{n} < x - 1$ , that is, $x > 1 + \frac{1}{n}$ . Then $x \notin [0, 1 + \frac{1}{n})$ , a contradiction. So $0 \leq x \leq 1$ .

The union. First, it is contained in $[0, 1)$ . If $x \in [0, 1 - \frac{1}{n}]$ for some $n$ , then $0 \leq x \leq 1 - \frac{1}{n} < 1$ .

Second, $[0, 1)$ is contained in it. Let $0 \leq x < 1$ . Then $1 - x > 0$ , and by the Archimedean property there is a natural number $n > \frac{1}{1 - x}$ , so $\frac{1}{n} < 1 - x$ , that is, $x < 1 - \frac{1}{n}$ . Hence $x \in [0, 1 - \frac{1}{n}]$ , and $x$ is in the union.

So an intersection of half-open intervals can be closed, and a union of closed intervals can be half-open.

11. Using only the formula $| X \cup Y | = | X | + | Y | - | X \cap Y |$ for finite sets and the laws of set algebra, prove that for all finite sets $A$ , $B$ and $C$ ,

| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |

Use it to count the integers from $1$ to $100$ that are divisible by at least one of $2$ , $3$ and $5$ .

Hint

Apply the two-set formula with $X = A \cup B$ and $Y = C$ , then use the distributive law on $(A \cup B) \cap C$ and apply the two-set formula again.

Solution

By the two-set formula with $X = A \cup B$ and $Y = C$ ,

| A \cup B \cup C | = | A \cup B | + | C | - | (A \cup B) \cap C |

The first term is $| A | + | B | - | A \cap B |$ , by the two-set formula again. For the last term, the distributive law gives $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ , and the intersection of these two sets is $(A \cap C) \cap (B \cap C) = A \cap B \cap C$ , by the associative, commutative and idempotent laws. So, by the two-set formula once more,

| (A \cup B) \cap C | = | A \cap C | + | B \cap C | - | A \cap B \cap C |

Substituting both into the first display gives the formula.

For the count, let $A$ , $B$ and $C$ be the multiples of $2$ , $3$ and $5$ in ${1, \dots, 100}$ . A number is a multiple of both $2$ and $3$ exactly when it is a multiple of $6$ (proved in the lesson on direct proof), and similarly for the other pairs and for all three, since $2$ , $3$ and $5$ are distinct primes. The number of multiples of $d$ from $1$ to $100$ is the quotient of $100$ by $d$ . So $| A | = 50$ , $| B | = 33$ , $| C | = 20$ , $| A \cap B | = 16$ , $| A \cap C | = 10$ , $| B \cap C | = 6$ , $| A \cap B \cap C | = 3$ , and

| A \cup B \cup C | = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74

So $74$ of the numbers are divisible by at least one of $2$ , $3$ and $5$ , and $26$ by none of them.

Challenge

12. Prove that there is no set $A$ with $P (A) \subseteq A$ . Deduce again that there is no set of all sets.

Hint

Russell's set, carved out of $A$ , is a subset of $A$ .

Solution

Suppose, for contradiction, that $A$ is a set with $P (A) \subseteq A$ . By separation there is a set

R = {x \in A : x \notin x}

and $R \subseteq A$ , so $R \in P (A)$ , and therefore $R \in A$ . Now apply the membership rule to $R$ itself. Since $R \in A$ , the rule says $R \in R$ exactly when $R \notin R$ . If $R \in R$ , then $R \notin R$ ; if $R \notin R$ , then $R \in R$ . Either way there is a contradiction, so no such $A$ exists.

If $V$ were a set containing every set, then every subset of $V$ , being a set, would be an element of $V$ , so $P (V) \subseteq V$ , which has just been shown impossible. So there is no set of all sets.

For finite sets the result is also a matter of counting, since a set with $n$ elements has $2^{n} > n$ subsets. The argument above works for every set, finite or infinite, and it is a special case of Cantor's theorem that $P (A)$ is always strictly larger than $A$ .

13. Let $A$ , $B$ and $C$ be subsets of a universe $U$ . Call a subset of $U$ generated if it can be built from $A$ , $B$ and $C$ by finitely many applications of $\cup$ , $\cap$ and complement. For each of the $8$ choices of $X \in {A, A^{c}}$ , $Y \in {B, B^{c}}$ and $Z \in {C, C^{c}}$ , call $X \cap Y \cap Z$ an atom. (a) Prove that the atoms are pairwise disjoint and that their union is $U$ . (b) Prove that every generated set is a union of some collection of atoms. (c) Deduce that there are at most $256$ generated sets, and exactly $256$ when every atom is non-empty.

Hint

For (b), use structural induction on how a generated set is built. The union of the atoms in a collection $S$ , the union of those in $T$ , and the intersection of the two, correspond to $S \cup T$ and $S \cap T$ ; by (a), the complement corresponds to the atoms not in $S$ .

Solution

(a) Let $x \in U$ . Exactly one of $x \in A$ , $x \in A^{c}$ holds, and likewise for $B$ and $C$ . So $x$ lies in exactly one atom, namely the one whose factors are the sets containing $x$ . Every element of $U$ is in some atom, so the union of the atoms is $U$ ; no element is in two atoms, so the atoms are pairwise disjoint.

(b) For a collection $S$ of atoms, write $⋃ S$ for the union of the atoms in $S$ (with $⋃ S = \emptyset$ when $S$ is empty). By (a), for every $x \in U$ , $x \in ⋃ S$ exactly when the unique atom containing $x$ belongs to $S$ . We prove by structural induction that every generated set has the form $⋃ S$ .

Base cases: $A$ is the union of the four atoms whose first factor is $A$ , since an element of $A$ lies in one of them and each of them lies inside $A$ . Likewise for $B$ and $C$ .

Steps: suppose $X = ⋃ S$ and $Y = ⋃ T$ . For $x \in U$ , let $a_{x}$ be the atom containing $x$ . Then $x \in X \cup Y$ exactly when $a_{x} \in S$ or $a_{x} \in T$ , that is, $a_{x} \in S \cup T$ , so $X \cup Y = ⋃ (S \cup T)$ . In the same way $X \cap Y = ⋃ (S \cap T)$ , and $x \in X^{c}$ exactly when $a_{x} \notin S$ , so $X^{c} = ⋃ S'$ , where $S'$ is the collection of atoms not in $S$ . So every rule preserves the property, and every generated set is a union of atoms.

(c) There are $8$ atoms, hence $2^{8} = 256$ collections of atoms by the theorem on power sets, and by (b) each generated set is $⋃ S$ for one of them. So there are at most $256$ generated sets.

Conversely, every $⋃ S$ is generated: each atom is generated, as an intersection of generated sets; unions of generated sets are generated; and $\emptyset = A \cap A^{c}$ is generated. If every atom is non-empty, then different collections give different sets: if $S \neq T$ , some atom lies in one and not the other, say in $S$ and not in $T$ , and an element of that atom is in $⋃ S$ but, by (a), not in $⋃ T$ . So there are exactly $256$ generated sets in that case.

The count matches the $2^{2^{3}} = 256$ truth tables in three variables, and (b) is the set version of the fact from the lesson on statements and connectives that every formula is equivalent to a disjunction of conjunctions, its disjunctive normal form.