We study first-order concatenation theory with bounded quantifiers. We give axiomatizations with interesting properties, and we prove some normal-form results. Finally, we prove a number of decidability and undecidability results.

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.

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 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}$.

We show that we can interpret concatenation theories in arithmetical theories without coding sequences by identifying binary strings with \(2\times 2\) matrices with determinant 1.

In the language \(\lbrace 0, 1, \circ, \preceq \rbrace \), where 0 and 1 are constant symbols, \(\circ \) is a binary function symbol and \(\preceq \) is a binary relation symbol, we formulate two theories, \( \textsf {WD} \) and \( {\textsf {D}}\), that are mutually interpretable with the theory of arithmetic \( {\textsf {R}} \) and Robinson arithmetic \({\textsf {Q}} \), respectively. The intended model of \( \textsf {WD} \) and \( {\textsf {D}}\) is the free semigroup (...) generated by \(\lbrace {\varvec{0}}, {\varvec{1}} \rbrace \) under string concatenation extended with the prefix relation. The theories \( \textsf {WD} \) and \( {\textsf {D}}\) are purely universally axiomatised, in contrast to \( {\textsf {Q}} \) which has the \(\varPi _2\) -axiom \(\forall x \; [ \ x = 0 \vee \exists y \; [ \ x = Sy \ ] \ ] \). (shrink)

Logical pluralism is the theory that there is more than one right logic. Logical instrumentalism is the view that a logic is a correct logic if it can be used to fruitfully pursue some deductive inquiry. Logical instrumentalism is a version of logical pluralism, since more than one logic can be used fruitfully. In this paper, I will show that a logical instrumentalist must accept linear logic as a correct logic, since linear logic is useful for studying natural language (...) syntax. I further show that this means that the logical instrumentalist must accept a wide range of connectives, in particular concatenation. I end by explaining why this is a feature rather than a bug. (shrink)

In his paper "Undecidability without arithmetization," Andrzej Grzegorczyk introduces a theory of concatenation $\mathsf{TC}$. We show that pairing is not definable in $\mathsf{TC}$. We determine a reasonable extension of $\mathsf{TC}$ that is sequential, that is, has a good sequence coding.

The dynamical equations of relativistic quantum mechanics prescribe the motion of wave packets for sets of events which trace out the world lines of the interacting particles. Electromagnetic theory suggests thatparticle world line densities be constructed from concatenation of event wave packets. These sequences are realized in terms of conserved probability currents. We show that these conserved currents provide a consistent particle and antiparticle interpretation for the asymptotic states in scattering processes. The relation between current conservation and unitarity (...) is used to establish relations between pair production and annihilation amplitudes and scattering. The discrete symmetriesC, T, P are studied and it is shown that no Dirac sea (for fermions where such a construction is possible, or bosons where it is not) is required for consistency of the theory. These currents, furthermore, represent the discrete symmetries in a way consistent with their interpretation as particle currents. (shrink)

Kristiansen and Murwanashyaka recently proved that Robinson arithmetic, Q, is interpretable in an elementary theory of full binary trees, T. We prove that, conversely, T is interpretable in Q by producing a formal interpretation of T in an elementary concatenation theory QT+, thereby also establishing mutual interpretability of T with several well-known weak essentially undecidable theories of numbers, strings, and sets. We also introduce a “hybrid” elementary theory of strings and trees, WQT*, and establish its mutual (...) interpretability with Robinson’s weak arithmetic R, the weak theory of trees WT of Kristiansen and Murwanashyaka, and the weak concatenation theory WTCε of Higuchi and Horihata. (shrink)

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)

In this work I propose a theory of evolution as a process of unfolding. This theory is based on four logically concatenated principles. The principle of evolutionary order establishes that the more complex cannot be generated from the simpler. The principle of origin establishes that there must be a maximum complexity that originates the others by logical deduction. Finally, the principle of unfolding and the principle of actualization guarantee the development of the evolutionary process from the simplest to (...) the most complex. These logical principles determine the existence of a virtual ideological matrix that contains the sequence of the preformed and folded morphogenetic fields. In this manner, the evolutionary process consists of the sequential unfolding and actualization of these fields, which is motorized by a process of teleologization carried out by the opening consciousness of the forms included in the fields of the ideological matrix. This theory leads to a radical change of perspective regarding the materialist worldview, and places life at the center of the evolutionary process as an activity carried out by a consciousness that seeks to fulfill a purpose by actualizing its own potentialities. (shrink)

We investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ₂—theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ₁—theory of multiplication and order is decidable in finite models (...) as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation. We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication. (shrink)

This paper is about partially ordered multisets (pomsets for short). We investigate a particular class of pomsets that we call order-deterministic, properly including all partially ordered sets, which satisfies a number of interesting properties: among other things, it forms a distributive lattice under pomset prefix (hence prefix closed sets of order-deterministic pomsets are prime algebraic), and it constitutes a reflective subcategory of the category of all pomsets. For the order-deterministic pomsets we develop an algebra with a sound and (-) complete (...) equational theory. The operators in the algebra are concatenation and join, the latter being a variation on the more usual disjoint union of pomsets. This theory is then extended in order to capture refinement of pomsets by incorporating homomorphisms between models as objects in the algebra and homomorphism application as a new operator. (shrink)

