Ws-1-solutions - Awesome PDF

Preview

Summary

Awesome ...

Description

MAD3105( Worksheet(1(Solutions( ( Suppose(R,(S(are(relations(on(a(set(A.( ! 1.( T( F((( If(R,(S(are(both(reflexive,(then(R∩ ∩ S(is(reflexive.( Proof:!!Suppose!a∈A.!!Since!R,!S!are!both!reflexive!on!A,!(a,!a)!∈R!and!(a,!a)!∈S.! Since!(a,!a)!is!in!both!R!and!S,!(a,!a)!∈&R∩S,!so!R∩S!is!reflexive.! ! 2.( T( F((( If(R,(S(are(both(irreflexive,(then(R∩ ∩ S(is(irreflexive.( Proof:!!Suppose!a∈A.!!Since!R,!S!are!both!irreflexive!on!A,!(a,!a)!∉R!and!(a,!a)!∉S.! Since!(a,!a)!is!in!neither!R!nor!S,!(a,!a)!∉&R∩S,!so!R∩S!is!irreflexive.! ! 3.( T( F((( If(R,(S(are(both(symmetric,(then(R∩ S(is(symmetric.( Proof:!!Suppose!(a,!b)!∈&R∩S.! Because!(a,!b)!∈&R∩S,!(a,!b)!∈&R!and!(a,!b)!∈&S.! Since!R,!S!are!both!symmetric!(b,!a)!∈&R!and!(b,!a)!∈&S.!! Since!(b,!a)!∈&R!and!(b,!a)!∈&S,&(b,!a)!∈&R∩S,!so!R∩S!is!symmetric.! ! 4.( T( F((( If(R,(S(are(both(antisymmetric,(then(R∩ S(is(antisymmetric.( Proof:!!Suppose!(a,!b)!∈&R∩S&and&(b,!a)!∈&R∩S.!!We!need!to!show!that!a&!=!b.& Because!(a,!b)!∈&R∩S!and!(b,!a)!∈&R∩S,!we!know!and!(a,!b)!∈&R&and!(b,!a)!∈&R,&and!since!R!is! antisymmetric,!a!=!b.! We!have!shown!that!whenever!(a,!b)!∈&R∩S&and&(b,!a)!∈&R∩S,!a!=!b,!so&R∩S!is!antisymmetric.! ! 5.( T( F((( If(R,(S(are(both(asymmetric,(then(R∩ S(is(asymmetric.( Proof:!!Suppose!(a,!b)!∈&R∩S.!!We!need!to!show!that!(b,!a)!∉&R∩S.! Because!(a,!b)!∈&R∩S,!we!know!and!(a,!b)!∈&R,&and,!since!R!is!asymmetric,!we!know!that!(b,!a)!∉&R.& Since!(b,!a)!∉&R,!we!know!that!(b,!a)!∉!R∩S.! We!have!shown!that!whenever!(a,!b)!∈&R∩S,!(b,!a)!∉!R∩S,!so!R∩S!is!asymmetric.! ! 6.( T( F((( If(R,(S(are(both(transitive,(then(R∩ S(is(transitive.( Proof:!!Suppose!(a,!b)!∈&R∩S&and&(b,!c)!∈&R∩S.!!We!need!to!show!that!(a,!c)!∈&R∩S.! Because!(a,!b)!∈&R∩S,!we!know!and!(a,!b)!∈&R&and!(a,!b)!∈&S.& Because!(b,!c)!∈&R∩S,!we!know!and!(b,!c)!∈&R&and!(b,!c)!∈&S.& Since!(a,!b)!∈&R!and!(b,!c)!∈&R!and!R!is!transitive!we!know!that!(a,!c)!∈&R.& Since!(a,!b)!∈&S&and!(b,!c)!∈&S!and!S!is!transitive!we!know!that!(a,!c)!∈&S.& Since!(a,!c)!∈&R&and!(a,!c)!∈&S,!(a,!c)!∈&R∩S.& We!have!shown!that!whenever!(a,!b)!∈&R∩S,!and!(b,!c)!∈!R∩S,!(a,!c)!∈R∩S!,!so!R∩S!is!transitive.! ! ! ! ! ! ! ! ! !

Suppose(R,(S(are(relations(on(a(set(A.( ! 7.( T( F((( If(R,(S(are(both(reflexive,(then(R∪ S(is(reflexive.( Proof:!!Suppose!a∈A.!!! Since!R!is!reflexive,!(a,!a)!∈R.! Since!(a,!a)!∈R,!(a,!a)!∈&R∪S,!so!R∪S!is!reflexive.! ! ! 8.( T( F((( If(R,(S(are(both(irreflexive,(then(R∪ ∪ S(is(irreflexive.( Proof:!!Suppose!a∈A.!!! Since!R!is!irreflexive,!(a,!a)!∉R.! Since!S!is!irreflexive,!(a,!a)!∉S.! ! Since!(a,!a)!∉R,!and!(a,!a)!∉S,!(a,!a)!∉&R∪S,!so!R∪S!is!irreflexive.! ! ! 9.( T( F((( If(R,(S(are(both(symmetric,(then(R∪ S(is(symmetric.( Proof:!!(a,!b)!∈&R∪S.!!We!must!show!(b,!a)!∈&R∪S.!!! Then!(a,!b)!∈&R!or!(a,!b)!∈&S.! So,!!(b,!a)!∈&R!or!(b,!a)!∈&S,!because!R!and!S!are!both!symmetric.! Since!(b,!a)!∈&R!or!(b,!a)!∈&S,!(a,!b)!∈&R∪S.! We!have!shown!that!whenever!(a,!b)!∈&R∪S,!(b,!a)!∈&R∪S,!so!∈&R∪S!is!symmetric.! ! 10.( T( F((( If(R,(S(are(both(antisymmetric,(then(R∪ S(is(antisymmetric.( Counterexample:!Let!A!=!{1,!2,!3},!let!R!=!{(1,!2)},!let!S!=!{(2,!1)}.! Note!that!R!and!S!are!both!antisymmetric.! Then!R∪S!=!{(1,!2),!(2,!1)},!which!is!not!antisymmetric.! ! 11.( T( F((( If(R,(S(are(both(asymmetric,(then(R∪ S(is(asymmetric.( ! Counterexample:!Let!A!=!{1,!2,!3},!let!R!=!{(1,!2)},!let!S!=!{(2,!1)}.! Note!that!R!and!S!are!both!asymmetric.! Then!R∪S!=!{(1,!2),!(2,!1)},!which!is!not!asymmetric.! ! 12.( T( F((( If(R,(S(are(both(transitive,(then(R∪ S(is(transitive.( ! Counterexample:!Let!A!=!{1,!2,!3},!let!R!=!{(1,!2)},!let!S!=!{(2,!1)}.! Note!that!R!and!S!are!both!(vacuously)!transitive.! Then!R∪S!=!{(1,!2),!(2,!1)},!which!is!not!transitive,!because,!for!instance,!1!is!related!to!2!and!2!is!related! to!1!but!1!is!not!related!to!1.! ! ! !

Suppose(R,(S(are(relations(on(a(set(A.( ! 13.( T( F((( If(R,(S(are(both(reflexive,(then(R–(S(is(reflexive.( Counterexample:!Let!A!=!{1,!2},!R!=!{(1,!1),!(2,!2),!(1,!2)},!S!=!{(1,!1),!(2,!2)}.!!R&and!S!are!both!reflexive,!but!! R–S!=!{(1,!2)},!which!is!not!reflexive.! ! ! 14.( T( F((( If(R,(S(are(both(irreflexive,(then(R–S(is(irreflexive.( Proof:!!Suppose!R,!S&are!both!irreflexive,!and!let!a!∈A.!!Since!R!is!irreflexive,!(a,!a)!∉R,!and!so!(a,!a)!∉R–S.& ! ! 15.( T( F((( If(R,(S(are(both(symmetric,(then(R–S(is(symmetric.( Proof:!!Suppose!(a,!b)!∈&R–S.!!Then!(a,!b)!∈&R!but!(a,!b)!∉&S.&&!!! Since!(a,!b)!∈&R!and!R!is!symmetric,!we!have!(b,!a)!∈R.&&& We!need!to!show!(b,!a)!∉&S.!!! Suppose!(b,!a)!∈&S.!!! Then,!because!S!is!symmetric,!we!have!(a,!b)!∈!S.!But!then!(a,!b)!∈&R!and!(a,!b)!∈&S,!contradicting! assumption!that!(a,!b)!∈&R–S.!!! We!have!shown!that!(b,!a)!∈&R–S!whenever!(a,!b)!∈&R–S,!so&R–S!is!symmetric.! ! ( 16.( T( F((( If(R,(S(are(both(antisymmetric,(then(R–S(is(antisymmetric.( Proof!by!contraposition:!suppose!R–S&is!not!antisymmetric.!!Then!there!are!distinct!a,!b!such!(a,!b)!∈&R–S! and!(b,!a)!∈&R–S.!!But!then!(a,!b)!∈&R!and!(b,!a)!∈&R,!so!R!is!not!antisymmetric.! ! ( ( 17.( T( F((( If(R,(S(are(both(asymmetric,(then(R–S(is(asymmetric.( Proof!by!contraposition:!suppose!R–S!is!not!asymmetric.!!Then!there!are!a,!b!such!(a,!b)!∈&R–S!! and!(b,!a)!∈&R–S.!!But!then!(a,!b)!∈&R!and!(b,!a)!∈&R,!so!R!is!not!asymmetric.! ! ! 18.( T( F((( If(R,(S(are(both(transitive,(then(R–S(is(transitive.( ! Counterexample:!Let!A!=!{1,!2,!3},!let!R!=!{(1,!2),!(2,!3),!(1,!3)},!let!S!=!{(1,!3)}.! Note!that!R!is!transitive!and!S!is!(vacuously)!transitive.! Then!R–S!=!{(1,!2),!(2,!3)},!which!is!not!transitive.! ! ! !

( Let'R'be'a'relation'on'a'set'A.( ( 19.( T( F( If(R(is(reflexive,(then(R(–1(is(reflexive.( ! Proof:!Suppose!R!is!reflexive!and!a∈A!is!arbitrary.!Since!R!is!reflexive,!(a,!a)!∈R,!and!then!switching!the! two!coordinates!we!get!(a,!a)!∈R–1,!so!R–1!is!reflexive.! ! 20.( T( F( If(R–1(is(irreflexive,(then(R(–1(is(irreflexive.( ! Proof!by!contraposition:!Suppose!R–1!is!not!irreflexive.!Then!there!is!a∈A!such!that!(a,!a)!∈R–1;!so,! switching!the!two!coordinates,!we!get!(a,!a)!∈R,!so!R!is!not!irreflexive.! ! ! 21.( T( F( If(R(is(symmetric,(then(R(–1(is(symmetric.( ! Proof:!Suppose!R!is!symmetric!and!(x,!y)!is!an!arbitrary!element!of!R–1.!Then!by!definition!of!R–1,!(y,!x)!∈R,! and!since!R!is!symmetric!(x,!y)!∈R;!since!(x,!y)!∈R,!by!definition!(y,!x)!∈R–1,!so!R&–1!is!symmetric.! ! 22.( T( F( If(R(is(antisymmetric,(then(R(–1(is(antisymmetric.( ! Proof!by!contraposition:!Suppose!R–1!is!not!antisymmetric.!!Then!there!are!distinct!x,!y!such!that!! (x,!y)!∈R–1!and!(y,!x)!∈R–1.!!But!this!means!that!(y,!x)!∈R!and!(x,!y)!∈R,!x!≠y,!so!R!is!not!antisymmetric.! ! ! 23.( T( F( If(R(is(asymmetric,(then(R(–1(is(asymmetric.( ! Proof!by!contraposition:!Suppose!R–1!is!not!asymmetric.!!Then!there!are!x,!y!such!that!! (x,!y)!∈R–1!and!(y,!x)!∈R–1.!!But!this!means!that!(y,!x)!∈R!and!(x,!y)!∈R,!so!R!is!not!asymmetric.! ! 24.( T( F( If(R(is(transitive,(then(R(–1(is(transitive.( ! Proof:!Suppose!(x,!y)!∈R–1!and!(y,!z)!∈R–1!for!some!arbitrary!x,!y.!!We!need!to!show!that!that!(x,!z)!∈R–1.!!! ! Since!(x,!y)!∈R–1!and!(y,!z)!∈R–1,!we!have!that!(y,!x)!∈R!and!(z,!y)!∈R,!and,!since!R!is!transitive,!(z,!x)!∈R.! Since!(z,!x)!∈R,!we!have!(x,!z)!∈R–1,!which!is!what!we!needed!to!prove.! ! ! ! ! ! ! ! ! !

! ! 25.( !

T(

F(

If(R(is(reflexive,(then(!R (is(reflexive.(((

( )

Counterexample:!Let!A&=!{1}!and!let!R!=!{(1,!1)};!then! 1,1 ∉R ,!so! !R(is!not!reflexive.! ! ! 26.( !

T(

F(

If(R(is(irreflexive,(then(!R (is(irreflexive.(

( )

Counterexample:!Let!A&=!{0,!1}!and!let!R!=!{(1,!0)};!note!that!R!is!irreflexive,!but! 1,1 ∈R ,!so!!R (is!not! !! irreflexive.! ! ! 27.( !

T(

F(

If(R(is(symmetric,(then(!R (is(symmetric.(

( )

Proof!by!contraposition:!Suppose!!R (is!not!symmetric.!!Then!there!are!x,!y&such!that! x , y ∈R !but! ! y,x ∉R .!This!means,!however,!that!! y,x ∈R but! x , y ∉R ,!so!R!is!not!symmetric.! ! ! ( (

( )

28.( !

( )

T(

F(

( )

If(R(is(antisymmetric,(then(!R (is(antisymmetric.(

( )

( )

Counterexample:!!Let!A!=!{1,!2,!3},!R!=!{(1,3)}.!!Note!that!R&is!antisymmetric,! 1,2 ∈R ,!and! 2,1 ∈R ,!so! !R ( !! !! is!not!antisymmetric.! ! 29.( T( F( If(R(is(asymmetric,(then(R(–1(asymmetric.( ! Counterexample:!!Let!A!=!{1,!2,!3},!R!=!{(1,3)}.!!Note!that!R&is!asymmetric,! 1,2 ∈R ,!and! 2,1 ∈R ,!so! !R (is! !! !! not!asymmetric.! ! ! ! 30.( T( F( If(R(is(transitive,(then(!R (is(transitive.( !

( )

( )

( )

Counterexample:!!Let!A!=!{1,!2},!R!=!{(1,1)}.!!Note!that!R&is!vacuously!transitive.!!Note!that 1,2 ∈R ,!and!

( 2,1) ∈R ,!but!! (1,1) ∉R ,!so!is!not!!R (transitive.! ! ! ! ! ! ! !

! 31.!Use(the(fact(that(composition(is(associative,(and(induction,(to(prove(Rn ! R = R ! Rn (for(n(=(1,(2,(3,( …( ! Proof!of!basis:!We!need!to!prove! R1 ! R = R ! R1 . !By!definition,! R1 = R ,!so! R1 ! R = R ! R = R ! R1 .! ! Proof!of!inductive:!Assume! R k ! R = R ! R k for!some!k!≥1.!!Then! ! R k+1 ! R ! (definition!of!Rn)! =! R k ! R ! R !!!!

( ) =! ( R ! R ) ! R ! ! =! R ! ( R ! R ) ! ! k

(inductive!hypothesis)!

k

(because!composition!is!associative)!

k+1

! (definition!of!Rn)! =! R ! R ! ! ! ! ! ! ! ! 32.( (Spring(2019(–(This(will(be(on(Test(2,(not(on(Test(1).((Prove(that((x,(y)(∈ ∈ Rn(iff(on(the(digraph( for(R(there(is(a(directed(path(of(length(n(from(x(to(y.( ! Proof!by!induction! Basis:!!Note!(x,!y)!∈R1!if!and!only!if!there!is!a!directed!edge!(that!is,!a!directed!path!of!length!1)!from!x!to!y.! ! Inductive:!Assume!that!(x,!y)!∈Rk!if!and!only!if!there!is!a!directed!path!of!length!k!from!x!to!y.! ! Suppose!that!there!is!a!directed!path!of!length!k!+!1!from!x!to!y.&&If!we!delete!the!last!edge,!then!we!have!a! directed!path!of!length!k!from!x!to!some!vertex!v,!and!the!deleted!edge!is!a!directed!path!of!length!one! from!v!to!y.! ! Since!we!have!a!directed!path!of!length!k!from!x!to!v,!our!inductive!hypothesis!states!that!the!ordered!pair! (x,!v)!∈Rk,!and!the!directed!edge!from!v!to!y!means!that!(v,!y)!∈R,!so!by!composition,!(x,!y)!∈Rk+1.! ! Conversely,!suppose!(x,!y)!∈Rk+1.!!Then,!by!definition!of!Rn,!there!is!v!such!that!(x,!v)!∈Rk!and!(v,!y)!∈R.! Since!(x,!v)!∈Rk,!our!inductive!hypothesis!states!that!there!is!a!directed!path!of!length&k!from!x&to!v.! Since!(v,!y)!∈R,!the!directed!edge!from!v!to!y!is!a!directed!path!of!length!1!from!v!to!y.!!Concatenating! those!paths!gives!us!a!directed!path!of!length!k+1!from!x!to!y.! ! ! ! ! ! !

Suppose(R,(S(are(relations(on(a(set(A.( ! 33.( T( F((( If(R,(S(are(both(reflexive,(then(S !R is(reflexive.( Proof:!Let!a∈A.!!Since!R!is!reflexive,!(a,!a)!∈R;!since!S!is!reflexive,!(a,!a)!∈S;&so,!(a,!a)!∈!S !R .! ! ! 34.( T( F((( If(R,(S(are(both(irreflexive,(then(S !R is(irreflexive.( Counterexample:!!Let!A!=!{1,!2},!R!=!{(1,!2)},!S!=!{(2,!1)}.!!Note!that!R,!S!are!irrefelxive,!but!(1,!1)!∈S ! !R ,!so S !R is!not!irreflexive.! ! ! ! 35.( T( F((( If(R,(S(are(both(symmetric,(then(S !R is(symmetric.( Counterexample:!Let!A!=!{1,!2,!3},!!R!=!{(1,!2),!(2,!1)},!S!=!{(2,!3),!(3,!2)}.!!! Note!that!R!and!S&are!both!symmetric,!but! S !R (=!{(1,!3)}!is!not!symmetric.! ! ( 36.( T( F((( If(R,(S(are(both(antisymmetric,(then(!S !R is(antisymmetric.( Counterexample:!Let!A!=!{1,!2,!3},!!R!=!{(1,!2),!(3,!2)},!S!=!{(2,!3),!(2,!1)}.!!! Then!R,!S!are!both!antisymmetric!but !S !R =!{(1,!3),!(3,!1)}!is!not!antisymmetric.! ! ( ( 37.( T( F((( If(R,(S(are(both(antisymmetric,(then(S !R is(asymmetric.( Counterexample:!Let!A!=!{1,!2,!3},!!R!=!{(1,!2),!(3,!2)},!S!=!{(2,!3),!(2,!1)}.!!! Then!R,!S!are!both!asymmetric!but S !R =!{(1,!3),!(3,!1)}!is!not!asymmetric.! ! ! ! 38.( T( F((( If(R,(S(are(both(transitive,(then(S !R is(transitive.( ! Counterexample:!Let!A!=!{1,!2,!3,!4,!5},!let!R!=!{(1,!5),!(2,!4)},!let!S!=!{(5,!2),!(4,!3)}.! Note!that!R!and!S&are!vacuously!transitive!but!S !R =!{(1,!2),!(2,!3)}!is!not!transitive.! ! ! ! ! ( (

Suppose(R,(S(are(relations(on(a(set(A.( ! 39.( T( F((( If(R,(S(are(both(reflexive,(then( S ⊕ Ris(reflexive.( Counterexample:!Let!A!=!{1,!2},!!R!=!{(1,!1),!(2,!2),!(1,!2)},!S!=!{(1,!1),!(2,!2),!(2,!1)}.!!! R!and!S!are!reflexive!but! S ⊕ R isn’t!reflexive.! ! 40.( T( F((( If(R,(S(are(both(irreflexive,(then(!S ⊕ R is(irreflexive.( Proof:!!Suppose!R,!S!are!irreflexive!and!a!∈A.!!We!have!(a,!a)∉R!and!(a,!a)∉S,!so!(a,!a)∉R⊕S.! ! ! ! 41.( T( F((( If(R,(S(are(both(symmetric,(then(!S ⊕ R is(symmetric.( Proof:!Suppose!R,!S!are!symmetric!and!(a,!b)∈R⊕S.!!Then!(a,!b)∈R!and!(a,!b)∉S!or!(a,!b)∈S&and!(b,!a)∉R.! In!case!(a,!b)∈R!and!(a,!b)∉S,!note!that!(b,!a)∈R!because!R!is!symmetric,!and!(b,!a)∉S!because,!since!S!is! symmetric,!if!(b,!a)!were!in!S,!(a,!b)!must!also!be!in!S;!this!shows!that!if!(a,!b)∈R!and!(a,!b)∉S!then!! (b,!a)∈R⊕S.!!In!case!(a,!b)∈S!and!(a,!b)∉R,!a!similar!proof!shows!(b,!a)∈R⊕S.!!Therefore,!R⊕S&is! symmetric.! ! ! ( 42.( T( F((( If(R,(S(are(both(antisymmetric,(then(!S ⊕ R is(antisymmetric.( Counterexample:!Let!A!=!{1,!2},!!R!=!{(1,!2)},!S!=!{(2,!1)}.!!! Then!R,!S!are!both!antisymmetric!but S ⊕ R =!{(1,!2),!(2,!1)}!is!not!antisymmetric.! ! ( ( 43.( T( F((( If(R,(S(are(both(asymmetric,(then(S ⊕ R is(asymmetric.( Counterexample:!Let!A!=!{1,!2},!!R!=!{(1,!2)},!S!=!{(2,!1)}.!!! Then!R,!S!are!both!asymmetric!but S ⊕ R =!{(1,!2),!(2,!1)}!is!not!asymmetric.! ! ! ! 44.( T( F((( If(R,(S(are(both(transitive,(then(!S ⊕ R is(transitive.( Counterexample:!Let!A!=!{1,!2},!!R!=!{(1,!2)},!S!=!{(2,!1)}.!!! Then!R,!S!are!both!(vacuously)!transitive,!but S ⊕ R =!{(1,!2),!(2,!1)}!is!not!transitive.! ! ! ! ! !

45.( T( F( R(is(transitive,(if(and(only(if(Rn(⊆ ⊆ (R(for(n(=(1,(2,(3,(…( ( First,!we!prove!Rn!⊆!R!implies!R&is!transitive:! Suppose!Rn!⊆!R!for!n!=!1,!2,!3,!…!!Let!(a,!b)!∈R!and!(b,!c)!∈R.!!Then!(a,!c)!∈R2!according!to!the!definition!of! R2.!!But!our!hypothesis!says!that!R2⊆!R,!so!(a,!c)!∈R.!!This!shows!that!R!is!transitive.! ! ! To!prove!the!converse,!we!will!use!induction.!!! Here!is!the!proof!of!inductive!step:!Suppose!we!have!transitive!R,!and!Rk!!⊆!R!for!some!k.!!To!show!that! Rk+1!⊆!R!we!show!that!any!ordered!pair!in!Rk+1!is!also!in!R.! Let!(a,!b)!∈&Rk+1.!!Then!there!is!c!such!that!(a,!c)!∈&R&and!(c,!b)!∈&Rk.!!Our!inductive!hypothesis!says!Rk!!⊆!R!,! so!(c,!b)!∈&R.!!But!R!is!transitive,!so!(a,!c)!∈&R&and!(c,!b)!∈&R!implies!(a,!b)!∈&R&and!the!proof!is!complete.!

Suppose(R(is(a(relation(on(a(set(A.( ! 46.( T( F((( If(R(is(reflexive,(then(Rn'is(reflexive(for(n≥2.( Proof!of!inductive!step:!Assume!Rk!is!reflexive!for!some!for!some!k≥2,!and!let!a!∈A.!!Since!R!is!reflexive,!! (a,!a)!∈R;!since!Rk!is!reflexive,!(a,!a)!∈Rk;!so,!(a,!a)!∈Rk+1!=!!Rk !R .!

! ! 47.( T( F((( If(R(is(irreflexive,(then(Rn'is(irreflexive(for(n≥2.( Counterexample:!Let!A!=!{1,!2},!!R!=!{(1,!2),!(2,!1)}.!!Then!R2!=!{(1,!1),!(2,!2)}.! ! ! 48.( T( F((( If(R(is(symmetric,(then(Rn'is(symmetric(for(n≥2.( ( Proof!of!inductive!step:!Suppose!Rk!is!symmetric!for!some!symmetric!relation!R,&and!let!(a,!b)!∈Rk+1.! By!definition!of!Rk+1,!there!is!c!such!(a,!c)!∈R!and!(c,!b)!∈Rk.!!Since!R!and!Rk!are!both!symmetric,!(c,!a)!∈R! and!(b,!c)!∈Rk,!respectively,!so! b,a ∈R!Rk = Rk !R = Rk+1 !! ! Note!that!this!proof!made!use!of!a!theorem!proved!earlier:! R!Rn = Rn !R for!all!relations!R!on!a!set!A.! ! 49.( T( F((( If(R(is(antisymmetric,(then(Rn'is(antisymmetric(for(n≥2.( Counterexample:!Let!A!=!{1,!2,!3,!4},!!R!=!{(1,!2),!(2,!3),!(3,!4),!(4,!1)}.! Then!R!is!antisymmetric!but!R2!=!{(1,!3),!(2,!4),!(3,!1),!(4,!2)}!is!not!antisymmetric.! ! 50.( T( F((( If(R,(S(are(both(asymmetric,(then(S ⊕ R is(asymmetric.( Counterexample:!Let!A!=!{1,!2,!3,!4},!!R!=!{(1,!2),!(2,!3),!(3,!4),!(4,!1)}!! Then!R!is!asymmetric!but!R2!=!{(1,!3),!(2,!4),!(3,!1),!(4,!2)}!is!not!asymmetric.! ! ! 51.( T( F((( If(R(is(transitive,(then(Rn'is(transitive(for(n≥2.((Use(this(theorem(in(your(proof:( ( ( ( R'is(transitive(if(and(only(if(Rn(⊆ ⊆ (R'for(n(=(1,(2,(3,(…( ! First,&we&use&induction&to&prove&that&if&R&is&transitive,&then&Rn&is&transitive.& ! Basis!step:!Nothing!to!prove,!because!R1!=!R!which!is!transitive!by!hypothesis.! Proof!of!inductive!step.!!Suppose!Rk!is!transitive!for!some!transitive!relation!R,&and!let!(a,!b)!∈Rk+1.! (b,!c)!∈Rk+1.!!We!need!to!show!(a,!c)!∈Rk+1.!!! First,!since!(a,!b)!∈Rk+1!and!Rk+1!⊆ ⊆ (R,!we!have!(a,!b)!∈R.!!! k+1 Next,!since!(b,!c)!∈R !there!is!d&such!that!(b,!d)!∈R!and!(d,!c)!∈Rk.!!! Also,!since!(a,!b)!∈R,!!(b,!d)!∈R!and!R!is!transitive,!we!have!(a,!d)!∈R.!!! Finally,!since!(a,!d)!∈R!and!(d,!c)!∈Rk,!we!have!(a,!c)!∈Rk+1.!!! ! & ! ( 52.( T( F( If(R(is(a(symmetric(relation(on(A,(then((r(R)(is(symmetric.( Spring(2019:(Thus(is(Test(2(material,(not(Test(1.( Proof:!Suppose!(x,!y)!∈!r(R)!=!R&∪!Δ.!!! Then!(x,!y)!∈R!or!(x,!y)!∈Δ.!!! If!(x,!y)!∈R!then!(y,!x)!∈R!because!R!is!symmetric,!and!so!(y,!x)!∈R∪!Δ!=!r(R).!!! If!(x,!y)!∈Δ!then!x!=!y!so!(x,!y)!=!(x,&x)!=!(y,!x)!∈Δ!and!so!(y,!x)!∈R∪!Δ!=r(R).!

( )

! 53.(( T( F( If(R(is(a(symmetric(relation(on(A,(then((t(R)(is(symmetric.( Spring(2019:(Thus(is(Test(2(material,(not(Test(1.( ( Proof:!Suppose!(x,!y)!∈!t(R).!!Then,!by!definition!of!t(R),!!(x,!y)!∈Rn!for!some!n≥1.!!Since!R!is!symmetric,!Rn! is!also!symmetric!for!all!n≥1!(we!proved!this!a!while!ago),!so!(y,!x)!∈Rn.!!Since!(y,!x)!∈Rn,!this!implies!that! (y,!x)!∈t(R),!and!so!t(R)!is!symmetric.!!! ! ! 54.( T( F( If(R(is(a(transitive(relation(on(A,(then((r(R)(is(transitive.( Spring(2019:(Thus(is(Test(2(material,(not(Test(1.( ( Proof:!Suppose!(x,!y)!∈!r(R)!=!R&∪!Δ!and!(y,!z)!∈!r(R)!=!R&∪!Δ.! Case!1:!(x,!y)!∈!R!and!(y,!z)!∈!R.!!In!this!case!(x,!z)!∈!R!since!R!is!transitive,!and!so!(x,!z)!∈!R&∪!Δ!=!r(R).! Case!2:!(x,!y)!∈!Δ!and!(y,!z)!∈!Δ.!!In!this!case!x!=!y!=!z!and!so!!(x,!z)!∈!Δ!⊆!r(R).! Case!3:!(x,!y)!∈!R!and!(y,!z)!∈!Δ.!!In!this!case!y!=!z!and!so!(x,!z)!=!(x,!y)!!∈!R!⊆!r(R).! Case!4:!(x,!y)!∈!Δ!and!(y,!z)!∈!R.!!In!this!case!x!=!y!and!so!(x,!z)!=!(y,!z)!!∈!R!⊆!r(R).! ! ( 55.( T( F( If(R(is(a(transitive(relation(on(A,(then((s(R)(is(transitive.( Spring(2019:(Thus(is(Test(2(material,(not(Test(1.( ! Counterexample:!Let!A!=!{1,!2,!3}!and!let!R!be!the!vacuously!transitive!relation!{(1,!2)}.!!Then!s(R)!=!{(1,!2),! (2,!1)},!which!is!not!transitive!because!(1,!2)!∈&s(R)!and!(2,!1)!∈&s(R)!but!(1,!1)!∉&s(R).( ! ! 56.( T( F( If(R(⊆ ⊆ (S(then(Rn(⊆ ⊆ (Sn'for(n(=(1,(2,(3,…! ! Proof!of!inductive!step:!!Suppose!R!⊆!S!and!Rk!⊆!Sk&for!some!k.! ! Let!(x,!y)!∈Rk+1.!!Then!there!is!a!such!that!(x,!a)!∈R!!and!(a,!y)!∈Rk.! But,!since!R!⊆!S,!we!have!(x,!a)!∈S,!and!since!Rk!⊆!Sk!we!have!(a,!y)!∈Sk,!so,!according!to!the!definition!of!Sn,! we!have!(x,!y)!∈Sk+1.! ! 57.( T( F( If((R(⊆ ⊆ (S(and(T(⊆ ⊆ (U'then(!R!T ⊆ S !U .(

( )

Proof:!Suppose! x , y ∈R!T .!!Then!there!is!a!such!that!(x,!a)!∈&T&and!(a,!y)!∈!R.!!But!since!R!⊆!S,!we!have! ! (a,!y)!∈!S,!and!likewise!since!T&⊆!U!we!have!(x,!a)!∈!U,!so,! x , y ∈S !U .! ! ! ! ! ! ! ! ! ! ( (

( )

58.(Suppose(S,(R(are(relations(from(A(to(B.(((Prove:( Spring(2019:(This(is(Test(2(material,(not(Test(1.( ! a.!(R–1)–1!=!R& ! Proof:!(x,&y)∈(R–1)–1!⇔!(y,&x)∈R–1!⇔!(x,&y)∈R.! ! b.!(R∪S)–1!=!R–1∪S–1! ! Proof:!(x,&y)∈!(R∪S)–1!! ⇔!(y,&x)∈R∪S!! ⇔!(y,&x)∈R&or!(y,&x)∈S!! ⇔!(x,&y)∈R–1!or!(x,&y)∈S–1! ⇔!(x,&y)∈&R–1∪S–1! ! c.!(R∩S)–1!=!R–1∩S–1 ! ! Proof:!(x,&y)∈(R∩S)–1!! ⇔!(y,&x)∈R∩S!! ⇔!(y,&x)∈R&and!(y,&x)∈S!! ⇔!(x,&y)∈R–1!and!(x,&y)∈S–1! ⇔!(x,&y)∈&R–1∩S–1! ! d.!(A×B)–1!=!B×A! ! Proof:!(x,&y)!∈!(A×B)–1! ⇔!(y,&x)∈&A×B! ⇔!y∈A&and!x!∈B! ⇔!(x,&y)!∈&B×A! ! e.!!∅–1!=!∅! Proof:!!We!use!proof!by!contradiction!to!show!that!∅–1!is!empty.!!! Suppose!there!is!an!ordered!pair!(x,!y)!in!∅–1.!!Then!the!ordered!pair!(y,!x)!is!in!∅.! This!contradicts!the!fact!that!∅!is!empty.!!Hence!∅–1!is!empty,!so!∅–1!=!∅.! !! ! −1

()

f.( R

= R −1 !

! Proof! −1

( x , y) ∈(R ) !

( )

( )

( )

( )

⇔ y,x ∈R ⇔ y,x ∉R ⇔ x , y ∉R −1 ⇔ x , y ∈R −1 ! !

!

(

g.!! R − S

−1

)

= R −1 − S −1 !

Proof:!!! −1

( x , y ) ∈(R − S ) ⇔ ( y,x ) ∈R − S ⇔ ( y,x ) ∈R ∧ ( y,x ) ∉S ⇔ ( x , y ) ∈R ∧ ( x , y ) ∉S ⇔ ( ...