Unit 2: Sets
In this unit, you will explore the ideas of what is called 'naive set theory.' Contrasted with 'axiomatic set theory,' naive set theory assumes that you already have an intuitive understanding of what it means to be a set. You should mainly be concerned with how two or more given sets can be combined to build other sets and how the number of members (i.e. the cardinality) of such sets is related to the cardinality of the given sets.
Completing this unit should take you approximately 10 hours.
Upon successful completion of this unit, you will be able to:
- formally define a set using set builder notation;
- identify and explain the difference between being a member of a set and being a subset of a set;
- build new sets from existing ones using the set operations, including unions, intersections, complements, symmetric difference, Cartesian product, and relative complements;
- verify properties of sets (e.g., distributive laws, DeMorgan's laws, etc.);
- compute the power set of a given set;
- compute the cardinality of the union (intersection) of two finite sets given the cardinalities of the sets and their intersection (union); and
- determine if two sets are equivalent.
2.1: What Is a Set? Set Builder Notation
Watch this lecture, which defines sets and will familiarize you with set notation and set language.
Read these pages, which discuss the basics of set theory. Note that there are three ways to define a set. The third method, recursion, will come up again later in the course, but this is a great time to learn it.
2.1.1: The Empty Set, the Universal Set
Read pages SF-1 through SF-8 for an introduction to sets, set notation, set properties and proofs, and ordering sets.
Watch this video for an elementary introduction to set theory. This will be useful to you in case you feel uneasy about the reading above.
2.1.2: Sets with Sets as Members
Read pages SF-9 through SF-11 to learn about subsets of sets. This text also is useful for learning how to prove various properties of sets.
2.2: Building New Sets from Given Sets
Read this page, then test your understanding by working the four problems at the bottom.
2.2.1: Properties of Union, Intersection, and Complementation
Read this page. It is important that you become aware that sets combine under union and intersection in very much the same ways that numbers combine under addition and multiplication. For example,
is a way to say union is commutative in the same way as 
says addition is commutative. One difference, however, is that the properties of addition and multiplication are defined as part of the number system (in our development) whereas the properties of sets under the operations we have defined are provable and hence must be proved.Read this lecture, paying special attention to the definition of Boolean Algebra and to the isomorphism between the two systems of propositional logic and that of sets. Work the three exercises at the bottom of the PDF and then have a look at the solutions at the end of the document.
2.2.2: The (Boolean) Algebra of Subsets of a Set
2.2.3: Using Characteristic Functions to Prove Properties of Sets
Read this page. This brief text will show you how to use characteristic functions to prove properties of sets. However, there are other reasons to learn how to do this. You will see later in the course that functions (not just characteristic functions play a critical role in the theory of cardinality (set size).
2.3: The Cartesian Product of Two or More Sets
Read this page for a definition and overview of the Cartesian product of sets.
2.3.1: The Disjoint Union and Addition
2.3.2: The Cartesian Product and Multiplication
Read this page, paying special attention to the proof of proposition 3.3.3 at the end of the page. There is a nice proof of this using characteristic functions, which you will be asked to produce later in the course.
2.4: Counting Finite Sets
2.4.1: The Cardinality of the Power Set of a Set
2.4.2: The Formula |A| + |B| = |A ⋃ B| + |A ⋂ B|
Read this page, which demonstrates the basic inclusion/exclusion equation outlined in the title of this subunit. The examples on this webpage are especially interesting; pay attention to example 2, which is about playing cards.
Unit 2 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.