Question

Let $\mathbf{(}\mathbf{N}\mathbf{,}\mathbf{<}\mathbf{)}$be the model with universe N and the “less than” relation. Show that Th$\mathbf{(}\mathbf{N}\mathbf{,}\mathbf{<}\mathbf{)}$ is decidable.

Short answer

Answer:

This statement id 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.

We will try to convert $Th(N.<)intoTh(N,+)$which is decidable itself.

So, decidability of $Th\left(N,<\right)$can be established by converting sentence S2 of

language $Th\left(N,<\right)$into sentence over the language $Th\left(N,+\right)$.

So, we will going to replace $i<jinS1to\exists k\left[\right(i+k=j)\wedge (k+k\left)\right]inS2$

Here, we use k which is a new variable.

We say S2 is equivalent to S2 because we have i < j which means that we can add a non-zero value in ‘i’ to get ‘j’.

To prove decidability of Th ( N,+) , S2 is to be express in prenex-normal form.

In order to bring important qualifier in the front of sentence, the qualifiers are made to pass through Boolean operation which are in the sentence.

It is to be noted that when the quantifier are brought, (˄ and ˅) will stay same.

Thus, $\neg \exists K\phi$becomes $\forall k\neg \phi and\neg \forall \phi becomes\exists k\neg \phi$

This prove that .$Th\left(N,<\right)$