Algebraic theories for extensive measurement are traditionally framed in terms of a binary relation $\lesssim $ and a concatenation (x,y)→ xy. For situations in which the data is "noisy," it is proposed here to consider each expression $y\lesssim x$ as symbolizing an event in a probability space. Denoting P(x,y) the probability of such an event, two theories are discussed corresponding to the two representing relations: p(x,y)=F[m(x)-m(y)], p(x,y)=F[m(x)/m(y)] with m(xy)=m(x)+m(y). Axiomatic analyses are given, and representation theorems are proven in detail.

An elementary theory of concatenation,QT+, is introduced and used to establish mutual interpretability of Robinson arithmetic, Minimal Predicative Set Theory, quantifier-free part of Kirby’s finitary set theory, and Adjunctive Set Theory, with or without extensionality. The most basic arithmetic and simplest set theory thus turn out to be variants of string theory.

If the title of this article resounds with the polemical palavering of literary theory in the 1940s, I have to submit that the allusion is not entirely accidental. It is not my intention here, however, to resuscitate the arguments of W. K. Wimsatt Jr and Monroe C. Beardsley, but rather to evoke a sense of parallelism between their issues and those at stake here. A crucial objective which informed Wimsatt's and Beardsley's project was to buttress the significance and irreducibility (...) of the literary text in the face of monopolistic authorial and receptional meaning-making. [3] The scholarly environment that was American New Criticism tended to consider intentionalism and emotionalism as threats to the epistemological prominence and integrity of the text, which was all too readily lost in a plenitude of contexts whose relevance for the literary work was not always impressively transparent. Similarly, within the domain of film studies, it has perhaps become increasingly unclear whether the real object of study is the film text itself, or rather a concatenation of different disciplinary discourses hailing from departments of psychology, sociology, and biology (to name a few). The colonization of cinema studies is not a novel development; as a process its apogee was in the 1970s. (shrink)

The proposition 'seattle is west of spokane' has three parts: two\nproper names and the predicate 'is west of.' the fact pictured has\ntwo: seattle and spokane. but the picture theory holds that there\nmust be a one-to-one correspondence between fact and proposition.\nhow does wittgenstein solve this problem in the 'tractatus'? on one\ninterpretation the fact contains a third part, a relation, corresponding\nto the predicate (evans and stenius). on another the proposition\nis transformed by analysis into a two-dimensional diagram, the predicate\ndisappearing in the process (...) (copi and anscombe). both are rejected.\ntwo new suggestions are offered: (1) the number of possible configurations\nof 'simple' objects is not greater than the number concatenations\nof names, so no predicate is needed in 'elementary' propositions;\n(2) or the predicate can be taken as the analogue of the direction\narrow on a map and not counted as a part of the proposition. (shrink)

This paper deals with Tarski's first axiomatic presentations of the syntax of deductive system. Andrzej Grzegorczyk's significant results which laid the foundations for the formalization of metalogic, are touched upon briefly. The results relate to Tarski's theory of concatenation, also called the theory of strings, and to Tarski's ideas on the formalization of metamathematics. There is a short mention of author's research in the field. The main part of the paper surveys research on the theory of (...) deductive systems initiated by Tarski, in particular research on the axiomatization of the general notion of consequence operation, axiom systems for the theories of classic consequence and for some equivalent theories, and axiom systems for the theories of nonclassic consequence. In this paper the results of Jerzy Supecki's research are taken into account, and also the author's and other people belonging to his circle of scientific research. Particular study is made of his dual characterization of deductive systems, both as systems in regard to acceptance and systems in regard to rejection . Comparison is made, therefore, with axiomatizations of the theories of rejection and dual consequence, and the theory of the usual consequence operation. (shrink)

Proof assistants are software-based tools that are used in the mechanization of proof construction and validation in mathematics and computer science, and also in certified program development. Different such tools are being increasingly used in order to accelerate and simplify proof checking, and the Coq proof assistant is one of the most well known and used in large-scale projects. Language and automata theory is a well-established area of mathematics, relevant to computer science foundations and information technology. In particular, context-free (...) language theory is of fundamental importance in the analysis, design, and implementation of computer programming languages. This work describes a formalization effort, using the Coq proof assistant, of fundamental results of the classical theory of contextfree grammars and languages. These include closure properties (union, concatenation, and Kleene star), grammar simplification (elimination of useless symbols, inaccessible symbols, empty rules, and unit rules), the existence of a Chomsky Normal Form for context-free grammars and the Pumping Lemma for context-free languages. The result is an important set of libraries covering the main results of context-free language theory, with more than 500 lemmas and theorems fully proved and checked. As it turns out, this is a comprehensive formalization of the classical context-free language theory in the Coq proof assistant and includes the formalization of the Pumping Lemma for context-free languages. The perspectives for the further development of this work are diverse and can be grouped in three different areas: inclusion of new devices and results, code extraction, and general enhancements of its libraries. (shrink)

