For each positive n , two alternative axiomatizations of the theory of strings over n alphabetic characters are presented. One class of axiomatizations derives from Tarski's system of the Wahrheitsbegriff and uses the n characters and concatenation as primitives. The other class involves using n character-prefixing operators as primitives and derives from Hermes' Semiotik. All underlying logics are second order. It is shown that, for each n, the two theories are definitionally equivalent [or synonymous in the sense of deBouvere]. It (...) is further shown that each member of one class is synonymous with each member of the other class; thus that all of the theories are definitionally equivalent with each other and with Peano arithmetic. Categoricity of Peano arithmetic then implies categoricity of each of the above theories. (shrink)

We prove that a variant of Robinson arithmetic $\mathsf{Q}$ with nontotal operations is interpretable in the theory of concatenation $\mathsf{TC}$ introduced by A. Grzegorczyk. Since $\mathsf{Q}$ is known to be interpretable in that nontotal variant, our result gives a positive answer to the problem whether $\mathsf{Q}$ is interpretable in $\mathsf{TC}$. An immediate consequence is essential undecidability of $\mathsf{TC}$.

In the present paper the well-known Gödels – Churchs argument concerning the undecidability of logic (of the first order functional calculus) is exhibited in a way which seems to be philosophically interestingfi The natural numbers are not used. (Neither Chinese Theorem nor other specifically mathematical tricks are applied.) Only elementary logic and very simple set-theoretical constructions are put into the proof. Instead of the arithmetization I use the theory of concatenation (formalized by Alfred Tarski). This theory proves to be an (...) appropriate tool. The decidability is defined directly as the property of graphical discernibility of formulas. (shrink)

We consider weak theories of concatenation, that is, theories for strings or texts. We prove that the theory of concatenation WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document}, which is a weak subtheory of Grzegorczyk’s theory TC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}^{-\varepsilon}}$$\end{document}, is a minimal essentially undecidable theory, that is, the theory WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document} is essentially undecidable and if one omits an axiom scheme from WTC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}^{-\varepsilon}}$$\end{document}, then the resulting theory is no longer essentially undecidable. Moreover, we give a positive answer to Grzegorczyk and Zdanowski’s conjecture that ‘The theory TC-ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}^{-\varepsilon}}$$\end{document} is a minimal essentially undecidable theory’. For the alternative theories WTC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{WTC}}$$\end{document} and TC\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf{TC}}$$\end{document} which have the empty string, we also prove that the each theory without the neutrality of ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varepsilon}$$\end{document} is to be such a theory too. (shrink)

We define a new theory of concatenation WTC which is much weaker than Grzegorczyk's well-known theory TC. We prove that WTC is mutually interpretable with the weak theory of arithmetic R. The latter is, in a technical sense, much weaker than Robinson's arithmetic Q, but still essentially undecidable. Hence, as a corollary, WTC is also essentially undecidable.

At the intersection of mathematics, computer science, and philosophy, mathematical logic examines the power and limitations of formal mathematical thinking. In this expansion of Leary's user-friendly 1st edition, readers with no previous study in the field are introduced to the basics of model theory, proof theory, and computability theory. The text is designed to be used either in an upper division undergraduate classroom, or for self study. Updating the 1st Edition's treatment of languages, structures, and deductions, leading to rigorous proofs (...) of Gödel's First and Second Incompleteness Theorems, the expanded 2nd Edition includes a new introduction to incompleteness through computability as well as solutions to selected exercises. (shrink)