×

Tarski’s theorem on intuitionistic logic, for polyhedra. (English) Zbl 1390.03015

It is a well-known fact that the intuitionistic propositional logic is complete with respect to the class of all Heyting algebras. The mentioned theorem by A. Tarski [Fundam. Math. 31, 103–134 (1938; Zbl 0020.33704)] states that this logic is complete w.r.t. to all Heyting algebras \(O(X)\) of open sets of a topological space \(X\): every non-theorem is falsified by some \(O(X)\). Actually, the class of admissible spaces here can be considerably restricted: for example, \(X\) may be any Euclidean space \(R^n\). This means, in particular, that the Heyting algebras \(O(R^n)\) and \(O(R^M)\) with \( m \neq n\) satisfy the same formulas; consequently, the intuitionistic logic cannot detect the topological dimension of an Euclidean space. Another classical result on intitionistic logic, which goes back to a short note in 1936 by S. Jaskowski [Actual. Sci. Ind. 393, 58–61 (1936; JFM 62.1045.07)], saying that the logic has the finite model property: a non-theorem can be falsified by a finite Heyting algebra. In the paper under review, the authors provide a Tarski style theorem that uses only locally finite Heyting algebras of open sets, and hence covers also Jaśkowski’s theorem [loc. cit.]. Namely, they consider the lattice of open subpolyhedra of a compact polyhedron \(P \subseteq R^n\), which turns out to be a locally finite Heyting subalgebra of \(O(P)\), and show that the intuitionistic logic is the logic of formulas valid just in all Heyting algebras arising in this way. They also show that the logic is able, in a sense, to capture the topological dimension of a polyhedron.

MSC:

03B20 Subsystems of classical logic (including intuitionistic logic)
06D20 Heyting algebras (lattice-theoretic aspects)
06D22 Frames, locales
55U10 Simplicial sets and complexes in algebraic topology
52B11 \(n\)-dimensional polytopes

References:

