Discrete Mathematics Workbook

This discrete mathematics workbook comprehensively covers the standard topics taught in a sophomore-level course. These include propositional logic, forming the foundation for mathematical reasoning and proof construction; set theory, exploring concepts like unions, intersections, and power sets, crucial for understanding relationships between collections of objects; and various proof techniques, essential for establishing the validity of mathematical statements. The text also delves into basic number theory, examining properties of integers and their relationships, as well as functions and relations, understanding mappings between sets and their properties; and finally, elementary combinatorics, focusing on counting and arranging objects, with applications in diverse fields beyond mathematics. The book's approach emphasizes developing students' mathematical maturity through these fundamental concepts, laying the groundwork for advanced studies. The integration of hands-on exercises allows for immediate application and reinforcement of the learned material, fostering a deeper understanding.

A defining characteristic of this workbook is its unique spiral approach to teaching discrete mathematics. Instead of presenting each topic once and moving on, the text revisits many key concepts multiple times. This iterative approach allows students to gradually build a more profound understanding of the material. Each revisitation offers a fresh perspective, possibly introducing new techniques or a higher level of complexity. This pedagogical strategy is carefully designed to help students refine their problem-solving skills. By repeatedly encountering similar concepts in various contexts, students are given opportunities to hone their abilities and gain confidence in their understanding. This method aims to improve students’ problem-solving strategies in a gradual and natural manner, fostering resilience and adaptability in their learning process. The deliberate repetition allows for a deeper comprehension, going beyond rote memorization to a genuine understanding of the underlying principles.

The text places significant emphasis on the art and craft of writing mathematical proofs. It guides students through a detailed process, starting from the initial draft of a proof and progressing through careful revision to a polished final version. This aspect sets the book apart from others that might simply present finished proofs without showing the underlying thought process. The emphasis on clear and precise communication mirrors the standards of professional mathematical writing. Students are encouraged to write complete sentences, employ correct notation, and revise their work meticulously. This focus on the process enhances the student’s ability to both create and critically analyze mathematical arguments. By understanding the step-by-step refinement, students develop a deeper appreciation for the rigor and elegance of mathematical proofs. It addresses the practical challenges students often face when transforming their initial ideas into formally correct and comprehensible mathematical arguments.

The workbook makes a conscious effort to address the often-unwritten conventions and implicit assumptions found in mathematical writing. These subtle aspects can be particularly challenging for beginners, leading to confusion and frustration. The book tackles these challenges head-on by clearly explaining those unspoken rules and conventions that experienced mathematicians often take for granted. It provides detailed explanations of mathematical jargon and notation, bridging the gap between formal mathematical language and the student's intuitive understanding. This approach aims to make the learning process more accessible and reduce the frustration commonly experienced by students new to the field of discrete mathematics. The aim is not only to teach concepts but also to foster a deeper comprehension of the underlying structure and implicit understanding common in formal mathematical work.

While the material is suitable for both mathematics and computer science majors, the text is primarily geared towards undergraduate mathematics students. The author explicitly acknowledges the difference in needs between these two groups and intentionally prioritizes the curriculum for mathematics majors. The depth of coverage and the focus on proof writing and mathematical rigor make it a more appropriate choice for a mathematics course. The selection of examples and exercises reinforce the targeted approach, ensuring relevance and engaging the mathematical students. Even though it could be used by computer science majors for a first-semester course, it's stated that they would need a supplementary text for the second semester, thereby highlighting its specific focus and intended audience.

Harris Kwong is a mathematics professor at SUNY Fredonia. His biographical details reveal a strong academic background, including his upbringing in Hong Kong, followed by higher education in the United States. He earned both his Bachelor of Science (B.S.) and Master of Science (M.S.) degrees from the University of Michigan, and later completed his Doctor of Philosophy (Ph.D.) at the University of Pennsylvania. This robust educational foundation underscores his expertise in the field of mathematics. His current position at SUNY Fredonia further solidifies his credentials as a respected academic in the mathematical community. The trajectory of his education, from Hong Kong to prominent universities in the US, reflects a dedicated pursuit of knowledge and expertise in the mathematical sciences.

