Enderton Problem 3.5

**logics** · January 4th 2012, 06:00 AM

(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.

**emakarov** · January 5th 2012, 11:49 AM

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)$ .

Thread: Enderton Problem 3.5

LinkBack

Thread Tools

Display

Enderton Problem 3.5

Re: Enderton Problem 3.5

Similar Math Help Forum Discussions

Enderton 3.5 Problem 1

Enderton 3.3 Problem 5

Enderton 3.3 Problem 8

Enderton 3.1 problem 1 (p.193)

Enderton 3.1 Problem 6 (p. 193)

Search Tags