Mathematical Reasoning: Writing and Proof

Introduction to Writing Proofs

01What Is a Statement? Truth Values and If-Then 02Quantifiers and Counterexamples: What One Example Can Prove 03The Truth Table for If-Then: When a Conditional Is False 04Using Conditionals: Theorems, Counterexamples and Closure Problem set Problem set 2

01Even and Odd Integers: Why a Proof Starts From the Definition 02The Know-Show Table: Proving Odd Times Odd Is Odd 03Writing Proofs for a Reader: Six Guidelines and Sums of Even and Odd 04Backward Answers Must Imply the Goal: Two More Direct Proofs Problem set Problem set 2

Logical Reasoning

01Logical Operators: Truth Rules for And, Or, Not and If-Then 02Only If, Necessary and Sufficient: Truth Tables and Tautologies 03Logical Equivalence: De Morgan's Laws and the Contrapositive 04Negating If-Then and Proving Equivalences by Chains Problem set Problem set 2

01Sets and Variables: The Roster Method and the Universal Set 02Element, Subset and Truth Set: Open Sentences as Predicates 03Set Builder Notation, the Empty Set, and Sentences True for All x Problem set Problem set 2

01Quantifiers: When For Every and There Exists Statements Are True 02Negating Quantified Statements: The Quantifier Switches 03Counterexamples and Negating Definitions With Quantifiers 04Statements With Two Quantifiers: Why the Order Matters Problem set Problem set 2

Constructing Proofs

01Divisibility: Definition, Notation, and Non-Divisors 02Proving Divisibility Is Transitive: Axioms, Definitions, Proof 03A Divisor of Two Numbers Divides Their Sum, and Counterexamples 04Congruence Modulo n: A Proof Mod 8 and 7 Rules for Writing Proofs Problem set Problem set 2

01Proving the Contrapositive When a Direct Proof Stalls 02Writing a Proof by Contrapositive: ab = 0 and De Morgan 03Proving Biconditionals: Two Conditionals, Each Marked 04Constructive and Nonconstructive Proofs of Existence Problem set Problem set 2

Contradiction, Cases and Proof Writing

01Why Proof by Contradiction Works and How to Negate the Claim 02Writing a Proof by Contradiction: x/y + y/x and Negations 03Proving Nonexistence by Contradiction: Even Equals Odd 04Proof That √2 Is Irrational: Rational and Irrational Numbers Problem set Problem set 2

01Proof by Cases: Why It Works, and Why n² + n Is Even 02Choosing Exhaustive Cases and Writing a Case Proof 03Absolute Value by Cases: Proving |x| = A and |-x| = |x|04The Triangle Inequality by Cases: |x + y| ≤ |x| + |y|Problem set Problem set 2

01Many Ways to Write 27 = 4q + r, and a Mod 6 Proof 02The Division Algorithm: One Quotient, One Remainder 03Proof by Remainders: Why 3 Divides n³ - n 04Adding, Multiplying and Powering Congruences 05Congruence Is Reflexive, Symmetric and Transitive 06Each Integer Is Congruent to Its Remainder: Squares Mod 5 07Ruling Out Cases to Prove a² ≡ 1 (mod 6)Problem set Problem set 2

01Direct, Contrapositive or Contradiction: Choosing a Proof 02Proof by Cases, Equivalences, and Existence Proofs 03Writing a Proof for a Reader: Openings and Signposts 04Writing the Math in a Proof: Displays and a Clear Ending Problem set Problem set 2

Mathematical Induction

01Inductive Sets: Why a Table of Cases Is Not a Proof 02The Principle of Mathematical Induction as an Axiom 03Induction on Sums: Add the Next Term to Both Sides 04Why Both Steps Matter: Proving 4 Divides 5ⁿ − 1 Problem set Problem set 2

01When Ordinary Induction Falls Short: n! vs 2ⁿ and Primes 02Extended Induction: Start the Basis Step at Any Integer M 03Strong Induction: Every Integer Above 1 Factors into Primes 04Three Basis Cases: Every n from 8 On Is a Sum of 3s and 5s Problem set Problem set 2

01Defining Sequences by Recursion: From Halving to n!02Fibonacci Numbers: Patterns, Rabbits and Sanskrit Verse 03Every Third Fibonacci Number Is Even: An Induction Proof 04Geometric Series by Induction: a(1 − rⁿ)/(1 − r)Problem set Problem set 2

Set Theory

01Intersection, Union, Difference, Complement: And, Or, Not for Sets 02Venn Diagrams for Two Sets: Four Regions and De Morgan's Law 03Proper Subsets, the Empty Set and Set Equality 04Venn Diagrams for Three Sets: Eight Regions and Subset Conditions 05Power Sets Have 2ⁿ Elements: Cardinality and the Number Systems Problem set Problem set 2

01Choose-an-Element Proofs: Multiples of 6 Are a Subset of the Evens 02Complements Reverse Subsets: A ⊆ B Implies Bᶜ ⊆ Aᶜ 03Proving Set Equality by Two Inclusions: A − (A − B) = A ∩ B 04Proving a Set Is Empty: Disjoint Sets and Element Chasing Problem set Problem set 2

01De Morgan's Law for Unions and Cycles of Conditionals 02Laws of Union and Intersection: Proving A ∩ B = B ∩ A 03Distributive Law: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)04Complement Laws and Proofs by the Algebra of Sets Problem set Problem set 2

