×

Almost everywhere equivalence of logics in finite model theory. (English) Zbl 0869.03019

Let \(L\) and \(L'\) be logics and \(\mu=(\mu_n)_{n\geq 1}\) the uniform measure, i.e., for fixed vocabulary \(\sigma\) the function \(\mu_n\) assigns the same probability to each \(\sigma\)-structure with universe \(\{1,\dots,n\}\). The authors introduce the notion \(L\leq_{\text{a.e}}L'\) (\(L\leq L'\) on a class \(C\) with \(\mu(C):=\lim_{n\to\infty}\mu_n(C)=1\)) and define \(L\equiv_{\text{a.e}}L'\) by \(L\leq_{\text{a.e}}L'\) and \(L'\leq_{\text{a.e}}L\). They state some immediate consequences of well-known theorems, e.g., \(FO\equiv_{\text{a.e}}L^\omega_{\infty\omega}< L_{\infty\omega}\). Moreover, they show that there are infinite ascending \(\leq_{\text{a.e}}\)-chains and arbitrary large finite antichains. For some classical results of model theory, they analyze whether they hold in the almost every sense for finite structures.

MSC:

03C13 Model theory of finite structures
03C40 Interpolation, preservation, definability
PDFBibTeX XMLCite
Full Text: DOI Link Link

References:

[1] DOI: 10.1016/0012-365X(85)90112-8 · Zbl 0579.03006 · doi:10.1016/0012-365X(85)90112-8
[2] Proceedings of the 5th IEEE symposium on logic in computer science pp 168– (1990)
[3] DOI: 10.1016/0890-5401(89)90055-2 · Zbl 0711.03004 · doi:10.1016/0890-5401(89)90055-2
[4] DOI: 10.1002/malq.19750210112 · Zbl 0317.02054 · doi:10.1002/malq.19750210112
[5] Complexity of computation 7 pp 43– (1974)
[6] Publications of the Mathematical Institute of the Hungarian Academy of Sciences 7 pp 17– (1960)
[7] Information and Control 119 pp 160– (1995)
[8] DOI: 10.1016/0022-0000(82)90012-5 · Zbl 0511.68073 · doi:10.1016/0022-0000(82)90012-5
[9] DOI: 10.1007/BF01305232 · Zbl 0785.68043 · doi:10.1007/BF01305232
[10] DOI: 10.1137/0209047 · Zbl 0454.05038 · doi:10.1137/0209047
[11] Proceedings of the 4th IEEE symposium on logic in computer science pp 71– (1989)
[12] Proceedings of the 14th ACM symposium on theory of computing pp 137– (1982)
[13] Foundations of databases (1995) · Zbl 0842.68022
[14] DOI: 10.1090/S0894-0347-1988-0924703-8 · doi:10.1090/S0894-0347-1988-0924703-8
[15] Fundamenda Mathematicae 44 pp 12– (1957)
[16] DOI: 10.1137/0216051 · Zbl 0634.68034 · doi:10.1137/0216051
[17] DOI: 10.1016/S0019-9958(86)80029-8 · Zbl 0612.68086 · doi:10.1016/S0019-9958(86)80029-8
[18] The Journal of Symbolic Logic (1995)
[19] Proceedings ofthe 9th IEEE symposium on logic in computer science pp 40– (1994)
[20] DOI: 10.1016/0168-0072(86)90055-2 · Zbl 0621.03013 · doi:10.1016/0168-0072(86)90055-2
[21] Current trends in theoretical computer science pp 1– (1988)
[22] Computation and proof theory pp 175– (1984)
[23] 3rd ERCIM database research group workshop on updates and constraints handling in advanced database systems, ERCIM-94-W004 CNR pp 130– (1992)
[24] Cybernetics 5 pp 142– (1969) · Zbl 0978.01027
[25] DOI: 10.2307/2272945 · Zbl 0341.02044 · doi:10.2307/2272945
[26] Computer science logic pp 228– (1995)
[27] Proceedings of the 10th IEEE symposium on logic in computer science pp 46– (1995)
[28] Proceedings of the 8th IEEE symposium on logic in computer science pp 191– (1993)
[29] Theoria 32 pp 186– (1966)
[30] DOI: 10.1016/0890-5401(92)90021-7 · Zbl 0762.03016 · doi:10.1016/0890-5401(92)90021-7
[31] DOI: 10.1016/0168-0072(94)00025-X · Zbl 0826.03017 · doi:10.1016/0168-0072(94)00025-X
[32] Probabilistic analysis of a canonical algorithm for graphs (1979)
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.