List of results

Theorems and lemmas 117 Definitions 54 Examples 103 Exercises 217

Proofs from Definitions: Sets and Functions

1.1 Proofs from Definitions

Definition 1.1.1 Even and Odd
Definition 1.1.2 Divisibility
Definition 1.1.3 Prime Number
Proposition 1.1.1 Divisibility Is Transitive
Example Method: direct proof from a definition
Example Divisors of a combination
Theorem 1.1.2 Every Integer Is Even or Odd
Example Method: proof by cases
Example A proof by cases
Example The parity of a sum
Example A pattern that breaks
Example Two divisors, one product
Example Method: disproof by counterexample, proof by example
Example Same pattern, lattice midpoint
Exercise A1
Exercise B1: Direct proofs
Exercise B2: Two cases
Exercise B3: Name the move, then complete it
Exercise B4: Prove or disprove
Exercise C1: Three cases
Exercise C2: Find the error
Exercise C3: Lattice points in space

1.2 Sets, Subsets and Russell's Paradox

Definition 1.2.1 Equality of Sets
Definition 1.2.2 Subset
Example Method: element-chasing
Example Three inclusions
Proposition 1.2.1 Equality Is Two Inclusions
Example Method: two inclusions
Proposition 1.2.2 Inclusion Is Transitive
Definition 1.2.3 Specification
Definition 1.2.4 Empty Set
Proposition 1.2.3 The Empty Set Is Unique
Example Computing sets given by a property
Theorem 1.2.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 B4: Prove or disprove
Exercise C1: Every set has something outside it
Exercise C2: Antisymmetry for sets of sets

1.3 Unions, Intersections, Complements and Families

Definition 1.3.1 Union, Intersection, Difference
Theorem 1.3.1 Algebra of Sets
Example Method: a chain of equivalences
Example A law by a chain
Definition 1.3.2 Power Set
Example Small power sets
Definition 1.3.3 Indexed Family
Definition 1.3.4 Union and Intersection of a Family
Proposition 1.3.2 Smallest Closed Set
Example Unions and intersections of intervals
Theorem 1.3.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 B4: Prove or disprove
Exercise C1: Power sets and operations
Exercise C2: Find the error

1.4 Ordered Pairs, Products and Relations

Definition 1.4.1 Ordered pair
Example Solving an equation between pairs
Example Method: existence and uniqueness
Definition 1.4.2 Cartesian product
Example The coordinates of an element of a product
Example Products, small and large
Proposition 1.4.1 Products and Set Operations
Example Two rectangles
Definition 1.4.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 B4: Prove or disprove
Exercise C1: The square of a union
Exercise C2: When one inclusion forces equality

1.5 Functions, Composition, Injections and Surjections

Definition 1.5.1 Function
Example First functions
Example Relations that are not functions
Proposition 1.5.1 Equality of Functions
Example Equal and unequal functions
Example All functions between two small sets
Proposition 1.5.2 Functions and the Empty Set
Definition 1.5.2 Composition
Example The order of composition matters
Proposition 1.5.3 Composition Is Associative
Definition 1.5.3 Injective
Definition 1.5.4 Surjective
Definition 1.5.5 Bijective
Example Method: proving injectivity
Example Method: proving surjectivity
Example Solving backwards, proving forwards
Example Deciding injective and surjective
Example Squaring, three ways
Theorem 1.5.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 B4: Prove or disprove
Exercise C1: Exit check: composites
Exercise C2: When the composite is a bijection

1.6 Left, Right and Two-Sided Inverses

Definition 1.6.1 Left and Right Inverses
Example Left inverses on small sets
Theorem 1.6.1 Left Inverses and Injectivity
Example Method: construct and verify
Example Running the construction
Proposition 1.6.2 Right Inverses Give Surjectivity
Example All right inverses of a small surjection
Proposition 1.6.3 Left and Right Inverses Agree
Definition 1.6.2 Inverse Function
Example Inverses found and checked
Theorem 1.6.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 B4: Prove or disprove
Exercise C1: One composite equal to the identity
Exercise C2: When is a left inverse unique?

1.7 Images and Preimages

Definition 1.7.1 Image
Definition 1.7.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.7.1 Preimages of Set Operations
Proposition 1.7.2 Preimage under a Composite
Theorem 1.7.3 Image of a Union
Example Two witnesses under one name
Theorem 1.7.4 Image of an Intersection
Proposition 1.7.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

