首页 | 本学科首页   官方微博 | 高级检索  
     


Tarski's theorem on intuitionistic logic,for polyhedra
Authors:Nick Bezhanishvili  Vincenzo Marra  Daniel McNeill  Andrea Pedrini
Affiliation:1. Institute for Logic, Language and Computation, University of Amsterdam, P.O. Box 94242, 1090 GE Amsterdam, The Netherlands;2. Dipartimento di Matematica “Federigo Enriques”, Università degli Studi di Milano, via Cesare Saldini 50, 20133 Milano, Italy;3. Dipartimento di Ingegneria Elettrica e dell''Informazione, Politecnico di Bari, via Edoardo Orabona, 4, 70125 Bari, Italy;4. Dipartimento di Matematica “Felice Casorati”, Università degli Studi di Pavia, Via Ferrata 5, 27100 Pavia, Italy
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 Rn with n?1 suffices, as does e.g. the Cantor space. In particular, intuitionistic logic cannot detect topological dimension in the Heyting algebra of all open sets of a Euclidean space. By contrast, we consider the lattice of open subpolyhedra of a given compact polyhedron P?Rn, prove that it is a locally finite Heyting subalgebra of the (non-locally-finite) algebra of all open sets of P, 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æ 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 Ja?kowski'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?
Keywords:primary  03B20  secondary  06D20  06D22  55U10  Intuitionistic logic  Topological semantics  Heyting algebra  Polyhedron  Triangulation  PL topology
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号