Hostname: page-component-745bb68f8f-v2bm5 Total loading time: 0 Render date: 2025-01-11T04:28:57.688Z Has data issue: false hasContentIssue false
  • English
  • Français

FINITE RELATION ALGEBRAS

Part of: Algebraic logic Model theory

Published online by Cambridge University Press:  19 October 2021

JAMES MATHEW KOUSSAS Open the ORCID record for JAMES MATHEW KOUSSAS [Opens in a new window]
JAMES MATHEW KOUSSAS*
Affiliation:
LA TROBE UNIVERSITY MELBOURNE, VICTORIA, AUSTRALIA
*
E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We will show that almost all nonassociative relation algebras are symmetric and integral (in the sense that the fraction of both labelled and unlabelled structures that are symmetric and integral tends to $1$ ), and using a Fraïssé limit, we will establish that the classes of all atom structures of nonassociative relation algebras and relation algebras both have $0$ – $1$ laws. As a consequence, we obtain improved asymptotic formulas for the numbers of these structures and broaden some known probabilistic results on relation algebras.

Keywords

relation algebrasatom structures0-1 laws

MSC classification

Primary: 03G15: Cylindric and polyadic algebras; relation algebras
Secondary: 03C13: Finite structures
Type
Article
Information
The Journal of Symbolic Logic , Volume 88 , Issue 2 , June 2023 , pp. 874 - 888
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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

Badesa, C., The Birth of Model Theory: Löwenheim’s Theorem in the Frame of the Theory of Relatives , Princeton University Press, Princeton, 2004. Translated from the Spanish by Michael Maudsley.CrossRefGoogle Scholar
Bell, J. P. and Burris, S. N., Compton’s method for proving logical limit laws , Model Theoretic Methods in Finite Combinatorics , Contemporary Mathematics, 558, American Mathematical Society, Providence, 2011.Google Scholar
Carnap, R., Logical Foundations of Probability , University of Chicago Press, Chicago, 1950.Google Scholar
Compton, K., A logical approach to asymptotic combinatorics. I. First-order properties . Advances in Mathematics , vol. 65 (1987), pp. 65–96.CrossRefGoogle Scholar
Compton, K., A logical approach to asymptotic combinatorics. II. Monadic second-order properties . Journal of Combinatorial Theory. Series A , vol. 50 (1989), pp. 110–131.CrossRefGoogle Scholar
De Morgan, A., Syllabus of a Proposed System of Logic , Walton and Maberly, London, 1860.Google Scholar
Fagin, R., Probabilities on finite models . this Journal, vol. 41 (1976), pp. 50–58.Google Scholar
Fagin, R., The number of finite relational structures . Discrete Mathematics , vol. 19 (1977), pp. 17–21.CrossRefGoogle Scholar
Fraïssé, R., Sur l’extension aux relations de quelques propriétés des ordres . Annales Scientifiques de l’École Normale Supérieure, Série 3 , vol. 71 (1954), pp. 363–388.CrossRefGoogle Scholar
Freese, R., On two kinds of probability in algebra . Algebra Universalis , vol. 27 (1990), pp. 70–79.10.1007/BF01190254CrossRefGoogle Scholar
Givant, S., Introduction to Relation Algebras , Springer, Cham, 2017.CrossRefGoogle Scholar
Glebskiĭ, Y. V., Kogan, D. I., Liogon’kiĭ, M. I., and Talanov, V. A., Range and degree of realizability of formuas in the restricted predicate calculus (in Russian) . Kibernetika (Kiev) , vol. 2 (1969), pp. 17–27 (English translation: Cybernetics , vol. 5 (1969), pp. 142–154).Google Scholar
Hirsch, R. and Hodkinson, I., Relation Algebras by Games , Studies in Logic and the Foundations of Mathematics, 147, North-Holland, Amsterdam, 2002.Google Scholar
Hirsch, R., Jackson, M. G., and Kowalski, T., Algebraic foundations for qualitative calculi and networks . Theoretical Computer Science , vol. 768 (2019), pp. 99–116.CrossRefGoogle Scholar
Hodges, W., A Shorter Model Theory , Cambridge University Press, Cambridge, 1997.Google Scholar
Liogon’kiĭ, M. I., On the question of quantitative characteristics of logical formulas (in Russian) . Kibernetika (Kiev) , vol. 3 (1970), pp. 16–22 (English translation: Cybernetics , vol. 6 (1970), pp. 205–211).Google Scholar
Lyndon, R. C., The representation of relation algebras . Annals of Mathematics. Second Series , vol. 51 (1950), pp. 707–727.CrossRefGoogle Scholar
Maddux, R. D., Some varieties containing relation algebras . Transactions of the American Mathematical Society , vol. 272 (1982), pp. 501–526.CrossRefGoogle Scholar
Maddux, R. D., Finite integral relation algebras , Universal Algebra and Lattice Theory (S. C. Charleston, editor), Springer, Berlin, 1985, pp. 175–197.CrossRefGoogle Scholar
Maddux, R. D., A perspective on the theory of relation algebras . Algebra Universalis , vol. 31 (1994), pp. 456–465.CrossRefGoogle Scholar
Maddux, R. D., Relation Algebras , Studies in Logic and the Foundations of Mathematics, 150, North-Holland, Amsterdam, 2006.Google Scholar
Peirce, C. S., Description of a notation for the logic of relatives, resulting from an amplification of the conceptions of Boole’s calculus of logic . Memoirs of the American Academy of Arts and Sciences , vol. 9 (1873), no. 2, pp. 317–378.CrossRefGoogle Scholar
Russell, B., The Principles of Mathematics , Cambridge University Press, Cambridge, 1903.Google Scholar
Schröder, E., Vorlesungen und Logik der Relative , Vorlesungen über die Algerbra der Logik, vol. 3, Teubner, Leibzig, 1895.Google Scholar
Tarski, A., On the calculus of relations . this Journal, vol. 6 (1941), pp. 73–89.Google Scholar