Sets

SetsMAT231Transition to Higher MathematicsFall 2014MAT231 (Transition to Higher Math)SetsFall 20141 / 31

Outline1SetsIntroductionCartesian ProductsSubsetsPower SetsUnion, Intersection, DifferenceSet ComplementVenn DiagramsIndexed SetsMAT231 (Transition to Higher Math)SetsFall 20142 / 31

Definition of setDefinitionA set is a collection of items, called elements or members. The elementsof a set may beabstract: numbers, ideas, conceptsphysical: numerals, objectsWe will usually use uppercase letters to name sets, and lower case lettersas elements. The symbol denotes membership: x A indicates that x isan element of the set A.Two sets A and B are equal if and only if they have the same elements.That is, A B if and only if every element in A is contained in B andevery element in B is contained in A.MAT231 (Transition to Higher Math)SetsFall 20143 / 31

Specifying sets: EnumerationThere are many ways to specify a set. The simplest way is to list theelements contained in the set, as in 1, 2, 3. This is called enumeration.We use braces { and } to bracket the list of elements in a set.Example{1, 2, 3}{t, u, v , w , x, y , z}{,, /}For sets, membership is all that matters and the order the elements arelisted in is insignificant. Thus {a, b, c} is the same set as {c, b, a}.MAT231 (Transition to Higher Math)SetsFall 20144 / 31

Specifying sets: EnumerationListing sets is inconvenient if there are a large number of elements inthem. If there is an easy-to-see pattern then an ellipsis can be used.Example{1, 2, 3, . . . , 10}{0, 2, 4, 6, . . .}{. . . , 5, 3, 1, 1, 3, 5, . . .}MAT231 (Transition to Higher Math)SetsFall 20145 / 31

Specifying sets: Set-builder notationSets can also be specified using set-builder notation. It provides aexpression for a typical element in the set and then one or moremembership rules.Example{x : x is an even integer}{b : b is a butterfly}MAT231 (Transition to Higher Math)SetsFall 20146 / 31

Some special setsThere are some important sets of numbers, which we now name.N {1, 2, 3, 4, . . .} is the set of natural numbers.Z {. . . , 3, 2, 1, 0, 1, 2, 3, . . .} is the set of integers.Q {x/y : x, y Z, y 6 0} is the set of rational numbersR is the set of real numbers.It is not possible to specify R using enumeration and using enumerationfor Q is extremely cumbersome. Set-builder notation, however, makesspecifying Q relatively easy.Another important set is the empty set, denoted {} or . This is the setthat contains no elements.MAT231 (Transition to Higher Math)SetsFall 20147 / 31

More examples of set-builder notationHere are some more examples using set-builder notation:Example{3n : n Z} {. . . , 6, 3, 0, 3, 6, . . .}{2n 1 : n N} {1, 2, 4, 8, 16, . . .}{x Z : x 2 5} { 2, 1, 0, 1, 2, 3, 4, 5, 6}MAT231 (Transition to Higher Math)SetsFall 20148 / 31

CardinalityThe cardinality of a set is the number of elements in the set. Thecardinality of a set X is denoted X .Example {a, b, c} 3 {x : x is a letter of the alphabet} 26 0 (this is the only set with cardinality zero) {x Z : x 2 12} 7A finite set has a finite number of elements, while a set having infinitelymany elements is called an infinite set.The cardinality of a finite set is a number; the cardinality of infinite sets isusually expressed by saying what well known infinite sets have the samecardinality.MAT231 (Transition to Higher Math)SetsFall 20149 / 31

CardinalityWhat are the cardinalities of the following sets:A {a, {b, c, d}} B {{a}, {b, c}, d} C {{a, b, c, d}} D {{a, b, {c, d}}, , { }} MAT231 (Transition to Higher Math)SetsFall 201410 / 31

CardinalityWhat are the cardinalities of the following sets:A {a, {b, c, d}} A 2B {{a}, {b, c}, d} C {{a, b, c, d}} D {{a, b, {c, d}}, , { }} MAT231 (Transition to Higher Math)SetsFall 201410 / 31

CardinalityWhat are the cardinalities of the following sets:A {a, {b, c, d}} A 2B {{a}, {b, c}, d} B 3C {{a, b, c, d}} D {{a, b, {c, d}}, , { }} MAT231 (Transition to Higher Math)SetsFall 201410 / 31

