CS341 Automata TheoryMathematial Preliminaries: A Review11 SetsAsetis a olletion of ob jets. For example, the olletion of all students in the CS341ourse is a set. The olletion of the four lettersa,b,anddis a set, whih we may allS;we writeS=fa; b; ; dg. There are various ways of desribing sets:\Expliit" enumeration of al l the objets in the set.Examples:S=fa; b; g,T=f1;2;3;4;5;6;7;8;9;10g.\Impliit" enumeration of the objets in the set.Examples:A=f0;1;2;3; : : :g, whih represents the set of all non-negative integers.B=f: : : ;2;1;0;1;2; : : :g, whih represents the set of a all integers.Formal desription.Examples:P=fn:n is ev eng.Q=f4n+ 5 :n= 0;1;2; : : :g.S=fn:n3and81< m < n; n60 (mod m)g.T=f(p; q ; r; s) :p!q or r!s or p$sg.\Preise" verbal desription.Examples:Ais the set of all students in CS341.Bis the set of all leap years in the seond entury.Some sp eial symb ols denote sp eial sets.Ndenotes the set of all the Naturals (1;2;3; : : :).Zdenotes the set of all the Integers (: : : ;2;1;0;1;2; : : :).Rdenotes the set of all the Reals.Qdenotes the set of all the Rationals.The ob jets omprising a set are alled itselementsormemb ers. For example, 7 isa member ofR; in symbols, 72R. Sometimes we simply sayaisinthe setS, or thatSontainsa. On the other hand, ifbis not an element ofS, we writeb =2S.In a set we do not distinguish rep etitions of the elements. Moreover, the elements of aset are unordered. Thus,fa; a; agis the same set asfag, andfa; b; gis the same set asfb; a; g.Two sets A and B are equal if and only if they have the same elements;we writeA=B.1This material was prepared by Luay Nakhleh.1The elements of a set need not b e related in any way, and in partiular, need not b e ofthe same type. For examples, the setf10; automata;f1;29g;(x; y ; z)gontains four elements:one is an integer, one is a string, one is a set and one is a list. A set whih ontains only oneelement is alled asingleton. The set that ontains no elements is alled theempty setand is denoted by;. Any set other than the empty set is said to b enonempty.A setSis asubsetof a setT, denoted byST, if every elementaofSis also anelement ofT, i.e.,ST:8a2S,a2T.For example,NZ. However,R6N. IfSTandS6=T, we say thatSis aprop ersubsetofT, and writeST.One way of provingS=Tis by showing thatSTandTS. Theardinalityof asetS, denoted byjSj, is the number of elements inS. For example,jf2;3;9gj= 3. If the sethas an innite number of elements, then its ardinality is1. Otherwise, the setSis nite.jNj=1, for example.1.1 Op erations on setsUnion:A[B=fa:a2A or a2Bg.Intersetion:A\B=fa:a2A and a2Bg.Differene:AB=fa:a2A and b =2Bg.Complement: (always taken with resp et to a \universal" set,U)A=UA.1.2 Prop erties of set op erationsIfA,B, andCare sets, the following laws hold.Idemp otenyA[A=AA\A=ACommutativityA[B=B[AA\B=B\AAsso iativity (A[B)[C=A[(B[C)(A\B)\C=A\(B\C)DistributivityA[(B\C) = (A[B)\(A[C)A\(B[C) = (A\B)[(A\C)AbsorptionA\(A[B) =AA[(A\B) =ADeMorgan's LawsA(B[C) = (AB)\(AC)A(B\C) = (AB)[(AC)2Two sets are said to b edisjointif they have no elements in ommon, i.e., if theirintersetion is;.It is p ossible to form intersetions and unions of more than two sets. IfSis a olletion ofsets, we writeSSfor the set whose elements are the elements of the sets inS. For example,ifS=ffng:n2Ng, thenSS=N. In general,SS=fx:x2Pfor somesetP2Sg.Similarly,TS=fx:x2Pfor eahsetP2Sg.The olletion of all subsets of a setSis itself a set, alled thep ower setofSanddenoted by 2S. For example,2f1;2g=f;;f1g;f2g;f1;2gg.Apartitionof a nonempty setSis a subset of 2Ssuh that;=2, and suh thateah element ofSis in one and only one set in . That is, is a partition ofSif is a setof subsets ofSsuh that1. eah element of is nonempty.2. distint members of are disjoint.3.S =A.For example,ff1;2g;f3;4ggis a partition ofS=f1;2;3;4g, whereasff1;2g;f1;3;4ggis not a partition ofS.2 Relations and FuntionsAs mentioned b efore, elements of a set are unordered. To distinguish b etween elements ofa set, we have to \order" them. We b egin by intro duingordered pairs. We write theordered pair of two ob jetsaandbas (a; b). The ordered pair (a; b) is not the same as thesetfa; bg. First, the order matters: (a; b) is dierent from (b; a), whereasfa; bg=fb; ag.Seond, the two omponents of an ordered pair need not b e distint; (7;7) is a valid orderedpair. Note that the two ordered pairs (a; b) and (; d) are equal only whena=andb=d.TheCartesian pro dutof two setsAandB, denotedAB, is the set of all orderedpairs (a; b) witha2Aandb2B, i.e.,AB=f(a; b) :a2A and b2Bg.Abinary relationon two setsAandBis a subset ofAB. For example,f(i; j) :i; j2Nand i < jgis theless-thanrelation.More generally, letnb e any natural number. Then, ifa1; : : : ; anarenob jets, notneessarily distint, (a1; : : : ; an) is anorderedn-tuple.Afuntionffroma setAtoa setB, denoted byf:A!B, is a binary relationRonAandBwith the following sp eial prop erty: for eah elementa2A, there is exatly3one ordered pair inRwith rst omp onenta. We allAthedomainoff, and the setff(a) :a2Ag Btherangeoff.A funtionf:A!Bisone-to-oneif for any two distint elementsa; b2A,f(a)6=f(b).A funtionf:A!BisontoBif eah element ofBis the image underfof someelement inA.A funtionf:A!Bis abijetionb etweenAandBif it is both one-to-one and onto.IfQandRare binary relations, then theiromp ositionQÆR, or simplyQR, isf(q ; r) :for some, (q ; )2Qand (; r)2Rg.2.1 Sp eial types of binary relationsWe an dene a binary relation on a single set; for example,RAA. Certain prop ertiesof suh relations are:Reexivity: A binary relationRAAisreexiveif (a; a)2Rfor eaha2A.Symmetry: A binary relationRAAissymmetriif (b; a)2Rwhenever (a; b)2R.Antisymmetry: A binary relationRAAisantisymmetriif whenever (a; b)2Randaandbare distint, then (b; a)=2R.Transitivity: A binary relationRAAistransitiveif whenever (a; b)2Rand(b; )2R, then (a; )2RA binary relationRAAthat is reexive, symmetri and transitive is alled anequivalene relation.Example: The binary relationR5=f(a; b) :a; b ar e nonneg ativ e
View Full Document
Unlocking...