Professor Kwong's research primarily centers on three key areas within mathematics: combinatorics, number theory, and graph theory. His work has been published in numerous international mathematics journals, demonstrating a significant contribution to the advancement of mathematical knowledge in these fields. Beyond his research articles, he actively participates in the problems and solutions sections of several respected mathematical publications. These include the Mathematics Monthly, Mathematics Magazine, College Journal of Mathematics, and the Fibonacci Quarterly. This consistent contribution to these publications highlights his dedication to disseminating mathematical knowledge and his deep engagement with the wider mathematical community. His wide-ranging contributions showcase not only his research expertise, but also his commitment to engaging with and mentoring others in the field.

The author concludes his biographical section with an expression of gratitude, giving thanks and praise to God for his success. This personal statement provides insight into his values and beliefs. It adds a personal touch to the traditionally formal presentation of an author’s biography and offers a glimpse into his personal perspective on his achievements. The inclusion of this personal statement serves to humanize the author and add a layer of depth beyond his purely academic accomplishments. This closing statement underlines a personal philosophy that complements his professional success, offering a complete picture of the individual behind the academic contributions.

The author begins by acknowledging the abundance of existing discrete mathematics textbooks. He then articulates his personal motivation for creating yet another one. He notes that mathematical writing often presents a challenge to beginners due to its specialized jargon and conventions, which are frequently left for students to decipher independently. Reflecting on his own experiences, he emphasizes the importance of understanding the motivation and context behind mathematical concepts. He highlights his teaching approach which involves thorough explanations and numerous examples, a stark contrast to the typical approach of presenting only polished, concise proofs. This personal reflection lays the groundwork for the book's distinctive features, underscoring its commitment to clarity and detailed explanation, filling a gap the author identified in existing literature. The preface sets the stage for the book's unique approach: a thorough, student-centered exploration of discrete mathematics rather than a presentation of solely elegant results.

A central theme of the preface is the author's dissatisfaction with existing textbooks which, in his view, primarily present polished results without illuminating the underlying thought processes. He contrasts this with his desire to create a text that delves deeply into the nuances of mathematical concepts, offering detailed explanations and numerous examples to enhance understanding. This approach aims to demystify mathematical arguments and empower students to actively analyze mathematical problems. The author’s personal journey of creating the book, starting with supplementary lecture notes, and then expanding them into a full-fledged textbook further emphasizes this commitment. The addition of marginal notes, hands-on exercises, summaries, and section exercises at various stages showcases a commitment to iterative improvement and to student feedback within the learning process. The text’s focus is on enabling students to not just passively receive information but actively engage with the process of discovering mathematical truths.

The intended audience for the textbook is primarily mathematics majors. The author justifies this focus by explaining that the needs of mathematics majors and computer science majors, although sometimes overlapping in a first discrete mathematics course, significantly diverge in subsequent courses. Therefore, attempting to cater to both groups within a single textbook proves to be counterproductive. This decision influences the selection of examples and the depth of coverage in various topics. By focusing on mathematics majors, the author can tailor the book's content to align more effectively with the specific needs and challenges of this group. The inclusion of calculus examples, designed to help students review their prior learning and see connections to discrete mathematics, further demonstrates the targeted approach. Although suitable for a first semester discrete mathematics course for computer science majors, the text is explicitly positioned as best suited for mathematics majors who need a more in-depth treatment of foundational concepts.

Chapter 3 initiates the study of proof techniques, emphasizing that a good mathematical proof must be both correct and clearly understandable. The chapter aims to equip students with the skills to construct and present effective mathematical arguments. It stresses that writing mathematical proofs is a skill developed through practice. The chapter starts with practical suggestions, underscoring the iterative nature of proof writing – a process of drafting, revision, and refinement. The importance of clarity and precision in mathematical writing is stressed. The chapter sets the stage for a comprehensive exploration of various proof methods, emphasizing the need for clear communication and rigorous argumentation. Students are urged to actively engage with the material and practice constructing proofs themselves.