"An important contribution to contemporary jurisprudential debate and to legal thought more generally, Just Interpretations is far ahead of currently available work."--Peter Goodrich, author of Oedipus Lex "I was struck repeatedly by the clarity of expression throughout the book. Rosenfeld's description and criticism of the recent work of leading thinkers distinguishes his work within the legal theory genre. Furthermore, his own theory is quite original and provocative."--Aviam Soifer, author of Law and the Company We Keep.

The syllogistic figures and moods can be taken to be argument schemata as can the rules of the Stoic propositional logic. Sentence schemata have been used in axiomatizations of logic only since the landmark 1927 von Neumann paper [31]. Modern philosophers know the role of schemata in explications of the semantic conception of truth through Tarski’s 1933 Convention T [42]. Mathematical logicians recognize the role of schemata in first-order number theory where Peano’s second-order Induction Axiom is approximated by Herbrand’s (...) Induction-Axiom Schema [23]. Similarly, in first-order set theory, Zermelo’s second-order Separation Axiom is approximated by Fraenkel’s first-order Separation Schema [17]. In some of several closely related senses, a schema is a complex system having multiple components one of which is a template-text or scheme-template, a syntactic string composed of one or more “blanks” and also possibly significant words and/or symbols. In accordance with a side condition the template-text of a schema is used as a “template” to specify a multitude, often infinite, of linguistic expressions such as phrases, sentences, or argument-texts, called instances of the schema. The side condition is a second component. The collection of instances may but need not be regarded as a third component. The instances are almost always considered to come from a previously identified language (whether formal or natural), which is often considered to be another component. This article reviews the often-conflicting uses of the expressions ‘schema’ and ‘scheme’ in the literature of logic. It discusses the different definitions presupposed by those uses. And it examines the ontological and epistemic presuppositions circumvented or mooted by the use of schemata, as well as the ontological and epistemic presuppositions engendered by their use. In short, this paper is an introduction to the history and philosophy of schemata. (shrink)

CORCORAN REVIEWS THE 4 VOLUMES OF TARSKI’S COLLECTED PAPERS Alfred Tarski (1901--1983) is widely regarded as one of the two giants of twentieth-century logic and also as one of the four greatest logicians of all time (Aristotle, Frege and Gödel being the other three). Of the four, Tarski was the most prolific as a logician. The four volumes of his collected papers, which exclude most of his 19 monographs, span over 2500 pages. Aristotle's writings are comparable in volume, but most (...) of the Aristotelian corpus is not about logic, whereas virtually everything written by Tarski concerns logic more or less directly. There is no doubt that Tarski wrote more on logic than any other author; he started publishing on logic in 1921 at the age of 20 and continued until his death at the age of 82. (shrink)

Extensive measurement is the standard measurement-theoretic approach for constructing a ratio scale. It involves the comparison of objects that can be concatenated in an additively representable way. This paper studies the implications of extensively measurable welfare for social choice theory. We do this in two frameworks: an Arrovian framework with a fixed population and no interpersonal comparisons, and a generalized framework with variable populations and full interpersonal comparability. In each framework we use extensive measurement to introduce novel domain restrictions, (...) independence conditions, and constraints on social evaluation. We prove a welfarism theorem for these domains and characterize the social welfare functions that satisfy the axioms of extensive measurement at both the individual and social levels. The main results are simple axiomatizations of strong dictatorship in the Arrovian framework and classical utilitarianism in the generalized framework. (shrink)

This thesis concerns alternative concatenating operations in extensive measurements and the degree to which concatenating operations are matter of convention. My arguments are directed against Ellis' claim that what prevents us from choosing alternative ways of combining extensive quantities is only convenience and simplicity and that the choice is not based on empirical reasons. ;My first argument is that, given certain relational theories of measurement, there can be no more than one concatenating operation per quantity; because combining operations are the (...) only conclusive distinguishing characteristic among distinct extensive measurements and thus the only thing that can serve as an indicator for the identity of a quantity. Rectangular and collinear concatenation, for example, cannot both be used as a way of combining lengths. However, rectangular concatenation could be used to measure some other extensive quantity since it fulfills the necessary conditions for adequate numerical assignment. ;For those that adopt theories of measurement which can support the claim that dinches measure length, I demonstrate, in the second argument, that rectangular concatenation would be a bad alternative and thus no alternative at all. Implementation of rectangular concatenation requires a new science; a science compatible with dinches violates present invariance principles and a new set must be provided, if possible. It is not clear that there is a set of invariance principles compatible with dinches which also gives basis for a science that explains the phenomena as well as the old one. Moreover, new invariance principles would be unintuitive and would require that certain fundamental concepts change their meaning. For these reasons the choice between them is guided by a number of empirical reasons and is not only a matter of convention. (shrink)