Mathematical Analysis 1. Lecture 1

About the course

This course does not replace the basic course of mathematical analysis taught at any mathematics faculty: it has twelve lectures, while the standard course is thirty lectures and thirty seminars. It is a supplement to the basic course, not a replacement for it.

The main learning happens through solving problems. A class goes like this: first the lecture, then the assistants accept problems from the problem sheets, in person only. There are no deadlines for the sheets; you can hand them in throughout the semester, so it is worth thinking about the problems anywhere, not only once a week. Even a problem you have not solved but have thought about does its job: learning the solution after that is not at all the same as learning it straight away. Try not to replace your own thinking with the internet, artificial intelligence or your neighbour; it is roughly the same thing.

Credit for the problem sheets: the bar is set optimistically at $80%$ of the boxes closed, in practice the boundary slides to $65$ – $70%$ ; there must be no empty sheets. Then a written exam at the beginning of December: $7$ – $10$ problems in four hours; if you have the sheet credit, the exam grade becomes the course grade.

If you cannot attend the lectures, read books.

Tip

V. A. Zorich. Mathematical Analysis, two volumes, you need both. An outstanding textbook; after each chapter there is a selection of problems, and whoever solves them all will know analysis better than many. At the beginning of the first volume there is also a list of the axioms of set theory.
S. M. Lvovski. Mathematical Analysis – a course given at the Independent University and published as a short, very concise book; with problems and sample IUM exams.
I. A. Vinogradova, S. N. Olekhnik, V. A. Sadovnichy. Problems and Exercises in Mathematical Analysis – a problem book, an edition after 2017. It differs from other collections in that each chapter is preceded by a brief summary of the theory and worked solutions of the main problems, including hard ones, so you can study from it on your own: read what you need to know, follow the worked solution with pen and paper, then take a similar problem and solve it yourself.
K. Kuratowski, A. Mostowski. Set Theory – for those interested in how set theory is built from axioms.

Sets

The exposition of analysis, like all of mathematics, rests on the language of set theory, so we start with sets and functions, almost from the very roots.

We do not know what a set is. The words "aggregate", "collection", "assemblage", "a gathering of objects called elements" are just many similar words, not a definition. We will define neither a set nor what can be an element of one. There is a set $A$ , there is an element $a$ , and there is the symbol $a \in A$ .

What we agree on at once: $a \in A$ is a statement. In any situation we encounter it must be possible to say whether it is true or false. If we find ourselves in a situation where this cannot be said, it contradicts our original agreement.

Definition (Subset, equality). $A \subset B$ if for every $a \in A$ we have $a \in B$ :

A \subset B ⟺ \forall a (a \in A \Rightarrow a \in B) .

$A = B$ if $A \subset B$ and $B \subset A$ .

The symbol $\subset$ is non-strict here: inclusion allows equality. If one needs to stress that the sets are not equal, one writes $A ⊊ B$ .

Definition (Empty set). The empty set $\emptyset$ is the set for which the statement $x \in \emptyset$ is always false, whatever is substituted for $x$ .

Whether such a set exists is not a question: in our game it exists. The word "nothing" is understood all-encompassingly. When at school people write " $x \in \emptyset$ " instead of "there are no roots", this is not a mistake, it is simply a statement that is false for all $x$ .

Two ways to specify a set

Listing: ${a, b, c}$ .
Specifying a property: ${x ∣ P (x)}$ : there is a statement $P$ involving the letter $x$ ; if it is true, $x$ is in the set, if false, it is not.

We use both ways in everyday life without thinking that these are sets: the list of students in the course is given by listing; "who attends the Independent University? People who love mathematics" is given by specifying a property. Everything seems natural, but difficulties arise on this path at once.

Russell's paradox

This difficulty was realised at the beginning of the twentieth century. Consider the set given by a property:

Y = {x ∣ x \in / x} .

For those who ask whether $x \in x$ ever happens at all: if it never does, so much the better: then the property is always true, and there is no problem with that. A set can perfectly well be an element of another set: say, ${1, {1, 2}}$ is a legitimate set given by listing.

Let us ask: is the statement $Y \in Y$ true?

If it is true, then $Y$ satisfies the property, that is, $Y \in / Y$ .
If it is false, then $Y \in / Y$ , so $Y$ satisfies the property and must lie in $Y$ .

