Hostname: page-component-848d4c4894-wg55d Total loading time: 0 Render date: 2024-06-03T07:05:58.198Z Has data issue: false hasContentIssue false
  • English
  • Français

On the expressibility hierarchy of Magidor-Malitz quantifiers

Published online by Cambridge University Press:  12 March 2014

Matatyahu Rubin  and
Saharon Shelah
Matatyahu Rubin
Affiliation:
Ben Gurion University of the Negev, Beer Sheva, Israel
Saharon Shelah
Affiliation:
The Hebrew University of Jerusalem, Jerusalem, Israel
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that the logics of Magidor-Malitz and their generalization by Rubin are distinct even for PC classes.

Let M ⊨ Qnx1 … xnφ(x1 … xn) mean that there is an uncountable subset A of ∣M∣ such that for every a1 …, an ∈ A, M ⊨ φ[a1, …, an].

Theorem 1.1 (Shelah) (♢ℵ1). For every n ∈ ωthe classKn+1 = {‹A, R› ∣ ‹A, R› ⊨ ¬ Qn+1x1 … xn+1R(x1, …, xn+1)} is not an ℵ0-PC-class in the logic ℒn, obtained by closing first order logic underQ1, …, Qn. I.e. for no countable ℒn-theory T, isKn+1the class of reducts of the models of T.

Theorem 1.2 (Rubin) (♢ℵ1). Let M ⊨ QE x yφ(x, y) mean that there is A ⊆ ∣M∣ such thatEA, φ = {‹a, b› ∣ a, b ∈ A and M ⊨ φ[a, b]) is an equivalence relation on A with uncountably many equivalence classes, and such that each equivalence class is uncountable. Let KE = {‹A, R› ∣ ‹A, R› ⊨ ¬ QExyR(x, y)}. Then KE is not an ℵ0-PC-class in the logic gotten by closing first order logic under the set of quantifiers {Qn ∣ n ∈ ω) which were defined in Theorem 1.1.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 48 , Issue 3 , September 1983 , pp. 542 - 557
Copyright
Copyright © Association for Symbolic Logic 1983

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[F]Fodor, G., Proof of a conjecture of P. Erdos, Acta Universitatis Szegediensis, Acta Scientiarum Mathematicarum, vol. 14 (1952), pp. 219–227.Google Scholar
[G]Garavaglia, S., Relative strength of Malitz quantifiers, Notre Dame Journal of Formal Logic, vol. 19 (1978), pp. 495–503.CrossRefGoogle Scholar
[H]Hajnal, A., Proof of a conjecture of S. Ruziewicz, Fundamenta Mathematicae, vol. 50 (1961), pp. 123–128.CrossRefGoogle Scholar
[Kr]Keisler, H. J., Logic with the quantifier “there exist uncountably many”, Annals of Mathematical Logic, vol. 1 (1970), pp. 1–93.CrossRefGoogle Scholar
[KT]Kunen, K. and Tall, F.Google Scholar
[Ma, Re]Malitz, J. and Reinhardt, W., Maximal models in the language with quantifier “there exist uncountably many”, Pacific Journal of Mathematics, vol. 40 (1972), pp. 139–155.CrossRefGoogle Scholar
[MM]Magidor, M. and Malitz, J., Compact extensions of L(Q)(part 1a), Annals of Mathematical Logic, vol. 2 (1977), pp. 217–261.CrossRefGoogle Scholar
[MR]Malitz, J. and Rubin, M., Fragments of higher order logic, Mathematical Logic in Latin America, North-Holland Studies in Logic, vol. 99, North-Holland, Amsterdam, 1980, pp. 219–238.Google Scholar
[Ra]Rabin, M.O., Arithmetical extensions with prescribed cardinality, Koninklijke Nederlandse Akademie von Wetenschappen, Proceedings, Series A, Mathematical Sciences, vol. 21 (1959), pp. 439–446.Google Scholar
[RS]Rubin, M. and Shelah, S., Combinatorial problems on trees. Partitions, ⊿-systems and large free subsets, Annals of Mathematical Logic (to appear).Google Scholar
[Sl]Shelah, S., Models with second order properties. III, Omitting types in λ+ for L(Q), Proceedings of the “Berlin Workshop in Logic July 1977”, Archiv fur Mathematische Logik und Grundlagenforschung, vol. 21 (1980), pp. 1–11.Google Scholar