Introduction to Proofs (Learn to Write Mathematical Proofs)

by Dave
(DAVE)—

Making the transition from calculus to analysis (or from elementary algebra to abstract algebra) can be one of the most challenging transitions for students. In this article, I guide you through this process and explain how to become confident and skilled. You’ll see many articles and videos that will explain and provide insights to help keep you on track and inspired.

What You’ll Learn in Logic and Proof

Master logic and proofs. With these lessons and videos you’ll learn about different styles and techniques of mathematical proofs.

  • Mathematical Statements
  • Logical Connectives
  • Constructing Truth Tables
  • Tautologies and Contradictions
  • Contrapositive, Converse, and Inverse
  • Modus Ponens and Substitution
  • Logical Equivalence
  • Introduction to Quantifiers
  • Propositional Functions
  • Universal Quantifier
  • Existential Quantifier
  • Uniqueness Quantifier
  • Negating Quantifiers
  • Counterexamples
  • Valid Arguments
  • Combining Quantifiers
  • Inference Rules
  • Direct Proofs
  • Indirect Proofs
  • Proof by Contrapositive
  • Proof by Cases
  • Simple Examples
  • Axiomatic Systems
  • Inference Rules for Quantified Statements
  • Theorems in Incidence Geometry
  • Summary of Logical Discourse

Chapter Description

We begin this course on logic and proof by discussing what mathematical statements are. We start with an elementary study of propositional logic by constructing truth tables and understanding their properties. We discuss tautologies, contradictions, and contingencies and also talk about contrapositives, converses and inverses.

The second part of this course discusses quantifiers. We present various types of quantifiers and study negating quantifiers. We pay special attention to combining quantifiers and writing valid arguments by working through several examples.

Writing mathematical arguments is the emphasis of this course. We examine two main strategies for writing proofs: a column proof versus a paragraph proof. We illustrate both approaches by considering various types of proof such as direct proof, indirect proof, proof by cases, and proof by contrapositive.

We finish this course with a discussion of how to perform logical discourse. Axiomatic systems are discussed in great detail, including an example of an axiomatic system called Incidence Geometry. We will prove several fundamental results using both strategies discussed above.

What You’ll Learn in Elementary Set Theory

Master elementary set theory. Learn about set operations, functions, one-to-one and onto functions, equivalence relations, and partitions.

  • Introduction to Sets
  • Set Operations
  • Symmetric Difference
  • Cartesian Product and Families
  • Finite Unions and Intersections
  • Indexed Sets
  • Domain and Codomain
  • The Image of a Function
  • The Preimage of a Function
  • Injective Functions
  • Surjective Functions
  • Composition of Functions
  • Inverse Functions
  • Binary Relations
  • Composition of Relations
  • The Image of a Relation
  • The Preimage of a Relation
  • Reflexive, Symmetric, and Transitive Relations
  • Equivalence Relations
  • Partitions
  • The Fundamental Theorem of Equivalence Relations
  • Closures

Chapter Description

This course begins with an introduction to sets from a naïve point of view, meaning we don’t start with a formal list of axioms. Instead, we focus on writing proofs concerning various set operations such as unions, intersections, power sets, and symmetric difference. Importantly we also explore families of indexed sets, which are crucial in studying subjects like real analysis.

Next, we study functions defined on sets that have no underlying structure. We focus our attention on domain, codomain, and set operations —emphasizing writing proofs. Then we focus our attention on one-to-one and onto functions and then characterize when a function has these properties. We also pay special attention to the composition of functions and inverse functions.

After studying sets and functions on sets, we now begin an introduction to binary relations on sets. We discuss the domain and range of a relation and the preimage, composition, and inverse of a relation. From here, we examine reflexive, symmetric, and transitive relations. We focus a great deal of attention on equivalence relations and partitions and then discuss the Fundamental Theorem of Equivalence Relations in great detail.

What You’ll Learn in Ordered Sets

Master ordered sets and learn about partial orderings, mappings on ordered sets, chain conditions, order ideals, and much more.

  • Partial Orderings
  • Up-Sets and Down-Sets
  • Closures
  • Spanning Sets
  • Bases
  • Chain Conditions
  • Order Ideals
  • Order-Preserving Mappings
  • Residuated Mappings
  • More on Closures
  • Isomorphisms
  • Max and Min with Galois Connections
  • Galois Connections
  • Closures and Dual Closures
  • Characterizations of Galois Connections
  • Semilattices and Lattices
  • Down-set Lattices
  • Sublattices
  • Lattice Morphisms
  • Complete Lattices

Chapter Description

In this course on ordered sets, we begin by detailing what a partial order relation is. We discuss up-sets and down-sets, linear independence, and bases for ordered sets. We also discuss order ideals and descending chain conditions on ordered sets. We then discuss monotone mappings, that is, mappings that preserve an ordering. Importantly, we then discuss residuated mappings and then Galois connections. We also discuss the computational aspects of Galois connections. We finish this part of the course by exploring closures and dual-closures.

In the latter part of the course, we study lattices, which are ordered sets with the meet and join operations defined in terms of the underlying ordering. We examine different kinds of lattices, including semi-lattices and complete lattices.

What You’ll Learn in Well-Founded Confluence

Master well-founded confluence. Learn well-founded relations, well-founded induction, Newman’s Lemma, and the unique normal forms property.

  • Well-Founded Induction
  • Descending Chains
  • Recursion
  • Antisymmetric and Irreflexive
  • Reduction Relations
  • Newman’s Lemma
  • Buchberger-Winkler’s Property
  • Reduction in the Integers
  • Reduction in Vector Spaces
  • Reduction in Polynomial Rings
  • What are Reduction Rings?
  • The Critical-Pair Completion Algorithm
  • Quotients of Reduction Rings
  • Sums of Reduction Rings
  • Modules over Reduction Rings
  • Polynomial Rings over Reduction Rings

Chapter Description

We begin this course by studying well-founded relations. In particular, we study well-founded recursion and well-founded induction. We also discuss anti-symmetric relations and irreflexive relations.

Next, we examine reduction relations by bringing together well-founded relations and partial ordering relations. We then examine Newman’s Lemma and the Buchberger-Winkler generalization, which discusses various types of properties for reduction relations.

Closures are an essential part of this theory. We detail the reflexive, transitive closure of a reduction relation and the reflexive, transitive closure of the symmetric closure of a reduction relation. Using well-founded confluence to study the underlying equivalence relation is emphasized.

And the next part of the course discusses various reduction structures, including reduction rings, modules over reduction rings, polynomial rings over reduction rings, and further quotients, products, and sums of reduction rings. In each of the structures, we emphasize that establishing a critical-pair completion procedure can be carried over to other algebraic structures.

Introduction to Proofs Course learning to write proofs reading working in math group

Pick-up these articles and videos on Introduction to Proofs so you can learn the invaluable skill of writing rigorous mathematical proofs for all to read.

Introduction to Proofs is a university course designed to prepare an undergraduate student for writing rigorous mathematical proofs. This course is divided into four main topics. The first is Logic and Proof, which covers propositional logic, quantifiers, mathematical proofs, and logical discourse. The second topic is Number Theory, which covers divisibility, mathematical induction, the Euclidean algorithm, and the Fundamental Theorem of Arithmetic. The third main topic is Introduction to Functions, which covers elementary set theory, families of sets, functions, one-to-one and onto functions, and composition and inverse functions. The fourth and final topic is Introduction to Relations, which covers: binary relations, equivalence relations, partial-order relations, well-founded relations, and confluent relations.