1. ## Enderton Problem 3.5

(Lindenbaum) Let $\displaystyle T$ be a decidable consistent theory (in a reasonable language). Show that $\displaystyle T$ can be extended to a complete decidable consistent theory $\displaystyle T^{'}$. Suggestion: Examine in turn each sentence $\displaystyle \sigma$; add either $\displaystyle \sigma$ or $\displaystyle \neg \sigma$ to $\displaystyle T$. But take care to maintain decidability.

I think the corresponding definition of decidability is given in page 62 of the textbook.

Any hint to start this problem?

Thanks.

2. ## Re: Enderton Problem 3.5

There exists a computable surjection $\displaystyle f$ from $\displaystyle \mathbb{N}$ to (the codes of) all sentences in the language.

Let $\displaystyle T_0=T$. Also, let $\displaystyle g(n)=f(n)$ if $\displaystyle T_n\cup\{f(n)\}$ is consistent and $\displaystyle g(n)=\neg f(n)$ (the negation of the formula with the code $\displaystyle f(n)$) otherwise. Finally, let $\displaystyle T_{n+1}=T_n\cup\{g(n)\}$. Prove that all $\displaystyle T_n$ and, therefore, $\displaystyle T_\omega\stackrel{\text{def}}{=} \bigcup_{n\in\mathbb{N}} T_n$ are consistent. So far this is a standard procedure for building a maximal consistent theory containing a given theory T. Show that $\displaystyle T_\omega$ is complete.

Prove that there is a way to compute each g(n) knowing g(0), ..., g(n - 1). So, one way to find if $\displaystyle T_\omega\vdash\alpha$, i.e., if $\displaystyle \alpha\in T_\omega$, is to find n such that $\displaystyle f(n)=\sharp\alpha$ and see if $\displaystyle g(n)=f(n)$ or $\displaystyle g(n)=\neg f(n)$.