Sets, relations and functions

The language of the course

The next lesson defines the natural numbers by means of a function, the successor, which is injective and does not reach $1$. The next unit constructs the integers and the rational numbers as classes of an equivalence relation; the lesson on combinatorics defines the number of elements by means of bijections; the order of the natural numbers is an order relation; and the third unit composes and inverts real functions. All these words belong to a single language, which should be fixed before it is used, together with the first theorems that the course will invoke later.

It is worth pointing out what is anticipated. The examples use small natural numbers with their order, their addition, their multiplication, divisibility and the remainder of a division, as they are learned at school. The next lesson defines the natural numbers by means of the Peano axioms, and the lessons of the unit define those operations and prove their properties without using any example from this one, so there is no circularity. No theorem of this lesson depends on the examples: the numbers only serve to show the theorems in action.

What is admitted

A set is a collection of objects, its elements; one writes $a \in A$ to say that $a$ belongs to $A$, and $a \notin A$ to deny it. Set and membership are not defined: they are primitive notions, like $1$ and the successor in arithmetic. However, not every property defines a set. If there existed the set $R$ of all sets that do not belong to themselves, the question whether $R$ belongs to $R$ would have no answer, because by the definition of $R$ one would have $R \in R \leftrightarrow R \notin R$. This contradiction, discovered by Russell in 1901, forces a restriction on the formation of sets: a property only selects elements of a set already given.

Admitted fact (rules of naive set theory). The rules of naive set theory that this lesson uses are admitted without proof: two sets with the same elements are equal; from a given set $A$ and a property $P$ one forms the set $\{ x \in A : P(x) \}$ of the elements of $A$ that satisfy it; and there exist the empty set, the set $\{a, b\}$ whose only elements are $a$ and $b$, the union of the elements of a set of sets, and the set of the subsets of a set. The existence of a set with the properties of the set of natural numbers is admitted in the next lesson.

These rules are part of the axioms of Zermelo and Fraenkel, whose study belongs to set theory and goes beyond this course; that is why they are admitted, and they are stated so that it is known exactly what is used.

The logic of quantifiers

Proofs combine statements with the connectives $\neg$, $\wedge$, $\vee$, $\rightarrow$ and $\leftrightarrow$, whose laws are studied in the complementary course Mathematical Logic I: Propositional Logic, starting from its language; here it suffices to recall that the implication $p \rightarrow q$ is false only when $p$ is true and $q$ false, that it is equivalent to its contrapositive $\neg q \rightarrow \neg p$, and that De Morgan’s laws negate a conjunction or a disjunction:

To speak of sets one also needs statements about all elements or about some of them. If $P(x)$ is a property of the elements of $A$, the statement $(\forall x \in A)\,P(x)$, which is read “for every $x$ in $A$, $P(x)$”, asserts that all the elements of $A$ satisfy it; the statement $(\exists x \in A)\,P(x)$, “there exists an $x$ in $A$ such that $P(x)$”, asserts that at least one satisfies it; and $(\exists! x \in A)\,P(x)$ asserts that exactly one satisfies it. The symbols $\forall$ and $\exists$ are called quantifiers, universal and existential.

Admitted fact (negation of quantifiers). To deny that all elements satisfy a property is to assert that some element does not satisfy it, and to deny that some element satisfies it is to assert that none does:

These rules, which belong to first-order logic, are admitted; they extend De Morgan’s laws, because if $A = \{a, b\}$ the universal statement is $P(a) \wedge P(b)$ and the existential one is $P(a) \vee P(b)$. The order of the quantifiers matters: the statement $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ says that every natural number has a greater one, and it is true; the statement $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ says that there is a natural number greater than all of them, greater even than itself, and it is false.

The logical form of a statement dictates the way to prove it. The strategies that this lesson uses are the following; their logical justification is studied in the lesson on deduction techniques.

• To prove $(\forall x \in A)\,P(x)$, take an arbitrary element $x$ of $A$, assuming nothing about it beyond its membership in $A$, and prove $P(x)$.
• To prove $(\exists x \in A)\,P(x)$, exhibit a specific element of $A$ that satisfies $P$; to refute $(\forall x \in A)\,P(x)$, a counterexample suffices, an element that does not satisfy it.
• To prove $p \rightarrow q$, assume $p$ and deduce $q$; or prove the contrapositive $\neg q \rightarrow \neg p$; or assume $p \wedge \neg q$ and reach a contradiction.
• To prove $p \leftrightarrow q$, prove the two implications $p \rightarrow q$ and $q \rightarrow p$.

Sets

Membership, equality and inclusion

A set is described by listing, enumerating its elements between braces, as $\{1, 2, 3\}$, or by set-builder notation, by means of a property, as $\{ n \in \mathbb{N} : n \leq 3 \}$, which is the same set. The rule of extensionality says that a set is determined by its elements:

