Decidability of logical theories
[4/100%]Show
LaTeX
Problem 6.5 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 6.1 "Exercises"
ᴬ Is the statement a member of ? Why or why not? What about the statement ?
?
Origin: Stated according to the original source
Problem 6.12 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 6.2 "Problems"
ᴬ Let be the model with universe and the "less than" relation. Show that is decidable.
?
Origin: Stated according to the original source
Problem 6.13 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 6.2 "Problems"
For each let , and let be the model whose universe is and that has relations corresponding to the + and × relations computed modulo . Show that for each , the theory is decidable.
?
Origin: Stated according to the original source
Problem 6.28 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 6.2 "Problems"
Let be a -ary relation. Say that is definable in if we can give a formula with free variables such that for all , is true exactly when . Show that each of the following relations is definable in .
?
Origin: Stated according to the original source
(a)
ᴬ
(b)
(c)
(d)
References
[Sip13] Sipser M. Introduction to the Theory of Computation. 3rd ed., Cengage Learning, 2013.