| dc.date.accessioned | 2023-09-08T13:16:38Z | |
| dc.date.available | 2023-09-08T13:16:38Z | |
| dc.date.issued | 2023 | |
| dc.identifier.uri | http://hdl.handle.net/10852/104677 | |
| dc.description.abstract | This thesis is motivated by the following questions:
- Does there exist a weakest theory for which Gödel’s first incompleteness theorem holds?
- Does there exist a weakest structure for which solvability of systems of equations with constraints is undecidable?
We explore these questions by investigating different foundations for basic finitary mathematics and use interpretability to compare them. The concept of interpretation provides a framework for comparing theories by abstracting away arbitrariness in the choice of non-logical symbols and basic principles. If two theories are interpretable in one another, then they are of the same strength: inferences in one can be translated into inferences in the other. | en_US |
| dc.language.iso | en | en_US |
| dc.relation.haspart | Paper I Kristiansen, L., Murwanashyaka, J.: First-order concatenation theory with bounded quantifiers. Archive for Mathematical Logic 60 no. 1-2 (2021) 77–104. An author version is included in the thesis. The published version is available at: https://doi.org/10.1007/s00153-020-00735-6 | |
| dc.relation.haspart | Paper II Kristiansen, L., Murwanashyaka, J.: On Interpretability Between Some Weak Essentially Undecidable Theories. in: Anselmo, M., Della Vedova, G., Manea, F., Pauly, A. (eds) Beyond the Horizon of Computability, CiE 2020, Lecture Notes in Computer Science, Vol. 12098, pp. 63–74, Springer International Publishing (2020). An author version is included in the thesis. The published version is available at: https://doi.org/10.1007/978-3-030-51466-2_6 | |
| dc.relation.haspart | Paper III Murwanashyaka, J.: Hilbert’s Tenth Problem for Term Algebras with a Substitution Operator. Invited Submission to Computability for the Computability in Europe 2022 Special Issue. To be published. The paper is removed from the thesis in DUO awaiting publishing. | |
| dc.relation.haspart | Paper IV Murwanashyaka, J.: On a First-Order Theory of Building Blocks and its Relation to Arithmetic and Set Theory. Submitted to Mathematical Logic Quarterly. To be published. The paper is removed from the thesis in DUO awaiting publishing. | |
| dc.relation.haspart | Paper V Murwanashyaka, J.: Weak Essentially Undecidable Theories of Concatenation, Part II. Archive for Mathematical Logic (accepted with minor revisions).To be published. The paper is removed from the thesis in DUO awaiting publishing. | |
| dc.relation.haspart | Paper VI Murwanashyaka, J.: Hilbert’s Tenth Problem for Term Algebras with a Substitution Operator. in: Berger, U., Franklin, J.N.Y., Manea, F., Pauly, A. (eds) Revolutions and Revelations in Computability, CiE 2022, Lecture Notes in Computer Science, Vol. 13359, pp. 196-207. An author version is included in the thesis. The published version is available at: https://doi.org/10.1007/978-3-031-08740-0_17 | |
| dc.relation.haspart | Paper VII Murwanashyaka, J.: Weak Essentially Undecidable Theories of Concatenation. Archive for Mathematical Logic, 61(7-8), 939–976 (2022). An author version is included in the thesis. The published version is available at: https://doi.org/10.1007/s00153-022-00820-y | |
| dc.relation.haspart | Paper VIII Murwanashyaka, J.: Weak Sequential Theories of Finite Full Binary trees. in: Berger, U., Franklin, J.N.Y., Manea, F., Pauly, A. (eds) Revolutions and Revelations in Computability, CiE 2022, Lecture Notes in Computer Science, Vol. 13359, pp. 208-219, Springer International Publishing (2022). An author version is included in the thesis. The published version is available at: https://doi.org/10.1007/978-3-031-08740-0_18 | |
| dc.relation.haspart | Paper IX Murwanashyaka, J., Pakhomov, F., Visser, A.: There are no minimal essentially undecidable theories. Journal of Logic and Computation (2023) An author version is included in the thesis. The published version is available at: https://doi.org/10.1093/logcom/exad005 | |
| dc.relation.uri | https://doi.org/10.1007/s00153-020-00735-6 | |
| dc.relation.uri | https://doi.org/10.1007/978-3-030-51466-2_6 | |
| dc.relation.uri | https://doi.org/10.1007/978-3-031-08740-0_17 | |
| dc.relation.uri | https://doi.org/10.1007/s00153-022-00820-y | |
| dc.relation.uri | https://doi.org/10.1007/978-3-031-08740-0_18 | |
| dc.relation.uri | https://doi.org/10.1093/logcom/exad005 | |
| dc.title | Papers on Weak First-Order Theories and Decidability Problems | en_US |
| dc.type | Doctoral thesis | en_US |
| dc.creator.author | Murwanashyaka, Juvenal | |
| dc.type.document | Doktoravhandling | en_US |