Induction, Contradiction, and Finite Sets

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
Example No endless descent in the natural numbers
Example Method: the least element
Example Going down by two
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 B4: Prove or disprove
Exercise C1: A greatest element from a least upper bound
Exercise C2: A well-ordered set with gaps

2.2 Induction, Strong Induction and Divisibility

Theorem 2.2.1 Induction from a Base
Theorem 2.2.2 Strong Induction from a Base
Example Method: finding $P(n)$ inside $P(n + 1)$
Example Where the step starts working
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, used later
Exercise B3, used later
Exercise B4: Prove or disprove
Exercise C1: Exit check: a flawed induction
Exercise C2: Lowest terms, used later
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 Contrapositive and Contradiction in Practice

Example A negative hypothesis
Example Method: choosing direct, contrapositive or contradiction
Theorem 2.4.1 There Are Infinitely Many Primes
Proposition 2.4.2 The Cube Root of 2 Is Irrational
Example Method: the smallest counterexample
Example Taking out the threes
Exercise A1
Exercise B1: Contrapositive
Exercise B2: Contradiction
Exercise B3: Name the move, then complete it
Exercise B4: Prove or disprove
Exercise C1: Two proofs by contradiction
Exercise C2: A bound from Euclid’s list
Exercise C3: Challenge: primes of the form $3k + 2$

2.5 Equinumerous Sets and Finite Sets

Definition 2.5.1 Equinumerous Sets
Proposition 2.5.1 Equinumerosity Is Reflexive, Symmetric and Transitive
Definition 2.5.2 Finite Set, Number of Elements
Definition 2.5.3 Infinite Set
Theorem 2.5.2 Pigeonhole Principle
Corollary 2.5.3 Pigeonhole for Finite Sets
Example Method: the pigeonhole principle
Example Back to the five lattice points
Corollary 2.5.4 The Number of Elements Is Unique
Proposition 2.5.5 Disjoint Unions
Proposition 2.5.6 Subsets of Finite Sets
Corollary 2.5.7 Removing a Point
Proposition 2.5.8 Counting Subsets
Theorem 2.5.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 B4: Prove or disprove
Exercise C1: Infinite means arbitrarily large finite pieces
Exercise C2: Counting products and functions
Exercise R1
Exercise R2
Exercise R3

Countable and Uncountable Sets

3.1 Countable Sets

Definition 3.1.1 Countable Set
Definition 3.1.2 Countably Infinite Set
Lemma 3.1.1 Subsets of the Natural Numbers
Theorem 3.1.2 Characterizations of Countable Sets
Example Method: list it
Proposition 3.1.3 Subsets of Countable Sets
Proposition 3.1.4 Images of Countable Sets
Proposition 3.1.5 Union of Two Countable Sets
Example Listing the rows one after another
Theorem 3.1.6 The Plane of Natural Numbers Is Countable
Corollary 3.1.7 Products of Countable Sets
Theorem 3.1.8 The Integers and the Rationals Are Countable
Example Integer combinations of $1$ and $\sqrt 2$
Example Coding the two-element subsets of $\mathbb{N}$
Exercise A1
Exercise B1
Exercise B2: Putting a proof in order
Exercise B3: A surjection by formula
Exercise B4: Prove or disprove
Exercise C1: Finite subsets of the natural numbers
Exercise C2: Find the error

3.2 Countable Unions and the Axiom of Choice

Axiom 3.2.1 Axiom of Choice
Example Method: name the choice
Example Choice or a rule?
Theorem 3.2.2 Surjections Have Right Inverses
Theorem 3.2.3 Countable Unions of Countable Sets
Example Unions that come with their lists
Theorem 3.2.4 The Algebraic Numbers Are Countable
Exercise A1
Exercise B1: Which constructions need choice?
Exercise B2: Finite sequences
Exercise B3
Exercise B4: Prove or disprove
Exercise C1: Exit check: countable unions
Exercise C2: Algebraic numbers without choice
Exercise C3: Finite unions

3.3 Diagonal Arguments: Uncountable Sets and Cantor's Theorem

