List of results

Theorems and lemmas 78 Definitions 43 Examples 39 Exercises 124

Sets, Functions, Images and Preimages

1.1 Sets, Subsets and Russell's Paradox

Definition 1.1.1 Equality of Sets
Definition 1.1.2 Subset
Example Three inclusions
Proposition 1.1.1 Equality Is Two Inclusions
Proposition 1.1.2 Inclusion Is Transitive
Definition 1.1.3 Specification
Definition 1.1.4 Empty Set
Proposition 1.1.3 The Empty Set Is Unique
Example Computing sets given by a property
Theorem 1.1.4 Russell’s Theorem
Exercise A1
Exercise B1: A set given by an equation
Exercise B2: A subset of the empty set
Exercise B3: Equal or not?
Exercise C1: Every set has something outside it
Exercise C2: Antisymmetry for sets of sets

1.2 Unions, Intersections, Complements and Families

Definition 1.2.1 Union, Intersection, Difference
Theorem 1.2.1 Algebra of Sets
Definition 1.2.2 Power Set
Example Small power sets
Definition 1.2.3 Indexed Family
Definition 1.2.4 Union and Intersection of a Family
Proposition 1.2.2 Smallest Closed Set
Example Unions and intersections of intervals
Theorem 1.2.3 De Morgan’s Laws for Families
Exercise A1
Exercise B1: Intersection and difference
Exercise B2: Three families of intervals
Exercise B3: Canceling a union
Exercise C1: Power sets and operations
Exercise C2: Find the error

1.3 Ordered Pairs, Products and Relations

Definition 1.3.1 Ordered pair
Example Solving an equation between pairs
Definition 1.3.2 Cartesian product
Example Products, small and large
Proposition 1.3.1 Products and Set Operations
Example Two rectangles
Definition 1.3.3 Relation
Example Relations as sets of pairs
Exercise A1
Exercise B1: An L-shaped region
Exercise B2: The intersection law, written with two pairs
Exercise B3: Two products crossed
Exercise C1: The square of a union
Exercise C2: When one inclusion forces equality

1.4 Functions, Composition, Injections and Surjections

Definition 1.4.1 Function
Example First functions
Example Relations that are not functions
Proposition 1.4.1 Equality of Functions
Example Equal and unequal functions
Example All functions between two small sets
Proposition 1.4.2 Functions and the Empty Set
Definition 1.4.2 Composition
Example The order of composition matters
Proposition 1.4.3 Composition Is Associative
Definition 1.4.3 Injective
Definition 1.4.4 Surjective
Definition 1.4.5 Bijective
Example Deciding injective and surjective
Example Squaring, three ways
Theorem 1.4.4 Composites of Injections and Surjections
Exercise A1
Exercise B1: Five functions
Exercise B2: Put the proof in order
Exercise B3: Examples on the natural numbers
Exercise C1: Exit check: composites
Exercise C2: When the composite is a bijection

1.5 Left, Right and Two-Sided Inverses

Definition 1.5.1 Left and Right Inverses
Example Left inverses on small sets
Theorem 1.5.1 Left Inverses and Injectivity
Example Running the construction
Proposition 1.5.2 Right Inverses Give Surjectivity
Example All right inverses of a small surjection
Proposition 1.5.3 Left and Right Inverses Agree
Definition 1.5.2 Inverse Function
Example Inverses found and checked
Theorem 1.5.4 Bijections Are the Invertible Functions
Exercise A1
Exercise B1: Counting one-sided inverses
Exercise B2: The inverse of a composite
Exercise B3: A bijection between an interval and the line
Exercise C1: One composite equal to the identity
Exercise C2: When is a left inverse unique?

1.6 Images and Preimages

Definition 1.6.1 Image
Definition 1.6.2 Preimage
Example Images and preimages by listing
Example Images and preimages of intervals under squaring
Example Reflections, scalings and sums as images
Theorem 1.6.1 Preimages of Set Operations
Proposition 1.6.2 Preimage under a Composite
Theorem 1.6.3 Image of a Union
Example Two witnesses under one name
Theorem 1.6.4 Image of an Intersection
Proposition 1.6.5 Image and Preimage Round Trips
Exercise A1
Exercise B1: Computing images and preimages
Exercise B2: Two laws, element by element
Exercise B3: The two readings of the inverse
Exercise C1: Images and differences
Exercise C2: Find the error
Exercise C3: Exit check: preimages
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Equivalence Relations, Orders, and Induction

