SetsSP22 MATH/CS 240: Discrete MathematicsUW-MadisonReference: zyBook chapter 3SP22 MATH/CS 240: Discrete Mathematics Sets 1 / 21Learning objectives1Express and interpret a set in roster notation and set-builder notation2Compute and prove properties about the complement, intersection, union,difference, Cartesian product, power set, subsets of sets3Draw and interpret Venn diagrams4Compute and prove properties about the cardinality of finite sets5Prove equality or subset relationships between sets using set identities andelement chasingSP22 MATH/CS 240: Discrete Mathematics Sets 2 / 21DefinitionA set is an unordered collection of distinct objects, called elements of the set.If a is an element of the set A, we write a ∈ A. Otherwise, we write a /∈ A.There are three ways to express a set:1Roster notation, e.g., C = {red, green, blue}2Set-builder notation, e.g., E = {n ∈ N : (∃k)(n = 2k)}3By applying set operations to other sets, e.g., S = A ∪ BTwo sets are equal if they have the same elements.How do we express A = B in terms of ∈?SP22 MATH/CS 240: Discrete Mathematics Sets 3 / 21Roster notationThe order in which we list the elements does not matter:{red, green, blue} = {green, red, blue}.Sometimes we describe a set without listing all of its elements:{1, 2, . . . , 10}is the set of all integers between 1 and 10 (inclusive).We may also list elements multiple times:{red, green, blue} = {red, blue, green, blue}.The above sets of colors are equal. If we care about the number of times anelement appears, then we should use multisets (not in the scope of this course).SP22 MATH/CS 240: Discrete Mathematics Sets 4 / 21Set-builder notationWe can think of a set as being specified by a unary predicate.For example, the predicate x > 0 with domain being the integersZ = {. . . , −1, 0, 1, . . . } specifies the set of positive integers, i.e.,{1, 2, . . . } = {x ∈ Z : x > 0}.The set of positive integers is often written as Z+or N+.Q: Which set is specified by the predicate(∃p ∈ Z)(∃q ∈ Z)(q 6= 0 ∧ x = p/q)with domain being the real numbers R?A: The rational numbers Q.SP22 MATH/CS 240: Discrete Mathematics Sets 5 / 21All or NothingDefinitionThe empty set is the set with no elements, denoted by ∅ or {}.Note that {∅} and ∅ are different sets!A set which contains some element is said to be nonempty.DefinitionThe universal set U is the set containing all objects currently under consideration.Unlike the empty set, the universal set depends on context.Intuitively:the empty set corresponds to a predicate which is always false;the universal set corresponds to a predicate which is always true.There is no set which contains all sets (Russell’s paradox).SP22 MATH/CS 240: Discrete Mathematics Sets 6 / 21Subsets and proper subsetsDefinitionA set A is a subset of a set B, and B is a superset of A, written A ⊆ B, if everyelement of A is also an element of B.A set A is a proper subset of a set B, and B is a proper superset of A, written A ( B,if A ⊆ B and A 6= B.How do we express A ⊆ B in terms of the predicates x ∈ A and x ∈ B?How do we prove a statement of the form A ⊆ B?How do we prove a statement of the form A 6⊆ B?How do we prove a statement of the form A ( B?SP22 MATH/CS 240: Discrete Mathematics Sets 7 / 21Subsets and proper subsetsFactsFor any set A, we have ∅ ⊆ A and A ⊆ A.If A ⊆ B and B ⊆ C, then A ⊆ C .A = B if and only if A ⊆ B and B ⊆ A. (This is useful for proving two sets areequal.)Notes about notation:A ⊂ B is another common way to say that A is a proper subset of B.Sometimes if A ⊆ B, we say that B contains A.Beware: this could mean either A ⊆ B or A ∈ B!Are there sets A and B such that A ⊆ B and A ∈ B?SP22 MATH/CS 240: Discrete Mathematics Sets 8 / 21Cardinality of a setDefinitionLet S be a set. If it has exactly n elements, for some n ∈ N, then we say that S isfinite and that n is the cardinality of S, written |S| = n.Example: |{∅, {∅}}| = 2.FactLet A and B be finite sets. If A ⊆ B, then |A| ≤ |B|.DefinitionIf a set is not finite, we say that it is infinite.Can we define a useful notion of cardinality for infinite sets?We will discuss this briefly after we discuss functions.SP22 MATH/CS 240: Discrete Mathematics Sets 9 / 21Operations on setsDefinitionGiven two sets A and B, we can define:A = {x : x /∈ A} (complement of A)A ∪ B = {x : x ∈ A ∨ x ∈ B} (union of A, B)A ∩ B = {x : x ∈ A ∧ x ∈ B} (intersection of A, B)A − B = {x : x ∈ A ∧ x /∈ B} (difference of A and B).Union and intersection are symmetric operations. The difference operation is notsymmetric.Exercise: Prove that in general, A − B and B − A are different sets.SP22 MATH/CS 240: Discrete Mathematics Sets 10 / 21Venn diagrams illustrating operations on setsA B A BA B A BSP22 MATH/CS 240: Discrete Mathematics Sets 11 / 21Venn diagramsVenn diagrams are useful for visualizing interactions between small numbers of sets(specifically 3 or less).They are a good way for us to discover proofs, but do not themselves constitute proofs.SP22 MATH/CS 240: Discrete Mathematics Sets 12 / 21Symmetric differenceDefinitionGiven two sets A and B, we can define their symmetric difference:A ⊕ B = {x : (x ∈ A ∧ x /∈ B) ∨ (x /∈ A ∧ x ∈ B)}or equivalently,A ⊕ B = {x : x ∈ A ⊕ x ∈ B}.A BSP22 MATH/CS 240: Discrete Mathematics Sets 13 / 21Set identitiesThe set operations we have defined satisfy certain identities, such as:Example of a set identityIf A and B are sets, thenA ∪ (A ∩ B) = A.One can prove such identities in (essentially) two ways:1Convert this identity to a biconditional/implication in propositional logic andprove that it is a tautology using laws of propositional logic. The above identitycorresponds top ∨ (p ∧ q) ↔ p. (Absorption law)(Think of p as x ∈ A and think of q as x ∈ B.)2Element chasing (next slide).SP22 MATH/CS 240: Discrete Mathematics Sets 14 / 21Proving set identities using element chasingProof of A ∪ (A ∩ B) = A by element chasing.We shall prove that A ∪ (A ∩ B) ⊆ A and A ∪ (A ∩ B) ⊇ A.First, suppose x ∈ A ∪ (A ∩ B). There are two cases.Case 1. x ∈ A. Then there is nothing to be done.Case 2. Otherwise, x ∈ A ∩ B. Then x ∈ A and x ∈ B. In particular, x ∈ A as desired.This proves that A ∪ (A ∩ B) ⊆ A.Second, suppose x ∈ A. Then x ∈ A ∪ (A ∩ B) (because a set y is an element ofA ∪ (A ∩ B) if and only if y ∈ A or y ∈ A ∩ …