A Spiral Workbook for Discrete Mathematics


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.


1 An Introduction

1.1 An Overview

1.2 Suggestions to Students

1.3 How to Read and Write Mathematics

1.4 Proving Identities

2 Logic

2.1 Propositions

2.2 Conjunctions and Disjunctions

2.3 Implications

2.4 Biconditional Statements

2.5 Logical Equivalences

2.6 Logical Quantifiers

3 Proof Techniques

3.1 An Introduction to Proof Techniques

3.2 Direct Proofs

3.3 Indirect Proofs

3.4 Mathematical Induction: An Introduction

3.5 More on Mathematical Induction

3.6 Mathematical Induction: The Strong Form

4 Sets

4.1 An Introduction

4.2 Subsets and Power Sets

4.3 Unions and Intersections

4.4 Cartesian Products

4.5 Index Sets

5 Basic Number Theory

5.1 The Principle of Well-Ordering

5.2 Division Algorithm

5.3 Divisibility

5.4 Greatest Common Divisors

5.5 More on GCD

5.6 Fundamental Theorem of Arithmetic

5.7 Modular Arithmetic

6 Functions

6.1 Functions: An Introduction

6.2 Definition of Functions

6.3 One-to-One Functions

6.4 Onto Functions

6.5 Properties of Functions

6.6 Inverse Functions

6.7 Composite Functions

7 Relations

7.1 Definition of Relations

7.2 Properties of Relations

7.3 Equivalence Relations

7.4 Partial and Total Ordering

8 Combinatorics

8.1 What is Combinatorics?

8.2 Addition and Multiplication Principles

8.3 Permutations

8.4 Combinations

8.5 The Binomial Theorem

A Solutions to Hands-On Exercises
B Answers to Selected Exercises

Harris Kwong

Harris Kwong is a mathematics professor at SUNY Fredonia. He was born and raised in Hong Kong. After finishing high school there, he came to the United States to further his education. He received his B.S. and M.S. degrees from the University of Michigan, and Ph.D. from the University of Pennsylvania. His research focuses on combinatorics, number theory, and graph theory. His work appears in many international mathematics journals. Besides research articles, he also contributes frequently to the problems and solutions sections of Mathematics Monthly, Mathematics Magazine, College Journal of Mathematics, and Fibonacci Quarterly. He gives thanks and praises to God for his success.