Abstract

Let L be a first-order language and Φ and ψ two $\Sigma _{1}^{1}$ L-sentences that cannot be satisfied simultaneously in any finite L-structure. Then obviously the following principle Chain L,Φ,ψ (n,m) holds: For any chain of finite L-structures C 1 ,...,C m with the universe [n] one of the following conditions must fail: 1. $C_{1}\vDash \Phi $ , 2. C i ≅ C i+1 , for i = 1,...,m — 1, 3. $C_{m}\vDash \Psi $ . For each fixed L and parameters n,m the principle Chain L,Φ,ψ (n,m) can be encoded into a propositional DNF formula of size polynomial in n,m. For any language L containing only constants and unary predicates we show that there is a constant c L such that the following holds: If a constant depth Frege system in DeMorgan language proves Chain L,Φ,ψ (n, c L · n) by a size s proof then the class of finite L-structures with universe [n] satisfying Φ can be separated from the class of those L-structures on [n] satisfying ψ by a depth 3 formula of size $2^{{\rm log}(s)^{O(1)}}$ and with bottom fan-in ${\rm log}(s)^{O(1)}$