DOC PREVIEW
OSU CSE 2321 - Sets

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 ifthe sets are pairwise disjoint,thatis,Si;Sj2 S and i ¤ j imply Si\SjD;,andtheir 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 [ BjDjAjCjBjjA \ Bj; (B.3)from which we can conclude thatjA [ BjjAjCjBj:If A and B are disjoint, thenjA \ BjD 0 and thusjA [ BjDjAjCjBj.IfA  B,thenjAjjBj.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; bgfa; b; cgDf.a; a/; .a; b/; .a; c/; .b; a/; .b; b/; .b; c/g.WhenA and B are finite …


View Full Document

OSU CSE 2321 - Sets

Documents in this Course
Load more
Download Sets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?