Results 1 to 2 of 2

Thread: Enderton Problem 3.5

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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)$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enderton 3.5 Problem 1
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 27th 2011, 10:59 AM
  2. Enderton 3.3 Problem 5
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 19th 2011, 07:34 AM
  3. Enderton 3.3 Problem 8
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Dec 19th 2011, 05:46 AM
  4. Enderton 3.1 problem 1 (p.193)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Dec 4th 2011, 10:30 AM
  5. Enderton 3.1 Problem 6 (p. 193)
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Dec 3rd 2011, 12:12 PM

Search Tags


/mathhelpforum @mathhelpforum