A Spiral Workbook for Discrete Mathematics (Kwong)

This is a text that covers the standard topics in a sophomore-level course in discrete mathematics: logic, sets, proof techniques, basic number theory, functions, relations, and elementary combinatorics, with an emphasis on motivation. It explains and clarifies the unwritten conventions in mathematics, and guides the students through a detailed discussion on how a proof is revised from its draft to a final polished form. Hands-on exercises help students understand a concept soon after learning it. The text adopts a spiral approach: many topics are revisited multiple times, sometimes from a different perspective or at a higher level of complexity. The goal is to slowly develop students’ problem-solving and writing skills.

What is discrete mathematics? Roughly speaking, it is the study of discrete objects. Here, discrete means “containing distinct or unconnected elements.” Examples include:

• Determining whether a mathematical argument is logically correct.
• Studying the relationship between finite sets.
• Counting the number of ways to arrange objects in a certain pattern.
• Analyzing processes that involve a finite number of steps.

Here are a few reasons why we study discrete mathematics:

To develop our ability to understand and create mathematical arguments.

To provide the mathematical foundation for advanced mathematics and computer science courses.

In this text, we will cover these five topics:

1. Logic and Proof Techniques. Logic allows us to determine if a certain argument is valid. We will also learn several basic proof techniques.
2. Sets. We study the fundamental properties of sets, and we will use the proof techniques we learned to prove important results in set theory.
3. Basic Number Theory. Number theory is one of the oldest branches of mathematics; it studies properties of integers. Again, we will use the proof techniques we learned to prove some basic facts in number theory.
4. Relations and Functions. Relations and functions describe the relationship between the elements from two sets. They play a key role in mathematics.
5. Combinatorics. Combinatorics studies the arrangement of objects. For instance, one may ask, in how many ways can we form a five-letter word. It is used in many disciplines beyond mathematics.

All of these topics are crucial in the development of your mathematical maturity. The importance of some of these concepts may not be apparent at the beginning. As time goes on, you will slowly understand why we cover such topics. In fact, you may not fully appreciate the subjects until you start taking advanced courses in mathematics.

This is a very challenging course partly because of its intensity. We have to cover many topics that appear totally unrelated at first. This is also the first time many students have to study mathematics in depth. You will be asked to write up your mathematical argument clearly, precisely, and rigorously, which is a new experience for most of you.

Learning how to think mathematically is far more important than knowing how to do all the computations. Consequently, the principal objective of this course is to help you develop the analytic skills you need to learn mathematics. To achieve this goal, we will show you the motivation behind the ideas, explain the results, and dissect why some solution methods work while others do not.