On finite-dimensional superintuitionistic logics

S. K. Sobolev

Izvestiya. Mathematics, Tome 11 (1977) no. 5, pp. 909-935

Résumé

A pseudoboolean algebra $\mathfrak M$ is called $n$-dimensional if the lattice $(Z_2)^{n+1}$ is not embeddable in $\mathfrak M$ as a lattice, where $Z_2$ is the two-element lattice. A superintuitionistic logic is said to be $n$-dimensional if the formula $E_n(x_1,\dots,x_n)\leftrightharpoons\bigvee_{i=1}^{n+1}(x_i=\bigvee_{j\ne i}x_j)$ belongs to it. A logic is $n$-dimensional if and only if it is approximable by $n$-dimensional algebras. All finite-dimensional logics are complete relative to Kripke semantics. An example is given of a formula that generates a logic not approximable by finite-dimensional algebras. It is proved that for every $n$, every finitely axiomatizable $n$-dimensional logic containing the formula $H(x,y)\leftrightharpoons(((x\to y)\to x)\to x)\vee (((y\to x)\to y)\to y)$ is decidable (already for $n=2$ there exist among such logics non-finitely-approximable ones). The proof uses the theory of finite automata on $\omega$-sequences. Bibliography: 10 titles.

Bibliographie

[1] Gerchiu V. Ya., “O finitnoi approksimiruemosti superintuitsionistskikh logik”, Matem. issledovaniya, 7, no. 1, Kishinev, 1972, 186–192 | Zbl

[2] Kuznetsov A. V., Gerchiu V. Ya., “O superintuitsionistskikh logikakh i finitnoi approksimiruemosti”, Dokl. AN SSSR, 195:5 (1970), 1029–1032 | Zbl

[3] Raseva E., Sikorskii R., Matematika metamatematiki, Nauka, M., 1972 | MR

[4] Sobolev S. K., “Problemy razreshimosti i finitnoi approksimiruemosti ploskikh superintuitsionistskikh logik”, VII Vsesoyuznyi simpozium po logike i metodologii nauki, Kiev, 1976, 143–145

[5] Buchi J. R., Siefkes D., “The monadic second order theory of all countable ordinals”, Lecture Notes in Mathematics, 328, 1973 | MR

[6] Dummett M. A., “A propositional calculus with a denumerable matrix”, J. Symb. Logic, 24:2 (1959), 97–106 | DOI | MR | Zbl

[7] Fine K., “Logic containing $S4$ without the finite model property”, Lecture Notes in Mathematics, 255, 1972, 98–102 | MR | Zbl

[8] Fine K., “Logics containing $K4$, I”, J. Symb. Logic, 39:1 (1974), 31–42 | DOI | MR | Zbl

[9] Kripke S. A., “Semantical analysis of intuitionistic logic, I”, Formal systems and recursive functions, Amsterdam, 1965, 92–130 | MR | Zbl

[10] Thomas I., “Finite limitations of Dummett's $LC$”, Notre Dame J. Formal Logic, 3 (1962), 170–174 | DOI | MR | Zbl