1. ## Enderton Problem 3.5

(Lindenbaum) Let $T$ be a decidable consistent theory (in a reasonable language). Show that $T$ can be extended to a complete decidable consistent theory $T^{'}$. Suggestion: Examine in turn each sentence $\sigma$; add either $\sigma$ or $\neg \sigma$ to $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 $f$ from $\mathbb{N}$ to (the codes of) all sentences in the language.

Let $T_0=T$. Also, let $g(n)=f(n)$ if $T_n\cup\{f(n)\}$ is consistent and $g(n)=\neg f(n)$ (the negation of the formula with the code $f(n)$) otherwise. Finally, let $T_{n+1}=T_n\cup\{g(n)\}$. Prove that all $T_n$ and, therefore, $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 $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 $T_\omega\vdash\alpha$, i.e., if $\alpha\in T_\omega$, is to find n such that $f(n)=\sharp\alpha$ and see if $g(n)=f(n)$ or $g(n)=\neg f(n)$.