FOM: On the expressiveness of languages and the recursive complexity of truth

[Roger Bishop Jones]

 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