×

Not all Kripke models of \(\mathsf{HA}\) are locally \(\mathsf{PA}\). (English) Zbl 07472316

Summary: Let K be an arbitrary Kripke model of Heyting Arithmetic, \(\mathsf{HA}\). For every node \(k\) in K, we can view the classical structure of \(k,\mathfrak{M}_k\) as a model of some classical theory of arithmetic. Let \(\mathsf{T}\) be a classical theory in the language of arithmetic. We say K is locally \(\mathsf{T}\), iff for every \(k\) in K, \(\mathfrak{M}_k\vDash\mathsf{T}\). One of the most important problems in the model theory of \(\mathsf{HA}\) is the following question: Is every Kripke model of \(\mathsf{HA}\) locally \(\mathsf{PA}\)? We answer this question negatively. We introduce two new Kripke model constructions to this end. The first construction actually characterizes the arithmetical structures that can be the root of a Kripke model \(\mathbf{K}\Vdash\mathsf{HA}+\mathsf{EC}\mathsf{T}_0(\mathsf{EC}\mathsf{T}_0\) stands for Extended Church Thesis). The characterization says that for every arithmetical structure \(\mathfrak{M}\), there exists a rooted Kripke model \(\mathbf{K}\Vdash\mathsf{HA}+\mathsf{EC}\mathsf{T}_0\) with the root \(r\) such that \(\mathfrak{M}_r=\mathfrak{M}\) iff \(\mathfrak{M}\vDash\mathbf{Th}_{\Pi_2}(\mathsf{PA})\). One of the consequences of this characterization is that there is a rooted Kripke model \(\mathbf{K}\Vdash\mathsf{HA}+\mathsf{EC}\mathsf{T}_0\) with the root \(r\) such that \(\mathfrak{M}_r\nvDash\mathbf{I}\Delta_1\) and hence K is not even locally \(\mathbf{I}\Delta_1\). The second Kripke model construction is an implicit way of doing the first construction which works for any reasonable consistent intuitionistic arithmetical theory \(\mathsf{T}\) with a recursively enumerable set of axioms that has the existence property. We get a sufficient condition from this construction that describes when for an arithmetical structure \(\mathfrak{M}\), there exists a rooted Kripke model \(\mathbf{K}\Vdash\mathsf{T}\) with the root \(r\) such that \(\mathfrak{M}_r=\mathfrak{M}\). As applications of this sufficient condition, we construct two new Kripke models. The first one is a Kripke model \(\mathbf{K}\Vdash\mathsf{HA}+\neg\theta +\mathsf{MP}(\theta\) is an instance of \(\mathsf{EC}\mathsf{T}_0\) and \(\mathsf{MP}\) is Markov’s principle) which is not locally \(\mathbf{I}\Delta_1\). The second one is a Kripke model \(\mathbf{K}\Vdash\mathsf{HA}\) such that K forces exactly the sentences that are provable from \(\mathsf{HA}\), but it is not locally \(\mathbf{I}\Delta_1\). Also, we will prove that every countable Kripke model of intuitionistic first-order logic can be transformed into another Kripke model with the full infinite binary tree as the Kripke frame such that both Kripke models force the same sentences. So with the previous result, there is a binary Kripke model K of \(\mathsf{HA}\) such that K is not locally \(\mathbf{I}\Delta_1\).

MSC:

03Fxx Proof theory and constructive mathematics
03Cxx Model theory
03Bxx General logic
Full Text: DOI

References:

