Results 1 to 2 of 2

Math Help - Enderton Problem 3.5

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    59

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

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

Search Tags


/mathhelpforum @mathhelpforum