Sh:171

• Shelah, S. (1986). Classifying generalized quantifiers. In Around classification theory of models, Vol. 1182, Springer, Berlin, pp. 1–46. DOI: 10.1007/BFb0098504 MR: 850052
  Part of [Sh:d]
• Abstract:
  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]

  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 \le \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\neq\lambda_3,
  rest on the case of equality page 35 line -16; defining \chi page 35 line -2

  6.11 page 40: finishing this case and from now on \chi\ge 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\le\lambda \le 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).

• published version (46p)

@incollection{Sh:171,
 author = {Shelah, Saharon},
 title = {{Classifying generalized quantifiers}},
 booktitle = {{Around classification theory of models}},
 series = {Lecture Notes in Math.},
 volume = {1182},
 year = {1986},
 pages = {1--46},
 publisher = {Springer, Berlin},
 mrnumber = {850052},
 mrclass = {03C80 (03C85)},
 doi = {10.1007/BFb0098504},
 note = {Part of [Sh:d]},
 refers_to_entry = {Part of [Sh:d]}
}