Example Back to the five strings
Theorem 3.3.1 The 0–1 Sequences Are Uncountable
Example Method: the diagonal
Example A function that outgrows a list
Theorem 3.3.2 Cantor’s Theorem
Corollary 3.3.3 The Subsets of the Naturals
Definition 3.3.1 Decimal Expansion
Theorem 3.3.4 The Reals Are Uncountable, by Decimals
Corollary 3.3.5 Transcendental Numbers Exist
Exercise A1
Exercise B1: A faded diagonal
Exercise B2
Exercise B3: Expansions of three numbers
Exercise B4: Prove or disprove
Exercise C1: Exit check: Cantor
Exercise C2: Permutations of the naturals

3.4 Comparing Sizes: the Schröder–Bernstein Theorem

Definition 3.4.1 Comparing Sizes
Proposition 3.4.1 Comparing Sizes Is Reflexive and Transitive
Proposition 3.4.2 Injections and Surjections
Theorem 3.4.3 Schröder–Bernstein Theorem
Example Method: injections both ways
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 B4: Prove or disprove
Exercise C1: The real line and the subsets of $\mathbb{N}$
Exercise C2: Find the error

3.5 Infinite Sets

Theorem 3.5.1 Infinite Sets Contain a Countably Infinite Subset
Theorem 3.5.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

3.6 Cardinal Arithmetic

Definition 3.6.1 Disjoint Union
Example Two copies of ℕ
Proposition 3.6.1 Sums, Products and Powers Respect Size
Proposition 3.6.2 Monotonicity
Example The diagonal pairing of ℕ × ℕ with ℕ
Example Method: build a bijection by encoding and decoding
Theorem 3.6.3 Laws of Cardinal Arithmetic
Example Method: prove a law of sizes by a bijection of sets
Theorem 3.6.4 Subsets and 0–1 Functions
Corollary 3.6.5 No Set Is the Size of Its 0–1 Functions
Theorem 3.6.6 The Line Is a Power of Two
Example Interleaving digits
Theorem 3.6.7 The Plane Is the Size of the Line
Theorem 3.6.8 Sequences of Natural Numbers
Corollary 3.6.9 Sequences of Real Numbers
Exercise A1
Exercise B1: Encodings
Exercise B2: More laws
Exercise B3: Sets the size of the line, used later
Exercise B4: Prove or disprove
Exercise C1: Functions from the line to the line
Exercise C2: Find the error
Exercise C3: Rearrangements of ℕ
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Relations: Equivalence and Order

4.1 Properties of Relations

Definition 4.1.1 Properties of a Relation
Example Deciding four properties
Example Method: proving or disproving a property of a relation
Proposition 4.1.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 B4: Prove or disprove
Exercise C1: Properties as equations between sets
Exercise C2: What symmetry and transitivity do give

4.2 Equivalence Relations and Partitions

Definition 4.2.1 Equivalence Relation
Example Four equivalence relations
Definition 4.2.2 Equivalence Class
Definition 4.2.3 Partition
Definition 4.2.4 Quotient Set
Theorem 4.2.1 Equivalence Classes Partition the Set
Theorem 4.2.2 Partitions and Equivalence Relations Correspond
Definition 4.2.5 Congruence Modulo n
Proposition 4.2.3 Congruence Is an Equivalence Relation
Proposition 4.2.4 The Integers Modulo n
Example The fibers of a function
Example The reals modulo the integers
Proposition 4.2.5 Congruence Respects Sums and Products
Example Method: checking that a definition on classes is well defined
Example A rule on classes that is not a function
Example Same size, revisited
Exercise A1
Exercise B1: Fractions as classes
Exercise B2: Computing in Z/7
Exercise B3: Which rules are well defined?
Exercise B4: Prove or disprove
Exercise C1: Exit check: classes partition
Exercise C2: Find the error

4.3 Partial Orders, Maximal and Greatest Elements

Definition 4.3.1 Partial Order
Example Inclusion is a partial order, rarely total
Definition 4.3.2 Upper and Lower Bounds
Definition 4.3.3 Greatest and Least Elements
Definition 4.3.4 Maximal and Minimal Elements
Proposition 4.3.1 Greatest and Least Elements Are Unique
Proposition 4.3.2 Greatest and Maximal Elements
Example Maximal elements that are not greatest
Definition 4.3.5 Supremum and Infimum
Example The supremum under divisibility is the least common multiple
Definition 4.3.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

Building Functions

5.1 Restriction, Extension and Gluing

