[PDF] Cartesian Products and Relations Definition (Cartesian product) If A

View - Download Cartesian Products and Relations Definition (Cartesian product) If A

Previous PDF

Next PDF

Cartesian Products and Relations

Denition (Cartesian product)IfAandBare sets, theCartesian productofAandB is the set

AB=f(a;b) : (a2A) and (b2B)g.

The following points are worth special attention: The Cartesian product of two sets is a set, and the elements of that set are ordered pairs. In each ordered pair, the rst component is an element ofA, and the second component is an element ofB.

Example (Cartesian product)IfA=ff1;2g;f3ggand

B=f(a;b);(c;d)g, then

DeterminingjABj.IfAandBare nite sets, thenjABj=jAjjBjbecause there are jAjchoices for the rst component of each ordered pair and, for each of these,jBjchoices for the second component of the ordered pair. Cartesian Product is not commutativeFor the setsAandBone paragraph above, This example shows that, in general,AB6=BA. The underlying reason is that ifA andBare non-empty and one set, sayA, contains an elementxwhich is not inB, then ABcontains an ordered pair with rst component equal tox, butBAcontains no such ordered pair. The condition thatAandBare non-empty is required because of the following Proposition.

Proposition CPR1. IfAis a set, thenA ;=;and; A=;.

Proof.

We argue by contradiction using the denition of Cartesian product: SupposeA ; 6=;and consider (x;y)2A ;. Then, by denition of Cartesian product,y2 ;, a contradiction. Therefore, the setA ;must be empty. The proof that; A=;is similar, and is left as anexercise.Proposition CPR2. IfAandBare sets,AB=BAif and only ifA=B, orA=;, orB=;.

Proof.

(() IfA=Bthen substitutingBforAgivesAB=AA=BA. IfA=;or

B=;, then by Proposition CP1,AB=;=BA.

()) Suppose thatAandBare non-empty sets andAB=BA. Letx2A. Since B6=;, there exists an elementy2B, so that (x;y)2AB. SinceAB=BA, we have that (x;y)2BA(too). By the denition of Cartesian product,x2B. Therefore,

AB. SimilarlyBA. Thus,A=B.It is sometimes true that the Cartesian product distributes over other set operations

similarly to the distributive law of multiplication over addition. 1

Proposition CPR3. LetA;BandCbe sets. Then,

