[PDF] Lecture Notes on Discrete Mathematics

View - Download Lecture Notes on Discrete Mathematics

Previous PDF

Next PDF

DRAFTLecture Notes on Discrete Mathematics

July 30, 2019

DRAFT2

DRAFTContents

1 Basic Set Theory7

1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1.5 Composition of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

1.6 Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2 The Natural Number System 25

2.1 Peano Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.2 Other forms of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . .

28

2.3 Applications of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . .

31

2.4 Well Ordering Property of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . .

33

2.5 Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.6 Construction of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

2.7 Construction of Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

3 Countable and Uncountable Sets 43

3.1 Finite and innite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.2 Families of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

3.3 Constructing bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.4 Cantor-Schroder-Bernstein Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3.5 Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

4 Elementary Number Theory 61

4.1 Division algorithm and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

4.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

4.3 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

68

5 Combinatorics - I 71

5.1 Addition and multiplication rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

5.2 Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

5.2.1 Counting words made with elements of a setS. . . . . . . . . . . . . . . . . .73

5.2.2 Counting words with distinct letters made with elements of a setS. . . . . . .74

5.2.3 Counting words where letters may repeat . . . . . . . . . . . . . . . . . . . . .

75

5.2.4 Counting subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

5.2.5 Pascal's identity and its combinatorial proof . . . . . . . . . . . . . . . . . . . .

77
3

DRAFT4CONTENTS

5.2.6 Counting in two ways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

78

5.3 Solutions in non-negative integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

5.4 Binomial and multinomial theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

5.5 Circular arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.6 Set partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

5.7 Number partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

5.8 Lattice paths and Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

6 Combinatorics - II 103

6.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

103

6.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .

107

6.3 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

110

6.3.1 Generating Functions and Partitions ofn. . . . . . . . . . . . . . . . . . . . .116

6.4 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

119

6.5 Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . . . .

124

7 Introduction to Logic 133

