We say that it has a Ramsey property over an ordered structure M = <U, [Omega]> if, for any SC, the following is true:
We also speak of a formula [Psi] having the Ramsey property if the above is true.
1998; Benedikt and Libkin, 1996], the Ramsey property implies the following collapse for generic queries:
1) If L has the Ramsey property over M = <U, [Omega]), and every L([is less than])-query is locally generic, then L has the locally generic collapse over M.
2) If L has the total Ramsey property over M, every L-query is totally generic, then L has the generic collapse over M.
By the Ramsey property, we find an infinite X [subset or equal to] U and a L(<U, [is less than]>)-definable Q' that coincide on X.
Thus, to limit their expressiveness over infinite structures, we have to prove the Ramsey property.
The key in the inductive proofs of the Ramsey property is the case of [Omega]-atomic subformulas.
If M = <R, [Omega])>, where [Omega] is analytic, and L is FO, or FO + lfp, or FO + pfp, or FO + ifp, or FO + count, or SO, then L has the total Ramsey property over M.
This shows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has the total Ramsey property over M, and thus it has generic collapse over M.