FOM: expr. power of syntax

[Thomas Forster]

Dear FOM-ers,
             I ahve recently been putting the finishing touches to an
undergraduate textbook on logic, and it has caused me to think quite
hard about some issues i want to sell to the kiddies.  In it i make a
big fuss about how essentially all the progress in modern logic became
possible once one had the idea of separating syntax from semantics so
that one could prove completeness theorems and the like.  We've had a
lot to say over the last 100yrs or so about the expressive power of
various kinds of syntax!  It then occurred to me that there is
probably quite a lot that can be said along the following lines: we
all know that regular languages (in the sense of Kleene) are pretty
trivial - in the sense that not much can be said in them.  Polynomial
notation for natural numbers seems to be about as good as it gets.  In
particular it's obvious that the language of propositional logic is
context-free not merely regular.  My question is: are there known
theorems which capture this insight rigorously?  One could imagine a
theorem along the lines ``There is no recursive (in the correct sense)
map f from the set of all strings over {p,q,', /\, \/, ~} into any
other language s.t. the image in f of the set of wffs is regular''.

   Does anybody know of such theorems?   If not, i'll have a go at
proving a few myself.....

       Thomas Forster