Timeline for Decidability survives new constants

8 events

when toggle format	what		by	license	comment
Mar 4 at 14:09	history	edited	Joel David Hamkins		edited tags
Nov 6, 2012 at 11:16	comment	added	Emil Jeřábek		Any formula $\phi(x)$ is equivalent to an existential formula $\psi(x)$, and since $M$ is decidable, we can actually compute $\psi$. Then $M\models\phi(n)$ reduces to $M\models\psi(n)$, and as $\psi$ is existential and $M$ is recursive, this makes $\{\phi:M\models\phi(n)\}$ recursively enumerable. However, its complement is also recursively enumerable, as the same argument also applies to $\neg\phi(x)$. Thus, it is decidable.
Nov 5, 2012 at 21:28	comment	added	Noah Schweber		@Emil, I'm probably being thick, but: why does remark 2 apply if $M$ is model complete?
Nov 5, 2012 at 15:47	history	edited	Marcus	CC BY-SA 3.0	added 5 characters in body
Nov 5, 2012 at 15:41	history	edited	Marcus	CC BY-SA 3.0	I made clear what "decidable" means in the question
Nov 5, 2012 at 15:03	comment	added	Emil Jeřábek		Remark 2 applies even if $M$ (or even $(M,n)$) is only model complete.
Nov 5, 2012 at 13:32	answer	added	Joel David Hamkins		timeline score: 4
Nov 5, 2012 at 12:26	history	asked	Marcus	CC BY-SA 3.0