It follows that in a description by listing neither the order nor repetitions matter: $\{1, 2, 2\}$ and $\{2, 1\}$ are the same set, because they have the same elements. It also follows that there is only one set without elements, the empty set $\emptyset$: two sets without elements have the same elements, namely none.

Definition (inclusion). A set $A$ is contained in a set $B$, or is a subset of $B$, when every element of $A$ is an element of $B$:

If, moreover, $A \neq B$, one says that $A$ is a proper subset of $B$.

The empty set is contained in every set $A$, because the implication $x \in \emptyset \rightarrow x \in A$ always has a false antecedent and is therefore true. Membership must be distinguished from inclusion: $1 \in \{1, 2\}$ and $\{1\} \subseteq \{1, 2\}$ are true, whereas $\{1\} \in \{1, 2\}$ is false, because the only elements of $\{1, 2\}$ are $1$ and $2$, and the set $\{1\}$ is equal to neither of them: $\{1\} \neq 1$, because the set whose only element is $1$ is not to be confused with $1$, and $\{1\} \neq 2$.

Union, intersection and difference

Definition (operations on sets). The union of $A$ and $B$ is the set of the elements that belong to at least one of them; the intersection, the set of those that belong to both; and the difference $A \setminus B$, the set of those that belong to $A$ and not to $B$:

If $B \subseteq A$, the difference $A \setminus B$ is called the complement of $B$ relative to $A$. Two sets are disjoint when their intersection is empty.

Each operation translates a connective: union, disjunction; intersection, conjunction; difference, conjunction with a negation. If this is so, each logical law produces a law of sets: union and intersection are commutative, associative and distributive over each other because the connectives are, and all these laws are proved like the following theorem. The complement is always taken relative to a reference set, because a set of everything that is not in $B$ would rebuild Russell’s paradox.

The power set

The subsets of a set in turn form a set, whose existence was admitted at the beginning. The power set of $A$, denoted $\mathcal{P}(A)$, is the set whose elements are the subsets of $A$:

For example, the power set of $\{1, 2, 3\}$ has eight elements: the empty set, three sets with one element, three with two elements, and $\{1, 2, 3\}$ itself.

For every set $A$, the empty set and $A$ itself are elements of $\mathcal{P}(A)$, and for each $a$ in $A$ one has $\{a\} \in \mathcal{P}(A)$, whereas $a$ is not, in general, an element of $\mathcal{P}(A)$. The lesson on combinatorics will prove that a set with $n$ elements has $2^n$ subsets.

Ordered pairs and the Cartesian product

A point of the plane, a fraction or a subtraction yet to be carried out are described by two objects in a definite order: the pair $(3, 5)$ is not the pair $(5, 3)$. The set $\{3, 5\}$ cannot represent it, because it is equal to $\{5, 3\}$. All that is required of an ordered pair is its characteristic property: two pairs are equal if and only if they have the same first component and the same second component. Kuratowski observed in 1921 that the notion of set suffices to construct an object with that property.

Definition (ordered pair). The ordered pair with first component $a$ and second component $b$ is the set

Once the characteristic property is proved, Kuratowski’s construction can be forgotten: everything the course says about pairs follows from it.

Definition (Cartesian product). The Cartesian product of $A$ and $B$ is the set of the pairs whose first component belongs to $A$ and whose second component belongs to $B$:

The expression $\{ (a, b) : a \in A \wedge b \in B \}$ is not by itself one of the admitted rules, which only allow one to separate elements of a set already formed. However, that set exists: if $a \in A$ and $b \in B$, the sets $\{a\}$ and $\{a, b\}$ are contained in $A \cup B$, and are therefore elements of $\mathcal{P}(A \cup B)$; it follows that the pair $(a, b) = \{ \{a\}, \{a, b\} \}$ is contained in $\mathcal{P}(A \cup B)$, that is, it is an element of $\mathcal{P}(\mathcal{P}(A \cup B))$. Therefore the Cartesian product is formed by separation inside that set, which exists by the admitted rules: $A \cup B$ is the union of the elements of $\{A, B\}$, and the power set is taken twice.

The name recalls Descartes: the plane of analytic geometry is $\mathbb{R} \times \mathbb{R}$. The product is not commutative: $\{1\} \times \{2\}$ contains only $(1, 2)$, and $\{2\} \times \{1\}$ only $(2, 1)$, which is different by the characteristic property.

Relations

To say that $2$ divides $6$, that $3$ is less than $5$, or that two days fall on the same day of the week is to assert that certain pairs of objects are related. If this is so, a relation is determined by the pairs it relates, and it can be defined as a set of pairs.

