Question

Show that ${\mathbf{⩽}}_{\mathbf{m}}$ is a transitive relation?

Short answer

It’s proved that ${⩽}_m$ is transitive relation.

Step-by-step solution

Defining ⩽m

Here, ${⩽}_m$ is mapping reducible. Mapping reducible is defined as:

A language L₁ is mapping reducible to language L₂, if there exist a computable function f such that $f:{\sum }^{*}\to {\sum }^{*}$ , where for all w

$w\in A\iff f\left(w\right)\in B$

It is expressed as $A{⩽}_{m}B$.

Defining Transitive relation

A relation is said to be transitive if there are three sets A, B, and C, then if:

Ais related to BandBis related toC.

Then, if A related to C. This means the relation between A, B, and C is transitive.

Proving ⩽m is a transitive relation

Let’s assume that $A{⩽}_{m}B$and $B{⩽}_{m}C$.

Then, two function f and g such that $x\in A\leftrightarrow f\left(x\right)\in B$and $y\in B\leftrightarrow g\left(y\right)\in C$.

Now, assuming a composite function $h\left(x\right)=g\left(f\left(x\right)\right)$. So we will build Turing Machine(TM) which will evaluate as:

• Run TM for f on the input x and produce output y.
• Run TM for g on input y, to produce output$h\left(x\right)=g\left(f\left(x\right)\right)$

Hence, h is a function computed from above TM.

Also,...

This makes $A{⩽}_{m}C$to be reduced by function h.

Hence, ${⩽}_m$ is transitive relation.