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, but the objects the proofs talk about have been informal, and this lesson makes them precise. It assumes the connectives, including the rule that a conditional with a false hypothesis is vacuously true, the quantifiers $\forall$ and $\exists$ , and induction.

Membership and set builder notation

A set is a collection of objects, its elements, 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 (starting at $1$ ), the integers, the rationals and the reals.

A small set can be listed between braces: ${2, 3, 5, 7}$ is the set of primes below $10$ . A large one is described by a property, 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, and the result is the set of 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. A second form puts an expression first: ${2 k : k \in ℤ}$ is the even integers.

The notation comes with one rule, and proofs use it constantly: $y$ belongs to ${x \in A : P (x)}$ exactly when $y \in A$ and $P (y)$ is true. The insistence on a surrounding set $A$ looks like pedantry, and the last section shows that it is not.

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)

To prove this universal conditional, let $x$ be an arbitrary element of $A$ and show, using only what membership in $A$ means, that $x \in B$ . One element of $A$ outside $B$ disproves it.

Two sets are equal when they have the same elements. So ${1, 2, 2} = {2, 1}$ : each element of either side, $1$ or $2$ , lies in the other. Order is not an element, and writing $2$ twice names the same element twice. The definition also gives the method this lesson is built round: $A = B$ exactly when $A \subseteq B$ and $B \subseteq A$ , so a proof that two sets are equal is two subset proofs, called a proof by double inclusion.

Keep $\in$ and $\subseteq$ apart: $1 \in {1, 2}$ and ${1} \subseteq {1, 2}$ , but ${1} \notin {1, 2}$ , since the set ${1}$ is not one of the numbers $1$ and $2$ . Yet ${1} \in {{1}, 2}$ .

Example. Prove that ${n \in ℤ : 2 ∣ n and 3 ∣ n} = {n \in ℤ : 6 ∣ n}$ .

Call the sides $L$ and $R$ . First, $L \subseteq R$ . Let $n \in L$ . Then $n$ is an even integer and $n = 3 b$ for some integer $b$ . If $b$ were odd, $3 b$ would be a product of odd numbers and so odd, contradicting $n$ even; hence $b = 2 c$ for some integer $c$ , and $n = 6 c$ . So $6 ∣ n$ , and $n \in R$ . Second, $R \subseteq L$ . Let $n \in R$ , so $n = 6 c$ for some integer $c$ . Then $n = 2 (3 c)$ and $n = 3 (2 c)$ , so $2 ∣ n$ and $3 ∣ n$ , and $n \in L$ . Each set is a subset of the other, so $L = R$ .

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

Answer

Call the left side $S$ ; note $x^{2} - 3 x + 2 = (x - 1) (x - 2)$ . First, $S \subseteq (1, 2)$ . Let $x \in S$ , so $(x - 1) (x - 2) < 0$ . A product of two reals is negative only when one factor is positive and the other negative, and since $x - 1 > x - 2$ , the positive one is $x - 1$ . 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$ . Hence $S = (1, 2)$ .

Union, intersection, difference and complement

Four operations build new sets from old, each a connective in disguise. $x$ is in the union $A \cup B$ when $x \in A$ or $x \in B$ , with the inclusive "or"; in the intersection $A \cap B$ when $x \in A$ and $x \in B$ ; and in the difference $A ∖ B$ when $x \in A$ and $x \notin B$ . With $A = {1, 2, 3, 4}$ and $B = {3, 4, 5}$ these are ${1, 2, 3, 4, 5}$ , ${3, 4}$ and ${1, 2}$ .

The complement of $A$ is everything not in $A$ , and "everything" needs a limit: a universe $U$ , fixed in advance and containing every set under discussion, with $A^{c} = U ∖ A$ . The universe is part of the meaning: the complement of the even integers is the odd integers when $U = ℤ$ , but also contains $\frac{1}{2}$ and $π$ when $U = ℝ$ .

The intersection of ${1, 2}$ and ${3}$ has no elements at all. It is the empty set $\emptyset$ , and it 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 the conditional is vacuously true. The same argument shows there is only one empty set, since two sets with no elements are each a subset of the other. But ${\emptyset}$ is not empty: it has one element.

Proving an identity by double inclusion

An identity between sets claims that two sets are equal for every choice of $A$ , $B$ and $C$ . A drawing of overlapping circles shows one arrangement; double inclusion covers them all, one arbitrary element at a time.

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

First, left in right. Let $x \in A \cap (B \cup C)$ . Then $x \in A$ , and $x \in B$ or $x \in C$ . If $x \in B$ , then $x \in A \cap B$ ; if $x \in C$ , then $x \in A \cap C$ . Either way $x$ is in the right side. Second, right in 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$ , so $x \in A \cap (B \cup C)$ ; the case $x \in A \cap C$ is the same with $C$ for $B$ . Each side contains the other, so they are equal.

An "or" in the hypothesis became a proof by cases, and an "or" in the conclusion needed only one of its parts. That is the pattern of most identity proofs.

