Chapter 5SetsSo far, we’ve been assuming only a basic understanding of sets. It’s time todiscuss sets systematically, including a useful range of constructions, opera-tions, notation, and special cases. We’ll also see how to compute the sizes ofsets and prove claims involving sets.5.1 SetsSets are an extremely general concept, defined as follows:Definition: A set is an unordered collection of obj ects.For example, the natural numbers are a set. So are the integers between3 and 7 (inclusive). So are a ll the planets in this solar system or all theprograms written by students in CS 225 in the last t hree years. The objectsin a set can be anything you want.The items in the set are called its elements or members. We’ve alreadyseen the notat ion for this: x ∈ A means that x is a member of the set A.There’s three ba sic ways to define a set:• describe its contents in mat hematical English, e.g. “the integers be-tween 3 and 7, inclusive.”52CHAPTER 5. SETS 53• list a ll its members, e.g. {3, 4, 5, 6, 7}• use so-called set builder notation, e.g. {x ∈ Z | 3 ≤ x ≤ 7}Set builder notation has two parts separated with a vertical bar or acolon. The first part names a variable (in this case x) that r anges over allobjects in the set. The second part gives one or more constraints that theseobjects must satisfy, e.g. 3 ≤ x ≤ 7. The type of the var iable (integer inour example) can be specified either before or after the vertical bar. Theseparator (| o r :) is often read “such that.”Here’s an example of a set containing an infinite number of objects• “multiples of 7”• {. . . − 14, −7, 0, 7, 14, 21, 28, . . .}• {x ∈ Z | x is a multiple o f 7}We couldn’t list a ll the elements, so we had to use “ . . .”. This is only agood idea if t he pattern will be clear to your reader. If you aren’t sure, useone of the o t her methods.If we wanted to use shorthand for “multiple of”, it might be conf using tohave | used for two different purposes. So it would probably be best to usethe colon variant of set builder not ation:{x ∈ Z : 7 | x}The notation can be used on sets containing non-numerical objects. Forexample, suppose that A = {dog, cat, tree}. Then the set {αs : α ∈ A}contains the strings dogs, cats, and trees.5.2 Things to be careful aboutA set is a n unordered collection. So {1, 2, 3} and {2, 3, 1} are two names f orthe same set. Each element occurs only once in a set. Or, alternatively, itdoesn’t matter how many times you write it. So {1, 2, 3} and {1, 2, 3, 2} alsoname the same set.CHAPTER 5. SETS 54We’ve seen ordered pairs and triples of numbers, such as (3, 4) and (4, 5, 2).The general term for an ordered sequence of k numbers is a k-tuple.1Tuplesare very different from sets, in that the order of values in a tuple mattersand duplicate elements don’t magically collapse. So (1, 2, 2, 3) 6= (1, 2, 3)and (1 , 2, 2, 3) 6= (2, 2, 1, 3). Therefore, make sure to enclose the elementsof a set in curly brackets and carefully distinguish curly brackets (set) fromparentheses (ordered pair).A mo r e subtle feature of tuples is that a tuple must contain at least twoelements. In formal mathematics, a 1-dimensional value x is just written a sx, not as (x). And there’s no such thing in mat hematics as a 0-tuple. So atuple is simply a way of grouping two o r more values into a single object.By contrast, a set is like a cardboard box, into which you can put objects.A kitty is different from a box containing a kitty. Similarly, a set containinga single object is different from the object by itself. For example, {57} is notthe same a s 57. A set can a lso contain nothing at all, like an empty box.The set containing nothing is called the empty set or the null set, and hasthe shorthand symbol ∅.2The empty set may seem like a pain in t he neck. However, computerscience applications are full of empty lists, strings of zero length, and thelike. It’s the kind of special case that all of you (even the non-theoreticians)will spend your life having to watch out for.Both sets and tuples can contain objects of more than one type, e.g.(cat, Fluffy, 1983) or {a, b, 3, 7}. A set can also contain complex objects,e.g. {(a, b), (1, 2, 3), 6} is a set containing three objects: an ordered pair, anordered tr iple, and a single number.5.3 Cardinality, inclusionIf A is a finite set (a set containing only a finite number of objects), then |A|is the number of (different) obj ects in A. This is also called the cardinality1There are latinate terms for longer sequences of numbers, e.g. quadruple, but theyaren’t used much.2Don’t write the emptyset as {}. Like a spelling mistake, this will make readers thinkless of your mathematical skills.CHAPTER 5. SETS 55of A. For example, |{a, b, 3} | = 3. And |{a, b, a, 3}| is also 3, because wecount a group of identical objects only o nce. The notation of cardinality alsoextends to sets with infinitely many members ( “infinite sets”) such as theintegers, but we won’t g et into the details of that right now.Notice that the notation |A| might mean set cardinality or it might be themore familiar absolute value. To tell which, figure out what type of objectA is. If it’s a set, the author meant cardinality. If it’s a number, the authormeant a bsolute value.If A and B are sets, then A is a subset of B (written A ⊆ B) if everyelement of A is also in B. Or, if you want it formally: ∀x, x ∈ A → x ∈ B.For example, Q ⊆ R, because every member of the rationals is also a memberof the reals.The notion of subset allows the two sets to be equal. So A ⊆ A is true f orany set A. So ⊆ is like ≤. If you want to force the two sets to be different (i.e.like <), you must say that A is a proper subset of B, written A ⊂ B. You’lloccasionally see reversed versions of these symbols to indicate the oppositerelation, e.g. B ⊇ A means the same as A ⊆ B.5.4 Vacuous truthIf we have a set A, an interesting question is whether the empty set shouldbe considered a subset of A. To answer this, let’s first back up and look atone subtlety of mathematical logic.Consider the fo llowing claim:Claim 26 For all natural numbers n, if 14 + n < 10, then n wood elves willattack Siebel Center tomorrow.I claim t his is true, a fact which most students find counter-intuitive. In fact,it wouldn’t be true if n was declared to be an integer.Notice that this statement has the form ∀n, P (n) → Q(n), where P (n) isthe predicate 14+n <