The chapter incorporates several examples to illustrate the application of proof techniques. A key example demonstrates how to prove that every positive integer can be expressed in the form 2^et, where 'e' is a non-negative integer and 't' is an odd integer. The solution method illustrates a systematic approach to proving a statement about all positive integers. The emphasis on clear, step-by-step explanations guides the reader through the logical progression of the argument. This example is typical of the detailed explanations provided throughout the chapter, enabling students to comprehend the intricate steps involved in constructing a successful mathematical proof. The inclusion of such detailed solutions allows students to understand both the final results and the thought process behind arriving at them. It encourages students to actively participate in the problem-solving process rather than simply memorizing formulas or procedures.

A significant portion of the chapter is dedicated to explaining the principle of mathematical induction, a powerful technique for proving statements about integers. The text meticulously differentiates between the weak and strong forms of mathematical induction. The weak form uses the result for n=k to prove the case for n=k+1, while the strong form uses the results for all n ≤ k to establish the case for n=k+1. The chapter uses illustrative examples to explain how to apply both forms effectively. The analogy to dominoes knocking each other down is employed to help visualize the process of induction. The explanation of mathematical induction, including its subtle nuances, is a significant contribution of this chapter, empowering students to understand and utilize this core technique in mathematical proofs. This thorough explanation includes not just the application of the principle but also its underlying logic, making it accessible even for beginners.

The chapter emphasizes the importance of polishing and refining mathematical arguments. The process of refining a proof from a draft to a final version is explicitly addressed, highlighting the need for accurate notation, complete sentences, and well-organized structure. The author shows that the initial draft often requires careful review, editing, and restructuring to achieve clarity and precision. The importance of checking for errors and ensuring the logical flow of the argument is also stressed. This focus on the iterative process of proof writing is a crucial aspect of the chapter, emphasizing that mathematical writing is a skill that improves with practice and careful attention to detail. The chapter equips students not just with techniques for creating proofs but also with the critical evaluation skills needed to produce polished, convincing mathematical arguments. Students are encouraged to go beyond just finding a solution to refining their arguments until they meet a standard of mathematical rigor.

Chapter 4 introduces the fundamental concepts of set theory, beginning with a discussion of sets and their elements. The text uses the analogy of a box to help visualize a set and its contents, clarifying the meaning of set notation using curly braces {}. It explains the difference between a set and its elements, emphasizing the importance of understanding the notation. The chapter explains how to describe sets using set builder notation, a concise and versatile method for defining sets based on properties of their elements. The chapter stresses the importance of understanding the notation and conventions used to represent sets, as this is foundational to further comprehension of set theory concepts. This introduction aims to lay a solid groundwork for students to build upon as they delve deeper into the intricacies of set theory.

Building upon the fundamental concepts, the chapter explores subsets and the power set of a set. The notion of a subset is carefully explained, clarifying the difference between membership (∈) and the subset relation (⊆). The concept of a power set, the set of all subsets of a given set, is introduced and illustrated. The chapter then moves on to describe various set operations. These include union (∪), intersection (∩), and set difference (-), explaining how these operations combine or modify sets. The discussion includes clear definitions and illustrative examples to aid understanding. The chapter emphasizes the importance of understanding the precise definitions of these operations and their implications in applying set operations to problem solving. A careful distinction between different set relationships, including subset and membership, is made to avoid common confusions.