2.1 The Natural Numbers and Well-Ordering

Lemma 2.1.1 Arithmetic of the Natural Numbers
Example An induction that ignores its hypothesis
Proposition 2.1.2 Arithmetic of the Integers
Theorem 2.1.3 Well-Ordering of the Natural Numbers
Theorem 2.1.4 Induction Is Equivalent to Well-Ordering
Corollary 2.1.5 Well-Ordering of Sets of Integers
Exercise A1
Exercise B1
Exercise B2: Putting a proof in order
Exercise B3
Exercise C1: A greatest element from a least upper bound
Exercise C2: A well-ordered set with gaps

2.2 Induction, Strong Induction and the Smallest Counterexample

Theorem 2.2.1 Induction from a Base
Theorem 2.2.2 Strong Induction from a Base
Definition 2.2.1 Divisibility
Definition 2.2.2 Prime Number
Theorem 2.2.3 Division Algorithm
Lemma 2.2.4 Lowest Terms, Up to Factors of Two
Theorem 2.2.5 Every Integer at Least Two Has a Prime Factor
Example All Numbers Are Equal
Exercise A1
Exercise B1
Exercise B2: Products of primes
Exercise B3
Exercise C1: Exit check: a flawed induction
Exercise C2: Lowest terms
Exercise C3: Smallest, not largest

2.3 Definition by Recursion

Theorem 2.3.1 Recursion Theorem
Corollary 2.3.2 Recursion from a Base
Corollary 2.3.3 Two-Step Recursion
Definition 2.3.1 Finite Sums and Products
Definition 2.3.2 Powers
Proposition 2.3.4 Laws of Powers
Proposition 2.3.5 Sum of the First Natural Numbers
Proposition 2.3.6 Geometric Sum
Theorem 2.3.7 Bernoulli’s Inequality
Proposition 2.3.8 Finite Sets Have a Maximum
Example Proving more to prove anything
Exercise A1
Exercise B1: Sum of cubes
Exercise B2: Starting at the right place
Exercise B3: A closed form
Exercise C1: Powers of two
Exercise C2: Bernoulli beyond its hypothesis
Exercise C3: Two identities at once

2.4 Properties of Relations

Definition 2.4.1 Properties of a Relation
Proposition 2.4.1 Divisibility on the Natural Numbers
Example Eight relations, four properties
Exercise A1
Exercise B1: Five relations
Exercise B2: Example generation
Exercise B3: Intersections and unions
Exercise C1: Properties as equations between sets
Exercise C2: What symmetry and transitivity do give

2.5 Equivalence Relations and Partitions

Definition 2.5.1 Equivalence Relation
Example Four equivalence relations
Definition 2.5.2 Equivalence Class
Definition 2.5.3 Partition
Definition 2.5.4 Quotient Set
Theorem 2.5.1 Equivalence Classes Partition the Set
Theorem 2.5.2 Partitions and Equivalence Relations Correspond
Definition 2.5.5 Congruence Modulo n
Proposition 2.5.3 Congruence Is an Equivalence Relation
Proposition 2.5.4 The Integers Modulo n
Example The fibers of a function
Example The reals modulo the integers
Proposition 2.5.5 Congruence Respects Sums and Products
Example A rule on classes that is not a function
Exercise A1
Exercise B1: Fractions as classes
Exercise B2: Computing in Z/7
Exercise B3: Which rules are well defined?
Exercise C1: Exit check: classes partition
Exercise C2: Find the error

2.6 Partial Orders, Maximal and Greatest Elements

Definition 2.6.1 Partial Order
Example Inclusion is a partial order, rarely total
Definition 2.6.2 Upper and Lower Bounds
Definition 2.6.3 Greatest and Least Elements
Definition 2.6.4 Maximal and Minimal Elements
Proposition 2.6.1 Greatest and Least Elements Are Unique
Proposition 2.6.2 Greatest and Maximal Elements
Example Maximal elements that are not greatest
Definition 2.6.5 Supremum and Infimum
Example The supremum under divisibility is the least common multiple
Definition 2.6.6 Well-Ordered Set
Exercise A1
Exercise B1: Suprema of families of sets
Exercise B2: Two maximal elements and a least one
Exercise B3: Minimal is least in a total order
Exercise C1: A well-order that is not like N
Exercise C2: Infima and suprema under divisibility
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Cardinality: Countable and Uncountable Sets

