91Ó°ÊÓ

Here, ${â\copyright ½}_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:{∑}^{*}→{∑}^{*}$ , where for all w

$w∈A⇔f\left(w\right)∈B$

It is expressed as $A{â\copyright ½}_{m}B$.

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.

Let’s assume that $A{â\copyright ½}_{m}B$and $B{â\copyright ½}_{m}C$.

Then, two function f and g such that $x∈A↔f\left(x\right)∈B$and $y∈B↔g\left(y\right)∈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{â\copyright ½}_{m}C$to be reduced by function h.

Hence, ${â\copyright ½}_m$ is transitive relation.