Classifying generalized quantifiers

by Shelah. [Sh:171]
Around classification theory models, 1986
We address the question of classifying generalized quantifier ranging on a family of relations of fixed arity on a fixed set U. We consider two notions of order (and equivalence) by interpretability. In essence, every such family is equivalent to one consisting of equivalence relations but we have to add a well ordering of length lambda . In the weaker equivalence, there is a gap in cardinality between the size of equivalence relations which can be interpreted and the one needed to interpret, which consistently may occurs. Of course, the problem of classifying families of equivalence relations is clear. The proof proceed by cases, summed up in section 7, where we concentrate on the less fine equivalence relation. [Note pages 24,25 where interchanged]}, abstract1 = { NOTE: if U is countable, the gap in cardinals disappear even for the weaker (i.e. finer) equivalence every such family is equivalent to a family of equivalence relations (if you want just to follow a proof of this then read): 0.6: definition 1.5 page 5: how to represent equivalence relations, hence later we can deal with a family with one isomorphism type 2.2 page 7: finish the analysis for interpreting cases of monadic quantifier 3.5 page 15: finish the analysis of interpreting one to one functions, concerning uniformity see the remark at the bottom of page 15

4.5 page 16: definition of lambda_2 (R) 4.17 page 23: reduction on a relation of cardinality <= lambda_2 (R) Def 5.1 page 26: defining lambda_3 Definition 5.11A(?) defining K^{word} page 3(?) Fact 5.2 page 26(?) lambda_2 in {lambda_3, lambda_2^+} 5.11,5.12, 5.14 pages 31,32,33: analyses the case lambda_2 not= lambda_3, rest on the case of equality page 35 line-16; defining chi page 35 line-2 }, abstract2 = {6.11 page 40: finishing this case and from now on chi >= cardinality(R) when U has cardinality aleph_0 Explanation of the from of the paper: The original aim of this article was to prove that for every K (a family of relations on U on a fixed arity) its quantifier is equivalent to one for KU, a family of equivalence relations (all such classes are assumed to be closed under isomorphism). Sections 1-6 were written for this and realize it to large extent. Clearly it suffice to deal with I with one isomorphism type as long as the interpretations are uniform. But two essential difficulties arise (1) the quantifier exists^{word}_{lambda} (a well ordering of length lambda), provably is not biinterpretable with exists_K for any family K of equivalence classes. This is not so serious: just add another case. (2) It is consistent that there are cardinals chi, lambda satisfying chi <= lambda <= 2^chi such that R is e.g. a family of chi sunsets of lambda, again we cannot reduce this to equivalence relations in general (see section 8) Only under the assumptions V=L and considering more liberal notion of bi-interpretability (equiv_{exp} rather than equiv_{int} the desired result is gotten. However when the gap degenerates for any reason we get the original hope (note exists^{word}_omega is second order quantification).

Back to the list of publications