CardinalityWhat are the cardinalities of the following sets:A {a, {b, c, d}} A 2B {{a}, {b, c}, d} B 3C {{a, b, c, d}} C 1D {{a, b, {c, d}}, , { }} MAT231 (Transition to Higher Math)SetsFall 201410 / 31

CardinalityWhat are the cardinalities of the following sets:A {a, {b, c, d}} A 2B {{a}, {b, c}, d} B 3C {{a, b, c, d}} C 1D {{a, b, {c, d}}, , { }} D 3MAT231 (Transition to Higher Math)SetsFall 201410 / 31

Cartesian productsDefinitionThe Cartesian product of two sets A and B is another set, denotedA B whose elements are ordered pairs, defined byA B {(a, b) : a A, b B}ExampleIf A {a, b, c} and B {0, 1} thenA B {(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)}whileB A {(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)}Recall that the order of elements in a set is unimportant, but the order ofelements in a ordered pair is significant.MAT231 (Transition to Higher Math)SetsFall 201411 / 31

Cartesian productsIf we extend the idea of an ordered pair to an ordered triple or even anordered n-tuple then we can define the Cartesian product of three ormore sets:A B C {(a, b, c) : a A, b B, c C }W X Y Z {(w , x, y , z) : w W , x X , y Y , z Z }Notice that the following two sets are different. One is the Cartesianproduct of three sets while the other is the Cartesian product of two sets.One contains ordered triples while the other contains ordered pairs.A B C {(a, b, c) : a A, b B, c C }A (B C ) {(a, (b, c)) : a A, b B, c C }MAT231 (Transition to Higher Math)SetsFall 201412 / 31

Cartesian products as powers of setsIn some applications Cartesian products of a set with itself are common.We use the notation A2 A A to denote this. In generalAn A A · · · A {(x1 , x2 , . . . , xn ) : x1 , x2 , . . . , xn A}Example{a, b}3 {(a, a, a), (a, a, b), (a, b, a), (a, b, b),(b, a, a), (b, a, b), (b, b, a), (b, b, b)}MAT231 (Transition to Higher Math)SetsFall 201413 / 31

Cardinality of Cartesian productsQuestion: What is A B ?MAT231 (Transition to Higher Math)SetsFall 201414 / 31

Cardinality of Cartesian productsQuestion: What is A B ?Answer: A B A · B MAT231 (Transition to Higher Math)SetsFall 201414 / 31

Cardinality of Cartesian productsQuestion: What is A B ?Answer: A B A · B Justification: Every element from A must be paired with every elementfrom B.MAT231 (Transition to Higher Math)SetsFall 201414 / 31

SubsetsDefinitionSuppose A and B are sets. If every element of A is also an element of Bthen we say A is a subset of B and denote this as A B. If A is not asubset of B we write A * B. This means there is at least one element ofA that is not contained in B.ExampleWhich of the following sets are subsets of A {1, 2, 3, 4, 5, 6}?{2, 4, 6}{0, 1, 2, 3}{1, 2, 3, 4, 5, 6} MAT231 (Transition to Higher Math)SetsFall 201415 / 31

SubsetsDefinitionSuppose A and B are sets. If every element of A is also an element of Bthen we say A is a subset of B and denote this as A B. If A is not asubset of B we write A * B. This means there is at least one element ofA that is not contained in B.ExampleWhich of the following sets are subsets of A {1, 2, 3, 4, 5, 6}?{2, 4, 6} (is a subset){0, 1, 2, 3}{1, 2, 3, 4, 5, 6} MAT231 (Transition to Higher Math)SetsFall 201415 / 31

SubsetsDefinitionSuppose A and B are sets. If every element of A is also an element of Bthen we say A is a subset of B and denote this as A B. If A is not asubset of B we write A * B. This means there is at least one element ofA that is not contained in B.ExampleWhich of the following sets are subsets of A {1, 2, 3, 4, 5, 6}?{2, 4, 6} (is a subset){0, 1, 2, 3} (is not a subset, 0 not contained in A){1, 2, 3, 4, 5, 6} MAT231 (Transition to Higher Math)SetsFall 201415 / 31

SubsetsDefinitionSuppose A and B are sets. If every element of A is also an element of Bthen we say A is a subset of B and denote this as A B. If A is not asubset of B we write A * B. This means there is at least one element ofA that is not contained in B.ExampleWhich of the following sets are subsets of A {1, 2, 3, 4, 5, 6}?{2, 4, 6} (is a subset){0, 1, 2, 3} (is not a subset, 0 not contained in A){1, 2, 3, 4, 5, 6} (is a subset, equal to A) MAT231 (Transition to Higher Math)SetsFall 201415 / 31

