A Category of Ordered Algebras Equivalent to the Category of Multialgebras

Marcelo Esteban Coniglio; Guilherme Vicentin  de Toledo

doi:10.18778/0138-0680.2023.23

Authors

Marcelo Esteban Coniglio University of Campinas (Unicamp), Institute of Philosophy and the Humanities (IFCH) and Centre for Logic, Epistemology and the History of Science (CLE)(UNICAMP) https://orcid.org/0000-0002-1807-0520
Guilherme Vicentin de Toledo Bar Ilan University, Department of Computer Science, The Spiegel Mathematics & Computer Center https://orcid.org/0000-0002-6539-398X

DOI:

https://doi.org/10.18778/0138-0680.2023.23

Keywords:

multialgebras, ordered algebras, non-deterministic semantics

Abstract

It is well known that there is a correspondence between sets and complete, atomic Boolean algebras (\(\textit{CABA}\)s) taking a set to its power-set and, conversely, a complete, atomic Boolean algebra to its set of atomic elements. Of course, such a correspondence induces an equivalence between the opposite category of \(\textbf{Set}\) and the category of \(\textit{CABA}\)s.

We modify this result by taking multialgebras over a signature \(\Sigma\), specifically those whose non-deterministic operations cannot return the empty-set, to \(\textit{CABA}\)s with their zero element removed (which we call a \(\textit{bottomless Boolean algebra}\)) equipped with a structure of \(\Sigma\)-algebra compatible with its order (that we call \(\textit{ord-algebras}\)). Conversely, an ord-algebra over \(\Sigma\) is taken to its set of atomic elements equipped with a structure of multialgebra over \(\Sigma\). This leads to an equivalence between the category of \(\Sigma\)-multialgebras and the category of ord-algebras over \(\Sigma\).

The intuition, here, is that if one wishes to do so, non-determinism may be replaced by a sufficiently rich ordering of the underlying structures.

References

J. C. Abbott, Implicational algebras, Bulletin mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie, vol. 11(59)(1) (1967), pp. 3–23, URL: http://www.jstor.org/stable/43679502
Google Scholar

A. Avron, I. Lev, Canonical Propositional Gentzen-type Systems, [in:] R. Gore, A. Leitsch, T. Nipkow (eds.), Proceedings of the 1st International Joint Conference on Automated Reasoning (IJCAR 2001), vol. 2083 of LNAI, Springer Verlag (2001), pp. 529–544, DOI: https://doi.org/10.1007/3-540-45744-5_45
Google Scholar DOI: https://doi.org/10.1007/3-540-45744-5_45

M. Baaz, O. Lahav, A. Zamansky, A Finite-valued Semantics for Canonical Labelled Calculi, J. of Automated Reasoning, vol. 51 (2013), pp. 401–430, DOI: https://doi.org/10.1007/s10817-013-9273-x
Google Scholar DOI: https://doi.org/10.1007/s10817-013-9273-x

I. Bošnjak, R. Madarász, On power structures, Algebra and Discrete Mathematics, vol. 2003(2) (2003), pp. 14–35.
Google Scholar

C. Brink, Power structures, Algebra Universalis, vol. 30(2) (1993), pp. 177–216, DOI: https://doi.org/10.1007/BF01196091
Google Scholar DOI: https://doi.org/10.1007/BF01196091

R. H. Bruck, A Survey of Binary Systems, Springer Berlin Heidelberg (1971), DOI: https://doi.org/10.1007/978-3-662-43119-1
Google Scholar DOI: https://doi.org/10.1007/978-3-662-43119-1

W. A. Carnielli, M. E. Coniglio, Paraconsistent Logic: Consistency, Contradiction and Negation, vol. 40 of Logic, Epistemology, and the Unity of Science, Springer International Publishing, Cham, Switzerland (2016), DOI: https://doi.org/10.1007/978-3-319-33205-5
Google Scholar DOI: https://doi.org/10.1007/978-3-319-33205-5

J. Cı̄rulis, A first-order logic for multi-algebras, Novi Sad Journal of Mathematics, vol. 34(2) (2004), pp. 27–36.
Google Scholar

M. E. Coniglio, A. Sernadas, C. Sernadas, J. Rasga, A graph-theoretic account of logics, Journal of Logic and Computation, vol. 19 (2009), pp. 1281–1320, DOI: https://doi.org/10.1093/logcom/exp023
Google Scholar DOI: https://doi.org/10.1093/logcom/exp023