We did nothing wrong (we introduced the set in the prescribed way) and landed exactly in the situation we agreed not to land in: we cannot say of the statement $Y \in Y$ whether it is true or false.

The cause of the paradox is universality: we wanted to consider all possible objects $x$ , and what "everything in the world" is, is not very clear. You will say: well, we do not need everything in the world, let us take only what is needed. But that is exactly how we define the things we need. The union

A \cup B = {x ∣ x \in A or x \in B}

has the same form: all possible $x$ for which something holds, and it is a priori no safer than the set $Y$ . And we use unions all the time. With intersection and difference there is no such problem: one can write

A \cap B = {x \in A ∣ x \in B}, A ∖ B = {x \in A ∣ x \in / B},

running not over all objects but only over the elements of $A$ . With the union you cannot wriggle out like that.

It is impossible to overcome this completely. What was done: the situation was reduced to a very small number of "unpleasant" rules, nine or ten axioms of set theory depending on the formulation (their list is at the beginning of Zorich's book). All sets are built according to these axioms. If a paradox comes up in the mathematics we study, one can go back along the chain: if it is not our own mistake, the chain will run into one of the few rules, and it will become clear where universality must be reduced. Whether there are other paradoxes, science does not know: this can be neither proved nor disproved; it is tested by life.

Remark. Of the axioms that genuinely create something "out of nowhere", there are only a few: the axiom of pairing, the axiom of union, the power set axiom (the set of all subsets) and the axiom of infinity. Separating by a property is allowed, but only inside a set that already exists. Below, after the Cantor–Bernstein and Cantor theorems, we will see how this rule saves us from Russell's paradox.

The ordered pair and the Cartesian product

To discuss functions as well as sets, we need one more operation, and for it the notion of an ordered pair. Simply put, it is a collection of two elements where it is said which is first and which is second. But we have just left the set itself undefined, and we do not want to introduce "first" and "second" as well (that is, the numbers $1$ and $2$ , which we do not have yet). Specialists came up with a way out.

Definition (Kuratowski's ordered pair).

(x, y) = {{x}, {x, y}} .

Exercise. Check that if $(x, y) = (a, b)$ , then $x = a$ and $y = b$ . That is what orderedness consists in: two such sets are equal not only when their contents are the same, but precisely when $x$ equals $a$ and $y$ equals $b$ . A good case-by-case exercise for anyone who wants to check whether they understand what "two sets are equal" means.

Definition (Cartesian product).

X \times Y = {(x, y) ∣ x \in X, y \in Y} .

How should one picture it? It is a table: the $x$ 's are laid out along one side, the $y$ 's along the other, and the pairs $(x, y)$ stand in the cells. Anyone who has seen the Cartesian coordinate system in the plane has visualised the Cartesian product of two lines as a plane.

Example (visualising products). A problem calling for a creative approach: any reasonable, natural visualisation will do: a geometric object given by two parameters, one of which runs over the first set and the other over the second.

Line $\times$ segment – an infinite strip.
Line $\times$ circle – a cylinder.
Circle $\times$ circle – a torus.
A sphere is not a Cartesian product in the natural sense.

If you match sets bijectively (a segment is in bijection with a line), then any continuum will depict anything, so we mean visual interpretations. Behind all these pictures stands one and the same thing, the table.

Functions

The Cartesian product is needed to introduce the second main character of the story. The first character is the set; the second, to which the first semester of analysis is mainly devoted, is the function.

At school (and in the nineteenth century) people said: a function is a rule, a law, a correspondence that assigns to each $x \in X$ a unique $y \in Y$ , denoted $f (x)$ . A function comes with its graph

Γ_{f} = {(x, y) \in X \times Y ∣ y = f (x)} .

A subset appears in the Cartesian product, but not an arbitrary one. The substantive part of the school phrase is the words "each" and "unique", and in the language of sets it is written like this:

\forall x \in X \exists! y \in Y : (x, y) \in Γ.

The graph of a function is when above each $x$ there is exactly one $y$ . A good idea arises: not to multiply words but to say exactly that.

Definition (Function). A function $f : X \to Y$ is a subset $Γ \subset X \times Y$ such that for each $x \in X$ there is exactly one $y \in Y$ for which $(x, y) \in Γ$ . The notation $y = f (x)$ is nothing but another way of writing that $(x, y) \in Γ$ .

TikZ diagram — A function as a subset $Γ \subset X \times Y$ : the vertical line above each point $x \in X$ meets $Γ$ exactly once.

This is great from the point of view of the definition: we did not multiply entities, nothing but sets was needed. And it is great from the point of view of understanding: unlike our distant ancestors, for us there is no difference between "the dependence of $y$ on $x$ ", a formula by which $y$ is computed, and a picture with a curve drawn. We pass easily from one to the other, and very often the geometric visualisation matters more than the formula.

Subsets of a Cartesian product are called relations, so a function is also called a functional relation.

Remark (functions of several variables). And where is "one variable" here? Who $X$ is has not been said; it can be anything, even $R^{10}$ . A function of ten variables is a function $R^{10} \to R$ ; the variables are just an encoding of the point $x$ , no more and no less. That is the beauty of the abstract language, often criticised for being detached from examples: having learned the definition of a function once, you know what a function of any number of variables is.

Composition

Introducing an object is not enough; one has to do something with it. The most important operation on functions is composition: a way of making some functions out of others.

Definition (Composition). If $f : X \to Y$ and $g : Y \to Z$ , then the function $g \circ f : X \to Z$ is defined,

(g \circ f) (x) = g (f (x)) .

In the language of graphs:

Γ_{g \circ f} = {(x, z) \in X \times Z ∣ \exists y \in Y : (x, y) \in Γ_{f}, (y, z) \in Γ_{g}} .

It looks like scholasticism, but it is literally how one builds the graph of a composition by hand: draw the graph of $f$ separately and the graph of $g$ separately, take $x$ , see how $y$ changes, and then from this $y$ see how $z$ changes. Drawing graphs by hand is a useful exercise, although a machine does it better than you: that is how you understand how functions work.

Theorem (Associativity of composition).

h \circ (g \circ f) = (h \circ g) \circ f .

Proof. Feed in $x$ and unfold the definitions:

(h \circ (g \circ f)) (x) = h ((g \circ f) (x)) = h (g (f (x))),

((h \circ g) \circ f) (x) = (h \circ g) (f (x)) = h (g (f (x))) .

The results are the same.

This proof is very clear, but unsatisfactory. Are you not left uneasy that the proof came down to two expressions coinciding letter by letter? One can "prove" a lot of things are "the same" that way. In fact we should have proved that the graph of the left-hand side coincides with the graph of the right-hand side.

Exercise. Carry out the proof in the language of graphs and see where exactly the proof happens. Writing out both sides, you will get two logical formulas with the quantifier "there exists $y$ such that …, and there exists $z$ such that …", which will look different on the surface: the brackets and quantifiers are placed differently. The moment of proof is checking that rewriting the formula does not change its truth, that is, comparing truth tables.

Remark. The same applies to the rules of operations on sets: De Morgan's laws, distributivity $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and the rest. Anyone who proved them with Euler circles, or glanced at a rigorous proof in passing, surely remembers the feeling "a strange proof: we wrote the same sentence twice, and it got proved". It could not have been so. At that moment two statements arose, and the truth of one must be honestly derived from the truth of the other. At the initial stage it is useful to do this; it is a bit tedious, so we will not do it on the board; for everyday life the proof above is enough.

Injections, surjections, bijections

There are no functions "on their own"; we always single out subclasses among them.

Definition (Injection, surjection, bijection). A function $f : X \to Y$ is called

an injection if for all $x_{1}, x_{2} \in X$ , $x_{1} \neq = x_{2}$ implies $f (x_{1}) \neq = f (x_{2})$ ;
a surjection if for every $y \in Y$ there is an $x \in X$ such that $y = f (x)$ ;
a bijection if $f$ is an injection and a surjection.

This is easy to remember. An injection is an embedding: points do not get glued together, $X$ is copied into $Y$ as it is, all the dots are preserved. A surjection is a covering, a laying over: the images of the points of $X$ have covered all of $Y$ . A bijection is both: the points of $X$ and $Y$ are lined up against each other, "wall against wall". A synonym: one-to-one correspondence. This is our first way of saying that two sets are "the same": one can rehang the labels and get one set from the other.

Why, you might think, invent these notions to burden you? It turns out one cannot do without them.

Theorem (On the inverse function). If $f : X \to Y$ is a bijection, then the rule assigning to each $y \in Y$ the $x \in X$ such that $y = f (x)$ is a function from $Y$ to $X$ . This function is denoted $f^{- 1}$ , called the inverse, and is a bijection.

Proof. For the inverse correspondence to be a function, we need such an $x$ to exist for each $y$ (true, since $f$ is a surjection) and to be unique (true, since $f$ is an injection): $y$ cannot "grow" out of two different $x$ 's.

Why is $f^{- 1}$ a bijection? It cannot glue two $y$ 's together: then two $y$ 's would grow out of one $x$ , while $f$ is a function. It is surjective: each $x$ has $y = f (x)$ corresponding to it.

Note that every "since" here is in fact "if and only if". If we want to get a function again after reversing all the arrows, injectivity and surjectivity are necessary. The words "function" and "bijection" turn out to be reflections of each other: being a bijection for $f$ is the same as being a function for the inverse correspondence; being a function for $f$ is the same as being a bijection for the inverse.

Example (inverse functions from school). That is how inverse functions were born at school. $x^{2}$ is not injective: we kept the injective branch on $[0, + \infty)$ , which is a bijection onto $[0, + \infty)$ , and took the inverse: the arithmetic $x$ . The sine itself is bad: we kept the piece on $[- π /2, π /2]$ , which is a bijection onto $[- 1, 1]$ , and got the arcsine. A full-fledged inverse function (rather than a "right inverse" or "left inverse" in some tricky sense) is built only for a bijection, because these are synonyms.

Groups and bijections

To realise another role of bijections, we need general algebraic definitions.

Definition (Set with an operation, group). $M$ is a set with an operation $*$ if a function $* : M \times M \to M$ is given, that is, to a pair of elements $(a, \tilde{a})$ an element $a * \tilde{a} \in M$ is functionally assigned, any element at all, even all pairs to one element.

A set with an operation $(M, *)$ is called a group if

the operation is associative: $(a * b) * c = a * (b * c)$ ;
there is an identity $e \in M$ : $e * a = a * e = a$ for all $a$ ;
for each $a \in M$ there is an inverse $a^{- 1}$ : $a * a^{- 1} = a^{- 1} * a = e$ .

Why was the group invented? To solve equations, the very first equation your schoolteacher taught you to solve. To find $x$ from $5 x = 10$ , you have to multiply by the inverse of five, rearrange the brackets (associativity), know that $5^{- 1} \cdot 5$ gives one and that multiplying by it changes nothing. Strange as it may seem, these are exactly the properties from the definition, and only they: the minimum needed to solve equations.

Example (groups). $(Z, +)$ ; $(Q ∖ {0}, \cdot)$ ; the group of motions of the plane, bijective transformations preserving distance, one of the most important groups in geometry; permutations. Very often the elements of a group are perceived as acting on some set: permutations permute elements, motions move the points of the plane. It turns out that one can always think this way; we are coming to that now.

Definition (Subgroup, isomorphism). $N \subset M$ is a subgroup if $N$ is itself a group with respect to the same operation.

Groups $(M_{1}, *_{1})$ and $(M_{2}, *_{2})$ are isomorphic if there is a bijection $f : M_{1} \to M_{2}$ preserving the operation:

f (x *_{1} y) = f (x) *_{2} f (y) .

Isomorphic groups differ only in the names of their elements. The symmetry group of the regular triangle and the group of permutations of three elements differ only visually: every symmetry of the triangle is a permutation of its vertices, and that is all.

Example (the group of bijections). The most important example of a group:

Bij (X) = {f : X \to X ∣ f is a bijection}

with the operation of composition. Composition is associative (proved above); the identity is the identity map $id_{X}$ , $x \mapsto x$ ; each bijection has an inverse, which together with it puts $X$ back in place. This group looks exactly like an action: the elements are moved somewhere, then another action is applied, and the operation is the composition of actions. This is an analogue of the group of motions of the plane.

Theorem (On embedding a group into the group of bijections). Every group $(X, *)$ is isomorphic to a subgroup of the group of bijections $Bij (X)$ .

That is, every group can be thought of as an action on some set, in this case on itself. How can $(Z, +)$ be represented by bijections? Assign to each $a \in Z$ the shift $x \mapsto x + a$ . In the general case it is done in exactly the same way: the theorem is monumental, and the proof is very simple.

Proof. Assign to an element $z \in X$ the map

f_{z} : X \to X, f_{z} (x) = z * x .

$f_{z}$ is a bijection. Injection: if $z * x_{1} = z * x_{2}$ , then multiplying on the left by $z^{- 1}$ we cancel and get $x_{1} = x_{2}$ . Surjection: the equation $z * x = y$ is solvable: $x = z^{- 1} * y$ ; that is what a group is for.

The assignment $z \mapsto f_{z}$ is injective. At which $x$ do different $f_{z_{1}}$ and $f_{z_{2}}$ differ? At the identity: $f_{z} (e) = z$ , so different $z$ 's correspond to maps with different values at the point $e$ .

The operation is preserved. We need to compute the composition:

f_{z_{1} * z_{2}} (x) = (z_{1} * z_{2}) * x = z_{1} * (z_{2} * x) = f_{z_{1}} (f_{z_{2}} (x)) = (f_{z_{1}} \circ f_{z_{2}}) (x),

and here the associativity from the definition of a group works for us. The product of elements has gone to the composition of the corresponding maps.

Surjectivity onto all bijections need not and cannot be checked: the image need not be all of $Bij (X)$ . But since the operation is preserved, the image ${f_{z}}$ is closed under composition, contains $f_{e} = id_{X}$ , and together with $f_{z}$ contains $f_{z^{- 1}} = f_{z}^{- 1}$ , that is, it is a subgroup, and $z \mapsto f_{z}$ is an isomorphism onto it.

A simple observation, but it gives another view of the role of bijections: they are interesting not only as a way of comparing sets but also as objects in their own right: they provide a universal group into which any group, however tricky, embeds. This is where we meet algebra, which you are studying in parallel.

Equinumerosity

Let us come back down to earth from the heights, to the story of comparing sets.

Definition (Equinumerosity). $A$ is equinumerous with $B$ (we write $A \sim B$ ) if there is a bijection $f : A \to B$ .

Obvious properties:

$A \sim A$ : the identity bijection.
If $A \sim B$ , then $B \sim A$ : this is again the inverse function theorem: the inverse of a bijection is a bijection. The original definition is asymmetric (it says from where and to where), and purely formally equinumerosity seems an asymmetric notion; remarkably, it is not.
If $A \sim B$ and $B \sim C$ , then $A \sim C$ : a composition of bijections is a bijection.

Exercise. A composition of bijections is a bijection. Injection: the first map did not glue anything, different $x$ 's went to different $y$ 's; the second did not glue anything, different $y$ 's went to different $z$ 's. Surjection: each $z$ has a $y$ it came from, and each $y$ has an $x$ ; so $z$ came from that $x$ .

Remark. Do not invoke cardinalities in vain. "Equinumerous" is fine. But if you start calculating with cardinals, you must know how to do it: this is again on the edge of axiomatics, and it is very easy to get into trouble over what is meant by this or that word. We will not do it. We always appeal to two given sets: is there a bijection between them or not.

Subsets and two-valued functions

For the set of functions from $X$ to $Y$ the notation $Y^{X}$ is often used. Why exactly a power, and why $Y$ is the base and $X$ the exponent and not the other way round, think about at leisure; it is easy to understand on finite sets. The set of all subsets of $X$ is denoted $2^{X}$ and called the power set. The two here is a shorthand for the set ${0, 1}$ , and it will now become clear why.

Definition (Indicator). The indicator of a subset $A \subset X$ is the function $1_{A} : X \to {0, 1}$ ,

1_{A} (x) = {1, 0, x \in A, x \in / A .

Theorem. The assignment $A \mapsto 1_{A}$ is a bijection between $2^{X}$ and ${0, 1}^{X}$ .

Proof. Injection: if $A \neq = B$ , there is an element that lies in one set and not in the other; at it one indicator equals $1$ and the other $0$ . Surjection: any function $f : X \to {0, 1}$ is an indicator, namely of the set ${x ∣ f (x) = 1}$ : where $f$ equals $1$ , the indicator equals $1$ , where $0$ , it equals $0$ , and there are no other values.

Talking about two-valued functions and talking about subsets is one and the same. It is a way of encoding: a subset of a finite set ${1, \dots, n}$ or of the natural numbers is naturally encoded by a sequence of zeros and ones (one if we take the element, zero if not), and it turns out that one can always do this.

Indicators themselves are an extremely useful thing. Using only addition and multiplication (without maxima or absolute values):

1_{A \cap B} = 1_{A} 1_{B}, 1_{A \cup B} = 1_{A} + 1_{B} - 1_{A} 1_{B}, 1_{A ∖ B} = 1_{A} (1 - 1_{B}) .

In the union the extra one that arises when a point lies in both sets has to be subtracted.

Remark. All the rules of operations on sets are conveniently checked with indicators: instead of logic and comparing truth tables you get an ordinary transformation of an algebraic expression. Anyone who has done combinatorics knows: split everything into sets, write down the indicators, and from there it is arithmetic; no ingenuity is required.

The Cantor–Bernstein theorem

Everything above was a prelude. Now two powerful statements about equinumerous sets, which do not yet take us into any astral heights; naive theorems.

Theorem (Cantor–Bernstein). If $A$ is equinumerous with some subset of $B$ , and $B$ is equinumerous with some subset of $A$ , then $A \sim B$ .

As long as we are in the naive theory and do not use Zermelo's theorem and Zorn's lemma, this is perhaps the most powerful tool for proving that sets are equinumerous. There are many proofs; here we give a less popular and not the simplest one, but they all begin in roughly the same way.

Proof. Reduction to three nested sets. Let $f : A \to B^{'}$ and $g : B \to A^{'}$ be bijections, $B^{'} \subset B$ , $A^{'} \subset A$ . Go through both: $A$ went onto $B^{'}$ , and then $g$ carried $B^{'}$ into the subset $g (B^{'}) \subset g (B) = A^{'}$ . Put

A_{0} = A, A_{1} = A^{'}, A_{2} = g (f (A)) = g (B^{'}), A_{0} \supset A_{1} \supset A_{2},

and $F = g \circ f$ is a bijection of $A_{0}$ onto $A_{2}$ . The hypothesis has reduced to a more laconic picture: the set $A_{1}$ is squeezed between $A_{0}$ and $A_{2}$ , and the outer two are equinumerous. It is enough to prove that $A_{0} \sim A_{1}$ : then $A = A_{0} \sim A_{1} = A^{'} \sim B$ .

What is the problem? The gap $A_{0} ∖ A_{1}$ : how to squeeze the bigger set into the smaller one, where to put the gap? Every proof, whichever you study, revolves around where to hide this set.

Good sets. Call $M \subset A_{0}$ good if

M \supset (A_{0} ∖ A_{1}) \cup F (M),

that is, $M$ contains the gap and its own image under $F$ . Good sets exist: for example, all of $A_{0}$ . Put

M = X good ⋂ X .

$M$ is good. Every good $X$ contains the gap, so the intersection contains the gap too. Further, $M \subset X$ for every good $X$ , so $F (M) \subset F (X) \subset X$ : the image of $M$ lies in every good $X$ , and hence $F (M) \subset M$ .

The key equality:

M = (A_{0} ∖ A_{1}) \cup F (M) .

The inclusion $\supset$ is the goodness of $M$ . Suppose it is strict: there is $z \in M$ not lying in $(A_{0} ∖ A_{1}) \cup F (M)$ . Then $M ∖ {z}$ is also good: the gap is still in it, since $z$ is not from the gap; and $F (M ∖ {z}) \subset F (M) \subset M ∖ {z}$ , since $z \in / F (M)$ . We have a good set strictly smaller than $M$ , while $M$ is already the smallest, we have intersected all the good ones. A contradiction.

What is special about $M$ : it hides the gap. The image $F (M)$ lies in $A_{2}$ and does not meet the gap, so when $F$ is applied, exactly the gap disappears from $M$ , and only it.

The bijection. Write

A_{0} = M ⊔ (A_{0} ∖ M), A_{1} = F (M) ⊔ (A_{1} ∖ F (M)) .

Throw $M$ out of $A_{0}$ : the gap and $F (M)$ go away, and $A_{1} ∖ F (M)$ remains. That is,

A_{0} ∖ M = A_{1} ∖ F (M) .

Now on $M$ we act by the bijection $F$ (it takes $M$ onto $F (M)$ ), and on $A_{0} ∖ M$ we act by the identity. The pieces do not intersect and cover everything, so this is a bijection of $A_{0}$ onto $A_{1}$ .

Remark. The argument bends the brain a little, but it uses neither the natural numbers nor countable infinity; it is a purely set-theoretic and relatively short proof; what saved us was the ability to intersect. Many have seen another, hypnotic proof in which the bijection is iterated and a countable family of rings is drawn, with the core treated separately. A good exercise for those who have seen it: find the set $M$ in that picture. It is there.

Cantor's theorem

The second most important theorem, which lets us understand what happens with sets that are not equinumerous. The result is in a sense negative.

Theorem (Cantor). $2^{X}$ is not equinumerous with $X$ .

Since $2^{X} \sim {0, 1}^{X}$ , it does not matter which of them we prove it for: also ${0, 1}^{X} \neq \sim X$ . Let us go through both proofs; both are short.

Proof. Via two-valued functions. Suppose ${0, 1}^{X} \sim X$ : to each $z \in X$ a function $f_{z} : X \to {0, 1}$ is assigned, and this is a bijection. Construct a new function by the rule

g (x) = 1 - f_{x} (x) .

Since $f_{x} (x)$ takes only the values $0$ and $1$ , $g$ is also a two-valued function. Since there is a bijection, $g = f_{z}$ for some $z$ . Then $f_{z} (x) = 1 - f_{x} (x)$ for all $x$ ; substitute $x = z$ :

f_{z} (z) = 1 - f_{z} (z), f_{z} (z) = \frac{1}{2},

and how is that $0$ or $1$ ? A contradiction.

Three lines, seemingly very simple, but with a trick, with a sleight of hand: this is Cantor's diagonal procedure, highly abstracted, the argument that sequences of zeros and ones are uncountable brought to laconic form.

Proof. In the language of sets. Let $F : X \to 2^{X}$ be a bijection: to each $z \in X$ corresponds a subset $F (z) \subset X$ . Make the set

Y = {x \in X ∣ x \in / F (x)}

A whiff of the beginning of the lecture. This is a subset of $X$ , perhaps empty, perhaps all of $X$ ; it does not matter. Since $F$ is a bijection, $Y = F (y)$ for some $y \in X$ . Does $y$ lie in $F (y)$ ? The same problems begin: if it lies there, it does not; if it does not, it does. But this is no longer a paradox, it is a contradiction: there is no such $y$ , and so there was no bijection. It is the assumption that is wrong, not the structure of the world.

Which of the two proofs is more intuitively clear, decide for yourselves.

Consequences: why Russell's paradox does not come back

From the Cantor–Bernstein and Cantor theorems one can derive that, if the axioms are followed correctly, problems like Russell's paradox do not arise. Let us trace this.

Theorem. There is no set of all sets.

Proof. Suppose the contrary: $M$ is the set of all sets. Then all subsets of $M$ are also sets, that is, $2^{M} \subset M$ . An inclusion always gives an injection, the identity map $2^{M} \to M$ . On the other hand, there is always an injection $M \to 2^{M}$ , $m \mapsto {m}$ . An injection is a bijection onto its image, so by the Cantor–Bernstein theorem $M \sim 2^{M}$ , and by Cantor's theorem this is impossible.

The two theorems forbid us to say that "everything in the world" is a set. Fine, you will say, you cannot take everything in the world. In set theory the rule is: separating by a property is allowed, but only inside a set. Was universality the only problem in Russell's paradox? Take some set $A$ and try to create the paradox inside it:

Y = {x \in A ∣ x \in / x} .

How the paradox was built: we check whether $Y$ lies in $Y$ .

If $Y \in Y$ , then $Y \in A$ and $Y \in / Y$ ; there is a smell of burning, a contradiction. So $Y \in / Y$ .
$Y \in / Y$ means that the condition " $Y \in A$ and $Y \in / Y$ " fails, that is, $Y \in / A$ or $Y \in Y$ . The second has already been rejected, so $Y \in / A$ remains.

No paradox happened: the possibility appeared that the set we built simply jumped outside $A$ . The situation is saved.

Remark. There is no hundred percent certainty that paradoxes will not appear later. But the rules are few: a finite list of axioms, and those that really create sets out of nowhere (pairing, union, power set, infinity) can be counted on the fingers of one hand, and if we follow them, then at least the original paradoxes and all-encompassing objects do not arise.

What comes next

Today we talked about sets, functions, bijections and the two main theorems on equinumerosity, Cantor's and Cantor–Bernstein's. Next time, two more abstract notions: order relations and equivalence relations; more about the natural, integer and rational numbers; and, as the cherry on the cake after the natural numbers, well-ordered sets and transfinite induction, that is, how relatively hard problems of set theory are solved.

Related works