List of results

The ZF Fragment and the von Neumann Natural Numbers

1.1 Axioms for Sets

Axiom 1.1.1 The Axioms (Z1)–(Z6)
Proposition 1.1.2 The Sets Named by the Axioms
Exercise A1
Exercise B1: Power sets and unions
Exercise B2: Intersections of sets of sets
Exercise C1: What the empty-set axiom really says; intersections as greatest lower bounds

1.2 Ordered Pairs Built from Sets

Definition 1.2.1 Ordered Pair as a Set
Example Three Encodings That Lose Information
Theorem 1.2.1 Characteristic Property of Pairs
Proposition 1.2.2 The Product Exists
Proposition 1.2.3 The Working Rules from the Axioms
Exercise A1
Exercise B1: Coordinates from unions and intersections
Exercise B2: Nested pairs
Exercise C1: Exit check: Kuratowski pairs
Exercise C2: Find the error
Exercise C3: Wiener’s encoding

1.3 Successors, Inductive Sets and the Natural Numbers

Definition 1.3.1 Successor of a set
Example The first natural numbers as sets
Definition 1.3.2 Inductive set
Axiom 1.3.1 Axiom of Infinity
Definition 1.3.3 The set of natural numbers
Theorem 1.3.2 The Least Inductive Set
Theorem 1.3.3 Induction on $\omega$
Exercise A1
Exercise B1: Intersections and differences
Exercise B2: Zero or a successor
Exercise C1: Two steps back

1.4 The Natural Numbers Satisfy Peano's Axioms

Definition 1.4.1 Transitive set
Lemma 1.4.1 Natural Numbers Are Transitive Sets
Theorem 1.4.2 Peano’s Axioms Hold in $\omega$
Definition 1.4.2 Peano system
Example Each axiom is needed
Proposition 1.4.3 No Pair Is a Natural Number
Exercise A1
Exercise B1: Put the proof in order
Exercise B2: Two steps at a time
Exercise C1: A Peano system with a different start
Exercise C2: Closed subsets of the chain

1.5 The Recursion Theorem; Addition and Multiplication

Theorem 1.5.1 Recursion Theorem on $\omega$
Definition 1.5.1 Addition and Multiplication on $\omega$
Corollary 1.5.2 Successor Cancellation
Theorem 1.5.3 Laws of Arithmetic on $\omega$
Exercise A1
Exercise B1: Small products
Exercise B2: Distributivity, last step blank
Exercise C1: Exit check: addition is commutative
Exercise C2: Associativity of multiplication, last half blank
Exercise C3: Doubling

1.6 Order and Well-Ordering of the Natural Numbers

Definition 1.6.1 Order on $\omega$
Theorem 1.6.1 Order on $\omega$
Theorem 1.6.2 Well-Ordering of $\omega$
Proposition 1.6.3 Order and Arithmetic on $\omega$
Proposition 1.6.4 Powers and Parity on $\omega$
Proposition 1.6.5 Tuples and Lists as Sets
Exercise A1
Exercise B1: Order as inclusion
Exercise B2: A product is at least its factor
Exercise C1: Strong induction on ω
Exercise C2: Find the error

1.7 All Peano Systems Are Alike

Theorem 1.7.1 Categoricity of the Peano Axioms
Proposition 1.7.2 Isomorphisms Preserve Arithmetic and Order
Corollary 1.7.3 ω Is the Natural Numbers
Exercise A1
Exercise B1: The even numbers
Exercise B2: The identification at work
Exercise C1: Writing out categoricity
Exercise C2: Without induction, no recursion
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Building the Integers and the Rationals from Equivalence Classes

2.1 The Integers as Classes of Pairs

Definition 2.1.1 The Integers
Proposition 2.1.1 The Relation Behind the Integers
Example Three classes, listed and drawn
Proposition 2.1.2 Normal Form of an Integer
Exercise A1
Exercise B1: Three look-alike relations
Exercise B2: A class in set-builder form
Exercise C1: Exit check: the relation that builds $\mathbb{Z}$

2.2 Well-Definedness, and the Arithmetic of the Integers

Theorem 2.2.1 Functions on Classes
Definition 2.2.1 Sum, Product and Negative of Integers
Proposition 2.2.2 The Operations on Integers Are Well Defined
Example The first coordinate is not a function of the class
Proposition 2.2.3 The Natural Numbers Embed in the Integers
Exercise A1
Exercise B1: Two rules that pass the check
Exercise B2: Determine which
Exercise C1: Properties of classes, and an operation that half works
Exercise C2: One at a time or both at once

2.3 The Integers as an Ordered Ring

