Question

For each let Ƶ_m = {0, 1, 2, . . . , m − 1}, and let = (Ƶ_m, +, ×) be the model whose universe is Ƶ_m and that has relations corresponding to the + and × relations computed modulo m. Show that for each m, the theory Th is decidable.

Short answer

Answer:

This statement is decidable is given below.

Step-by-step solution

Turing Machine

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-zero. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

Problem is decidfable.

$M_m=\{0,1,2,...,m-1\}form>1$is a universe

$M_m=(P_{m\text{'}}+,x)$model whose universe is $p_m$.

+ and x are relations over modulo m.

We need to show that $Th\left(f_m\right)$ is decidable.

We can clear observe that Ƶ_m is finite as up to m terms.

So we can easily enumerate all possible values into formula and check if the formula is right or not.

• If it is TRUE, then it belong to $Th\left(f_m\right)$.
• If it is NOT TRUE, then it belong to $Th\left(f_m\right)$.

Let, Ǝx_i such that $\varphi =\left(x_1,x_2,\dots ,x_i\right)$ Put $X_i=0,1,\dots ,m-|$

So, if formula$\varphi =\left(x_1,x_2,\dots ,x_i\right)$ is true for any value of x_i then the original value is true.

Now, a model of theory is considered to be decidable if the formula which is true and also belong to the model.

So, by above recursive strategy, we say is decidable.