[1] Aguzzoli, S.; Gerla, B.; Marra, V., Gödel algebras free over finite distributive lattices, Ann. Pure Appl. Logic, 155, 3, 183-193 (2008) · Zbl 1153.06004
[2] (Aiello, M.; Pratt-Hartmann, I.; van Benthem, J., Handbook of Spatial Logics (2007), Springer: Springer Dordrecht) · Zbl 1172.03001
[3] Alexandrov, P. S., Combinatorial Topology. Vol. 1, 2 and 3 (1998), Dover Publications, Inc.: Dover Publications, Inc. Mineola, NY, Translated from the Russian. Reprint of the 1956, 1957 and 1960 translations · Zbl 0903.55001
[4] Balbes, R.; Dwinger, P., Distributive Lattices (1974), University of Missouri Press: University of Missouri Press Columbia, Mo · Zbl 0321.06012
[5] Bezhanishvili, G.; Bezhanishvili, N., An algebraic approach to filtrations for superintuitionistic logics, (van Eijck, J.; Iemhoff, N.; Joosten, J., Liber Amicorum Albert Visser (2016), College Publications), 47-56 · Zbl 1418.03186
[6] Bezhanishvili, G.; Gehrke, M., Completeness of S4 with respect to the real line: revisited, Ann. Pure Appl. Logic, 131, 1-3, 287-301 (2005) · Zbl 1066.03032
[7] Bezhanishvili, G.; Bezhanishvili, N.; Gabelaia, D.; Kurz, A., Bitopological duality for distributive lattices and Heyting algebras, Math. Structures Comput. Sci., 20, 3, 359-393 (2010) · Zbl 1193.06012
[8] Bezhanishvili, G.; Bezhanishvili, N.; Lucero-Bryan, J.; van Mill, J., Krull dimension in modal logic, J. Symbolic Logic (2017), in press · Zbl 1421.03007
[9] Birkhoff, G., Rings of sets, Duke Math. J., 3, 3, 443-454 (1937) · Zbl 0017.19403
[10] Björner, A., Topological Methods, Handbook of Combinatorics, Vol. 1, 2, 1819-1872 (1995), Elsevier: Elsevier Amsterdam · Zbl 0851.52016
[11] Chagrov, A.; Zakharyaschev, M., Modal Logic (1997), The Clarendon Press: The Clarendon Press New York · Zbl 0871.03007
[12] Esakia, L. L., Topological Kripke models, Dokl. Akad. Nauk SSSR, 214, 298-301 (1974) · Zbl 0296.02030
[13] Fritsch, R.; Piccinini, R. A., Cellular Structures in Topology, Cambridge Studies in Advanced Mathematics, vol. 19 (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0837.55001
[14] Ghilardi, S., Free Heyting algebras as bi-Heyting algebras, C. R. Math. Rep. Acad. Sci. Can., 14, 6, 240-244 (1992) · Zbl 0788.06012
[15] Ghilardi, S.; Zawadowski, M., Sheaves, Games, and Model Completions, Trends in Logic—Studia Logica Library, vol. 14 (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1036.03001
[16] Glaser, L. C., Geometrical Combinatorial Topology. Vol. I, Van Nostrand Reinhold Mathematics Studies, vol. 27 (1970), Van Nostrand Reinhold Co.: Van Nostrand Reinhold Co. New York · Zbl 0212.55603
[17] Hudson, J. F.P., Piecewise Linear Topology (1969), W. A. Benjamin, Inc.: W. A. Benjamin, Inc. New York-Amsterdam, University of Chicago Lecture Notes prepared with the assistance of J. L. Shaneson and J. Lees · Zbl 0189.54507
[18] Hurewicz, W.; Wallman, H., Dimension Theory, Princeton Mathematical Series, vol. 4 (1941), Princeton University Press: Princeton University Press Princeton, N. J. · JFM 67.1092.03
[19] Jaśkowski, S., Recherches sur le système de la logique intuitioniste, Actual. Sci. Ind., 393, 58-61 (1936) · JFM 62.1045.07
[20] Johnstone, P. T., Stone Spaces, Cambridge Studies in Advanced Mathematics, vol. 3 (1982), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0499.54001
[21] Mac Lane, S.; Moerdijk, I., Sheaves in Geometry and Logic, Universitext (1994), Springer-Verlag: Springer-Verlag New York, A first introduction to topos theory, Corrected reprint of the 1992 edition
[22] Maunder, C. R.F., Algebraic Topology (1996), Dover Publications, Inc.: Dover Publications, Inc. Mineola, NY, Reprint of the 1980 edition · Zbl 0205.27302
[23] McKinsey, J. C.C., A solution of the decision problem for the Lewis systems S2 and S 4, with an application to topology, J. Symbolic Logic, 6, 117-134 (1941) · JFM 67.0974.01
[24] McKinsey, J. C.C.; Tarski, A., The algebra of topology, Ann. of Math. (2), 45, 141-191 (1944) · Zbl 0060.06206
[25] McKinsey, J. C.C.; Tarski, A., On closed elements in closure algebras, Ann. of Math. (2), 47, 122-162 (1946) · Zbl 0060.06207
[26] McKinsey, J. C.C.; Tarski, A., Some theorems about the sentential calculi of Lewis and Heyting, J. Symbolic Logic, 13, 1-15 (1948) · Zbl 0037.29409
[27] Morandi, P., Dualities in lattice theory (2005), available from
[28] Nishimura, I., On formulas of one variable in intuitionistic propositional calculus, J. Symbolic Logic, 25, 327-331 (1960), (1962) · Zbl 0108.00302
[29] Pears, A. R., Dimension Theory of General Spaces (1975), Cambridge University Press: Cambridge University Press Cambridge, England-New York-Melbourne · Zbl 0312.54001
[30] Rieger, L., On the lattice theory of Brouwerian propositional logic, Acta Fac. Nat. Univ. Carol., Prague, 1949, 189, 40 (1949)
[31] Rose, G. F., Propositional calculus and realizability, Trans. Amer. Math. Soc., 75, 1-19 (1953) · Zbl 0053.19901
[32] Rourke, C. P.; Sanderson, B. J., Introduction to Piecewise-Linear Topology, Springer Study Edition (1982), Springer-Verlag: Springer-Verlag Berlin-New York, reprint · Zbl 0477.57003
[33] Stallings, J. R., Lectures on Polyhedral Topology, Tata Institute of Fundamental Research Lectures on Mathematics, vol. 43 (1967), Tata Institute of Fundamental Research: Tata Institute of Fundamental Research Bombay, Notes by G. Ananda Swarup · Zbl 0182.26203
[34] Statman, R., Intuitionistic propositional logic is polynomial-space complete, Theoret. Comput. Sci., 9, 1, 67-72 (1979) · Zbl 0411.03049
[35] Tarski, A., Der Aussagenkalkül und die Topologie, Fund. Math., 31, 103-134 (1938) · JFM 64.0928.04
[36] Tarski, A., Logic, Semantics, Metamathematics (1983), Hackett Publishing Co.: Hackett Publishing Co. Indianapolis, IN, Papers from 1923 to 1938. Translated by J. H. Woodger. Edited and with an introduction by J. Corcoran
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.