The chapter highlights some common misconceptions that often arise in set theory. For instance, it explicitly addresses the difference between the empty set (∅) and the set containing the empty set ({∅}). It also emphasizes that the same mathematical concept may have different notations used by different authors or in different mathematical contexts. The importance of carefully examining the context and understanding the precise meaning of notations is consistently stressed. An example problem involving the computation of set intersections, unions, and differences clarifies practical application. The chapter encourages a careful approach to notation and interpretation. The inclusion of exercises also encourages students to practice these concepts and to develop a keen eye for detail in working with sets.

Chapter 5 begins by introducing the Principle of Well-Ordering, which states that every non-empty subset of natural numbers has a smallest element. This principle, while seemingly intuitive, is not easily proven using only basic arithmetic properties of natural numbers. Therefore, it is presented as an axiom. The chapter highlights the connection between this principle and the Principle of Mathematical Induction, noting that they are logically equivalent. This foundational concept is crucial in number theory, providing a basis for proving various properties of integers. The explanation makes clear that, while the idea behind well-ordering appears simple, it cannot be fully proven from basic arithmetic properties alone. This sets the stage for the importance of axioms in the development of number theory.

A key focus of the chapter is the fundamental theorem of arithmetic, also known as the unique prime factorization theorem. This theorem states that every integer greater than 1 can be represented uniquely as a product of prime numbers. The chapter presents a proof of this theorem's existence, using the principle of well-ordering. The proof is constructed through proof by contradiction. Euclid's Lemma, which states that if a prime number divides the product of two integers, then it must divide at least one of the integers, plays a crucial role in the proof. The unique prime factorization is a cornerstone of number theory, and its rigorous proof illustrates the power of proof techniques introduced earlier. The chapter demonstrates the interconnection between different core concepts in mathematics, highlighting the importance of understanding fundamental theorems and their proofs.

The chapter further explores the division algorithm, which states that for any integers a and b (with b > 0), there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b. This algorithm forms the basis for long division, a familiar process that is analyzed in more detail to clarify its underlying mathematical principles. The discussion covers different scenarios, including dividing negative integers by positive integers. The concept of the least common multiple (LCM) is then introduced with a practical application to illustrate its usefulness. The example problem of determining when two lights blinking at different intervals will blink simultaneously uses the concept of least common multiples and emphasizes how this number theoretical concept connects to seemingly different areas. The detailed discussion emphasizes the theoretical understanding behind the LCM calculation and its applications to real-world problems.

Chapter 6 begins by defining functions, emphasizing that for a function to be well-defined, the image f(x) must be unique for any given x-value. The chapter introduces key terminology: the domain, which represents the set of all permissible input values; the codomain, which represents the set of all possible output values; and the range, which is the subset of the codomain consisting of the actual output values. The distinction between the codomain and range is highlighted, as the codomain encompasses all potential outputs, while the range only includes those values that are actually produced by the function. An example is used to illustrate these concepts using a grading system. This foundational understanding is critical for working with functions and lays the groundwork for subsequent discussions on function properties.

The chapter proceeds to discuss essential properties of functions. The concepts of one-to-one (injective) and onto (surjective) functions are defined and explained with illustrative examples. A one-to-one function ensures that distinct input values always result in distinct output values. An onto function ensures that every element in the codomain is mapped to by at least one element in the domain. The chapter stresses that determining whether a given function is one-to-one or onto often requires careful consideration, especially in the context of modular arithmetic or infinite sets. This section emphasizes that these concepts, while seemingly straightforward, require careful analysis and demonstration of their properties.

The chapter proceeds to examine functions involving modular arithmetic. An example demonstrates a function with different moduli in its domain and codomain, highlighting the potential complexities and subtleties involved in such scenarios. This section serves as a warning to students to exercise caution when dealing with functions of this nature. Furthermore, the chapter touches on the challenges that can arise when dealing with functions that have infinite sets as their domains or codomains. The chapter notes that the infinite nature of such sets may yield unexpected results compared to those with finite sets. The section points out the potential pitfalls and encourages careful consideration of these unique aspects of functions involving infinite sets. It underscores that working with infinite sets requires a higher level of mathematical maturity and precision.