×

zbMATH — the first resource for mathematics

Equations in free topoboolean algebra. (English. Russian original) Zbl 0624.03007
Algebra Logic 25, 109-127 (1986); translation from Algebra Logika 25, No. 2, 172-204 (1986).
Let \(\Lambda\) be a modal or superintuitionistic logic and \(F_{\omega}(\Lambda)\) the free algebra of rank \(\omega\) in the variety of algebras corresponding to \(\Lambda\). For each of the logics S4 and Int the author obtains the following main results. Let \(\Sigma_ f\) be the signature of \(F_{\omega}(\Lambda)\) enriched by the free generators as constant operations. Then: 1) The universal theory of \(F_{\omega}(\Lambda)\) is decidable and there exists an algorithm constructing an obstacle (i.e., roughly speaking, a counter-example) for those universal formulas of \(\Sigma_ f\) that are false in \(F_{\omega}(\Lambda)\). 2) There exists an algorithm verifying the solvability of equations in \(F_{\omega}(\Lambda)\) and finding the solutions of solvable equations.
Reviewer: S.Rudeanu

MSC:
03B25 Decidability of theories and sets of sentences
03G10 Logical aspects of lattices and related structures
06B25 Free lattices, projective lattices, word problems
08B20 Free algebras
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] G. S. Makanin, ”The problem of solvability of equations in a free semigroup,” Mat. Sb.,103, No. 2, 147–236 (1977). · Zbl 0371.20047
[2] G. S. Makanin, ”Equations in a free group,” Izv. Akad. Nauk SSSR, Ser. Mat.,46, No. 6, 1199–1273 (1982). · Zbl 0511.20019
[3] G. S. Makanin, ”Decidability of the universal and positive theories of the free group,” Izv. Akad. Nauk SSSR, Ser. Mat.,48, No. 4, 735–749 (1984).
[4] V. V. Rybakov, ”Admissible rules of pretabular modal logics,” Algebra Logika,20, No. 4, 440–464 (1981). · Zbl 0489.03005
[5] V. V. Rybakov, ”Decidability of the admissibility problem in modal logics with finitely many strata,” Algebra Logika,23, No. 1, 100–116 (1984).
[6] V. V. Rybakov, ”Admissible rules for logics containing S4.3,” Sib. Mat. Zh.,25, No. 5, 141–145 (1984). · Zbl 0582.03009
[7] V. V. Rybakov, ”A criterion for admissibility of rules in the modal logic S4 and the intuitionistic logic,” Algebra Logika,23, No. 5, 546–572 (1984). · Zbl 0598.03013
[8] Yu. I. Khmelevskii, ”Equations in a free semigroup,” Trudy MIAN SSSR,107 (1976).
[9] Yu. I. Khmelevskii, ”Systems of equations in a free group,” Izv. Akad. Nauk SSSR, Ser. Mat.,35, No. 6, 1237–1268 (1971);36, No. 1, 110–179 (1972).
[10] V. B. Shekhtman, ”Undecidable superintuitionistic calculus of propositions,” Dokl. Akad. Nauk SSSR,240, No. 3, 549–552 (1978). · Zbl 0417.03010
[11] V. B. Shekhtman, ”Undecidable calculi of propositions,” in: Problems of Cybernetics. Nonclassical Logics and Their Application [in Russian], Moscow (1982), pp. 74–116. · Zbl 0499.03003
[12] R. C. Lyndon, ”Equations in free groups,” Trans. Am. Math. Soc.,96, 445–457 (1960). · Zbl 0108.02301 · doi:10.1090/S0002-9947-1960-0151503-8
[13] H. Freedman, ”One-hundred-and-two problems in mathematical logic,” J. Symb. Logic,40, No. 3, 113–130 (1975). · Zbl 0318.02002 · doi:10.2307/2271891
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.