[net.math] logic question

debray@sbcs.UUCP (Saumya Debray) (12/24/83)

:
Given two logics A and B, and A is more expressive than B:

(1) if A and B are both decidable, does the fact that A is more
    expressive than B imply that A's decision procedure is harder
    (i.e. of higher complexity) than B's?

(2) if A and B are not both decidable, does the fact that A is more
    expressive than B imply that A is of a higher unsolvability degree
    than B?


-- 

Saumya Debray
SUNY at Stony Brook

		{floyd, bunker, cbosgd, mcvax, cmcl2}!philabs!
							      \
	Usenet:						       sbcs!debray
							      /
		   {allegra, teklabs, hp-pcd, metheus}!ogcvax!

	CSNet: debray@suny-sbcs@CSNet-Relay

condict@csd1.UUCP (Michael Condict) (12/27/83)

Well, it's nice to finally see something other than number theory or
real analysis mentioned in this group.  I'm not sure of exactly what you
mean by "logic" and by "A is more expressive than B" but under the most
likely assumptions, question (1) can be answered as follows (the question
was: when A is more expressive than B and both are decidable is it guaranteed
that A's decision procedure is harder than B's):

(i) By "logic", I assume you mean any formal language with a semantic definition
that assigns truth values to strings (or sentences) in the language (and
possibly an associated calculus for proving theorems)

(ii) If by "more expressive" you mean that the language of A contains the
language of B as a subset, then the answer is easy.  Since each sentence of B
is a sentence of A, A's decision procedure can be directly used for B, so it
certainly cannot be any harder to decide truths in B.  It may, however, be
just as hard to decide B.

(ii) Under the more general assumption that A expresses B under some
translation (from sentences of B to sentences of A that are equivalent), then
the immediate answer is that it can not be harder to decide
B than the sum of the complexity for A and complexity of the translation.  As
usual, if the translation is polynomial, one can safely ignore it when
dealing with complexity classes of polynomial degree or higher.

(iii) I'm afraid, however, that you were really interested in the case when
A can express B but B cannot express A (that is when A is strictly more
expressive than B) and that you wanted to know whether that meant the decision
procedure for A had to be strictly harder than for B.  Well, to answer that,
it must first be clear exactly what you mean by "B cannot express A", because
if A and B are both decidable, and B can express both *true* and *false* then,
in some sense, the computable function that takes any valid sentence of A to
*true* in B and any invalid sentence to *false* correctly expresses A in B.
However, if by "expresses" you mean that each sentence of A must be mapped to
a sentence of B containing the same set of free variables and in such a way
that, for every interpretation giving values to those free variables, the
B sentence has the same truth value as the A sentence, then I don't know the
answer.

I believe the analysis for the undecidable case (question (2)) is similar.

Michael Condict        ...!cmcl2!csd1!condict
Courant Inst., N.Y.U.