SubsetsDefinitionSuppose A and B are sets. If every element of A is also an element of Bthen we say A is a subset of B and denote this as A B. If A is not asubset of B we write A * B. This means there is at least one element ofA that is not contained in B.ExampleWhich of the following sets are subsets of A {1, 2, 3, 4, 5, 6}?{2, 4, 6} (is a subset){0, 1, 2, 3} (is not a subset, 0 not contained in A){1, 2, 3, 4, 5, 6} (is a subset, equal to A) (is a subset - does not contain any element not in A)MAT231 (Transition to Higher Math)SetsFall 201415 / 31

The Empty set as a subsetThe last example leads to an important fact: the empty set is a subsetof every set. Thus X for all sets X .We can rephrase set equality in terms of subsets. Two sets A and B areequal if and only if A B and B A.MAT231 (Transition to Higher Math)SetsFall 201416 / 31

Listing subsetsSuppose L {w , x, y , z}. List the subsets of L.Clearly is a subset.MAT231 (Transition to Higher Math)SetsFall 201417 / 31

Listing subsetsSuppose L {w , x, y , z}. List the subsets of L.Clearly is a subset.{w }, {x}, {y }, and {z} are also subsets of L.MAT231 (Transition to Higher Math)SetsFall 201417 / 31

Listing subsetsSuppose L {w , x, y , z}. List the subsets of L.Clearly is a subset.{w }, {x}, {y }, and {z} are also subsets of L.So are {w , x}, {w , y }, {w , z}, {x, y }, {x, z}, and {y , z}. Thesesubsets all have cardinality 2.MAT231 (Transition to Higher Math)SetsFall 201417 / 31

Listing subsetsSuppose L {w , x, y , z}. List the subsets of L.Clearly is a subset.{w }, {x}, {y }, and {z} are also subsets of L.So are {w , x}, {w , y }, {w , z}, {x, y }, {x, z}, and {y , z}. Thesesubsets all have cardinality 2.{w , x, y }, {w , x, z}, {w , y , z}, and {x, y , z} are the only subsets withcardinality 3.MAT231 (Transition to Higher Math)SetsFall 201417 / 31

Listing subsetsSuppose L {w , x, y , z}. List the subsets of L.Clearly is a subset.{w }, {x}, {y }, and {z} are also subsets of L.So are {w , x}, {w , y }, {w , z}, {x, y }, {x, z}, and {y , z}. Thesesubsets all have cardinality 2.{w , x, y }, {w , x, z}, {w , y , z}, and {x, y , z} are the only subsets withcardinality 3.Finally, the only subset of cardinality 4 is the set L itself: {w , x, y , z}.MAT231 (Transition to Higher Math)SetsFall 201417 / 31

Listing subsetsWhile tedious, listing subsets is straightforward:Start with the empty set .List all the singleton subsets (sets with one element).List all possible subsets with two elements.List all possible subsets with three elements.Continue until original set itself is listed as a subset.MAT231 (Transition to Higher Math)SetsFall 201418 / 31

Power SetsDefinitionIf A is a set, the power set of A is another set, denoted P(A) and is theset of all subsets of A.P(A) {X : X A}ExampleP({a, b}) { , {a}, {b}, {a, b}}P({a, b, c}) { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}MAT231 (Transition to Higher Math)SetsFall 201419 / 31

Cardinality of power setsSuppose A is a finite set. What is the cardinality of P(A)?Notice that P( ) 1 (since P( ) { }) P({a}) 2 P({a, b}) 4 P({a, b, c}) 8Can you think of a general rule?MAT231 (Transition to Higher Math)SetsFall 201420 / 31

Cardinality of power setsSuppose A is a finite set. What is the cardinality of P(A)?Notice that P( ) 1 (since P( ) { }) P({a}) 2 P({a, b}) 4 P({a, b, c}) 8Can you think of a general rule?FactIf A is a finite set, P(A) 2 A .MAT231 (Transition to Higher Math)SetsFall 201420 / 31

Union, Intersection, DifferenceDefinitionSuppose A and B are two sets.The union of A and B is the setA B {x : x A or x B}The intersection of A and B is the setA B {x : x A and x B}The difference of A and B is the setA B {x : x A and x / B}(Sometimes A\B is used to denote set difference)MAT231 (Transition to Higher Math)SetsFall 201421 / 31