[FOM] Tarski and progress in decidability

[Timothy Bays]

I think there must be a typo in problem 1 here.  Suppose we work in a 
language which contains only one non-logical constant: a.  Let S 
contains the sentence Ax x=a.  Let T=S.  Then S and T are compatible, S 
is axiomitizable, and T is decidable.

Is it perhaps the *finitely* axiomitizable that we're supposed to drop? 
  Or have I missed the context of the problem somehow?

Best -- Tim


On Wednesday, January 14, 2004, at 01:23  AM, 
William.Piper at colorado.edu wrote:

> Hello all,
>
>    I am currently reading "Undecidable Theories" by Tarski et al. and 
> have come
> across two "problems" which he claimed are open. Of course, the book 
> was
> published in 1968, so I don't know if this is still the case for these
> two "problems".
>
> Here they are:
>
> (1) On pg. 18, Thm 6. Let T and S be two compatible theories such that 
> every
> constant of S is also a constant of T. If S is essentially undecidable 
> and
> finitely axiomatizable, then T is undecidable, and so is every 
> subtheory of T
> which has the same constants as T.
>
> The "problem" here asks whether or not we can drop the assumption that 
> S is
> essentially undecidable and let S be an arbitrary axiomatizable theory 
> (which
> may not be finitely axiomatizable). I assume that every constant of S 
> must
> still be a constant of T.
>
> (2) The second "problem" is directly related and is mentioned on pg. 
> 19. Does
> every essentially undecidable theory which is axiomatizable have an 
> essentially
> undecidable subtheory which is finitely axiomatizable? If there exist 
> some
> essentially undecidable theories with the previously mentioned 
> property, which
> theories are they and what characterizes them? I.e. what are the 
> necessary and
> sufficient conditions for these particular theories?
>
> Have results on either of these been established since 1968?
>
> Everett
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>