Cartesian product cross product A and B A B A B f a b j a ...

1 Definition 1 TheCartesian product (orcross product ) ofAandB, denoted byA B, is the setA B={(a,b)|a Aandb B}1. the elements (a,b) ofA Bareordered pairs2. for pairs (a,b),(c,d) we have(a,b) = (c,d) a=candb=dDefinition 2 Then-fold productof setsA1,A2,..,Anis the set ofn-tuplesA1 A2 .. An={(a1,a2,..,an)|ai Aifor all 1 i n}()October 30, 20071 / 12 Definition 1 TheCartesian product (orcross product ) ofAandB, denoted byA B, is the setA B={(a,b)|a Aandb B}1. the elements (a,b) ofA Bareordered pairs2. for pairs (a,b),(c,d) we have(a,b) = (c,d) a=candb=dDefinition 2 Then-fold productof setsA1,A2,..,Anis the set ofn-tuplesA1 A2 .. An={(a1,a2,..,an)|ai Aifor all 1 i n}()October 30, 20071 / 12 Definition 1 TheCartesian product (orcross product ) ofAandB, denoted byA B, is the setA B={(a,b)|a Aandb B}1. the elements (a,b) ofA Bareordered pairs2.

2 For pairs (a,b),(c,d) we have(a,b) = (c,d) a=candb=dDefinition 2 Then-fold productof setsA1,A2,..,Anis the set ofn-tuplesA1 A2 .. An={(a1,a2,..,an)|ai Aifor all 1 i n}()October 30, 20071 / 12 Definition 1A B={(a,b)|a Aandb B}A={2,3,4}B={4,5}a)A B={(2,4),(2,5),(3,4),(3,5),(4,4),(4,5)}b )B A={(4,2),(4,3),(4,4),(5,2),(5,3),(5,4)}O O//23445 A BAB()October 30, 20072 / 12 Definition 1A B={(a,b)|a Aandb B}A={2,3,4}B={4,5}a)A B={(2,4),(2,5),(3,4),(3,5),(4,4),(4,5)}b )B A={(4,2),(4,3),(4,4),(5,2),(5,3),(5,4)}O O//23445 A BAB()October 30, 20072 / 12 Definition 1A B={(a,b)|a Aandb B}A={2,3,4}B={4,5}a)A B={(2,4),(2,5),(3,4),(3,5),(4,4),(4,5)}b )B A={(4,2),(4,3),(4,4),(5,2),(5,3),(5,4)}O O//23445 A BABOO//23445 B ABA()October 30, 20072 / 12B={4,5}a)B2=B B={(4,4),(4,5),(5,4),(5,5)}b)B3=B B B={(4,4,4),(4,4,5),(4,5,4),(4,5,5),(5,4, 4),(5,4,5),(5,5,4),(5,5,5)}OO//4545 B BBB()October 30, 20073 / 12B={4,5}a)B2=B B={(4,4),(4,5),(5,4),(5,5)}b)

3 B3=B B B={(4,4,4),(4,4,5),(4,5,4),(4,5,5),(5,4, 4),(5,4,5),(5,5,4),(5,5,5)}OO//4545 B BBB()October 30, 20073 / 12B={4,5}a)B2=B B={(4,4),(4,5),(5,4),(5,5)}b)B3=B B B={(4,4,4),(4,4,5),(4,5,4),(4,5,5),(5,4, 4),(5,4,5),(5,5,4),(5,5,5)}OO//::ttttttt ttttttttttttttttttttttt4444454545 B B BBBB()October 30, 20073 / 12{4, } {x,y} { , , }Tree Diagram()(4)( )(4,x)(4,y)( ,x)( ,y)(4,x, )(4,x, )(4,x, )(4,y, )(4,y, )(4,y, )( ,x, )( ,x, )( ,x, )( ,y, )( ,y, )( ,y, ) ????????????ooooooOOOOOO ooooooOOOOOO ggggggWWWWWW ggggggWWWWWW ggggggWWWWWW ggggggWWWWWW()October 30, 20074 / 12 Definition 3A(binary) relationfromAtoBis a subset ofA (binary) relationonAis a subset ofA {2,3,4}andB={4,5}a)R1={(2,4),(3,5)}b)R2= {(2,4),(3,4),(4,4)}c)R3={(2,4),(2,5),(4, 4),(4,5)}d)R4= OO//23445 R1AB()October 30, 20075 / 12 Definition 3A(binary) relationfromAtoBis a subset ofA (binary) relationonAis a subset ofA {2,3,4}andB={4,5}a)R1={(2,4),(3,5)}b)R2= {(2,4),(3,4),(4,4)}c)R3={(2,4),(2,5),(4, 4),(4,5)}d)R4= OO//23445 R1AB()October 30, 20075 / 12 Definition 3A(binary) relationfromAtoBis a subset ofA (binary) relationonAis a subset ofA {2,3,4}andB={4,5}a)R1={(2,4),(3,5)}b)R2= {(2,4),(3,4),(4,4)}c)R3={(2,4),(2,5),(4, 4),(4,5)}d)R4= OO//23445 R2AB()October 30, 20075 / 12 Definition 3A(binary)

