On probabilistic elimination of generalized quantifiers. (English) Zbl 0996.03023
Let \(Q\) be a collection of generalized quantifiers. The author gives a convenient characterization for the cases where the logic \(L^\omega_{\infty\omega}(Q)\) has almost sure quantifier elimination [in the sense of Yu. V. Glebskij, D. I. Kogan, M. I. Liogon’kij and V. A. Talanov, Kibernetika 1969, No. 2, 17-27 (1969; Zbl 0209.30803) and R. Fagin, J. Symb. Log. 41, 50-58 (1976; Zbl 0341.02044)]. The results provide a method to prove zero-one and convergence laws for these logics. The paper contains many extensions of known zero-one laws.
Reviewer: S.R.Kogalovskij (Ivanovo)
MSC:
| 03C10 | Quantifier elimination, model completeness, and related topics |
| 03C13 | Model theory of finite structures |
| 03C75 | Other infinitary logic |
Keywords:
generalized quantifiers; almost sure quantifier elimination; convergence laws; zero-one lawsReferences:
| [1] | Random graphs, Academic Press, London, ( 1985). |
| [2] | Chernoff, Ann Math Stat 23 pp 493– (1952) · Zbl 0048.11804 · doi:10.1214/aoms/1177729330 |
| [3] | Feasible computation through model theory,Ph.D. thesis, University of Pennsylvania, 1993. |
| [4] | and Generalized quantifiers and 0-1 laws, Proc Tenth Annual IEEE Symp Logic in Computer Science, 1995, pp. 54-64. |
| [5] | Fagin, J Symbolic Logic 41 pp 50– (1976) · doi:10.1017/S0022481200051756 |
| [6] | and Asymptotic probabilities of languages with generalized quantifiers, Proc Eighth Annual IEEE Symp Logic in Computer Science, 1993, pp. 199-207. |
| [7] | Glebskii, Kibernetika (Kiev) 5 pp 17– (1969) |
| [8] | Hella, Bull Symbolic Logic 2 pp 422– (1996) · Zbl 0869.03019 · doi:10.2307/421173 |
| [9] | Knyazev, Kibernetica 2 pp 110– (1990) |
| [10] | Kolaitis, Ann Pure and Applied Logic 74 pp 23– (1995) · Zbl 0826.03017 · doi:10.1016/0168-0072(94)00025-X |
| [11] | Kolaitis, Inform and Comput 98 pp 258– (1992) · Zbl 0762.03016 · doi:10.1016/0890-5401(92)90021-7 |
| [12] | Lindström, Theoria 32 pp 186– (1966) |
| [13] | Luosto, J Symbolic Logic 65 pp 1241– (2000) · Zbl 0964.03036 · doi:10.2307/2586699 |
| [14] | Lynch, Ann Math Logic 18 pp 91– (1980) · Zbl 0433.03020 · doi:10.1016/0003-4843(80)90014-5 |
| [15] | Lynch, Random Struct Alg 5 pp 155– (1994) · Zbl 0789.03014 · doi:10.1002/rsa.3240050115 |
| [16] | Lynch, J Symbolic Logic 62 pp 609– (1997) · Zbl 0882.03038 · doi:10.2307/2275550 |
| [17] | McArthur, Lecture Notes in Comput Sci 933 pp 228– (1995) · doi:10.1007/BFb0022259 |
| [18] | Shelah, Random Struct Alg 5 pp 375– (1994) · Zbl 0807.03023 · doi:10.1002/rsa.3240050302 |
| [19] | Spencer, J Symbolic Logic 58 pp 33– (1993) · Zbl 0788.03038 · doi:10.2307/2275320 |
| [20] | Väänänen, J Logic Lang Inform 6 pp 275– (1997) · Zbl 0880.03014 · doi:10.1023/A:1008209019899 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
