×

Effectiveness in RPL, with applications to continuous logic. (English) Zbl 1225.03056

Summary: We introduce a foundation for the computable model theory of rational Pavelka logic (an extension of Łukasiewicz logic) and continuous logic, and prove effective versions of some related theorems in model theory. We show how to reduce continuous logic to rational Pavelka logic. We also define notions of computability and decidability of a model for logics with computable, but uncountable, set of truth values; we show that the provability degree of a formula with respect to a linear theory is computable, and use this to carry out an effective Henkin construction. Therefore, for any effectively given consistent linear theory in continuous logic, we effectively produce its decidable model. This is the best possible result, since we show that the computable model theory of continuous logic is an extension of the computable model theory of classical logic. We conclude by noting that the unique separable model of a separably categorical and computably axiomatizable theory (such as that of a probability space or an \(L^{p}\) Banach lattice) is decidable.

MSC:

03D45 Theory of numerations, effectively presented structures
03B50 Many-valued logic
03C57 Computable structure theory, computable model theory
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramsky, Samson; Jung, Achim, Domain theory, (Abramsky, Samson; Gabbay, Dov M.; Maibaum, T. S.E., Handbook of Logic in Computer Science, vol. 3 (1994), Oxford University Press), 1-168, chapter 1
[2] Beeson, Michael J., Foundations of constructive mathematics, (Metamathematical Studies (1980), Springer-Verlag) · Zbl 0565.03028
[3] Itaï BenYaacov, Alexander J. Berenstein, C. Ward Henson, Model-theoretic independence in the banach lattices \(l^p ( \mu )\), (in press); Itaï BenYaacov, Alexander J. Berenstein, C. Ward Henson, Model-theoretic independence in the banach lattices \(l^p ( \mu )\), (in press)
[4] BenYaacov, Itaï; Berenstein, Alexander; Ward Henson, C.; Usvyatsov, Alexander, Model theory for metric structures, (Chatzidakis, Zoé; Macpherson, Dugald; Pillay, Anand; Wilkie, Alex, Model Theory with Applications to Algebra and Analysis, volume 2. Model Theory with Applications to Algebra and Analysis, volume 2, London Math Society Lecture Note Series, vol. 350 (2008)), 315-427 · Zbl 1233.03045
[5] BenYaacov, Itaï; Iovino, José, Model theoretic forcing in analysis, Annals of Pure and Applied Logic, 158, 163-174 (2009) · Zbl 1160.03010
[6] Itaï BenYaacov, Arthur Paul Pedersen, A proof of completeness for continuous first-order logic, Journal of Symbolic Logic (in press); Itaï BenYaacov, Arthur Paul Pedersen, A proof of completeness for continuous first-order logic, Journal of Symbolic Logic (in press)
[7] Itaï BenYaacov, Alexander Usvyatsov, Continuous first order logic and local stability, Transactions of the American Mathematical Society (in press); Itaï BenYaacov, Alexander Usvyatsov, Continuous first order logic and local stability, Transactions of the American Mathematical Society (in press)
[8] J. Blank, Computability on Topological Spaces by Effective Domain Representations, Ph.D. Thesis, Uppsala Dissertations in Mathematics 7, 1997; J. Blank, Computability on Topological Spaces by Effective Domain Representations, Ph.D. Thesis, Uppsala Dissertations in Mathematics 7, 1997
[9] Blank, J., Domain representability of metric spaces, Annals of Pure and Applied Logic, 83, 225-247 (1997) · Zbl 0867.03014
[10] Blank, J., Domain representations of topological spaces, Theoretical Computer Science, 247, 229-255 (2000) · Zbl 0949.68096
[11] Blum, Lenore; Cucker, Felipe; Shub, Mike; Smale, Steve, Complexity and real number computation: A manifesto, International Journal of Bifurcation and Chaos, 6, 3-26 (1996) · Zbl 0872.68036
[12] Blum, Lenore; Cucker, Felipe; Shub, Mike; Smale, Steve, Complexity and Real Computation (1998), Springer · Zbl 0872.68036
[13] Blum, Lenore; Shub, Mike; Smale, Steve, On a theory of computation and complexity over real numbers: Np-completeness, recursive functions and universal machines, Bulletin of American Mathematical Society, 21, 1, 1-46 (1989) · Zbl 0681.03020
[14] Chang, Chen Chung; Keisler, H. Jerome, Continuous Model Theory (1966), Princeton University Press · Zbl 0149.00402
[15] Edalat, Abbas, Domains for computation in mathematics, physics and exact real arithmetic, Bull. Symbolic Logic, 3, 4, 401-452 (1997) · Zbl 0946.03055
[16] Edalat, Abbas; Heckmann, R., A computational model for metric spaces, Theoretical Computer Science, 193, 53-73 (1998) · Zbl 1011.54026
[17] Edalat, Abbas; Sünderhauf, Philipp, Computable banach spaces via domain theory, Theoretical Computer Science, 219, 169-184 (1999) · Zbl 0916.68045
[18] Edalat, Abbas; Sünderhauf, Philipp, A domain theoretic approach to computability on the real line, Theoretical Computer Science, 210, 73-98 (1999) · Zbl 0912.68031
[19] (Ershov, Yu. L., Handbook of Recursive Mathematics, Volume I: Recursive Model Theory (1998), North-Holland)
[20] Ershov, Yu. L., Handbook of Recursive Mathematics, Volume II: Recursive Algebra, Analysis and Combinatorics (1998), North-Holland
[21] (Ershov, Yu. L.; Goncharov, S. S.; Nerode, A.; Remmel, J. B., Handbook of Recursive Mathematics (1998), Elsevier) · Zbl 0930.03037
[22] Ganguli, Suman; Nerode, Anil, Effective completeness theorems for modal logic, Annals of Pure and Applied Logic, 128, 141-195 (2004) · Zbl 1056.03008
[23] (Griffor, Edward R., Handbook of Computability Theory (1999), Elsevier) · Zbl 0923.03001
[24] Grzeggorczyk, Andrej, Computable functionals, Fundementa Mathmaticae, 42, 168-202 (1955)
[25] Grzeggorczyk, Andrej, On the definitions of computable real continuous functions, Fundementa Mathmaticae, 44, 61-71 (1957)
[26] Hajek, Petr, Metamathematics of Fuzzy Logic, Trends in Logic, vol. 4 (1998), Kluwer Academic Publishers · Zbl 0937.03030
[27] V. Harizanov, Pure computable model theory, in: Ershov et al. [21]; V. Harizanov, Pure computable model theory, in: Ershov et al. [21] · Zbl 0952.03037
[28] Kalantari, Iraj; Welch, Lawrence, Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis, i, Annals of Pure and Applied Logic, 93, 125-151 (1998) · Zbl 0946.03052
[29] Kalantari, Iraj; Welch, Lawrence, Recursive and nonextendible functions over the reals; filter foundation for recursive analysis, ii, Annals of Pure and Applied Logic, 98, 87-110 (1999) · Zbl 0954.03043
[30] Ko, Ker-I, Complexity Theory of Real Functions (1991), Birkhäuser · Zbl 0791.03019
[31] Ko, Ker-I, Polynomial computability in analysis, (Handbook of Recursive Mathematics, Volume II: Recursive Algebra, Analysis and Combinatorics (1998), Elsevier) · Zbl 0926.03049
[32] Metcalfe, George; Olivetti, Nicola; Gabbay, Dov M., Proof theory of fuzzy logic, (Applied Logic Series, vol. 36 (2009), Springer) · Zbl 1168.03002
[33] T.S. Miller, Pure Recursive Model Theory, in: Griffor [23], chapter 15, pp. 507-532; T.S. Miller, Pure Recursive Model Theory, in: Griffor [23], chapter 15, pp. 507-532
[34] Martin Boykan Pour-El, The structure of computability in analysis and physical theory: An extension of church’s thesis, in: Griffor [23], chapter 13, pp. 450-471; Martin Boykan Pour-El, The structure of computability in analysis and physical theory: An extension of church’s thesis, in: Griffor [23], chapter 13, pp. 450-471 · Zbl 0945.03091
[35] Pour-El, M. B.; Richards, J. I., Computability in analysis and physics, (Perspectives in Mathematical Logic (1989), Springer) · Zbl 1365.03010
[36] Stoltenberg-Hansen, Viggo; Tucker, John, Computability on topological spaces via domain representations, (New Computational Paradigms: Changing Conceptions of What is Computable (2007), Springer) · Zbl 1149.03035
[37] Troelstra, A. S.; van Dalen, D., Constructivism in Mathematics, vol. I (1987), North-Holland · Zbl 0653.03040
[38] Weirauch, Klaus, (Computable Analysis, An Introduction. Computable Analysis, An Introduction, Texts in Theoretical Computer Science (2000), Springer)
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.