4 RelationfromAtoBis a subset ofA (binary) relationonAis a subset ofA {2,3,4}andB={4,5}a)R1={(2,4),(3,5)}b)R2= {(2,4),(3,4),(4,4)}c)R3={(2,4),(2,5),(4, 4),(4,5)}d)R4= OO//23445 R3AB()October 30, 20075 / 12 Definition 3A(binary) relationfromAtoBis a subset ofA (binary) relationonAis a subset ofA {2,3,4}andB={4,5}a)R1={(2,4),(3,5)}b)R2= {(2,4),(3,4),(4,4)}c)R3={(2,4),(2,5),(4, 4),(4,5)}d)R4= OO//23445R4AB()October 30, 20075 / 12 RelationR={(x,y) Z Z|1 x y 4}=={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3) ,(2,4),(3,3),(3,4),(4,4)}OO//12341234 RNotation(x,y) RmxRy(think ofRas )()October 30, 20076 / 12 RelationR={(x,y) Z Z|1 x y 4}=={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3) ,(2,4),(3,3),(3,4),(4,4)}OO//12341234 RNotation(x,y) RmxRy(think ofRas )()October 30, 20076 / 12 RelationR={(x,y) Z Z|1 x y 4}=={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3) ,(2,4),(3,3),(3,4),(4,4)}OO//12341234 RNotation(x,y) RmxRy(think ofRas )()October 30, 20076 / 12{Justin,Joey,Kevin,Nick} {Britney,Christina,Jessica,Kelly,Sarah}J ustinJoeyKevinNickBritneyChristinaJessic aKellySarahdddddddddddddddddZZZZZZZZZZZZ ZZZZZOOOOOOOOOOOOOOOOOOODDDDDDDDDDDDDDDD DDDDDD::::::::::::::::::::::::::oooooooo oooooooooodddddddddddddddddZZZZZZZZZZZZZ ZZZZOOOOOOOOOOOOOOOOOODDDDDDDDDDDDDDDDDD DDDD zzzzzzzzzzzzzzzzzzzzzzoooooooooooooooooo odddddddddddddddddZZZZZZZZZZZZZZZZZOOOOO OOOOOOOOOOOOOO zzzzzzzzzzzzzzzzzzzzzzoooooooooooooooooo odddddddddddddddddZZZZZZZZZZZZZZZZZ()Oct ober 30, 20077 / 12 Who dated whom?

5 {(Ju,Br),(Ju,Je),(Jo,Ke),(Jo,Sa),(Ke,Br) ,(Ke,Ch),(Ni,Ch),(Ni,Ke),(Ni,Sa)}JustinJ oeyKevinNickBritneyChristinaJessicaKelly SarahddddddddddddddddddddddddddddddddddO OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOODDDDDDD DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzoooooooooooooooooooooooooooooooooooo oozzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz zzzzzzdddddddddddddddddddddddddddddddddd ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ()Octo ber 30, 20078 / 12 Who is dating whom?{(Ju,Je),(Ke,Br),(Ni,Ch),(Ni,Ke)}Ju stinJoeyKevinNickBritneyChristinaJessica KellySarah()October 30, 20079 / 12 Theorem 4 For any set A, we have A = ( and A= ) (a,b) A , thena Aandb , impossible. Theorem 5 For any sets A,B,Ca)A (B C) = (A B) (A C)b)A (B C) = (A B) (A C)c) (A B) C= (A C) (B C)d) (A B) C= (A C) (B C) ) (a,b) A (B C) a Aandb B C a Aandb Bandb C (a,b) A Band(a,b) A C (a,b) (A B) (A C) ()October 30, 200710 / 12 Theorem 4 For any set A, we have A = ( and A= ) (a,b) A , thena Aandb , impossible.

6 Theorem 5 For any sets A,B,Ca)A (B C) = (A B) (A C)b)A (B C) = (A B) (A C)c) (A B) C= (A C) (B C)d) (A B) C= (A C) (B C) ) (a,b) A (B C) a Aandb B C a Aandb Bandb C (a,b) A Band(a,b) A C (a,b) (A B) (A C) ()October 30, 200710 / 12 Observation 6 For any two sets A,B , the number of elements in A B is|A B|=|A| |B|Hence there are exactly|P(A B)|= 2|A B|= 2|A| |B|differentrelations from A to B .()October 30, 200711 / 12 Observation 6 For any two sets A,B , the number of elements in A B is|A B|=|A| |B|Hence there are exactly|P(A B)|= 2|A B|= 2|A| |B|differentrelations from A to B .()October 30, 200711 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?

7 Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ? Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ? Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?

8 Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ? Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ? Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).

9 Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ? Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ?

10 Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?Answer:(95)= 126f) # of relations onAthatcontain at least seven elements ? Answer:(97)+(98)+(99)= 121()October 30, 200712 / 12 - IfA={1,2,3,4,5}andB={w,x,y,z}, how manyelements are there inP(A B).Answer: 220= 1,048, - ForA={1,2,3}andB={2,4,5}a)|A B|=?Answer: 9b) # of relations fromAtoB?Answer: 29= 512c) # of relations onA?Answer: 29= 512d) # of relations fromAtoBthat contain (1,2) and (1,5) ?Answer: 27= 128e) # of relations fromAtoBthat contain exactly five ordered pairs ?