Sets, Functions, Images and Preimages

Every definition of analysis is a sentence about sets and functions. “The supremum of $A$ is the least element of the set of upper bounds of $A$ .” “A function is continuous if the preimage of every open set is open.” Logic and Proof, Chapters 1 to 8 supplied the grammar of such sentences: the connectives, the quantifiers, and the prose that carries their rules. This chapter supplies the nouns: sets and subsets, unions and intersections of whole families of sets, ordered pairs and products, relations, functions, inverses, images and preimages. It is also where the logic of the first eight chapters becomes visible inside mathematics. Inclusion is a “for every” around an “implies”, a union is an “or”, the union of a family is a “there exists”, and a function is a “for every there exists exactly one”. The laws of sets are the laws of logic, read through membership, and the chapter uses this from its second section to its last.

Two surprises drive the chapter. The first is that the naive rule “any property defines a set” is contradictory (Russell’s paradox), so we must say which sets exist, and every set in this book is cut out of a set already given. The second is the chapter’s motivating problem. For $f(x) = x^2$ , is $f(A \cap B) = f(A) \cap f(B)$ ? Is $f^{-1}(C \cap D) = f^{-1}(C) \cap f^{-1}(D)$ ? Why is the second always true and the first not? The answer is a single quantifier: membership in an image hides a “there exists”, and membership in a preimage hides nothing. Preimages therefore respect every set operation, and images only unions. This asymmetry is why analysis defines continuity by preimages.

What you need. Logic and Proof, Chapters 1–8. From Logic and Proof, Chapters 1 and 2: the rules for the connectives and the derived laws used as rules, above all distributivity (Logic and Proof, Proposition 1.6.1), De Morgan’s laws (Logic and Proof, Proposition 2.5.5), an iff as two implications (Logic and Proof, Proposition 2.4.1), the contrapositive (Logic and Proof, Proposition 2.3.2), vacuous implication (Logic and Proof, Proposition 2.1.2), and derived rules (Logic and Proof, Definition 2.3.1). From Logic and Proof, Chapter 4: the standard equivalences (Logic and Proof, Proposition 4.5.1) and completeness (Logic and Proof, Theorem 4.8.4). From Logic and Proof, Chapters 5 and 6: the rules for “for every” and “there exists”, bounded quantifiers (Logic and Proof, Definition 5.1.1) and their rules (Logic and Proof, Proposition 6.1.1), the rules for equality (Logic and Proof, Definition 5.7.1), unique existence (Logic and Proof, Definition 5.8.1, Logic and Proof, Proposition 5.8.1), and the laws for negating quantifiers. From Logic and Proof, Chapter 8: plain-prose proofs, the convention on which steps may be silent, and the catalogue of what is not allowed. The number sets $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ , $\mathbb{R}$ are used as familiar sets, with their school arithmetic and order.

Time. About 35 hours on the core track (all of A, one B and one C per section, the exit checks); about 45 hours for everything.

Roadmap

Sets, subsets and Russell’s paradox. What a set is allowed to be, equality by elements, the subset relation and the element-chasing proofs that establish it, describing sets by a property cut out of an ambient set, the empty set, and why no set contains every set.
Unions, intersections, complements and families. The set operations as the connectives read through membership, the algebra of sets as propositional logic, power sets, unions and intersections of arbitrary families, and De Morgan’s laws for families, including the empty one.
Ordered pairs, products and relations. An object that remembers order, the product $A \times B$ and how it interacts with the set operations, and relations as sets of pairs.
Functions, composition, injections and surjections. A function as a graph with a declared target, when two functions are equal, composition, and the two questions of injectivity and surjectivity, with the squaring map as three different functions.
Left, right and two-sided inverses. A left inverse exists exactly for injective maps (on a nonempty domain), a right inverse forces surjectivity, bijections are the maps with a two-sided inverse, and the question whether every surjection has a right inverse, which needs a new principle.
Images and preimages. What a function does to sets, why preimages respect every operation and images only unions, where injectivity and surjectivity repair the failures, and sets of numbers such as $-A$ and $A + B$ as images.

Named moves

Element-chasing. To prove $A \subseteq B$ : “let $x \in A$ ”, unwind the definition of $A$ , and rewind into the definition of $B$ . To prove $A = B$ : two inclusions.
Unwind the image. “ $y \in f(A)$ ” means “there is $a \in A$ with $f(a) = y$ ”: name the witness before using it. A preimage has no witness to name.
Refute with a small witness. A two- or three-element set, the map $x \mapsto x^2$ , the empty set.
Build the inverse from the definition. For a left inverse, send $f(x)$ back to $x$ and everything else to one fixed point.