An introduction to Set Theory as the foundation of Discrete Mathematics:
definitions, operations (union, intersection, complement), Venn diagrams, the
Inclusion-Exclusion Principle and cardinality, with practical examples in Python
and SQL.
The articles are listed below, in the order they were written.
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.
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.
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.
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.