01Ordered Pairs as Solutions: The Truth Set of 2x + 3y = 12 02The Cartesian Product A × B: Listing Pairs, Testing Laws 03Products of Intervals Are Rectangles in the Plane 04Proving A × (B ∪ C) = (A × B) ∪ (A × C)Problem set Problem set 2

01Union and Intersection of a Family: Some Versus All 02Indexed Unions: Subscripts for Infinitely Many Sets 03Families Indexed by Any Set: One Interval per Real Number 04De Morgan's Laws for Any Family, and Pairwise Disjoint Problem set Problem set 2

Functions

01What Is a Function? Exactly One Output for Each Input 02Functions Without Formulas: Birthdays and Sums of Divisors 03Images and Preimages: The Formal Definition of a Function 04The Range of a Function: From Graphs and Arrow Diagrams Problem set Problem set 2

01Polygon Diagonals and Derivatives: A Formula Is Not a Function 02Equal Functions: Why x⁵ mod 5 Is the Identity on R₅ 03Derivatives, Averages and Sequences as Functions 04Functions of Two Variables: Preimages in ℤ × ℤ Problem set Problem set 2

01Shared and Missed Outputs: Why 5x + 3 Has Neither 02Injections: Proving a Function Is One-to-One 03Surjections and Bijections: Is 3m + 2 Onto?04Domain and Codomain Decide: x² + 1 and e⁻ˣ 05One-to-One and Onto for Functions on ℝ × ℝ Problem set Problem set 2

01Following Two Arrows: How g(f(x)) Builds a Function 02g ∘ f: The Function on the Right Acts First 03Decomposing a Function: Cut at the Last Step 04Composing Surjections: Pull c Back Through g, Then f 05What an Injective or Surjective Composite Reveals Problem set Problem set 2

01A Function as a Set of Ordered Pairs: Each Input Once 02Reversing Every Arrow: The Function That Undoes a Bijection 03Swapping the Pairs: The Inverse of a Function as a Set 04Proof: f Inverse Is a Function Exactly When f Is a Bijection 05Undo the Last Step First: The Inverse of a Composite Problem set Problem set 2

01Applying a Function to a Set: Forward and Backward 02Image and Preimage: Why Squaring Splits an Interval 03Images, Preimages and Set Operations: Six Conjectures 04Proof: The Image of an Intersection Is Only a Subset 05Preimages Preserve Unions and Intersections Exactly Problem set Problem set 2

Relations

01Conditions on Pairs: Bordering States and an Ellipse 02Relations Defined: Any Subset of A × B, Domain and Range 03x R y Notation: Testing the Divides Relation Three Ways 04Which Relations Are Functions? The Circle vs the Parabola 05Drawing Relations: Shaded Regions and Directed Graphs Problem set Problem set 2

01Reflexive, Symmetric and Transitive Relations 02Congruence Modulo n as a Symmetric Relation 03Reading Relation Properties off a Directed Graph 04Equivalence Relations: All Three Properties 05Congruence Modulo n Means Matching Remainders 06Equivalence Relations: Angles, Lines and Set Sizes Problem set Problem set 2

01Sorting a Set: The Classes of an Equivalence Relation 02Three Remainders, Three Sets: The Integers Modulo 3 03Equivalence Classes: Everything Equivalent to y 04Equal or Disjoint: Why Classes Never Partly Overlap 05Partitions and Equivalence Relations: Same Information Problem set Problem set 2

01Remainders of Sums, Products and Digit Sums Mod 6 and Mod 9 02Adding Classes in ℤₙ: Why ⊕ and ⊙ Are Well Defined 03Addition and Multiplication Tables for ℤ₂, ℤ₃ and ℤ₅ 04Zero Divisors in ℤ₆: When the Zero Product Property Fails 05Why the Divisibility Test for 9 Works: Powers of Ten Are 1 Mod 9 Problem set Problem set 2

Remainders of Sums, Products and Digit Sums Mod 6 and Mod 9

Why does every member of [3] plus every member of [4] leave remainder 1 mod 6, and does a number share its remainder mod 9 with its digit sum?

Loading…

Questions

Work each one out before you check it. Every question has a scratch pad and a calculator.

Question 1
Find the remainder when $x \equiv 5 \pmod 6$ is divided by $6$ .
$r =$
Question 2
Suppose $x \equiv 5 \pmod 6$ and $y \equiv 4 \pmod 6$ . Find the remainder of $x \equiv 5 \pmod 6$ on division by $6$ .
$r =$
Question 3
Suppose $x \equiv 5 \pmod 6$ . Find the remainder of $x^3$ on division by $6$ .
$r =$
Question 4
Use the Division Algorithm to write $7403 = 9q + r$ with integers $q$ and $r$ and $0 \le r \le 8$ . Find $q$ and $r$ .
$q =$
$r =$
Question 5
Let $n = 48\,765$ and let $s(n)$ be the sum of its digits. Find $s(n)$ and the remainder of $s(n)$ on division by $9$ .
$s(n) =$
remainder $=$

←Previous Partitions and Equivalence Relations: Same Information Next Adding Classes in ℤₙ: Why ⊕ and ⊙ Are Well Defined →