(a)A(B\C) = (AB)\(AC); (b)A(B[C) = (AB)[(AC); (c) (A\B)C= (AC)\(BC); (d) (A[B)C= (AC)[(BC).

Proof.

We prove part (b) and leave the proofs of the remaining parts as anexercise. We have (x;y)2A(B[C),x2Aandy2B[C,(x2A) and (y2Bory2C) ,[(x2A) and (y2B)] or [(x2A) and (y2C)] (by a distributive law of logic)

,[(x;y)2AB] or [(x;y)2AC],(x;y)2(AB)[(AC).Exercise. Investigate, and prove or disprove as appropriate, similar statements involving

the set operations relative complement (AB), and symmetric dierence. Denition (relation).Arelation from a setAto a setBis a subset ofAB. A(binary) relation onAis a subset ofAA. It is important to remember that a relation is a set or ordered pairs. There need be no relationship between the components of the ordered pairs;anyset of ordered pairs is a relation. Usually, however, we choose which ordered pairs belong to the relation so that components are related in some way, so we think of the relation as somehow representing the connection. For example, ifA=fGary;Jing;KeikagandB=f7447;7448;7455g, thenR=f(Gary;7448);(Jing;7447);(Keika;7455)gis a relation fromAtoBthat pairs each UVic Math instructor in setAand her/his UVic telephone extension in setB. Counting relations.Since any subset ofABis a relation fromAtoB, it follows that ifAandBare nite sets then the number of relations fromAtoBis 2jABj= 2jAjjBj. One way to see this is as the number of subsets ofAB. A direct way to count is the same way one counts subsets: observe that for each of thejABj=jAjjBjordered pairs inABthere are two possibilities, either the ordered pair belongs to the relation or it doesn't, so by the rule of product the number of relations fromAtoBis 222 2 (jAj jBjtwos). Similarly, ifAis a nite set then the number of relations onAis 2jAjjAj. LetA=f1;2;:::10g. By the above, there are 2100relations onA. The number of these that contain the pairs (1;1);(2;2);:::;(10;10) is 110290= 290: each of the 10 specied pairs must be in the relation (1 way to do this), and there are two possibilities { in or not { for each of the remaining 90 pairs. Similar reasoning shows that the number of relations onAthat contain none of (1;2);(3;4);(5;6) is 297. The number of relations onAthat contain (2;5) or (7;9) is 2100298(total minus the number that contain neither ordered pair). A dierent way of counting these gives the equivalent expression 2

99+ 299298

(the number that contain (2;5) plus number that contain (7;9) minus the number that contain both). Finally, the number of relations onAthat contain either (2;5) or (7;9) but not both is 2

98+ 298(the number that contain (2;5) and not (7;9) plus the number that

contain (7;9) and not (2;5)). 2 Example (less than or equal to relation)The relationRon the setA=f1;2;3ggiven by

R=f(1;1);(1;2);(1;3);(2;2);(2;3);(3;3)g

is the set of all ordered pairs (a;b) of elements ofAsuch thataband we can think of the setRas representing the \less than or equal to" relation. Inx notation for relations.IfRis a relation onAand (a;b)2R, we sometimes use the inx notationaRband say \ais related tob(underR)". Ifais not related tobunder R, we sometimes use the inx notation with a slash through theR. Example (subset relation, inx notation).LetB=fa;b;cgand letSbe the relation onP(B) (thepower setofB, i.e. the set of all subsets ofB) dened byXSY,XY. That is, a subsetXofBis related to a subsetYofBunderSexactly whenXis a subset ofY. The symbolScan be regarded as a synonym for the symbolor, alternatively, the symbolcould be regarded as the name of the set of all ordered pairs (X;Y) where

X;Y2 P(B) andXis a subset ofY.

Example (recursively dened relations).Relations are sets (of ordered pairs), and thus can sometimes be dened recursively. For example, letDbe the relation onZ+(the positive integers) dened by:

BASIS: 1R5;

RECURSION: For allx;y2Z+, ifxRythen (x+ 1)R(y+ 5). After generating a few terms, it is not diculy to guess and prove that R=f(a;b)2Z+Z+:b= 5ag. The statement to be proved isP(a):An ordered pair (a;b)belongs toRif and only ifb= 5a. We rst prove by induction onathatifa2Z+andb= 5a, then(a;b)2R: BASIS (a= 1): (1;5)2Rby denition ofR. Thus, the statement is true fora= 1. INDUCTION HYPOTHESIS: For somek1, suppose that ifn= 5kthen (k;n)2R. INDUCTION STEP: Supposem= 5(k+ 1). Thenm5 = 5k, so by the induction hypothesis (k;m5)2R. By the denition ofR;(k;m5)2R)(k+1;m5+5)2R.

Thus, ifm= 5(k+ 1), then (k+ 1;m)2R.

Therefore, by induction, for alla2Z+, ifa2Z+andb= 5a, then (a;b)2R. To complete the proof, we show by induction onathatif(a;b)2Rthenb= 5a: BASIS (a= 1): By denition ofR, the only ordered pair inRwith rst component equal to 1 is (1;5). Since 5 = 51, the statement is true fora= 1. INDUCTION HYPOTHESIS: For somek1, suppose that if (k;n)2R, thenn= 5k. INDUCTION STEP: Suppose (k+ 1;m)2R. By denition ofR, this can happen only if (k;m5)2R. By the induction hypothesis,m5 = 5k. Hencem= 5k+ 5 = 5(k+ 1).

Thus, if (k+ 1;m)2R, thenm= 5(k+ 1).

Therefore, by induction, for alla2Z+, if (a;b)2Rthenb= 5a. For a more dicult example, consider the relationSonZ+dened by:

BASIS: (1;2);(1;3)2S;

RECURSION: For allx;y2Z+, if (x;y)2Sthen (x+ 1;y+ 2);(x+ 1;y+ 3)2S. Exercise: Prove by induction thatS=f(k;n)2Z+Z+: 2kn3kg. 3

Functions

Denition (function). Afunction from a setAto a setBis a relationffromAto Bwith the property that for every elementa2Athere exists one and only one element b2Bsuch that (a;b)2f. Denition (image, value, preimage). Iffis a function fromAtoB, then we use the notationf:A!B. >From the denition of a function iff:A!B, thenfcan be viewed as an assignment, to each elementa2A, of a unique elementbinB. If (a;b)2f, then we denote the assignment ofbtoaby writingb=f(a) and callingbthe image ofa underf, or thevalue offat (a); the elementais called apreimageofb. (Note that it is apreimage rather thanthepreimage; more than one element ofAcould map tob.) It is common usage to say \fmapsAtoB". This expression arises from the usual arrow diagram where each element ofAis joined by an arrow to the element ofBassigned to it. Unfortunately, this tends to lead to the confusion that the elements ofAare somehow assigned to the elements ofB,which is backwards!It is the elements ofBthat are assigned to the elements ofA. It is important to keep the following facts straight. Every element ofAhas some element ofBassigned to it. No element ofAis assigned more than one element ofB, each is assignedexactly one. There is no guarantee that dierent elements ofAare assigned dierent elements ofB. When we say that each element ofAis assigned a unique element ofB, we mean that each element ofAis assigned one and only one elemnt ofB. This does notmean that ifa16=a2, thenf(a1)6=f(a2); it is quite possible thatf(a1) =f(a2) (We have a special name for functions with the property thata16=a2impliesf(a1)6=f(a2):

1-1.) There is no guarantee that any particular element ofBis assigned to any element

ofA. (We have a special name for functions with the property that every element ofBis the image of at least one element ofA: onto.) Denition (domain, inputs, codomain, range). Before we can talk about functions, we need names for the objects we want to talk about: The setAis called thedomain, and the elements ofAare calledinputstof(so the domain is where the inputs live).

The setBis called thecodomain.

The subset ofBconsisting of the elements which are values off(i.e., are assigned to some element inA) is called therange off. (Think: the values offrange over the elements in this set.) The range offis the setf(A) =fb:b2Bandb=f(a) for somea2Ag. Example (function, domain, codomain, range, image, preimage). LetAbe the set of all faculty and students at UVic, and letBbe the set of all amounts of money in dollars and cents. Letfbe the relation fromAtoBwhere (a;b)2f,persona2A owes amountbto the library. Since for every persona2Athere is a unique amount of money that s/he owes to the library (possibly $0),fis a function. The domain offisA, its codomain isB, and its range is the set of all amounts of money that are owed (each by at least one person). If (Gary, $1:59)2f, thenf(Gary) = $1:59, the image of Gary 4 is $1:59, a pre-image of $1:59 is Gary, and the amount $1:59 belongs to the range off. (Note: any person who owes $1:59 to the library is also a pre-image of $1:59.) The above example demonstrates a function which can not be dened by \giving a formula" forf(a). In the denition of functionAandBare just sets { there don't have to be any numbers anywhere { so it may be very dicult to give a formula. Example (function, domain, codomain, range, image, preimage). Letf:R!R dened byf(x) = 2dxe. (Recall that, for a real numberx,the ceiling ofx, denoteddxe is the smallest integer which is greater than or equal tox. Hencefis a function.) The domain offis the setRof real numbers. The codomain is also the set of real numbers. The range offis the set of even integers: sincedxeis an integer,f(x) = 2dxeis an even integer. Thus, the range is a subset of the even integers. To see that every even integer

2t;(t2Z) is a value off, observe that fort2Z,f(t) = 2dte= 2t.

Exercises. We leave as an exercise for the reader to determine the range of the function g:R!Rdened byg(x) =bxc2. (Recall that for a real numberx,the oor ofx, denoted bxcis the largest integer which is less than or equal tox.) For more exercises, nd the range ofh:R!Rdened byh(x) =b2xc, and show that the range of`:Z!Zdened by`(n) =n2+ 4n+ 4 isfk2:k2Ng=f02;12;22;:::g. Counting functions. LetAandBbe nite sets, sayA=fa1;a2;:::;amgandB= fb1;b2;:::;bng. We count the number of functions fromAtoB. By the denition of function, for eacha2Athere is exactly oneb2Bsuch that (a;b)2f. Thus, there aren choices for the element to be paired witha1,nchoices for the element to be paired with a

2, and so on. In general, for each choice forathere aren=jBjchoices for the element

bsuch that (a;b)2f. By the rule of product, the number of functions fromAtoBis thereforenn n(mterms, all equal ton), which equalsnm(orjBjjAj). Denition (image of a set, preimage of a set). The notions of image and preimage can be generalized to sets. Supposef:A!Bis a function. IfA1A, thenthe image of A

1underfis the set

f(A1) =fb2B:b=f(a) for somea2A1g. That is,f(A1) is the set whose elements are the images underfof the elements inA1. If B

1B, thenthe preimage ofB1underfis the set

f

1(B1) =fa2A:f(a)2B1g.

That is,f1(B1) is the set of elements inAwhose image underfis inB1. Example (image of a set, preimage of a set). LetA=f1;2;3;4;5g;B=fa;b;c;dg andf:A!Bbe given by f=f(1;d);(2;a);(3;c);(4;a);(5;c)g. Thenf(f1;2;3g) =fd;a;cg, andf1(fd;a;cg) =f1;2;3;4;5g. Notice that this shows that iff(A1) =B1then it need not be the case thatf1(B1) =A1; it is however, true that iff(A1) =B1, thenf1(B1)A1. (To see this, lety2B1. theny=f(x) for somex2A1. Hencex2f1(B1).) We leave it as anexerciseto prove that equality occurs, that isf1(f(A1)) =A1, if and only if there is no elementa2AA1such that f(a)2f(A1). As a furtherexercise, prove that forB1Bwe havef(f1(B1))B1, 5 with equality if and only ifB1is a subset of the range off(that is, every element ofB1 is the image of some element ofA). Observe that iff:A!Bis a function then, by denirtion of functionf1(B) =A andf(A) is the range off(which is a subset ofB). LetB1B. By denition of preimage of a subset of the codomain we havef1(B1) =;if and only if there is no elementx2A withf(x)2B1. Thusf1(;) =;and, in the example abovef1(fbg) =;. Example (nding the range). Letf:R!Zbe dened byf(x) =d2xe+b2xc. To determine the range off, we begin by testing a few values ofx: f(0) = 0; Ifx2(0;1=2), then 2x2(0;1) sod2xe= 1 andb2xc= 0, hencef(x) = 1; f(1=2) = 2; Ifx2(1=2;1) then 2x2(1;2)d2xe= 2 andb2xc= 1, hencef(x) = 3; f(1) = 4; Ifx2(1;3=2), then 2x2(2;3) sod2xe= 3 andb2xc= 2, hencef(x) = 5. f(3=2) = 6. Based on these computations, it seems reasonable to guess that the range offisZ. We prove that this is the case. First, observe thatf(x) is an integer for everyx2R, so f(R)Z. To show the opposite inclusion, lety2Z. We must ndx2Rsuch that f(x) =y. Ifyis even, sayy= 2t;t2Z, thenf(t=2) =d2t=2e+b2t=2c= 2t=y. Ifyis odd, sayy= 2t+ 1;t2Z, then for anyx2(t=2;t=2 + 1=2) we have 2x2(t;t+ 1), hence f(x) = (t+1)+t= 2t+1 =y. Hence the range offisZ. As anexercise, show that the image of the setNof natural numbers isf(N) =f4n:n2Ng. Example (nding preimages). Letg:R!Zbe dened byg(x) =b3xc. We determine the preimage off1;1gand ofT=f2n:n2Ng. To determineg1(f1;1g) we need to gure out the preimages of each element off1;1g. We haveg(x) =1, b3xc=1,

3x2[1;0)$x2[1=3;0). Similarly,g(x) = 1,x2[1=3;2=3). Thus,g1(f1;1g) =

[1=3;0)[[1=3;2=3). The setg1(T) can be determined in the same way. Forn2Nwe haveg(x) = 2n, b3xc= 2n,3x2[2n;2n+ 1),x2[2n=3;(2n+ 1)=3). Therefore, g

1(T) =S1

n=0[2n=3;(2n+ 1)=3) = [0;1=3)[[2=3;1)[[4=3;5=3)[[3;7=3)[ . Theorem F1. Letf:A!Bbe a function,A1;A2AandB1;B2B. Then (a)f(A1[A2) =f(A1)[f(A2); (b)f(A1\A2)f(A1)\f(A2). (c)f1(B1[B2) =f1(B1)[f1(B2). (d)f1(B1\B2) =f1(B1)\f1(B2).

Proof.

We prove (b) and leave the others as exercises. Lety2f(A1\A2). theny=f(x) for somex2A1\A2. Sincex2A1\A2if and only ifx2A1andx2A2, we havey=f(x) for somex2A1andy=f(x) for somex2A2. Therefore,y2f(A1) andy2f(A2), i.e. y2f(A1)\f(A2).To see that strict containment can occur in part (b) of Theorem F1, consider the functionf:f1;2;3g ! f1;2gwheref=f(1;1);(2;1);(3;2). TakeA1=f1;3gandA2= f2;3g. Thenf(A1\A2) =f(f3g) =f2gwhereasf(A1)\f(A2) =f1;2g\f1;2g=f1;2g. 6 Denition (equality of functions). Two functionsf:A!Bandg:A!Bareequal iff(x) =g(x) for everyx2A. Iffandgare equal, we writef=g. There is a subtle point hidden in the denition of equality of functions. For two functions to be equal, they must have the same domain, the same codomain, and give the same value for the same input. Thus, technically, the functionf:Z!Zdened byquotesdbs_dbs13.pdfusesText_19

[PDF] a/b/c = ac/b

[PDF] a/b/c/d division

[PDF] a/b/c math

[PDF] a/b + c/d = a+c/b+d

[PDF] (a/b)/c

[PDF] combien y a-t-il de semaines dans une année

[PDF] nombre semaine année 2017

[PDF] combien il y a de semaine dans l'année

[PDF] 1 décennie

[PDF] la loi de finance 2017 maroc pdf

[PDF] loi de finance 2017 maroc bulletin officiel

[PDF] loi de finance 2017 maroc résumé

[PDF] loi de finances 2016 maroc pdf

[PDF] projet de loi de finance 2017 maroc pdf

[PDF] budget citoyen 2017 maroc pdf