FOM: expr. power of syntax

[Steve Stevenson]

 >              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''.

I think you're referring to "formal languages." 

@Book{salomaa73:_formal_languag,
  author =	 {Arto Salomaa},
  title = 	 {Formal Languages},
  publisher = 	 {Academic Press},
  year = 	 1973
}