Definition 5.1.1 Restriction, Extension, Inclusion
Proposition 5.1.1 Restrictions
Theorem 5.1.2 Gluing Functions
Example Method: define a function by gluing
Example Piecewise definitions are gluings
Definition 5.1.2 Indicator Function
Proposition 5.1.3 Set Operations as Arithmetic of Indicators
Example Symmetric difference is associative
Exercise A1
Exercise B1: Three pieces
Exercise B2: Injective across pieces
Exercise B3: By indicators
Exercise B4: Prove or disprove
Exercise C1: Counting extensions
Exercise C2: Find the error
Exercise C3: Cantor through indicators

5.2 Fibers and the Canonical Factorization

Proposition 5.2.1 The Fibers of a Function
Theorem 5.2.2 Canonical Factorization
Example Fractions as classes
Theorem 5.2.3 Functions out of a Quotient
Example Method: define a function on a quotient
Example Maps out of the clock
Exercise A1
Exercise B1: The absolute value, factored
Exercise B2: Same fibers
Exercise B3: A coarser relation
Exercise B4: Prove or disprove
Exercise C1: Equal fibers
Exercise C2: Find the error
Exercise C3: Exit check: depends only on f

5.3 Binary Operations

Definition 5.3.1 Binary Operation
Example Operations
Definition 5.3.2 Associative, Commutative, Identity, Inverse
Example A right identity that is not an identity
Proposition 5.3.1 An Identity Is Unique
Example Method: compute one expression in two ways
Proposition 5.3.2 Inverses Are Unique for an Associative Operation
Example Without associativity, two inverses
Proposition 5.3.3 Inverses of Products
Proposition 5.3.4 Pointwise Operations
Proposition 5.3.5 Composition on X^X
Proposition 5.3.6 Operations on a Quotient
Exercise A1
Exercise B1: Deciding properties
Exercise B2: Every square is the identity
Exercise B3: Two kinds of inverse
Exercise B4: Prove or disprove
Exercise C1: Four factors
Exercise C2: Find the error
Exercise C3: Transport by a bijection

5.4 Permutations and Iteration

Definition 5.4.1 Permutation
Proposition 5.4.1 Permutations under Composition
Definition 5.4.2 Iterates
Proposition 5.4.2 Laws of Iterates
Definition 5.4.3 Orbit, Forward Orbit, Fixed Point
Theorem 5.4.3 The Orbits of a Permutation Partition the Set
Proposition 5.4.4 Following an Orbit
Example Method: follow an orbit
Example The three-pile shuffle
Definition 5.4.4 Cycle
Theorem 5.4.5 Cycle Decomposition
Corollary 5.4.6 Some Power Is the Identity
Proposition 5.4.7 Forward Orbits of a Self-Map of a Finite Set
Example Squaring on an eleven-hour clock
Exercise A1
Exercise B1: Doubling on nine hours
Exercise B2: Iterates commute
Exercise B3: Orbits are invariant
Exercise B4: Prove or disprove
Exercise C1: Exit check: fifteen cards
Exercise C2: Find the error
Exercise C3: Each point, its own clock
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Zorn's Lemma

6.1 Chains and Zorn's Lemma

Definition 6.1.1 Chain
Lemma 6.1.1 Finitely Many Members of a Chain
Theorem 6.1.2 Zorn’s Lemma
Theorem 6.1.3 Zorn’s Lemma Gives Choice
Example Method: the maximality template
Example A set of representatives
Exercise A1
Exercise B1: Maximal chains
Exercise B2: Name the move, then complete it
Exercise B3: A small poset of partial injections
Exercise B4: Prove or disprove
Exercise C1: Find the error
Exercise C2: Exit check: when no choice is needed

6.2 Using Zorn's Lemma

Theorem 6.2.1 Any Two Sets Are Comparable
Corollary 6.2.2 Trichotomy for Sizes
Lemma 6.2.3 Adding One Comparison
Theorem 6.2.4 Every Partial Order Extends to a Total Order
Example A total order containing divisibility
Exercise A1
Exercise B1: Name the move, then complete it
Exercise B2: A total order on the subsets of a three-element set
Exercise B3: A total order on the plane
Exercise C1: Exit check: an order is the intersection of its total extensions
Exercise C2: Find the error
Exercise R1: Surjections one way or the other
Exercise R2: Maximal chains give Zorn’s lemma
Exercise R3: The basis theorem, read as a template