B Sets, Etc.Many chapters of this book touch on the elements of discrete mathematics. Thisappendix reviews more completely the notations, definitions, and elementary prop-erties of sets, relations, functions, graphs, and trees. If you are already well versedin this material, you can probably just skim this chapter.B.1 SetsA set is a collection of distinguishable objects, called its members or elements.Ifan object x is a member of a set S, we write x 2 S (read “x isamemberofS”or, more briefly, “x is in S”). If x is not a member of S, we write x 62 S.Wecan describe a set by explicitly listing its members as a list inside braces. Forexample, we can define a set S to contain precisely the numbers 1, 2,and3 bywriting S Df1; 2; 3g.Since2 is a member of the set S, we can write 2 2 S,andsince 4 is not a member, we have 4 … S. A set cannot contain the same object morethan once,1and its elements are not ordered. Two sets A and B are equal, writtenA D B, if they contain the same elements. For example,f1; 2; 3; 1gDf1; 2; 3gDf3; 2; 1g.We adopt special notations for frequently encountered sets:; denotes the empty set, that is, the set containing no members.Z denotes the set of integers, that is, the setf:::;2;1; 0; 1; 2; : : :g.R denotes the set of real numbers.N denotes the set of natural numbers, that is, the setf0; 1; 2; : : :g.21A variation of a set, which can contain the same object more than once, is called a multiset.2Some authors start the natural numbers with 1 instead of 0. The modern trend seems to be to startwith 0.B.1 Sets 1159If all the elements of a set A are contained in a set B,thatis,ifx 2 A impliesx 2 B, then we write A B and say that A is a subset of B. A set A is aproper subset of B, written A B,ifA B but A ¤ B. (Some authors use thesymbol “” to denote the ordinary subset relation, rather than the proper-subsetrelation.) For any set A,wehaveA A. For two sets A and B,wehaveA D Bif and only if A B and B A. For any three sets A, B,andC ,ifA Band B C ,thenA C . For any set A,wehave;A.We sometimes define sets in terms of other sets. Given a set A, we can define aset B A by stating a property that distinguishes the elements of B. For example,we can define the set of even integers byfx W x 2 Z and x=2 is an integerg.Thecolon in this notation is read “such that.” (Some authors use a vertical bar in placeof the colon.)Given two sets A and B, we can also define new sets by applying set operations:The intersection of sets A and B is the setA \ B Dfx W x 2 A and x 2 Bg:The union of sets A and B is the setA [ B Dfx W x 2 A or x 2 Bg:The difference between two sets A and B is the setA B Dfx W x 2 A and x … Bg:Set operations obey the following laws:Empty set laws:A \; D ;;A [; D A:Idempotency laws:A \ A D A;A [ A D A:Commutative laws:A \ B D B \ A;A [ B D B [ A:1160 Appendix B Sets, Etc.AAAAAABBBBB.B \ C/ [[DDDDA .B \ C/ .A B/ .A C/CCCCCFigure B.1 A Venn diagram illustrating the first of DeMorgan’s laws (B.2). Each of the sets A, B,and C is represented as a circle.Associative laws:A \ .B \ C/ D .A \ B/ \ C;A [ .B [ C/ D .A [ B/ [C:Distributive laws:A \ .B [ C/ D .A \ B/ [.A \ C/ ;A [ .B \ C/ D .A [ B/ \.A [ C/ :(B.1)Absorption laws:A \ .A [ B/ D A;A [ .A \ B/ D A:DeMorgan’s laws:A .B \ C/ D .A B/ [ .A C/ ;A .B [ C/ D .A B/ \ .A C/ :(B.2)Figure B.1 illustrates the first of DeMorgan’s laws, using a Venn diagram: a graph-ical picture in which sets are represented as regions of the plane.Often, all the sets under consideration are subsets of some larger set U called theuniverse. For example, if we are considering various sets made up only of integers,the set Z of integers is an appropriate universe. Given a universe U ,wedefinethecomplement of a set A asA D U A Dfx W x 2 U and x 62 Ag. For any setA U , we have the following laws:A D A;A \A D;;A [A D U:B.1 Sets 1161We can rewrite DeMorgan’s laws (B.2) with set complements. For any two setsB;C U ,wehaveB \ C D B [ C;B [ C D B \ C:Two sets A and B are disjoint if they have no elements in common, that is, ifA \B D;. A collection S DfSigof nonempty sets forms a partition of a set S ifthe sets are pairwise disjoint,thatis,Si;Sj2 S and i ¤ j imply Si\SjD;,andtheir union is S,thatis,S D[Si2SSi:In other words, S forms a partition of S if each element of S appears in exactlyone Si2 S .The number of elements in a set is the cardinality (or size) of the set, denotedjSj.Two sets have the same cardinality if their elements can be put into a one-to-onecorrespondence. The cardinality of the empty set isj;jD 0. If the cardinality of aset is a natural number, we say the set is finite; otherwise, it is infinite. An infiniteset that can be put into a one-to-one correspondence with the natural numbers N iscountably infinite; otherwise, it is uncountable. For example, the integers Z arecountable, but the reals R are uncountable.For any two finite sets A and B, we have the identityjA [ BjDjAjCjBjjA \ Bj; (B.3)from which we can conclude thatjA [ BjjAjCjBj:If A and B are disjoint, thenjA \ BjD 0 and thusjA [ BjDjAjCjBj.IfA B,thenjAjjBj.A finite set of n elements is sometimes called an n-set.A1-set is called asingleton. A subset of k elements of a set is sometimes called a k-subset.We denote the set of all subsets of a set S, including the empty set and S itself,by 2S; we call 2Sthe power set of S. For example, 2fa;bgDf;;fag;fbg;fa; bgg.The power set of a finite set S has cardinality 2jSj(see Exercise B.1-5).We sometimes care about setlike structures in which the elements are ordered.An ordered pair of two elements a and b is denoted .a; b/ and is defined formallyas the set .a; b/ Dfa;fa; bgg. Thus, the ordered pair .a; b/ is not thesameastheordered pair .b; a/.1162 Appendix B Sets, Etc.The Cartesian product of two sets A and B, denoted A B, is the set of allordered pairs such that the first element of the pair is an element of A and thesecond is an element of B. More formally,A B Df.a; b/ W a 2 A and b 2 Bg:For example,fa; bgfa; b; cgDf.a; a/; .a; b/; .a; c/; .b; a/; .b; b/; .b; c/g.WhenA and B are finite …
View Full Document