Contents
CHAPTER 1
Sets, Proof Templates, and Induction
1.1 Basic Definitions 1
1.1.1
Describing Sets Mathematically 2
1.1.2 Set Membership 4
1.1.3 Equality of Sets 4
1.1.4 Finite and Infinite Sets 5
1.1.5 Relations Between Sets 5
1.1.6 Venn Diagrams 7
1.1.7 Templates 8
1.2 Exercises 13
1.3 Operations on Sets 15
1.3.1 Union and Intersection 15
1.3.2 Set Difference, Complements, and DeMorgan's Laws 20
1.3.3 New Proof Templates 26
1.3.4 Power Sets and Products 28
1.3.5 Lattices and Boolean Algebras 28
1.4 Exercises 31
1.5 The Principle of Inclusion-Exclusion 34
1.5.1 Finite Cardinality 34
1.5.2 Principle of Inclusion-Exclusion for Two Sets 36
1.5.3 Principle of Inclusion-Exclusion for Three Sets 37
1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets 41
1.6 Exercises 42
vii