Discrete Mathematics question 13 programs p ahd pp as equiva

Discrete Mathematics
question 13

programs p ahd pp as equivaeri they wys the same outputs for given inputs. Is this an equivalence relation on P? Explain. 13. Consider Z × P and define (m, n) ~ (p, q) if rnq np. a) Show that ~is an equivalence relation on & x P (b) Show that is the equivalence relation correspond- ing to lhe lunction 2 x P Q given by f(m, n) = ; see Theorem 2(a). 14. In the proof of Theorem 2(b), we obtained the equality ([5])-[5]. Does this mean that the function has an inverse and that the inverse of v is the identity function

Solution

13) Given that (m,n)~(p,q) if mq =np

Reflexive:

Consider (m,n)~(m,n)

This is true if mn = nm which is true as multiplication is commutative

Symmetric

Let (m,n)~(p,q) Then mq = np

or qm = pn

Hence (p,q)~(m,n)

So symmetric

Transitive:

Let (m,n) ~(p,q) and (p,q)~(r,s)

Then mq = np and ps = rq

Multiply left sides and right sides

mpqs = nprq

Cancel pq to get

ms = nr

Or (m,n)~(r,s)

Hence transitive.

So it follows that ~ is equivalence relation.

--------------------------------------------------

b) f(m,n) = m/n where m/n is rational

f(m,m) = m/m =1 and 1 is rational.

So f is reflexive

Symmetric: If m/n is rational, n not 0

If m~n and n ~p then m/n is rational and n/p is rational

So n and p are not zero

Hence m/p is rational

This implies f(m,p) is true thus transitive.