Chapter 5 Sets So far we ve been assuming only a basic understanding of sets It s time to discuss sets systematically including a useful range of constructions operations notation and special cases We ll also see how to compute the sizes of sets and prove claims involving sets 5 1 Sets Sets are an extremely general concept defined as follows Definition A set is an unordered collection of objects For example the natural numbers are a set So are the integers between 3 and 7 inclusive So are all the planets in this solar system or all the programs written by students in CS 225 in the last three years The objects in a set can be anything you want The items in the set are called its elements or members We ve already seen the notation for this x A means that x is a member of the set A There s three basic ways to define a set describe its contents in mathematical English e g the integers between 3 and 7 inclusive 52 CHAPTER 5 SETS 53 list all 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 a colon The first part names a variable in this case x that ranges over all objects in the set The second part gives one or more constraints that these objects must satisfy e g 3 x 7 The type of the variable integer in our example can be specified either before or after the vertical bar The separator or 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 of 7 We couldn t list all the elements so we had to use This is only a good idea if the pattern will be clear to your reader If you aren t sure use one of the other methods If we wanted to use shorthand for multiple of it might be confusing to have used for two different purposes So it would probably be best to use the colon variant of set builder notation x Z 7 x The notation can be used on sets containing non numerical objects For example suppose that A dog cat tree Then the set s A contains the strings dogs cats and trees 5 2 Things to be careful about A set is an unordered collection So 1 2 3 and 2 3 1 are two names for the same set Each element occurs only once in a set Or alternatively it doesn t matter how many times you write it So 1 2 3 and 1 2 3 2 also name the same set CHAPTER 5 SETS 54 We 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 1 Tuples are very different from sets in that the order of values in a tuple matters and 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 elements of a set in curly brackets and carefully distinguish curly brackets set from parentheses ordered pair A more subtle feature of tuples is that a tuple must contain at least two elements In formal mathematics a 1 dimensional value x is just written as x not as x And there s no such thing in mathematics as a 0 tuple So a tuple is simply a way of grouping two or 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 containing a single object is different from the object by itself For example 57 is not the same as 57 A set can also contain nothing at all like an empty box The set containing nothing is called the empty set or the null set and has the shorthand symbol 2 The empty set may seem like a pain in the neck However computer science applications are full of empty lists strings of zero length and the like 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 an ordered triple and a single number 5 3 Cardinality inclusion If A is a finite set a set containing only a finite number of objects then A is the number of different objects in A This is also called the cardinality 1 There are latinate terms for longer sequences of numbers e g quadruple but they aren t used much 2 Don t write the emptyset as Like a spelling mistake this will make readers think less of your mathematical skills CHAPTER 5 SETS 55 of A For example a b 3 3 And a b a 3 is also 3 because we count a group of identical objects only once The notation of cardinality also extends to sets with infinitely many members infinite sets such as the integers but we won t get into the details of that right now Notice that the notation A might mean set cardinality or it might be the more familiar absolute value To tell which figure out what type of object A is If it s a set the author meant cardinality If it s a number the author meant absolute value If A and B are sets then A is a subset of B written A B if every element 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 member of the reals The notion of subset allows the two sets to be equal So A A is true for any 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 ll occasionally see reversed versions of these symbols to indicate the opposite relation e g B A means the same as A B 5 4 Vacuous truth If we have a set A an interesting question is whether the empty set should be considered a subset of A To answer this let s first back up and look at one subtlety of mathematical logic Consider the following claim Claim 26 For all natural numbers n if 14 n 10 then n wood elves will …