Re: Question on Conservative Extensions

This question came about because I'm doing some problems on
undecidability and they state assumptions in two ways.

(1) T' is a finitely axiomatizable theory of L', and T = T' [intersect]

Sn_L.
(2) Let S be a finite set of sentences of L. Then T = Cn_L(S) and T' =
Cn_{L'}(S).

Here's an example of two of the problems:

Let L be a language with just finitely many non-logical symbols and Let
L' = L U {c}, where c is a constant symbol not in L. Assume that T' is
a finitely axiomatizable essentially undecidable theory of L' and let T
= T' [intersect] Sn_L (where Sn_L represents the sentences of L). Prove
that T is essentially undecidable.

---------------------

Let L be a language with just finitely many nonlogical symbols and let
L' = L U {c}, where c is an individual constant symbol not in L. Let S
be a set of sentences of L and Let T be the consequences of S in L,
while T' is the consequences of S in L'. Prove that T is undecidable
iff T' is undecidable.


Wouldn't the proofs of these two problems be very similar (of corse,
apart from the statement in the second problem that since T' is a
conservative extension of T, if T is undecidable, then T' is
undecidable)? In the first I dont see the need for the finitely
axiomatizable part.

.

Relevant Pages

  • Re: Godels comments about the "true reason" for incompleteness
    ... arbitrary Q. Obviously there is an implied quantification over Q, ... letters of the object language). ... we want to convey that "all" propositions follow from a contradiction. ... refutable in PA and as confirmed by the supposed undecidability of S. ...
    (sci.logic)
  • Re: Godels comments about the "true reason" for incompleteness
    ... principles regarding formal sentences result in theories synonymous, ... We now perform a mutual translation as follows. ... expressible in the language of T into the language of PA. ... Similarly the undecidability of in T ...
    (sci.logic)
  • Re: .EXE -> .ASM -> .EXE
    ... Since the language of the two examples of the "liar's paradox" which I ... propositional logic *does* map exactly to the concept of undecidability ... in Computer Science. ... you're confusing computability with decidability. ...
    (alt.lang.asm)