FOM: On the expressiveness of languages and the recursive complexity of truth
Roger Bishop Jones
rbjones at rbjones.com
Mon Sep 4 12:34:08 EDT 2000
PREAMBLE/RECAPITULATION
In a recent exchange with Steve Simpson I offered the following brief
justification of a previous denial (by me) that a recently reviewed book by
Manzano
could contain a reduction of second order to first order logic which would
be satisfactory for all observers:
>I know that Manzano's book contains no effective truth preserving
reduction
>of standard second order logic to first order logic because the true
>sentences of first order logic are recursively enumerable, whereas those
of
>standard second order logic are not.
At this point I had made a connection in my mind between the expressiveness
of languages and the recursive complexity of their sets of true sentences,
which however I did not mention (thinking it obvious).
Later, among his other contributions Martin Davis emphasised the complexity
of second order validities:
>2. Joe Shipman has indicated some of the set-theoretic cans of worms
opened
>when one considers full validity for second-order sentences. I want to add
>the remark that many open mathematical questions are equivalent to the
>validity of corresponding sentences of second-order logic. This includes
>Goldbach's conjecture, the twin primes conjecture, and the Riemann
>Hypothesis. Likewise the various combinatorial problems that Harvey
>Friedman has been showing require large cardinal assumptions for their
>proof are each also equivalent to such a sentence. Obviously this fact
>casts no particular light on these problems, but rather shows how
>intractable second-order validity is.
To me, having in mind the above connection, this is a testimony to the
expressiveness of second order logic, and a confirmation of my reasons for
resisting attempts to drop it in histories dustbin.
This was a part of a short series of exchanges in which someone says
something about second order validities in a tone of horror, and I respond
inverting the tone.
Martin next issued a challenge to me to provide examples illustrating the
greater expressiveness of second order logic.
Because of the fact that his recent messages had provided me with the
strongest evidence so far
of the expressiveness of second order logic, it did not occur to me for one
second that he really needed examples.
Only after sending my response did it occur to me that there may be some
readers who have not yet seen the connection.
EXPRESSIVENESS & COMPLEXITY
I am not aware that any precise sense has been given to the word
"expressive", if it has, the sense proposed here is not intended to be the
same.
The basic idea is that a formal language A is more expressive than another
B
if everything that can be said in B can be said in A.
One way to show this is by exhibiting a special kind of reduction from the
sentences of B to those of A.
We will call this kind of reduction a "translation", hinting that we expect
it to preserve meaning.
Because different languages are likely to have their semantics specified in
different ways, to make "meaning preserving" precise may unduly restrict
the
scope of the definition.
An alternative very weak constraint on the kind of reduction which could
count as a translation for the purpose of ordering languages by
expressiveness is that which I used in my discussion with Steve Simpson.
The proposed minimal constraint on reductions is that they be effective
and truth preserving.
>From this an ordering of languages by expressiveness may be derived.
Language A is less expressive than (or as expressive as) language B only if
there is an effective truth preserving map from the sentences of A into
those of B.
Now spelling out the connection between expressiveness (as thus partly
defined) and complexity (degree of unsolvability) of truth:
A translation from A to B reduces the decision problem for truth in A to
that in B, and is therefore not possible if the degree of A is higher than
that of B.
Consequently if truth in A has a higher degree than truth in B, A is
strictly more expressive than B.
COMPLETENESS
On the desirability of completeness we may now note, that if a logic is
complete its truths are recursively enumerable.
Consequently, all complete logics stand on the lowest rung of this ladder
of
expressiveness.
(speaking loosely; the order is not linear)
EXAMPLES
If examples are still needed the most obvious is the language of true
(first
order) arithmetic, which from these considerations is less
expressive than second order logic, but not less expressive than first.
APOLOGIES
I am not a logician, and this is thrown together.
I don't doubt that others could (and perhaps have) done this much better.
Roger Jones
RBJones at RBJones.com
More information about the FOM
mailing list