[FOM] Tarski and progress in decidability
Timothy Bays
timothy.bays.5 at nd.edu
Wed Jan 14 16:51:28 EST 2004
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
>
More information about the FOM
mailing list