Definition 2.3.1 Commutative Ring, Field
Theorem 2.3.1 The Integers Form a Commutative Ring
Proposition 2.3.2 Algebra in a Commutative Ring
Definition 2.3.2 Ordered Ring, Ordered Field
Proposition 2.3.3 Order from a Positive Set
Definition 2.3.3 Order on the Integers
Theorem 2.3.4 The Integers Form an Ordered Ring
Proposition 2.3.5 Rules for Inequalities in an Ordered Ring
Proposition 2.3.6 Least and Greatest Elements of Sets of Integers
Example A field with two elements that cannot be ordered
Exercise A1
Exercise B1: Three rows in detail
Exercise B2: The wrong positive set
Exercise C1: Ordered rings with $1 \ne 0$ are infinite

2.4 The Rationals as Classes of Fractions

Proposition 2.4.1 Cross-Multiplication Is an Equivalence Relation
Definition 2.4.1 The Rational Numbers
Definition 2.4.2 Operations on the Rationals
Proposition 2.4.2 The Operations on the Rationals Are Well Defined
Example Formulas that ignore the class
Theorem 2.4.3 The Rationals Form a Field
Proposition 2.4.4 The Integers Embed in the Rationals
Example Non-zero denominators give the same rationals
Exercise A1
Exercise B1: Three rows in detail
Exercise B2: Addition is well defined
Exercise C1: The least denominator
Exercise C2: Find the error

2.5 The Rationals as an Ordered Field; the Archimedean Property

Definition 2.5.1 The Order on $\mathbb{Q}$
Theorem 2.5.1 The Rationals Form an Ordered Field
Proposition 2.5.2 Reciprocals Reverse Order
Theorem 2.5.3 The Rationals Are Archimedean
Corollary 2.5.4 Small Reciprocals in $\mathbb{Q}$
Proposition 2.5.5 Integer Part of a Rational
Exercise A1
Exercise B1
Exercise B2: A rational of the form a + 1/n
Exercise B3
Exercise C1: Exit check: $\mathbb{Q}$ is Archimedean
Exercise C2: The comparison, on representatives
Exercise C3: Find the error

2.6 The Gaps in the Rationals

Theorem 2.6.1 No Rational Squares to Two
Theorem 2.6.2 A Bounded Set of Rationals with No Rational Supremum
Example A Rational Sequence Aimed at the Gap
Exercise A1
Exercise B1: Put the proof in order
Exercise B2
Exercise B3
Exercise C1: Exit check: the gap at $\sqrt 2$
Exercise C2: Which integers have a rational square root?
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Divisibility, Division with Remainder, and Modular Arithmetic

3.1 Divisibility and Division with Remainder

Proposition 3.1.1 Rules for Divisibility in $\mathbb{Z}$
Theorem 3.1.2 Division with Remainder in $\mathbb{Z}$
Corollary 3.1.3 Even and Odd Integers
Exercise A1
Exercise B1: Negative divisors
Exercise B2: Three in a row
Exercise C1: Division from the integer part

3.2 The Greatest Common Divisor, Bézout, and the Euclidean Algorithm

Definition 3.2.1 Integer Combinations
Definition 3.2.2 Greatest Common Divisor
Theorem 3.2.1 Bézout’s Theorem
Definition 3.2.3 Coprime Integers
Corollary 3.2.2 Coprime Means 1 Is a Combination
Lemma 3.2.3 One Step of the Euclidean Algorithm
Theorem 3.2.4 The Euclidean Algorithm
Example Two runs of the algorithm
Exercise A1
Exercise B1
Exercise B2
Exercise B3: The algorithm stops quickly
Exercise C1: Exit check: Bézout
Exercise C2: Scaling the gcd

3.3 Euclid's Lemma and the Fundamental Theorem of Arithmetic

Theorem 3.3.1 Euclid’s Lemma
Definition 3.3.1 List, Product of a List, Prime Factorization
Corollary 3.3.2 A Prime Dividing a Product
Proposition 3.3.3 Coprime Divisors of a Number
Lemma 3.3.4 The Least Divisor Is Prime
Theorem 3.3.5 Fundamental Theorem of Arithmetic
Proposition 3.3.6 Lowest Terms
Exercise A1
Exercise B1: Put the proof in order
Exercise B2: The least common multiple
Exercise B3: Two factorizations and a gcd
Exercise C1: Exit check: unique factorization
Exercise C2: Find the error
Exercise C3: There is no last prime

3.4 Ideals, Quotient Rings, and the Integers Modulo n

Definition 3.4.1 Ideal
Theorem 3.4.1 Quotient Ring by an Ideal
Theorem 3.4.2 Ideals of the Integers
Definition 3.4.2 The Integers Modulo n
Theorem 3.4.3 The Ring of Integers Modulo n
Example Multiplication modulo six and modulo five
Exercise A1
Exercise B1: The ring with four elements
Exercise B2: Determine which
Exercise C1: Changing the modulus
Exercise C2: Closed under subtraction