Definition (relation). A relation from $A$ to $B$ is a subset $R$ of the product $A \times B$; a relation on $A$ is a relation from $A$ to $A$. If $(a, b) \in R$, one says that $a$ is related to $b$ by $R$.

For example, the relation “less than or equal to” on $\{1, 2, 3\}$ is the set of pairs $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. For frequently used relations one writes a symbol between the terms, as $a \leq b$ or $a \mid b$, instead of $(a, b) \in R$. Four properties of a relation on a set recur throughout the course.

Definition (properties of relations). A relation $R$ on $A$ is reflexive, symmetric, antisymmetric or transitive when it satisfies, respectively, the following conditions.

• It is reflexive if every element is related to itself: $(\forall a \in A)\,((a, a) \in R)$;
• It is symmetric if the relation of $a$ to $b$ implies that of $b$ to $a$: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$;
• It is antisymmetric if two elements related in both directions are equal: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$;
• It is transitive if the relation of $a$ to $b$ and that of $b$ to $c$ imply that of $a$ to $c$: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

On the grid of $A \times A$, a relation is a set of points. It is reflexive when it contains the whole diagonal, that of the pairs $(a, a)$; it is symmetric when its drawing is symmetric with respect to the diagonal; and it is antisymmetric when no point off the diagonal has its mirror image in the relation. Antisymmetric does not mean “not symmetric”: equality is both, and proposed problem 1 asks for a relation that is neither.

Equivalence relations

The relation “having the same parity” behaves like a partial equality: it identifies the numbers that agree in one respect, their parity, and forgets the rest. The three properties that make it behave in this way receive a name.

Definition (equivalence relation). A relation on $A$ is an equivalence relation when it is reflexive, symmetric and transitive. One then writes $a \sim b$, and says that $a$ is equivalent to $b$. The class of $a$ is the set of the elements equivalent to $a$, and each of them is a representative of the class:

The set of all the classes is called the quotient set and is denoted $A/{\sim}$.

Equivalence relations include equality, whose classes have a single element; same parity, with two classes; having the same remainder on division by $3$, with three; and falling on the same day of the week, with seven, which is solved problem 3. In general, if $g$ is a function defined on $A$, the relation $g(x) = g(y)$ inherits the three properties from equality, and solved problem 5 shows that every equivalence is of this form.

The classes therefore divide the set into blocks that do not overlap. This way of dividing a set deserves a definition of its own.

Definition (partition). A partition of a set $A$ is a set of subsets of $A$, called blocks, that are nonempty, pairwise disjoint and whose union is $A$; equivalently, each element of $A$ belongs to exactly one block.

Giving an equivalence on $A$ and giving a partition of $A$ are therefore two ways of saying the same thing; solved problem 4 takes advantage of this to count equivalences. The quotient set is the partition seen as a new set: on passing from $A$ to $A/{\sim}$, equivalent elements merge into a single one.

In the same way, in the lesson on the rational numbers two fractions $(p, q)$ and $(r, s)$ are equivalent when $ps = qr$, and a rational number is a class; and in the lesson on congruences, the residues modulo $n$ are the classes of an equivalence between integers.

Order relations

The divisibility of the previous example is not symmetric but antisymmetric: instead of identifying elements, it orders them. Relations of this kind receive a name of their own.

Definition (order). A relation on $A$ is an order relation, or partial order, when it is reflexive, antisymmetric and transitive; one then writes $a \preceq b$, and says that $a$ precedes $b$. The order is total when any two elements are comparable, that is, when for all $a$ and $b$ one has $a \preceq b$ or $b \preceq a$.

Examples of orders are the relation $\leq$ between natural numbers, which is total by the trichotomy proved in the lesson on the operations on natural numbers; inclusion, by the theorem on its properties, which is not total, because $\{1\}$ and $\{2\}$ are not comparable; and divisibility between natural numbers, whose antisymmetry is proved in the lesson on divisibility, which is not total, because neither $2 \mid 3$ nor $3 \mid 2$. A finite order is drawn with a Hasse diagram: one point per element, with $b$ higher than $a$ when $a$ precedes $b$, and a segment when there is no other element between them; transitivity allows the other segments to be omitted.

Definition (bounds and extreme elements). Let $\preceq$ be an order on $A$ and $X$ a subset of $A$. The bounds and the extreme elements of $X$ are defined as follows.

• An element $c$ of $A$ is a lower bound of $X$ if it precedes all the elements of $X$, and an upper bound if all the elements of $X$ precede it.
• A least element of $X$ is a lower bound of $X$ that belongs to $X$, and a greatest element is an upper bound that belongs to $X$.
• An element $m$ of $X$ is minimal if no element of $X$ other than itself precedes it, and maximal if it precedes no element of $X$ other than itself.
• The infimum of $X$ is the greatest element of the set of its lower bounds, and the supremum is the least element of the set of its upper bounds, when they exist.