Tarski's theorem on intuitionistic logic, for polyhedra

DOI10.1016/J.APAL.2017.12.005MaRDI QIDQ1706265zbMATH OpenOpenAlexFDO

Authors Nick Bezhanishvili, Vincenzo Marra, Daniel K. McNeill, Andrea Pedrini

Publication date 21 March 2018

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05094

finite model proprty Heyting algebra intuitionistic logic PL-topology polyhedron topological semantics triangulation

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

Abstract: In 1938, Tarski proved that a formula is not intuitionistically valid if, and only if, it has a counter-model in the Heyting algebra of open sets of some topological space. In fact, Tarski showed that any Euclidean space R^n with n >= 1 suffices, as does e.g. the Cantor space. In particular, intuitionistic logic cannot detect topological dimension in the frame of all open sets of a Euclidean space. By contrast, we consider the lattice of open subpolyhedra of a given compact polyhedron P subseteq R^n, prove that it is a locally finite Heyting subalgebra of the (non-locally-finite) algebra of all open sets of R^n, and show that intuitionistic logic is able to capture the topological dimension of P through the bounded-depth axiom schemata. Further, we show that intuitionistic logic is precisely the logic of formul{ae} valid in all Heyting algebras arising from polyhedra in this manner. Thus, our main theorem reconciles through polyhedral geometry two classical results: topological completeness in the style of Tarski, and Jaskowski's theorem that intuitionistic logic enjoys the finite model property. Several questions of interest remain open. E.g., what is the intermediate logic of all closed triangulable manifolds?

Review text

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 \textit{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 \textit{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.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Tarski's theorem on intuitionistic logic, for polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1706265)