Mathematical Reasoning and Discrete Math
TODOs
I still need to
- Finish remaining chapters until completing the discussion of number theory.
- Add videos.
- Clean the bottom of the main page.
- Give every chapter a consolidated set of definitions and theorems at the top. Also give every page a set of extra exercises.
- Write theorems with "premises" and "conclusion" indicators.
- Write a section on program preconditions and postconditions.
- Include a section on philosophy.
- Meaning in mathematics does not exist without our defining it. For example there is no such thing as an "infinitely large number" unless we define it in some precise way. The number 0.999... does not exist until we define it first.
Welcome and Feedback
Welcome to this course in mathematical reasoning! This website delivers a one-quarter semester course. Put briefly, this semester covers naive set theory, logic, and number theory. There will be a part 2, assuming I eventually finish part 1.
If you see mistakes in this website, please let me know! You can open an issue at the GitHub repo: GitHub Math Reason.
Not only that, but if you find anything confusing or just have editorial feedback, you can always let me know! I especially want to hear feedback from people who are trying to learn the subject for the first time, so that I can make the material easier to learn. Just remember that the more specific and constructive your feedback is, the more I am able to act on it.
Content
This is a course on university-level mathematics, designed to prepare first-year students for the techniques that are used throughout the rest of their mathematical careers.
The subject of this course is really two-fold: It has both domain knowledge, as well as mathematical technique.
The domain knowledge that this course covers includes
-
Number theory
-
Rational, real, and complex numbers
-
Sets and formal logic
-
Type theory
-
Relations
-
Functions
-
Combinatorics
-
Recursion
-
Matrices
-
Graphs
-
Algorithms
But besides learning substantive topics in mathematics, this course also aims to teach how to reason about mathematics. Therefore this course includes parallel lessons in
-
Direct and indirect proof
-
Proof by cases
-
Proof by contradiction
-
Counterexamples
-
Diagrammatic reasoning
-
Induction
-
The pigeonhole principle
-
Proof of correctness
The content of this text is very similar to other texts on discrete mathematics, with a few exceptions. Most discrete math texts have less content than I have included on formal logic. They also do not discuss type theory and the lambda calculus, which are usually in the domain of computer science.
Because I have in mind an audience of mathematics majors, I have included these topics because I think it will help them throughout their mathematical careers.
Structure
The structure of this text is intended to be unlike the usual mathematics textbook, in a number of ways.
- I want to have a thorough coverage of formal and informal logic, since the intent is to train future mathematicians. The main tool of mathematics is logic.
- Chapter 1 gives a case study in how logic is used in the study of mathematics. In particular I show the use of logic to study elementary number theory. As we later discuss logic, the reader can apply all of the broad and abstract lessons of logic, to the concrete example of number theory.
- Where possible I try to explain not just the proofs of theorems, but how to write the proofs of theorems. That means explaining writing style, structure, and discovery of proofs.
- This resource provides an "theorem assistant". This is very similar to Lean, but written in Python, and it places a higher priority on making proofs readable even when written in code. This is helpful for understanding the logic and level of detail in which proofs should be written.
Advice on Studying
The most important advice that I can give you about how to study this subject, and how to study more generally, is: be curious, and be tough.
Go into this with the understanding that it will be hard and confusing. No author will ever be able to make advanced mathematics easy. I hope to make it more accessible with this text, but studying mathematical reasoning will still demand that the reader is up for a challenge and a time commitment.
But if you genuinely find the ideas interesting, take heart! You can learn them with enough exercise. Do not be intimidated by notation or abstraction. With time, exposure, focus, and use of these ideas, what initially seems obscure can come to feel natural and clear.
Being curious and wanting to know this content is necessary to keep you motivated. You'll need to be so motivated that, when you are inevitably frustrated by something you don't immediately understand, you will spend minutes, hours, or even days living in that confusion. You'll find that your endurance grows, as if you were a long distance runner.
But notices what I emphasized: This becomes possible with enough exercise. Not enough reading, not enough thinking. There is a famous saying in mathematics,
A mathematician reads with a pencil in her hand.
Every mathematician, whenever reading any new piece of mathematics, always finds exercises, or makes up their own exercises to ensure that they fully understand what they are reading. You should begin to develop the same habit.
This text puts exercises throughout the body of the text, as well as after each chapter. The exercises inside the body are intended to be quick, direct, easy. That doesn't mean they will take no time. Just that they are intended to be a easy as I can make them while still exercising what is necessary.
Do not rely just on the exercises that I provide here. These exercises are intended to be minimal to ensure understanding. I don't want to give too many exercises, if you're already understanding the material well, and would benefit from just getting in with it. But if you find that you struggle with any exercise, then you should make up more exercises until you solve them with mastery. If you cannot think of exercises to give yourself, then seek out exercises written by someone else. That could mean exercises that I have written after the end of the chapter. You could also seek out other resources, like asking an AI for an unlimited number of similar exercises, or using another textbook as a supplement to this one.
The exercises at the end of the chapter are intended to be more challenging: They don't just make sure that you've understood what you've read, like the exercises in the middle of the chapter do. They ask you to become increasingly creative, thinking beyond merely what you've been told. You will have to find solutions to problems, for which you haven't seen the solution to perfectly similar examples. This is unavoidable with many proofs of theorems: once a theorem is proved, there is not necessarily another theorem that is similar enough to act as a direct exercise of the same ideas and methods.
Chapters
Chapter 0: The Bare Necessities of Sets and Functions
Chapter 1: A Case Study in Number Theory
Chapter 2: Syntax and Semantics
Chapter 3: Propositional Logic, Syntax and Semantics
Chapter 4: Propositional Proof Theory
Chapter 5: Predicate Syntax and Semantics
Chapter 6: First-order Logic, Syntax and Semantics
Chapter 7: Applications of First-order Logic
Old content (do not look, they will eventually be deleted):
Chapter 4: Predicate Syntax and Semantics
Chapter 5: Terms and Equality, Syntax, Semantics, Proofs
Chapter 6: Quantifier Syntax and Semantics
Chapter : Quantifier Proof Theory
Chapter : Induction and Recursion
Chapter : Functions and Cardinality
Chapter : The Pigeonhole Principle
Chapter : Axiomatic Arithmetic