M. E. Coniglio, G. V. Toledo, Weakly Free Multialgebras, Bulletin of the Section of Logic, vol. 51(1) (2021), pp. 109–141, URL: https://czasopisma.uni.lodz.pl/bulletin/article/view/5680
Google Scholar DOI: https://doi.org/10.18778/0138-0680.2021.19

M. E. Coniglio, G. V. Toledo, A Category of Ordered Algebras Equivalent to the Category of Multialgebras, arXiv 2209.08158 [math.CT] (2022), URL: https://arxiv.org/abs/2209.08158
Google Scholar

H. B. Curry, Foundations of mathematical logic, 2nd ed., Dover Books on Mathematics, Dover Publications, Mineola, NY (1977).
Google Scholar

M. Dresher, O. Ore, Theory of Multigroups, American Journal of Mathematics, vol. 60(3) (1938), pp. 705–733, DOI: https://doi.org/https://doi.org/10.2307/2371606
Google Scholar DOI: https://doi.org/10.2307/2371606

G. Hansoul, A duality for Boolean algebras with operators, Algebra Universalis, vol. 17(1) (1983), pp. 34–49, DOI: https://doi.org/10.1007/BF01194512
Google Scholar DOI: https://doi.org/10.1007/BF01194512

F. Marty, Sur une generalization de la notion de groupe, [in:] Comptes rendus du huitième Congrès des mathématiciens scandinaves tenu à Stockholm 14–18 août 1934 (1935), pp. 45–49.
Google Scholar

A. Monteiro, Cours sur les algebrés de Hilbert et de Tarski, Instituto de Matemática, Universidad Nacional del Sur, Bahía Blanca, Argentina (1960).
Google Scholar

A. Monteiro, L. Iturrioz, Les algebrés de Tarski avec un nombre fini de générateurs libres, 1965. A. Monteiro: Unpublished papers I. Notas de Lógica Matemática, 40, Universidad Nacional del Sur, Instituto de Matemática, Bahía Blanca, Argentina. (1996).
Google Scholar

F. M. Nolan, Multi algebras & related structures, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand (1979), URL: http://dx.doi.org/10.26021/2302
Google Scholar

C. Pelea, S. Breaz, Multialgebras and term functions over the algebra of their nonvoid subsets, Mathematica, vol. 43(2) (2001), pp. 143–149
Google Scholar

H. E. Pickett, Homomorphisms and subalgebras of multialgebras, Pacific Journal of Mathematics, vol. 21 (1967), pp. 327–342, DOI: https://doi.org/10.2140/pjm.1967.21.327
Google Scholar DOI: https://doi.org/10.2140/pjm.1967.21.327

U. Rivieccio, Implicative twist-structures, Algebra Universalis, vol. 71(2) (2014), pp. 155–186, DOI: https://doi.org/10.1007/s00012-014-0272-5
Google Scholar DOI: https://doi.org/10.1007/s00012-014-0272-5

M. H. Stone, The Theory of Representations for Boolean Algebras, Transactions of the American Mathematical Society, vol. 40 (1936), pp. 37–111, DOI: https://doi.org/10.2307/1989664
Google Scholar DOI: https://doi.org/10.1090/S0002-9947-1936-1501865-8

G. V. Toledo, Multialgebras and non-deterministic semantics applied to paraconsistent logics, Ph.D. thesis, University of Campinas, Campinas, SP, Brazil (2022), URL: https://repositorio.unicamp.br/acervo/detalhe/1244055
Google Scholar

J. van Oosten, Basic Category Theory, Basic Research in Computer Science. BRICS Lecture Series LS-95-1. Ultrecht University, Netherlands (1995), URL: https://www.brics.dk/LS/95/1/BRICS-LS-95-1.ps.gz
Google Scholar

M. Walicki, S. Meldal, Multialgebras, power algebras and complete calculi of identities and inclusions, [in:] E. Astesiano, G. Reggio, A. Tarlecki (eds.), Recent Trends in Data Type Specification, Springer Berlin Heidelberg, Berlin, Heidelberg (1995), pp. 453–468, DOI: https://doi.org/https://doi.org/10.1007/BFb0014444
Google Scholar DOI: https://doi.org/10.1007/BFb0014444