Testing whether an element is in a set takes constant time on average, while in a list the time grows with its size. We will see how set theory becomes Python code: set and frozenset, comprehension, membership and inclusion, union, intersection and difference, hashing, and practical applications.
Adding the sizes of two sets counts the intersection twice. The Inclusion-Exclusion Principle fixes the count, for two, three, or any number of sets. We will also see infinities of different sizes, derangements, and the Sieve of Eratosthenes.
Union, intersection, difference, and complement are the basic operations on sets, and they show up in SQL as UNION, INTERSECT, and EXCEPT. We see each one in Venn diagrams, along with De Morgan’s laws, distributivity, and the difference between a Venn diagram and an Euler diagram.
The collection of tall people is not a set: there is no criterion that decides, for any person, whether they belong or not. We define set, membership, roster and set-builder descriptions, equality, inclusion, and the power set.
In how many ways can you choose a valid password? What is the shortest path between two cities? These are questions of discrete mathematics. This roadmap introduces the site’s four series on the topic: sets, induction and recurrence, combinatorics, and graphs, with 28 articles.