3.5 Units, Prime Moduli, and the Chinese Remainder Theorem

Definition 3.5.1 Unit of a Commutative Ring
Theorem 3.5.1 Units Modulo n
Example Inverting a class modulo sixty
Theorem 3.5.2 The Integers Modulo n Form a Field Exactly When n Is Prime
Theorem 3.5.3 Chinese Remainder Theorem for Two Moduli
Example Two remainders at once, and two failures
Exercise A1
Exercise B1
Exercise B2
Exercise B3
Exercise C1: Exit check: units and the field $\mathbb{Z}/p\mathbb{Z}$
Exercise C2: Find the error
Exercise C3
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Ordered Fields and Sequences in an Ordered Field

4.1 Working in an Ordered Field

Lemma 4.1.1 Fraction Rules in a Field
Proposition 4.1.2 Halves and Comparisons in an Ordered Field
Definition 4.1.1 Absolute Value in an Ordered Field
Proposition 4.1.3 Rules for the Absolute Value
Exercise A1
Exercise B1: Two companions of (c) and (d)
Exercise B2: Solving an inequality
Exercise B3: Two more triangle inequalities
Exercise C1: A field that cannot be ordered
Exercise C2: Maximum and minimum through the absolute value

4.2 The Rationals inside an Ordered Field; the Archimedean Property

Definition 4.2.1 Natural Numbers and Powers in an Ordered Field
Proposition 4.2.1 The Natural Numbers inside an Ordered Field
Theorem 4.2.2 The Rationals Embed in Every Ordered Field
Definition 4.2.2 Archimedean Ordered Field
Proposition 4.2.3 Small Reciprocals in an Archimedean Field
Proposition 4.2.4 Integer Part in an Archimedean Field
Theorem 4.2.5 The Rationals Are Dense in an Archimedean Field
Example A Non-Archimedean Ordered Field
Exercise A1
Exercise B1: Archimedes’ form
Exercise B2: Smaller than every reciprocal
Exercise B3: Rationals with a power of two as denominator
Exercise C1: Many rationals, and rational approximation
Exercise C2: Where the proof for the rationals breaks
Exercise C3: The order of the rationals is the only one

4.3 Sequences and Limits in an Ordered Field

Definition 4.3.1 Sequence; Eventually
Definition 4.3.2 Limit of a Sequence in an Ordered Field
Example First Limits
Definition 4.3.3 Null Sequence
Definition 4.3.4 Bounded Sequence
Proposition 4.3.1 Archimedes as a Null Sequence
Proposition 4.3.2 Only the Tail Matters
Proposition 4.3.3 Limits Through Null Sequences
Theorem 4.3.4 Uniqueness of Limits
Proposition 4.3.5 Convergent Sequences Are Bounded
Exercise A1
Exercise B1
Exercise B2
Exercise B3: Bounded but not convergent, in $\mathbb{Q}(t)$
Exercise C1: A positive limit keeps the terms positive
Exercise C2: Find the error

4.4 The Algebra and Order of Limits

Proposition 4.4.1 Null Times Bounded Is Null
Lemma 4.4.2 Terms Near a Non-zero Limit
Theorem 4.4.3 Limit Laws
Proposition 4.4.4 Limits Preserve Weak Inequalities
Exercise A1
Exercise B1
Exercise B2: Put the proof in order
Exercise B3: Close to a convergent sequence
Exercise C1: Exit check: the product law
Exercise C2: Non-negative terms and reciprocals

4.5 Cauchy Sequences

Definition 4.5.1 Cauchy Sequence
Proposition 4.5.1 Convergent Sequences Are Cauchy
Proposition 4.5.2 Cauchy Sequences Are Bounded
Theorem 4.5.3 Sums and Products of Cauchy Sequences
Theorem 4.5.4 The Sign of a Non-Null Cauchy Sequence
Proposition 4.5.5 Sign Stability under Null Differences
Proposition 4.5.6 Reciprocals of Cauchy Sequences
Example Shrinking Steps, Terms That Do Not Settle
Exercise A1
Exercise B1
Exercise B2
Exercise B3
Exercise C1
Exercise C2: Exit check: the sign theorem
Exercise C3: Find the error

4.6 A Cauchy Sequence with No Rational Limit

Theorem 4.6.1 The Newton Sequence Is Cauchy with No Rational Limit
Exercise A1
Exercise B1
Exercise B2
Exercise C1: Exit check: a Cauchy sequence with no rational limit
Exercise C2: Cauchy depends on the field
Exercise R1
Exercise R2
Exercise R3
Exercise R4

Constructing the Real Numbers from Cauchy Sequences

5.1 Sequences That Should Converge

