Ultraproducts, Higher Order Logics and Complexity Theory

Gábor Sági

Which ultraproducts preserve the validity of formulas of higher order logics ? To answer this question, we will introduce natural topologies (called ultratopologies) on ultraproducts. We will show, that ultraproducts preserving certain higher order formulas can be characterised in terms of these topologies.

Some connections between classical model theoretic notions and ultratopologies are also proved. In addition, we will present some partial results about a problem due to Tarski and Keisler asking an algebraic– model theoretic (or topological or set theoretic ?) characterisation of pseudo–elementary classes.

Finally we will discuss some consequences of our results and methods to the famous conjecture of complexity theory stating “P − time ≠ NP − time”.

Address: Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, H-1053, Reáltanoda u. 13-15.

E-mail: sagi@math-inst.hu