Alan Reading will talk about "Preservation theorems".
Preservation theorems refer to results describing formula classes in terms of their model theoretic properties. It is a commonplace in algebra that a substructure of a group is a sub-semigroup with cancellation laws such as ab=ac implies b=c. More generally a substructure of a structure satisfies all universal ("for all") statements true in the larger structure. Dually, every existential ("there exists") statement true in the smaller structure is true in the larger. Not perhaps surprisingly, this is a general fact from model theory but perhaps more suprisingly the result reverses and one can prove that universal statements are precisely those preserved downwards in this way. We will see how this is done. The results here will be generalised to other classes and other notions of extension.
Similarly, it is known from algebra that the truth of universal-existential statements are preserved in unions of chains of models. For example, this fact is essential knowledge for the construction of an algebraically closed field. This also is a general fact and there is a converse too. The proof is a bit more delicate as it involves constructing a chain that fails to preserve the truth of a statement under the assumption that that statement is not universal-existential.
Richard Kaye, "Further witnessing theorems with applications".
We will expand on: witnessing theorems for polynomial time, and also for second order bounded arithmetic, with applicaions to predicates that are provably in NP-intersect-co-NP. Model-theoretic interpretations will be given.