What if the foundation that all of mathematics is built upon isn’t as firm as we thought it was?
Note: The natural numbers sometimes include zero and sometimes don’t — it depends on how you define it. Within logic, zero is always included as a natural number.
The mathematical material covered includes the basics of number theory (including unique factorization, congruences, the distribution of primes, and quadratic reciprocity) and of abstract algebra (including groups, rings, fields, and vector spaces). It also includes an introduction to discrete probability theory—this material is needed to properly treat the topics of probabilistic algorithms and cryptographic applications.
This textbook contains the content of a two semester course in discrete structures, which is typically a second-year course for students in computer science or mathematics, but it does not have a calculus prerequisite. The material for the first semester is in chapters 1-10 and includes logic, set theory, functions, relations, recursion, graphs, trees, and elementary combinatorics. The second semester material in chapters 11-16 deals with algebraic structures: binary operations, groups, matrix algebra, Boolean algebra, monoids and automata, rings and fields.