Now you. Prove that 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$ , or if $x$ is in both $B$ and $C$ , then $x$ is in $A \cup B$ and in $A \cup C$ , so in the right side. Second, right in left. Let $x \in (A \cup B) \cap (A \cup C)$ . If $x \in A$ , it is in the left side. If not, 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$ is in the left side. The sets are equal.

De Morgan's laws for sets

Augustus De Morgan's laws for statements, from 1847, say that $\neg (P \lor Q)$ is equivalent to $\neg P \land \neg Q$ , and $\neg (P \land Q)$ to $\neg P \lor \neg Q$ . Since union is "or", intersection "and" and complement "not", the same laws hold for subsets of a universe $U$ :

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

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$ ; likewise $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$ . Every identity here is an equivalence of statements with " $x \in$ " written in front.

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 $x \notin A$ or $x \notin B$ , that is, $x \in A^{c}$ or $x \in B^{c}$ , and $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 \notin A$ , so $x \notin A \cap B$ ; if $x \in B^{c}$ , the same holds with $B$ . Either way $x \in (A \cap B)^{c}$ . The sets are equal.

Power sets and products

The power set $P (A)$ is the set of all subsets of $A$ . For $A = {1, 2, 3}$ it has eight elements: $\emptyset$ , three one-element sets, three pairs, and $A$ itself. Writing $| A |$ for the number of elements of a finite set, the pattern is general: if $| A | = n$ , then $| P (A) | = 2^{n}$ .

The proof is by induction on $n \geq 0$ . When $n = 0$ , $A = \emptyset$ , whose only subset is $\emptyset$ , and $1 = 2^{0}$ . Suppose every set of $n$ elements has $2^{n}$ subsets, and let $| A | = n + 1$ . Choose $a \in A$ and let $A^{'} = A ∖ {a}$ , which has $n$ elements. A subset of $A$ either omits $a$ , and is then a subset of $A^{'}$ , or contains $a$ , and is then $S \cup {a}$ for exactly one subset $S$ of $A^{'}$ . There are $2^{n}$ of each kind and none of both, so $A$ has $2^{n} + 2^{n} = 2^{n + 1}$ subsets.

An ordered pair $(a, b)$ differs from the set ${a, b}$ : $(a, b) = (c, d)$ exactly when $a = c$ and $b = d$ . The Cartesian product $A \times B$ is the set of all pairs $(a, b)$ with $a \in A$ and $b \in B$ , named after Descartes because $ℝ \times ℝ$ is the coordinate plane. For finite sets $| A \times B | = | A | | B |$ : sort the pairs by first coordinate, and each of the $| A |$ choices of $a$ gives a row of exactly $| B |$ pairs, with no pair in two rows. So ${1, 2, 3} \times {x, y}$ has $3 \times 2 = 6$ elements.

Unions and intersections of many sets

A family of sets $A_{1}, A_{2}, A_{3}, \dots$ , one for each $n \in ℕ$ , has a union and an intersection defined by the quantifiers:

x \in A_{1} \cup A_{2} \cup \dots ⟺ \exists n (x \in A_{n}) x \in A_{1} \cap A_{2} \cap \dots ⟺ \forall n (x \in A_{n})

Take $A_{n} = (0, \frac{1}{n})$ . The intersection of $A_{1}$ to $A_{N}$ is $(0, \frac{1}{N})$ , never empty, yet the intersection over all $n \in ℕ$ is $\emptyset$ . Suppose $x$ lies in every $A_{n}$ . Then $x > 0$ , so some natural number $n$ exceeds $\frac{1}{x}$ (a property of the reals proved in a later lesson), and for it $\frac{1}{n} < x$ , so $x \notin A_{n}$ , a contradiction. What holds at every finite stage can fail for the whole family.

Russell's paradox

Georg Cantor, who founded the theory, defined a set in 1895 as any collection of definite, distinct objects into a whole. Read literally, that allows ${x : P (x)}$ for any property $P$ , with no surrounding set. In 1901 Bertrand Russell took the property $x \notin x$ and formed

R = {x : x \notin x}

By the membership rule, $R \in R$ exactly when $R \notin R$ , and no statement can be equivalent to its own negation. Russell's letter of June 1902 reached Gottlob Frege as the second volume of his foundations of arithmetic, built on exactly this kind of set, went to press.

The repair, due to Ernst Zermelo in 1908, is the rule this lesson has used throughout: a property may only carve a subset out of a set already known, as ${x \in A : P (x)}$ . Run Russell's argument on $R_{A} = {x \in A : x \notin x}$ . If $R_{A}$ were in $A$ , then $R_{A} \in R_{A}$ exactly when $R_{A} \notin R_{A}$ , so $R_{A} \notin A$ . The paradox becomes a theorem: no set contains every set, which is why a complement needs a universe.

Sets now have a precise language and a method of proof, but a set on its own does nothing. 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.