3.1 Equinumerous Sets and Finite Sets

Definition 3.1.1 Equinumerous Sets
Proposition 3.1.1 Equinumerosity Is Reflexive, Symmetric and Transitive
Definition 3.1.2 Finite Set, Number of Elements
Definition 3.1.3 Infinite Set
Theorem 3.1.2 Pigeonhole Principle
Corollary 3.1.3 Pigeonhole for Finite Sets
Corollary 3.1.4 The Number of Elements Is Unique
Proposition 3.1.5 Disjoint Unions
Proposition 3.1.6 Subsets of Finite Sets
Corollary 3.1.7 Removing a Point
Proposition 3.1.8 Counting Subsets
Theorem 3.1.9 A Finite Set Has No Proper Copy
Example Hilbert’s Hotel
Exercise A1
Exercise B1: Moving the guests
Exercise B2: Choosing the holes
Exercise B3: Finite unions
Exercise C1: Infinite means arbitrarily large finite pieces
Exercise C2: Counting products and functions

3.2 Countable Sets

Definition 3.2.1 Countable Set
Definition 3.2.2 Countably Infinite Set
Lemma 3.2.1 Subsets of the Natural Numbers
Theorem 3.2.2 Characterizations of Countable Sets
Proposition 3.2.3 Subsets of Countable Sets
Proposition 3.2.4 Images of Countable Sets
Proposition 3.2.5 Union of Two Countable Sets
Example Listing the rows one after another
Theorem 3.2.6 The Plane of Natural Numbers Is Countable
Corollary 3.2.7 Products of Countable Sets
Theorem 3.2.8 The Integers and the Rationals Are Countable
Exercise A1
Exercise B1
Exercise B2: Putting a proof in order
Exercise B3: A surjection by formula
Exercise C1: Finite subsets of the natural numbers
Exercise C2: Find the error

3.3 Countable Unions and the Axiom of Choice

Axiom 3.3.1 Axiom of Choice
Theorem 3.3.2 Surjections Have Right Inverses
Theorem 3.3.3 Countable Unions of Countable Sets
Example Unions that come with their lists
Theorem 3.3.4 The Algebraic Numbers Are Countable
Exercise A1
Exercise B1: Which constructions need choice?
Exercise B2: Finite sequences
Exercise B3
Exercise C1: Exit check: countable unions
Exercise C2: Algebraic numbers without choice
Exercise C3: Finite unions

3.4 Diagonal Arguments: Uncountable Sets and Cantor's Theorem

Theorem 3.4.1 The 0–1 Sequences Are Uncountable
Theorem 3.4.2 Cantor’s Theorem
Corollary 3.4.3 The Subsets of the Naturals
Definition 3.4.1 Decimal Expansion
Theorem 3.4.4 The Reals Are Uncountable, by Decimals
Corollary 3.4.5 Transcendental Numbers Exist
Exercise A1
Exercise B1: A faded diagonal
Exercise B2
Exercise B3: Expansions of three numbers
Exercise C1: Exit check: Cantor
Exercise C2: Permutations of the naturals

3.5 Comparing Sizes: the Schröder–Bernstein Theorem

Definition 3.5.1 Comparing Sizes
Proposition 3.5.1 Comparing Sizes Is Reflexive and Transitive
Proposition 3.5.2 Injections and Surjections
Theorem 3.5.3 Schröder–Bernstein Theorem
Example The closed and the open unit interval
Example The real line and its intervals
Exercise A1
Exercise B1: Injections both ways
Exercise B2: A proper subset of the same size
Exercise B3: Interleaving two sequences
Exercise C1: The real line and the subsets of $\mathbb{N}$
Exercise C2: Find the error

3.6 Infinite Sets

Theorem 3.6.1 Infinite Sets Contain a Countably Infinite Subset
Theorem 3.6.2 Infinite Sets and Proper Subsets
Exercise A1
Exercise B1: Removing finitely many points
Exercise B2: Absorbing a countable set
Exercise B3: A big hole
Exercise C1: Increasing functions
Exercise C2: The irrationals
Exercise R1
Exercise R2
Exercise R3
Exercise R4