arXiv Analytics

Sign in

arXiv:1207.4414 [math.LO]AbstractReferencesReviewsResources

Model-theoretic characterization of intuitionistic propositional formulas

Grigory K. Olkhovikov

Published 2012-07-18Version 1

Notions of k-asimulation and asimulation are introduced as asymmetric counterparts to k-bisimulation and bisimulation, respectively. It is proved that a first-order formula is equivalent to a standard translation of an intuitionistic propositional formula iff it is invariant with respect to k-asimulations for some k, and then that a first-order formula is equivalent to a standard translation of an intuitionistic propositional formula iff it is invariant with respect to asimulations. Finally, it is proved that a first-order formula is intuitionistically equivalent to a standard translation of an intuitionistic propositional formula iff it is invariant with respect to asimulations between intuitionistic models.

Comments: 16 pages, 0 figures. arXiv admin note: substantial text overlap with arXiv:1202.1195
Categories: math.LO
Related articles: Most relevant | Search more
arXiv:math/0404205 [math.LO] (Published 2004-04-09)
FPL may be equivalent to FO but not equivalent to PFP
arXiv:1206.3920 [math.LO] (Published 2012-06-18)
The problem of Horn and Tarski
arXiv:2306.01790 [math.LO] (Published 2023-05-31)
Nash Equilibrium and Axiom of Choice Are Equivalent

Links

Toolbox