Discrete Mathematics, Chapters 2 and 9: Sets, Relations ...

1 Discrete Mathematics, Chapters 2 and 9:Sets, Relations and Functions, Sequences, sums ,Cardinality of SetsRichard MayrUniversity of Edinburgh, UKRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 91 / 74 Outline1 Sets2 Relations3 Functions4 Sequences5 Cardinality of SetsRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 92 / 74 Set TheoryBasic building block for types of objects in Discrete operations in programming languages: Issues about datastructures used to represent sets and the computational cost ofset theory is the foundation of different systems of axioms have been set theory (ZF) is extended by the axiom of choice to we are not concerned with a formal set of axioms for settheory. Instead, we will use what is called naive set Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 93 / 74 SetsA set is anunorderedcollection of objects, , students in thisclass; air molecules in this objects in a set are called the elements, or members of theset.

2 A set is said to contain its notationx Sdenotes thatxis an element of the not a member ofS, writex/ Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 94 / 74 Describing a Set: Roster MethodS={a,b,c,d}.Order not importantS={a,b,c,d}={b,c,a,d}.Each distinct object is either a member or not; listing more thanonce does not change the {a,b,c,d}={a,b,c,b,c,d}.Dots .. may be used to describe a set without listing all of themembers when the pattern is {a,b,c,d,..,z}orS={5,6,7,..,20}.Do not overuse this. Patters are not always as clear as the Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 95 / 74 Some Important SetsB= Boolean values ={true,false}N= natural numbers ={0,1,2,3,..}Z= integers ={.., 3, 2, 1,0,1,2,3,..}Z+=Z 1= positive integers ={1,2,3,..}R= set of real numbersR+=R>0= set of positive real numbersC= set of complex numbersQ= set of rational numbersRichard Mayr (University of Edinburgh, UK) Discrete Mathematics.

3 Chapters 2 and 96 / 74 Set Builder NotationSpecify the property (or properties) that all members of the setmust {x|xis a positive integer less than 100}S={x|x Z+ x<100}S={x Z+|x<100}A predicate can be used, ,S={x|P(x)}whereP(x)is true iffxis a prime rational numbersQ+={x R| p,q Z+x=p/q}Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 97 / 74 Interval NotationUsed to describe subsets of sets upon which an order is defined, ,numbers.[a,b] ={x|a x b}[a,b) ={x|a x<b}(a,b] ={x|a<x b}(a,b) ={x|a<x<b}closed interval[a,b]open interval(a,b)half-open intervals[a,b)and(a,b]Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 98 / 74 Universal Set and Empty SetThe universal setUis the set containing everything currentlyunder depends on the explicitly stated, sometimes empty set is the set with no by or{}.Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 99 / 74 Russell s Paradox(After Bertrand Russell (1872 1970); Logician, mathematician andphilosopher.)

4 Nobel Prize in Literature 1950.)Naive set theory contains the set of all sets which are not members of {S |S / S } IsSa member of itself? , ,S S?Related formulation: The barber shaves all people who do not shave themselves, butno one else. Who shaves the barber? Modern formulations (such as Zerlemo-Fraenkel) avoid suchobvious problems by stricter axioms about set , it is impossible to prove in ZF that ZF is consistent(unless ZF is inconsistent).Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 910 / 74 Things to rememberSetscanbe elements of other sets, ,{{1,2,3},a,{u},{b,c}}The empty set is different from the set containing the empty set 6={ }Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 911 / 74 Subsets and Set EqualityDefinitionSetAis a subset of setBiff every element ofAis also an element ofB. Formally:A B x(x A x B)In particular, SandS Sfor every setsAandBare equal iff they have the same elements.

5 Formally:A=B A B B ,{1,5,5,5,3,3,1}={1,3,5}={3,5,1}.Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 912 / 74 Proper SubsetsDefinitionAis aproper subsetofBiffA BandA6=B. This is denoted byA Bcan be expressed by x(x A x B) x(x B x/ A)Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 913 / 74 Set CardinalityDefinitionIf there are exactlyndistinct elements in a setS, wherenis anonnegative integer, we say thatSis finite. Otherwise it is cardinality of a finite setS, denoted by|S|, is the number of(distinct) elements :| |=0 LetSbe the set of letters of the English alphabet. Then|S|=26.|{1,2,3}|=3|{ }|=1 The set of integersZis Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 914 / 74 Power SetsDefinitionThe set of all subsets of a setSis called thepower is denoted byP(S)or :P(S) ={S |S S}In particular,S P(S)and P(S).Example:P({a,b}) ={ ,{a},{b},{a,b}}If|S|=nthen|P(S)|=2n.

