The finitely axiomatizable complete theories of non-associative arrow frames. (English) Zbl 1457.03043
The paper studies the non-associative arrow logic NAL.
One of the important notions used for studying NAL is a notion of normal forms. Let \(F_k(X)\) denote a set of normal forms of degree \(k\) in variable from \(X\). Then the following holds:
There is an algorithm that, given a formula \(\varphi\), a set of propositional variables \(X \supseteq \mathrm{var}(\phi)\) and a finite ordinal \(k\) bigger than or equal to the maximum depth of modal operators nesting in \(\phi\), generates a finite set \(\Sigma \subseteq F_k(X)\) such that \(\vDash \varphi \leftrightarrow \bigvee\Sigma\).
A game theory semantic of NAL has been intensively studied. Using it, an alternative proof [I. Németi, Proc. Am. Math. Soc. 100, 340–344 (1987; Zbl 0638.03061)] of the following result is presented: NAL has the finite model property and it is decidable.
In addition, the descriptions of all finitely axiomatizable, all complete and all consistent theories of NAL are given.
A negative answer to a problem concerning the atomicity of the free non-associative relation algebras is given.
One of the important notions used for studying NAL is a notion of normal forms. Let \(F_k(X)\) denote a set of normal forms of degree \(k\) in variable from \(X\). Then the following holds:
There is an algorithm that, given a formula \(\varphi\), a set of propositional variables \(X \supseteq \mathrm{var}(\phi)\) and a finite ordinal \(k\) bigger than or equal to the maximum depth of modal operators nesting in \(\phi\), generates a finite set \(\Sigma \subseteq F_k(X)\) such that \(\vDash \varphi \leftrightarrow \bigvee\Sigma\).
A game theory semantic of NAL has been intensively studied. Using it, an alternative proof [I. Németi, Proc. Am. Math. Soc. 100, 340–344 (1987; Zbl 0638.03061)] of the following result is presented: NAL has the finite model property and it is decidable.
In addition, the descriptions of all finitely axiomatizable, all complete and all consistent theories of NAL are given.
A negative answer to a problem concerning the atomicity of the free non-associative relation algebras is given.
Reviewer: Alex Citkin (Warren)
MSC:
| 03B45 | Modal logic (including the logic of norms) |
| 03G15 | Cylindric and polyadic algebras; relation algebras |
| 06E25 | Boolean algebras with additional operations (diagonalizable algebras, etc.) |
Citations:
Zbl 0638.03061References:
| [1] | Andréka, H.; Jónsson, B.; Németi, I., Free algebras in discriminator varieties, Algebra Universalis, 28, 3, 401-447 (1991) · Zbl 0745.03050 |
| [2] | Andréka, H.; Monk, J. D.; Németi, I., Algebraic Logic, Colloquia Mathematica Societatis János Bolyai, vol. 54 (1991), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam-Oxford-New York · Zbl 0741.00041 |
| [3] | Andréka, H.; Ferenczi, M.; Németi, I., Cylindric-Like Algebras and Algebraic Logic, Bolyai Soc. Math. Stud., vol. 22 (2013), Springer Publishing Company |
| [4] | Aslan, T.; Khaled, M., Stone type representation theorems via games, Colloquium Mathematicum, 155, 1, 141-155 (2019) · Zbl 1529.03279 |
| [5] | Fine, K., Normal forms in modal logic, Notre Dame J. Form. Log., 16, 12, 229-237 (1975) · Zbl 0245.02025 |
| [6] | Gabbay, D. M.; Kurucz, A.; Wolter, F.; Zakharyaschev, M., Many-Dimensional Modal Logics: Theory and Applications, Stud. Logic Found. Math., vol. 148 (2003), Elsevier · Zbl 1051.03001 |
| [7] | Gyenis, Z., On atomicity of free algebras in certain cylindric-like varieties, Log. J. IGPL, 19, 1, 44-52 (2011) · Zbl 1216.03067 |
| [8] | Harrop, R., On the existence of finite models and decision procedures for propositional calculi, Proc. Camb. Philos. Soc., 54, 1, 1-13 (1958) · Zbl 0080.00803 |
| [9] | Hirsch, R.; Hodkinson, I., Step by step-building representations in algebraic logic, J. Symbolic Logic, 62, 1, 225-279 (1997) · Zbl 0879.03018 |
| [10] | Hirsch, R.; Hodkinson, I., Complete representations in algebraic logic, J. Symbolic Logic, 62, 3, 816-847 (1997) · Zbl 0893.03025 |
| [11] | Hirsch, R.; Hodkinson, I., Relation Algebras by Games, Stud. Logic Found. Math., vol. 147 (2002), Elsevier: Elsevier North Holland · Zbl 1018.03002 |
| [12] | Hodges, W., Building Models by Games (1985), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0569.03015 |
| [13] | Khaled, M.; Sayed Ahmed, T., On complete representations of algebras of logic, Log. J. IGPL, 17, 3, 267-272 (2009) · Zbl 1168.03050 |
| [14] | Khaled, M., Weak Gödel’s incompleteness property for some decidable versions of the calculus of relations (2016), Manuscript |
| [15] | Khaled, M., Gödel Incompleteness Properties and the Guarded Fragment: an Algebraic Approach (2016), Central European University: Central European University Budapest, PhD thesis |
| [16] | Khaled, M., The free non-commutative cylindric algebras are not atomic, Log. J. IGPL, 25, 5, 673-685 (2017) · Zbl 1492.03023 |
| [17] | Khaled, M., General normal forms for any additive logic, Studia Sci. Math. Hungar., 54, 3, 394-409 (2017) · Zbl 1413.03021 |
| [18] | Maddux, R., Some varieties containing relation algebras, Trans. Amer. Math. Soc., 272, 2, 501-526 (1982) · Zbl 0515.03039 |
| [19] | M. Marx, Dynamic arrow logic with pairs, 1996, pp. 109-129. In: [20]; M. Marx, Dynamic arrow logic with pairs, 1996, pp. 109-129. In: [20] · Zbl 0874.03025 |
| [20] | Marx, M.; Pólos, L.; Masuch, M., Arrow Logic and Multi-Modal Logic, Studies in Logic, Language and Information (1996), CSLI Publications: CSLI Publications Stanford · Zbl 0859.00018 |
| [21] | Marx, M.; Venema, Y., Multi-Dimensional Modal Logic, Appl. Log. Ser., vol. 4 (1997), Kluwer Academic Publishers · Zbl 0942.03029 |
| [22] | Németi, I., Free Algebras and Decidability in Algebraic Logic (1986), Hungarian Academy of Sciences: Hungarian Academy of Sciences Budapest, English version is [24] |
| [23] | Németi, I., Decidability of relation algebras with weakened associativity, Proc. Amer. Math. Soc., 100, 340-344 (1987) · Zbl 0638.03061 |
| [24] | Nemeti, I., Decidable versions of first order logic and cylindric-relativized set algebras, (Csirmaz, L.; Gabbay, D. M.; de Rijke, M., Studies in Logic, Language and Computation. Studies in Logic, Language and Computation, Logic Colloquium’92 (Proc. Veszprem, Hungary 1992) (1995), CSLI Publications), 177-241 · Zbl 0852.03002 |
| [25] | Tarski, A., On the calculus of relations, J. Symbolic Logic, 6, 3, 73-89 (1941) · JFM 67.0973.02 |
| [26] | Tarski, A.; Givant, S., A Formalization of Set Theory Without Variables, Colloquium Publications, vol. 41 (1987), American Mathematical Society: American Mathematical Society Providence, R.I. · Zbl 0654.03036 |
| [27] | van Benthem, J., Modal Logic and Classical Logic, Indices: Monographs in Philosophical Logic and Formal Linguistics, vol. 3 (1983), Humanities Press · Zbl 0639.03014 |
| [28] | van Benthem, J., Language in Action: Categories, Lambdas and Dynamic Logic, Studies in Logic, vol. 130 (1991), North-Holland · Zbl 0717.03001 |
| [29] | van Benthem, J., Dynamic arrow logic, (van Eijck, J.; Visser, A., Logic and Information Flow (1994), MIT Press: MIT Press Cambridge), 15-29 · Zbl 0876.03014 |
| [30] | Y. Venema, A crash course in arrow logic, 1996, pp. 3-34. In: [20]; Y. Venema, A crash course in arrow logic, 1996, pp. 3-34. In: [20] · Zbl 0878.03012 |
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.