Definition 5.1.1 Cauchy Sequences of Rationals
Definition 5.1.2 Equivalent Cauchy Sequences
Proposition 5.1.1 Equivalence of Cauchy Sequences Is an Equivalence Relation
Example The Truncations and the Newton Sequence Are Equivalent
Example Finite Changes and Shifts
Exercise A1
Exercise B1: Equivalent or not
Exercise B2: Null differences preserve Cauchy
Exercise B3: Every other Newton term
Exercise C1: Subsequences

5.2 The Real Numbers and Their Arithmetic

Definition 5.2.1 The Real Numbers
Definition 5.2.2 Sum, Product and Negative of Real Numbers
Theorem 5.2.1 The Operations on Real Numbers Are Well Defined
Theorem 5.2.2 The Real Numbers Form a Commutative Ring
Theorem 5.2.3 The Real Numbers Form a Field
Example Termwise Reciprocals Are Not a Definition
Exercise A1
Exercise B1: The negative, directly
Exercise B2: The larger of two reals, faded
Exercise B3: A square root of two
Exercise C1: Exit check: multiplication is well defined
Exercise C2: No square is zero except zero

5.3 Positive Classes and the Order

Example Termwise Order Is Not an Order on Classes
Definition 5.3.1 Positive Cauchy Sequence
Proposition 5.3.1 Positivity Is a Property of the Class
Theorem 5.3.2 The Positive Real Numbers
Definition 5.3.2 Order on the Reals
Theorem 5.3.3 The Reals Form an Ordered Field
Lemma 5.3.4 Termwise Inequalities Pass to Classes
Proposition 5.3.5 The Absolute Value Is Computed Termwise
Exercise A1
Exercise B1
Exercise B2
Exercise B3
Exercise C1
Exercise C2: Find the error

5.4 The Rationals Inside the Reals

Definition 5.4.1 The Rationals in the Reals
Theorem 5.4.1 The Rationals Embed in the Reals
Theorem 5.4.2 The Reals Are Archimedean
Theorem 5.4.3 The Rationals Are Dense in the Reals
Corollary 5.4.4 Rational Tolerances Suffice
Theorem 5.4.5 A Cauchy Sequence Converges to Its Class
Example The Class of the Newton Sequence
Exercise A1
Exercise B1
Exercise B2
Exercise B3: Put the proof in order
Exercise C1
Exercise C2

5.5 Every Cauchy Sequence of Reals Converges

Theorem 5.5.1 The Constructed Reals Are Cauchy-Complete
Example Picking Representatives Is a Use of Choice
Exercise A1
Exercise B1
Exercise B2
Exercise C1: Exit check: Cauchy completeness
Exercise C2: Find the error

5.6 The Real Numbers Form a Complete Ordered Field

Definition 5.6.1 Complete Ordered Field
Lemma 5.6.1 A Lower Bound for Powers of Two
Theorem 5.6.2 Archimedean and Cauchy-Complete Implies Complete
Theorem 5.6.3 The Constructed Reals Form a Complete Ordered Field
Exercise A1
Exercise B1
Exercise B2
Exercise C1: Exit check: completeness from Cauchy completeness
Exercise C2: The rationals are not complete, by bisection
Exercise R1
Exercise R2
Exercise R3
Exercise R4

The Complete Ordered Field Is Unique

6.1 What Completeness Gives at Once

Definition 6.1.1 Order-Preserving Field Map
Proposition 6.1.1 Field Maps Fix the Rationals
Theorem 6.1.2 A Complete Ordered Field Is Archimedean
Example A Supremum Computed by Archimedes
Definition 6.1.2 The Rationals below an Element
Example The Rationals below the Square Root of Two
Lemma 6.1.3 Rationals Separate
Proposition 6.1.4 Square Roots in a Complete Ordered Field
Exercise A1
Exercise B1
Exercise B2
Exercise C1: An Archimedean field is no larger than the subsets of the rationals
Exercise C2: Find the error

6.2 Building the Map from the Rationals Below

Lemma 6.2.1 Rationals below a Sum
Lemma 6.2.2 Rationals below a Product
Theorem 6.2.3 Embedding an Archimedean Field in a Complete One
Exercise A1
Exercise B1
Exercise B2: Cube roots
Exercise C1: Exit check: at most one map into an Archimedean field
Exercise C2: Dense image, and when the map is onto

6.3 Two Complete Ordered Fields, One Isomorphism

Theorem 6.3.1 Uniqueness of the Complete Ordered Field
Corollary 6.3.2 Every Complete Ordered Field Is a Copy of the Reals
Example Two Models, One Square Root of Two
Corollary 6.3.3 A Complete Ordered Field Has Only the Trivial Order Automorphism
Theorem 6.3.4 Field Maps of a Complete Ordered Field to Itself
Exercise A1
Exercise B1
Exercise B2
Exercise C1: Exit check: field maps of a complete ordered field
Exercise C2: Find the error