[1] Abiri, M.; Moniri, M.; Zaare, M., From forcing to satisfaction in Kripke models of intuitionistic predicate logic, Log. J. IGPL, 26, 5, 464-474 (2018) · Zbl 1492.03003
[2] Abiri, M.; Moniri, M.; Zaare, M., Forcing and satisfaction in Kripke models of intuitionistic arithmetic, Log. J. IGPL, 27, 5, 659-670 (2019) · Zbl 1494.03028
[3] Ardeshir, M.; Hesaam, B., Every rooted narrow tree Kripke model of HA is locally PA, Math. Log. Q., 48, 3, 391-395 (2002) · Zbl 1011.03044
[4] Ardeshir, M.; Hesaam, B., An introduction to Basic Arithmetic, Log. J. IGPL, 16, 1, 1-13 (2008) · Zbl 1168.03045
[5] Ardeshir, M.; Khaniki, E.; Shahriari, M., Provably total recursive functions and MRDP theorem in Basic Arithmetic and its extensions (2020)
[6] Ardeshir, M.; Ruitenburg, W.; Salehi, S., Intuitionistic axiomatizations for bounded extension Kripke models, Ann. Pure Appl. Log., 124, 1-3, 267-285 (2003) · Zbl 1040.03044
[7] Buss, S. R., Intuitionistic validity in T-normal Kripke structures, Ann. Pure Appl. Log., 59, 3, 159-173 (1993) · Zbl 0802.03006
[8] Chagrov, A. V.; Zakharyaschev, M., Modal Logic, Oxford Logic Guides, vol. 35 (1997), Oxford University Press · Zbl 0871.03007
[9] Friedman, H., Classically and intuitionistically provably recursive functions, (Müller, G. H.; Scott, D. S., Higher Set Theory. Higher Set Theory, Lecture Notes in Mathematics, vol. 669 (1978), Springer: Springer Berlin, Heidelberg) · Zbl 0396.03045
[10] Jeřábek, E., Intuitionistic Lowenheim-Skolem? (answer) (2011), MathOverflow
[11] Marković, Z., On the structure of Kripke models of Heyting Arithmetic, Math. Log. Q., 39, 1, 531-538 (1993) · Zbl 0805.03050
[12] Mojtahedi, M., Localizing finite-depth Kripke models, Log. J. IGPL, 27, 3, 239-251 (2018) · Zbl 1515.03055
[13] Moniri, M., H-theories, fragments of HA and PA-normality, Arch. Math. Log., 41, 1, 101-105 (2002) · Zbl 1022.03042
[14] Parsons, Ch., On a number theoretic choice schema and its relation to induction, (Kino, A.; Myhill, J.; Vesley, R. E., Intuitionism and Proof Theory: Proceedings of the Summer Conference at Buffalo N.Y. 1968. Intuitionism and Proof Theory: Proceedings of the Summer Conference at Buffalo N.Y. 1968, Studies in Logic and the Foundations of Mathematics, vol. 60 (1970), Elsevier), 459-473 · Zbl 0202.01202
[15] Połacik, T., Partially-elementary extension Kripke models: a characterization and applications, Log. J. IGPL, 14, 1, 73-86 (2006) · Zbl 1102.03040
[16] Rabin, M. O., Non-standard models and independence of the induction axiom, (Essays Found. Math., Dedicat. to A.A. Fraenkel on His 70th Anniv.. Essays Found. Math., Dedicat. to A.A. Fraenkel on His 70th Anniv., 1962 (1962)), 287-299 · Zbl 0143.01001
[17] Ruitenburg, W., Basic predicate calculus, Notre Dame J. Form. Log., 39, 1, 18-46 (1998) · Zbl 0967.03005
[18] Slaman, T. A., \( \operatorname{\Sigma}_n\)-bounding and \(\operatorname{\Delta}_n\)-induction, Proc. Am. Math. Soc., 132, 8, 2449-2456 (2004) · Zbl 1053.03034
[19] Smoryński, C., Applications of Kripke models, (Troelstra, A. S., Metamathematical Investigation of Intuitionistic Arithmetic and Analysis. Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Lecture Notes in Mathematics, vol. 344 (1973), Springer Berlin Heidelberg) · Zbl 0275.02025
[20] Smoryński, C., The incompleteness theorems, (Barwise, J., Handbook of Mathematical Logic. Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, vol. 90 (1977), Elsevier), 821-865
[21] Smoryński, C., Self-reference and Modal Logic, Universitext (1985), Springer: Springer New York, NY · Zbl 0596.03001
[22] Troelstra, A. S.; van Dalen, D., Constructivism in Mathematics. An Introduction, vol. I, vol. 121 (1988), North-Holland: North-Holland Amsterdam etc. · Zbl 0653.03040
[23] van Dalen, D.; Mulder, H.; Krabbe, E. C.W.; Visser, A., Finite Kripke models of HA are locally PA, Notre Dame J. Form. Log., 27, 4, 528-532 (1986) · Zbl 0632.03048
[24] Wehmeier, K. F., Classical and intuitionistic models of arithmetic, Notre Dame J. Form. Log., 37, 3, 452-461 (1996) · Zbl 0871.03027
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.