Gallier J., Quaintance J. Mathematical Foundations And Aspects of Discrete Mathematics

University of Pennsylvania, 2022. - 713 p.This is a book about discrete mathematics that also discusses mathematical reasoning and logic. Since the publication of the first edition of this book a few years ago, we came to realize that for a significant number of readers, it is their first exposure to the rules of mathematical reasoning and to logic.As a consequence, the version of Chapter 1 from the first edition may be a bit too abstract and too formal for those readers, and they may find this discouraging. To remedy this problem, we have written a new version of the first edition of Chapter 1. This new chapter is more elementary, more intuitive, and less formal. It also contains less material, but as in the first edition, it is still possible to skip Chapter 1 without causing any problem or gap, because the other chapters of this book do not depend on the material of Chapter 1.In this second edition, we tried to make the exposition simpler and clearer. We added some figures, some examples, clarified certain definitions, and simplified some proofs. A few changes and additions were also made.In Chapter 2 we added a section (Section 2.12) which describes the Haar transform on sequences in an elementary fashion as a certain bijection. We also show how the Haar transform can be used to compress audio signals (see Section 2.13). This is a spectacular and concrete illustration of the abstract notion of a bijection.We created a separate chapter (Chapter 3) dealing with the set-theoretical notions of equinumerosity, finite, countable, and infinite sets. In this new chapter we discuss the pigeonhole principle more extensively. In particular, we discuss the Frobenius coin problem (and its special case, the McNuggets number problem). we also created a new section on finite and infinite sets (Section 3.3).Chapter 5 of the first edition has been split into two chapters: Chapter 5, on partial orders, well-founded orderings, and lattices.Chapter 7, on Unique Prime Factorization in Z and GCDs, Fibonacci and Lucas Numbers, Public Key Cryptography and RSA.This way, the foundational material is contained in Chapter 1 (which can be omitted by readers familiar with basic mathematical reasoning and logic) and Chapters 2–5.Chapters 6–10 cover the core of discrete mathematics. In Chapter 6, we added some problems on the Stirling numbers of the first and of the second kind. We also added a Section (Section 6.7) on Mobius inversion. The chapters devoted to graph theory now appear consecutively. This makes it easier to recall concepts introduced in Chapter 9 when reading Chapter 10.In Chapter 10 we discuss more advanced topics requiring some linear algebra: cocycles, cotrees, flows, and tensions, matchings, coverings, and planar graphs. We also discuss the network flow problem and prove the max-flow min-cut theorem in an original way due to M. Sakarovitch.We added some problems and supplied some missing proofs here and there. Of course, we corrected a bunch of typos.