6 Proof by induction onn; see later Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 915 / 74 TuplesThe orderedn-tuple(a1,a2,..,an)is the ordered collection ofnelements, wherea1is the first,a2the second, etc., andanthen-th( , the last).Twon-tuples are equal iff their corresponding elements are equal.(a1,a2,..,an) = (b1,b2,..,bn) a1=b1 a2=b2 an=bn2-tuples are called ordered Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 916 / 74 Cartesian ProductDefinitionThe Cartesian product of two setsAandB, denoted byA B, is theset of all ordered pairs(a,b)wherea Aandb B={(a,b)|a A b B}DefinitionThe Cartesian product ofnsetsA1, ,An, denoted byA1 A2 An, is the set of all tuples(a1,a2,..,an)whereai Aifori=1,.., A2 An={(a1,a2,..,an)|ai Aifori=1,2,..,n}Example: What isA B CwhereA={0,1},B={1,2}andC={0,1,2}.Soluti on:A B C={(0,1,0),(0,1,1),(0,1,2),(0,2,0),(0,2, 1),(0,2,2),(1,1,0),(1,1,1),(1,1,2),(1,2, 0),(1,2,1),(1,1,2)}Richard Mayr (University of Edinburgh, UK) Discrete Mathematics.

7 Chapters 2 and 917 / 74 Truth Sets and Characteristic PredicatesWe fix a (x)be a predicate onU. The truth set ofPis the subset ofUwherePis true.{x U|P(x)}LetS Ube a subset ofU. The characteristic predicate ofSisthe predicatePthat is true exactly onS, ,P(x) x SRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 918 / 74 Set Operations: Union, Intersection, ComplementGiven a domainUand two setsA, union of two setsA,Bis defined byA B={x|x A x B}.General union of several sets:A1 An={x|x A1 x An}The intersection of two setsA,Bis defined byA B={x|x A x B}.General intersection of several sets:A1 An={x|x A1 x An}The complement defined byA={x U|x/ A}Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 919 / 74 Set DifferenceDefinitionThe difference between setsAandB, denotedA Bis the setcontaining the elements ofAthat are not inB. Formally:A B={x|x A x/ B}=A BA Bis also called the complement differencebetween setsAandB, denotedA4 Bisthe set containing the elements ofAthat are not inBor :A4B={x|x A xor x B}= (A B) (B A)A4B= (A B) (A B).

8 Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 920 / 74 Cardinality of Finite Derived Sets|A B|=|A|+|B| |A B|In particular,|A B| |A|+|B|.|A B| |A||A B| |B||A B| |A||A4B|=?Clicker1|A|+|B|2|A|+|B| |A B|3|A|+|B| 2|A B|4|A|+|B|+|A B|5|A|+|B|+2|A B|6|A|+|B| |A B||A|+|B| 2|A B|Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 921 / 74 Cardinality of Finite Derived Sets|A B|=|A|+|B| |A B|In particular,|A B| |A|+|B|.|A B| |A||A B| |B||A B| |A||A4B|=?Clicker1|A|+|B|2|A|+|B| |A B|3|A|+|B| 2|A B|4|A|+|B|+|A B|5|A|+|B|+2|A B|6|A|+|B| |A B||A|+|B| 2|A B|Richard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 921 / 74 Set IdentitiesIdentity lawsA =A A U=ADomination lawsA U=U A = Idempotent lawsA A=A A A=AComplementation law(A) =AComplement lawsA A= A A=URichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 922 / 74 Set Identities (cont.)

9 Commutative lawsA B=B A A B=B AAssociative lawsA (B C) = (A B) CA (B C) = (A B) CDistributive lawsA (B C) = (A B) (A C)A (B C) = (A B) (A C)Absorption lawsA (A B) =A A (A B) =ADe Morgan s lawsA B=A BA B=A BRichard Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 923 / 74 RelationsDefinitionGiven setsA1,..,An, a subsetR A1 Anis ann-ary : DatabaseRcontains tuples (Street name, House number,currently inhabited flag), ,R Strings N B. SoRis a setsAandB,R A Bis a binary relation property(x,y) Ris also written :R R Zwhere(x,y) Riffy=bxc(rounding down).DefinitionR A Ais called a relation : Z Zis the less or equal relation on the Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 924 / 74 Relations and MatricesA binary relationR A Bcan be described by a boolean matrix(and vice-versa).Define a boolean matrixM. Index its rows over setAand itscolumns of (a,b) =Tiff(a,b) Mayr (University of Edinburgh, UK) Discrete Mathematics.

10 Chapters 2 and 925 / 74 Properties of Binary RelationsA binary relationR A Ais calledReflexive iff x(x,x) RSymmetric iff x,y((x,y) R (y,x) R)Antisymmetric iff x,y((x,y) R (y,x) R x=y)Transitive iff x,y,z((x,y) R (y,z) R (x,z) R).Examples: and=are reflexive, but<is symmetric, but is not. is :=is also antisymmetric, ,=is symmetric andantisymmetric.<is also antisymmetric, since the precondition of the implicationis always ,R={(x,y)|x+y 3}is not antisymmetric, since(1,2),(2,1) three,=, and<are {(x,y)|y=2x}is not Mayr (University of Edinburgh, UK) Discrete Mathematics. Chapters 2 and 926 / 74 Binary Relations : ExampleLetR={(x,y) Z+ Z+| k Z+y=kx}Clicker: IsR1reflexive, symmetric, transitive2not reflexive, antisymmetric, not transitive3reflexive, not antisymmetric, transitive4reflexive, symmetric, not transitive5reflexive, antisymmetric, transitive6reflexive, not symmetric, not transitiveRichard Mayr (University of Edinburgh, UK) Discrete Mathematics.