[FOM] Tarski and progress in decidability

[William.Piper@colorado.edu]

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