From what I understand, Higher Order Logics cannot be reduced to lower ones -- for example, Second Order Logic cannot be reduced to FOPL. But, can't I use FOPL to reason about the behavior of a Turing Machine running a second order logic solver, and thus solve second order logic problems in FOPL?


Edit: I mean reducibility in the sense of <http://en.wikipedia.org/wiki/Second-order_logic#Non-reducibility_to_first-order_logic> that there are second order sentences that cannot be expressed in first order logic. I suppose solve was the wrong word to use. What I meant is that I don't see why one can't view application of the inference rules of second order logic as just string rewriting, and so come up with a way of representing such strings and the inference rules in FOPL, and thereby perform whatever inference I could in Second Order Logic using FOPL.



What is the relationship between FOPL and Higher Order Logics?
As François G. Dorais pointed out you have to read carefully wikipedia's article. 


The main difference in expressiveness between first order logic and second order logic is given by the semantics. 


We can turn a second order language in a special kind of first order language simply considering *second order variables* as variables ranging over a different sort, or making no distinction between *first and second order variables* and using two unary predicates, one for first order objects (i.e. individuals), the other for second order ones (i.e. relations), to distinguish when a variable have to range over individuals or when it ranges over relations.  

With these trick we can completely translate second order syntax in a first order one.


The same trick cannot be applied in general for the second order semantics, in particular for the standard semantics. In standard semantics we impose that in every interpretation the second order variables range over the *power set* of the domain of the interpretation (i.e. the range of variation for first order variables). If we want to reduce second order semantics to first order ones with the trick above we cannot require such strict condition, in this case the domain of variation for second order variable could be every family of subset of the domain of the interpretation. These kind of things are allowed in Henkin semantics which are simply a rewriting of first order multisorted semantics for second order logics but which are also weaker semantics (less expressive) when compared with standard ones.