7.1 Logic of Statements (SL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

133

7.2 Formulas and truth values in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

134

7.3 Equivalence and Normal forms in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . .

137

7.4 Inferences in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

143

7.5 Predicate logic (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

149

7.6 Equivalences and Validity in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

153

7.7 Inferences in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

156

8 Partially Ordered Sets, Lattices and Boolean Algebra 161

8.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

161

8.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

169

8.3 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

176

8.4 Axiom of choice and its equivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

181

9 Graphs - I191

9.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

191

9.2 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

197

9.3 Isomorphism in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

200

9.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

202

9.5 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

208

9.6 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

210

9.7 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

214

9.8 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

215

9.9 Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

219

10 Graphs - II221

10.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

221

10.2 Matching in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

223

10.3 Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

226

10.4 Degree sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

227

DRAFTCONTENTS5

10.5 Representing graphs with matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

228

11 Polya Theory

231

11.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

231

11.2 Lagrange's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

240

11.3 Group action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

244

11.4 The Cycle index polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

248

11.5 Polya's inventory polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

251

Index258

DRAFT6CONTENTS

DRAFTChapter 1

Basic Set Theory

The following notations will be followed throughout the book. 1. The empt yset, denoted ?, is the set that has no element.

2.N:=f1;2;:::g, the set of Natural numbers;

3.W:=f0;1;2;:::g, the set of whole numbers

4.Z:=f0;1;1;2;2;:::g, the set of Integers;

5.Q:=fpq

:p;q2Z; q6= 0g, the set of Rational numbers;

6.R:= the set of Real numbers; and

7.C:= the set of Complex numbers.

This chapter will be devoted to understanding set theory, relations, functions. We start with the basic

set theory.

1.1 Sets

Mathematicians over the last two centuries have been used to the idea of considering a collection of

objects/numbers as a single entity. These entities are what are typically called sets. The technique of

using the concept of a set to answer questions is hardly new. It has been in use since ancient times.

However, the rigorous treatment of sets happened only in the 19-th century due to the German math- ematician Georg Cantor. He was solely responsible in ensuring that sets had a home in mathematics. Cantor developed the concept of the set during his study of the trigonometric series, which is now known as the limit point or the derived set operator. He developed two types of transnite numbers, namely, transnite ordinals and transnite cardinals. His new and path-breaking ideas were not well received by his contemporaries. Further, from his denition of a set, a number of contradictions and paradoxes arose. One of the most famous paradoxes is the Russell's Paradox, due to Bertrand Russell in 1918. This paradox amongst others, opened the stage for the development of axiomatic set theory.

The interested reader may refer to Katz [8].

In this book, we will consider the intuitive or naive view point of sets. The notion of a set is taken

as a primitive and so we will not try to dene it explicitly. We only give an informal description of sets and then proceed to establish their properties. A \well-dened collection" of distinct objects can be considered to be a set. Thus, the principal property of a set is that of \membership" or \belonging". Well-dened, in this context, would enable us to determine whether a particular object is a member of a set or not. 7

DRAFT8CHAPTER 1. BASIC SET THEORY

Members of the collection comprising the set are also referred to as elements of the set. Elements of a set can be just about anything from real physical objects to abstract mathematical objects. An important feature of a set is that its elements are \distinct" or \uniquely identiable." A set is typically expressed by curly braces,f genclosing its elements. IfAis a set andais an element of it, we writea2A. The fact thatais not an element ofAis written asa62A. For instance, ifAis the setf1;4;9;2g, then 12A;42A;22Aand 92A. But 762A; 62A, the English word `four' is not inA, etc. Example 1.1.1.1.Let X=fapple;tomato;orangeg. Here, orange2X, but potato62X.

2.X=fa1;a2;:::;a10g. Then,a10062X.

3. Observ ethat t hesets f1;2;3g,f3;1;2gandfdigits in the number 12321gare the same as the order in which the elements appear doesn't matter. We now address the idea of distinctness of elements of a set, which comes with its own subtleties. Example 1.1.2.1.Consider the list of digits 1 ;2;1;4;2. Is it a set? 2. Let X=f1;2;3;4;5;6;7;8;9;10g. ThenXis the set of rst 10 natural numbers. Or equivalently,

Xis the set of integers between 0 and 11.

Denition 1.1.3.The setSthat contains no element is called theempty setor thenull setand is denoted byf gor?. A set that has only one element is called asingleton set. One has three main ways for specifying a set. They are: 1. Listing all its elemen ts(list n otation),e.g.,X=f2;4;6;8;10g. ThenXis the set of even integers between 0 and 12. 2. Stating a p ropertywith notation (predicate notation), e.g., (a)X=fx:xis a prime numberg. This is read as \Xis the set of allxsuch thatxis a prime number". Here,xis a variable and stands for any object that meets the criteria after the colon. (b) The set X=f2;4;6;8;10gin the predicate notation can be written as i.X=fx: 0< x10;xis an even integerg, or ii.X=fx: 1< x <11;xis an even integerg, or iii.x=fx: 2x10;xis an even integergetc. Note that the above expressions are certain rules that help in dening the elements of the set X. In general, one writesX=fx:p(x)gorX=fxjp(x)gto denote the set of all elementsx (variable) such that propertyp(x) holds. In the above, note that \colon" is sometimes replaced by \j". 3. Dening a set of rules whic hgenerate its mem bers(recursiv enotation), e.g., let

X=fx:xis an even integer greater than 3g:

Then,Xcan also be specied by

(a) 4 2X, (b) whenev erx2X, thenx+ 22X, and (c) ev eryelemen tof Xsatises the above two rules.

DRAFT1.2. OPERATIONS ON SETS9

In the recursive denition of a set, the rst rule is the basis of recursion, the second rule gives a method to generate new element(s) from the elements already determined and the third rule binds or restricts the dened set to the elements generated by the rst two rules. The third rule should always be there. But, in practice it is left implicit. At this stage, one should make it explicit.

Denition 1.1.4.LetXandYbe two sets.

1. Supp oseXis the set such that wheneverx2X, thenx2Yas well. Here,Xis said to be a subsetof the setY, and is denoted byXY. When there existsx2Xsuch thatx62Y, then we say thatXis not a subset ofY; and we writeX6Y. 2. If XYandYX, thenXandYare said to beequal, and is denoted byX=Y. 3.

If XYandX6=Y, thenXis called aproper subsetofY.

Thus,Xis a proper subset ofYif and only ifXYandX6=Y. Example 1.1.5.1.F oran yset X, we see thatXX. Thus,??. Also,?X. Hence, the empty set is a subset of every set. It thus follows that there is only one empty set. 2.

W ekno wth atNWZQRC.

3.

Note that ?62?.

4.

Let X=fa;b;cg. Thena2Xbutfag X. Also,ffagg 6X.

5. Notice that ffagg 6 fagandfag 6 ffagg; thoughfag 2 fa;faggand alsofag fa;fagg. We now mention some set operations that enable us in generating new sets from existing ones.

1.2 Operations on sets

Denition 1.2.1.LetXandYbe two sets.

1. The unionofXandY, denoted byX[Y, is the set that consists of all elements ofXand also all elements ofY. More specically,X[Y=fxjx2Xorx2Yg. 2. The intersectionofXandY, denoted byX\Y, is the set of all common elements ofXand

Y. More specically,X\Y=fxjx2Xandx2Yg.

3.

The sets XandYare said to bedisjointifX\Y=?.

Example 1.2.2.1.Let A=f1;2;4;18gandB=fx:xis an integer;0< x5g. Then,

A[B=f1;2;3;4;5;18gandA\B=f1;2;4g:

2.

Let S=fx2R: 0x1gandT=fx2R::5x <7g. Then,

S[T=fx2R: 0x <7gandS\T=fx2R::5x1g:

3.

Let X=ffb;cg;ffbg;fcgg;bgandY=fa;b;cg. Then

X\Y=fbgandX[Y=fa;b;c;fb;cg;ffbg;fcgg g:

We now state a few properties related to the union and intersection of sets.

Lemma 1.2.3.LetR;SandTbe sets. Then,

1. (a) S[T=T[SandS\T=T\S(union and intersection are commutative operations).

DRAFT10CHAPTER 1. BASIC SET THEORY

(b)R[(S[T) = (R[S)[TandR\(S\T) = (R\S)\T(union and intersection are associative operations). (c)SS[T; TS[T. (d)S\TS; S\TT. (e)S[?=S; S\?=?. (f)S[S=S\S=S. 2. Distributive laws (c ombinesunion and i ntersection): (a)R[(S\T) = (R[S)\(R[T)(union distributes over intersection). (b)R\(S[T) = (R\S)[(R[T)(intersection distributes over union). Proof.2a. Letx2R[(S\T). Then,x2Rorx2S\T. Ifx2Rthen,x2R[Sandx2R[T. Thus,x2(R[S)\(R[T). Ifx62R, thenx2S\T. So,x2Sandx2T. Here,x2R[Sand x2R[T. Thus,x2(R[S)\(R[T). In other words,R[(S\T)(R[S)\(R[T). Now, lety2(R[S)\(R[T). Then,y2R[Sandy2R[T. Now, ify2R[Sthen either y2Rory2Sor both. Ify2R, theny2R[(S\T). Ify62Rthen the conditionsy2R[Sandy2R[Timply thaty2S andy2T. Thus,y2S\Tand hencey2R[(S\T). This shows that (R[S)\(R[T)R[(S\T),

and thereby proving the rst distributive law. The remaining proofs are left as exercises.Exercise1.2.4.1.Complete the pr oofof L emma1.2.3.

2.

Pr ovethe fol lowing:

(a)S[(S\T) =S\(S[T) =S. (b)STif and only ifS[T=T. (c)

If RTandSTthenR[ST.

(d)

If RSandRTthenRS\T.

(e)

If STthenR[SR[TandR\SR\T.

(f)

If S[T6=?then eitherS6=?orT6=?.

(g)

If S\T6=?then bothS6=?andT6=?.

(h)S=Tif and only ifS[T=S\T.

Denition 1.2.5.LetXandYbe two sets.

1. The set dierenceofXandY, denoted byXnY, is dened byXnY=fx2X:x62Yg. 2. The set ( XnY)[(YnX), denoted byXY, is called thesymmetric dierenceofXandY. Example 1.2.6.1.Let A=f1;2;4;18gandB=fx2Z: 0< x5g. Then,

AnB=f18g; BnA=f3;5gandAB=f3;5;18g:

2.

Let S=fx2R: 0x1gandT=fx2R: 0:5x <7g. Then,

SnT=fx2R: 0x <0:5gandTnS=fx2R: 1< x <7g:

3.

Let X=ffb;cg;ffbg;fcgg;bgandY=fa;b;cg. Then

DRAFT1.3. RELATIONS11

In naive set theory, all sets are essentially dened to be subsets of some reference set, referred to as the universal set, and is denoted byU. We now dene the complement of a set. Denition 1.2.7.LetUbe the universal set andXU. Then, thecomplementofX, denoted by X c, is dened byXc=fx2U:x62Xg.

We state more properties of sets.

Lemma 1.2.8.LetUbe the universal set andS;TU. Then,

1.Uc=?and?c=U.

2.S[Sc=UandS\Sc=?.

3.S[U=UandS\U=S.

4.(Sc)c=S.

5.SScif and only ifS=?.

6.STif and only ifTcSc.

7.S=Tcif and only ifS\T=?andS[T=U.

8.SnT=S\TcandTnS=T\Sc.

9.ST= (S[T)n(S\T).

10.

De-Mor gan'sL aws:

(a)(S[T)c=Sc\Tc. (b)(S\T)c=Sc[Tc. The De-Morgan's laws help us to convert arbitrary set expressions into those that involve only complements and unions or only complements and intersections. Exercise1.2.9.LetSandTbe subsets of a universal setU. 1.

Then pr oveL emma1.2.8.

2.

Supp osethat ST=T. IsS=??

Denition 1.2.10.LetXbe a set. Then, the set that contains all subsets ofXis called thepower setofXand is denoted byP(X) or 2X. Example 1.2.11.1.Let X=?. ThenP(?) =P(X) =f?;Xg=f?g. 2.

Let X=f?g. ThenP(f?g) =P(X) =f?;Xg=f?;f?gg.

3. Let X=fa;b;cg. ThenP(X) =f?;fag;fbg;fcg;fa;bg;fa;cg;fb;cg;fa;b;cgg. 4. Let X=ffb;cg;ffbg;fcggg. ThenP(X) =f?;ffb;cgg;fffbg;fcggg;ffb;cg;ffbg;fcggg g.

1.3 Relations

In this section, we introduce the set theoretic concepts of relations and functions. We will use these

concepts to relate dierent sets. This method also helps in constructing new sets from existing ones.

DRAFT12CHAPTER 1. BASIC SET THEORY

Denition 1.3.1.LetXandYbe two sets. Then their Cartesian product, denoted byXY, is dened asXY=f(a;b) :a2X;b2Yg. The elements ofXYare also calledordered pairs with the elements ofXas the rst entry and elements ofYas the second entry. Thus, (a1;b1) = (a2;b2) if and only ifa1=a2andb1=b2:

Example 1.3.2.1.Let X=fa;b;cgandY=f1;2;3;4g. Then

2. The Euclidean plan e,denoted b yR2=RR=f(x;y) :x;y2Rg. 3. By con vention,?Y=X?=?. In fact,XY=?if and only ifX=?orY=?. Remark 1.3.3.LetXandYbe two nonempty sets. Then,XYcan also be dened as follows: Letx2Xandy2Yand think of (x;y) as the setffxg;fx;ygg,i.e., we have a new set in which an

element (a set formed using the rst element of the ordered pair) is a subset of the other element (a set

formed with both the elements of the ordered pair). Then, with the above understanding, the ordered pair (y;x) will correspond to the setffyg;fx;ygg. As the two setsffxg;fx;yggandffyg;fx;yggare not the same, the ordered pair (x;y)6= (y;x). Exercise1.3.4.LetX;Y;ZandWbe nonempty sets. Then, prove the following statements: 1. The pr oductc onstructionc anb euse don sets sever altimes, e.g.,

XYZ=f(x;y;z) :x2X;y2Y;z2Zg= (XY)Z=X(YZ):

2.X(Y[Z) = (XY)[(XZ).

3.X(Y\Z) = (XY)\(XZ).

4.(XY)\(ZW) = (X\Z)(Y\W).

5.(XY)[(ZW)(X[Z)(Y[W). Give an example to show that the converse need not

be true. 6. Is it p ossibleto write the set T=f(x;x;y) :x;y2Ngas Cartesian product of3sets? What about the the setT=f(x;x2;y) :x;y2Ng? A relation can be informally thought of as a property which either holds or does not hold between two objects. For example,xis taller thanycan be a relation. However, ifxis taller thany, theny cannot be taller thanx. Denition 1.3.5.LetXandYbe two nonempty sets. ArelationRfromXtoYis a subset of XY,i.e., it is a collection of certain ordered pairs. We writexRyto mean (x;y)2RXY. Thus, for any two setsXandY, the sets?andXYare always relations fromXtoY. A relation fromXtoXis called arelation onX. Example 1.3.6.1.Let Xbe any nonempty set and consider the setP(X). Dene a relationR onP(X) byR=f(S;T)2 P(X) P(X) :STg. 2.

Let A=fa;b;c;dg. Some relationsRonAare:

(a)R=AA.

DRAFT1.3. RELATIONS13

(c)R=f(a;a);(b;b);(c;c)g. (d)R=f(a;a);(a;b);(b;a);(b;b);(c;d)g. (f)R=f(a;b);(b;c);(a;c);(d;d)g. (i)R=f(a;a);(b;b);(c;c);(a;b);(b;c)g. Sometimes, we draw pictures to have a better understanding of dierent relations. For example, to draw pictures for relations on a setX, we rst put a node for each elementx2Xand label itx. Then, for each (x;y)2R, we draw a directed line fromxtoy. If (x;x)2Rthen a loop is drawn atx. The pictures for some of the relations is given in Figure 1.1.a b c d A!A a b c d

Example2.b

a b c d

Example2.c

1Figure 1.1: Pictorial representation of some relations from Example 2

3. Let A=f1;2;3g,B=fa;b;cgand letR=f(1;a);(1;b);(2;c)g. Figure 1.2 represents the relationR.1 1 3 2 a b c RFigure 1.2: Pictorial representation of the relation in Example 3 4. Let R=f(x;y) :x;y2Zandy=x+5mfor somem2Zgis a relation onZ. If we try to draw a picture for this relation then there is no arrow between any two elements off1;2;3;4;5g. 5. Fix n2N. LetR=f(x;y) :x;y2Zandy=x+nmfor somem2Zg. Then,Ris a relation onZ. A picture for this relation has no arrow between any two elements off1;2;3;:::;ng.1 We use pictures to help our understanding and they are not parts of proof.

DRAFT14CHAPTER 1. BASIC SET THEORY

Denition 1.3.7.LetXandYbe two nonempty sets and letRbe a relation fromXtoY. Then, theinverse relation, denoted byR1, is a relation fromYtoX, dened byR1=f(y;x)2YX: (x;y)2Rg. So, for allx2Xandy2Y (x;y)2Rif and only if (y;x)2R1: Example 1.3.8.1.If R=f(1;a);(1;b);(2;c)gthenR1=f(a;1);(b;1);(c;2)g. 2. Let R=f(a;b);(b;c);(a;c)gbe a relation onA=fa;b;cgthenR1=f(b;a);(c;b);(c;a)gis also a relation onA. LetRbe a relation fromXtoY. Consider an elementx2X. It is natural to ask if there exists y2Ysuch that (x;y)2R. This gives rise to the following three possibilities: 1. ( x;y)62Rfor ally2Y. 2.

There is a unique y2Ysuch that (x;y)2R.

3. There exists at least t woelemen tsy1;y22Ysuch that (x;y1);(x;y2)2R. One can ask similar questions for an elementy2Y. To accommodate all these, we introduce a notation in the following denition. Denition 1.3.9.LetRbe a nonempty relation fromXtoY. Then, 1. the set domR:=fx: (x;y)2Rgis called thedomain ofR1, andquotesdbs_dbs47.pdfusesText_47

[PDF] 3 4 equivalent in cooking

[PDF] 3 as bac

[PDF] 3 commerce private colege in bbsr

[PDF] 3 commerce syllabus

[PDF] 3 ejemplos de indice

[PDF] 3 eme svt genetique

[PDF] 3 exemple qui illustre la puissance mondiale des etat unis

[PDF] 3 membranes de l'oeil

[PDF] 3*500 bac 2015

[PDF] 3*500 bac bareme 2017

[PDF] 3-d maths symbols

[PDF] 3.3.2 maintien opérationnel des postes de travail et aménagement des espaces

[PDF] 31 laminas del tat

[PDF] 31 laminas del tat para imprimir

[PDF] 31 laminas del tat pdf