A~test for completeness with respect to implicit reducibility in the chain super-intutionistic logics

I. V. Cucu

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2006), pp. 23-30.

Résumé

We examine chain logics $C_2,C_3,\dots$, which are intermediary between classical and intuitionistic logics. They are also the logics of pseudo-Boolean algebras of type $⟨E_m,\vee ,\supset ,\mathrm{\neg }⟩$, where $E_m$ is the chain $0{\tau }_1{\tau }_2\dots {\tau }_{m-2}1$ ($m=2,3,\dots$). The formula $F$ is called to be implicitly expressible in logic $L$ by the system $\mathrm{\Sigma }$ of formulas if the relation $$ L\vdash(F\sim q)\sim((G_1\sim H_1)\\dots\(C_k\sim H_k)) $$ is true, where $q$ do not appear in $F$, and formula$G_i$ and $H_i$, for $i=1,\dots ,k$, are explicitly expressible in $L$ via $\mathrm{\Sigma }$ The formula $F$ is said to be implicitly reducible in logic $L$ to formulas of $\mathrm{\Sigma }$ if there exists a finite sequence of formulas $G_1,G_2,\dots ,G_l$ where $G_l$ coincides with $F$ and for $j=1,\dots ,l$ the formula $G_j$ is implicitly expressible in $L$ by $\mathrm{\Sigma }\cup \{G_1,\dots ,G_{j-1}\}$. The system $\mathrm{\Sigma }$ is called complete relative to implicit reducibility in logic $L$ if any formula is implicitly reducible in $L$ to $\mathrm{\Sigma }$. The paper contains the criterion for recognition of completeness with respect to implicit reducibility in the logic $C_m$, for any $m=2,3,\dots$ . The criterion is based on 13 closed pre-complete classes of formulas.

Bibliographie

[1] Post E. L., Two-valued iterative systems of mathematical logic, Princeton, 1941 | MR | Zbl

[2] Iablonski S. V., “Functional constuctions in $k$-valued logic”, Trudy MIAN SSSR, 51, Moscow, 1958, 5–142 (in Russian) | MR

[3] Rosenberg I., C. R. Acad. Sci. Groupe 1, 260, Paris, 1965, 3817–3819 | MR | Zbl

[4] Raţa M. F., “On functional completeness in the intuitionistic logic”, Probl. Kibern., 1982, no. 39, 107–150 (in Russian)

[5] Kuznetsov A. V., “On functional expressibility in super-intuitionistic logics”, Mat. Issled., 6:4 (1971), 75–122 (in Russian) | MR | Zbl

[6] Iaśkowski S., Actes du Congres Intern. de Philosophie Scientifique, VI, Paris, 1936, 58–61

[7] Ianov Iu. I., Muchinik A. A., “On the existence of $k$-valued closed classes without finite basis”, DAN SSSR, 127:1 (1959), 44–46 (in Russian) | MR

[8] Rasiowa H., Sikorski R., The mathematics of Metamathematics, Warszawa, 1963 | MR

[9] Kuznetsov A. V., “On tools for the discovery of nondeducibility or nonexpressibility”, Logical Deduction, Nauka, Moscow, 1979, 5–33 (in Russian) | MR

[10] Dummett M. A., “A propositional calculus with denumerable matrix”, J. Symb. Logic, 242 (1959), 97–106 | DOI | MR

[11] Gödel K., “Zum intuitionistischen Aussagenkalkül”, Akad. Wiss. Anzeiger, 69 (1932), 65–66 | Zbl

[12] Birkhoff G., Lattice theory, New York, 1960

[13] Cohn P. M., Universal Algebra, New York, 1965 | MR

[14] Raţa M. F., “On the class of functions of three-valued logic corresponding to First Iaśkowski's Matrix”, Probl. Kibern., 1969, no. 21, 185–214 (in Russian) | Zbl

[15] Raţa M. F., Cucu I. V., “On completeness with respect to implicit reducibility in the logic of First Iaśkowski's Matrix”, Bul. Acad. of Sci. of Moldova, 1988, no. 1, 23–29 (in Russian) | MR