Sample · 14-Sets, Relations and Discrete Structures
Chapter 14 Overview
Book 5 — Discrete Mathematics · CHAPTER 14: Sets, Relations and Discrete Structures
"A set is a Many that allows itself to be thought of as a One." — Georg Cantor, the founder of set theory
Welcome to Book 5. Discrete mathematics is the study of structures that are counted rather than measured — and it all begins with the set, a collection of distinct objects. From sets we build everything else: relations (which objects are connected) and orders (how objects rank). These three ideas are the grammar of the entire book.
The Venn diagram above captures the first essential skill: combining sets and counting them correctly. The inclusion-exclusion formula \( |A\cup B|=|A|+|B|-|A\cap B| \) fixes the most common counting error — double-counting the overlap. From there we climb to relations, where properties like reflexive, symmetric, and transitive decide whether a relation partitions a set into equivalence classes; and to partial orders, where the notions of chain and antichain measure how much a structure can be ordered.
Three sections build the foundation: the algebra and counting of sets (14.1), the theory of relations and equivalence (14.2), and partial orders with their chains and antichains (14.3). Use the map to place a problem — and note how each layer is built from the one before.
📋 How this chapter works
The usual rhythm, tuned for discrete structures.
| Section | What it gives you |
|---|---|
| 📋 Strategy Corner | the definitions, the key counting formula, and the standard method |
| Decision flowchart | the method as a procedure, with the self-check that validates the answer |
| 🌍 Math in the Real World | where these structures power databases, logic, and computing |
| ⚠️ Common Trap | the specific way strong students lose the mark |
| Worked Example | a full solution, with the check that confirms the count or property |
| 🚀 Challenge Yourself | a harder problem with a hint but no solution |
The golden rule of this chapter: to count a combined set, never add blindly — account for overlaps. And to classify a relation, check the three properties one at a time. Discrete mathematics rewards careful bookkeeping over cleverness.
14.1 Sets
14.1 Sets
A set is an unordered collection of distinct objects, its elements. From two sets \( A,B \) we form the union \( A\cup B \) (in either), the intersection \( A\cap B \) (in both), the difference \( A\setminus B \), and the complement \( A^c \) (everything in the universe not in \( A \)). Counting combined sets is governed by inclusion-exclusion.
Three constructions build richer objects. The Cartesian product \( A\times B \) is the set of ordered pairs \( (a,b) \), with \( |A\times B|=|A|\,|B| \). The power set \( \mathcal{P}(A) \) is the set of all subsets, with \( |\mathcal{P}(A)|=2^{|A|} \). And the set identities — De Morgan’s laws, distributivity, and their kin — let you manipulate set expressions like algebra.
Continue reading — 7 chapters, worked examples and practice.
Sign in to buy