Decidability of logical theories

[4/100%]
Show
LaTeX

ᴬ Is the statement ∃x∀y[x+y=y]\exists x \forall y[x+y=y] a member of Th⁡(N,+)\operatorname {Th}(\mathcal{N},+)? Why or why not? What about the statement ∃x∀y[x+y=x]\exists x \forall y[x+y=x]?

?

ᴬ Let (N,<)(\mathcal{N},<) be the model with universe N\mathcal{N} and the "less than" relation. Show that Th⁡(N,<)\operatorname {Th}(\mathcal{N},<) is decidable.

?

For each m>1m>1 let Zm={0,1,2,…,m−1}\mathcal{Z}_{m}=\left\{ 0,1,2, \ldots , m-1\right\}, and let Fm=(Zm,+,×)\mathcal{F}_{m}=\left(\mathcal{Z}_{m},+, \times \right) be the model whose universe is Zm\mathcal{Z}_{m} and that has relations corresponding to the + and × relations computed modulo mm. Show that for each mm, the theory Th⁡(Fm)\operatorname {Th}\left(\mathcal{F}_{m}\right) is decidable.

?

Let R⊆NkR \subseteq \mathcal{N}^{k} be a kk-ary relation. Say that RR is definable in Th⁡(N,+)\operatorname {Th}(\mathcal{N},+) if we can give a formula ϕ\phi with kk free variables x1,…,xkx_{1}, \ldots , x_{k} such that for all a1,…,ak∈Na_{1}, \ldots , a_{k} \in \mathcal{N}, ϕ(a1,…,ak)\phi \left(a_{1}, \ldots , a_{k}\right) is true exactly when a1,…,ak∈Ra_{1}, \ldots , a_{k} \in R. Show that each of the following relations is definable in Th⁡(N,+)\operatorname {Th}(\mathcal{N},+).

?
(a)

ᴬ R0={0}R_{0}=\left\{ 0\right\}

(b)

R1={1}R_{1}=\left\{ 1\right\}

(c)

R=={(a,a)∣a∈N}R_{=}=\left\{ (a, a) \mid a \in \mathcal{N}\right\}

(d)

R<={(a,b)∣a,b∈N and a<b}R_{<}=\left\{ (a, b) \mid a, b \in \mathcal{N}\text{ and }a<b\right\}

References

[Sip13] Sipser M. Introduction to the Theory of Computation. 3rd ed., Cengage Learning, 2013.