In 1934 Alonzo Church, Kurt Gödei, S. C. Kleene, and J. B. Rosser were all to be found in Princeton, New Jersey. In 1936 Church founded The Journal of Symbolic Logic. Shortly thereafter Alan Turing arrived for a two year visit. The United States had become a world center for cutting-edge research in mathematical logic. In this brief survey1 we shall examine some of the writings of American logicians during the 1920s, a period of important beginnings and remarkable insights as (...) well as of confused gropings.The publication of Whitehead and Russell's monumental Principia Mathematica [18] during the years 1910-1913 provided the basis for much of the research that was to follow. It also provided the basis for confusion that remained a factor during the period we are discussing. In 1908, Henri Poincaré, a famous skeptic where mathematical logic was concerned, wrote pointedly :It is difficult to admit that the word if acquires, when written ⊃, a virtue it did not possess when written if.Principia provided no very convincing answer to Poincaré. Indeed the fact that the authors of Principia saw fit to place their first two “primitive propositions”*1.1: Anything implied by a true proposition is true.*1.2: ⊢ p ⋁ p ⊃ punder one and the same heading suggest that they had thought of what they were doing as just such a translation as Poincare had derided. (shrink)

We initiate the study of reducts of relational structures up to primitive positive interdefinability: After providing the tools for such a study, we apply these tools in order to obtain a classification of the reducts of the logic of equality. It turns out that there exists a continum of such reducts. Equivalently, expressed in the language of universal algebra, we classify those locally closed clones over a countable domain which contain all permutations of the domain.

Let K be a finite set of finite structures. We give a syntactic characterization of the property: every element of K is injective in ISP(K). We use this result to establish that A is injective in ISP(A) for every two-element algebra A.

We prove several interpolation theorems for many-valued infinitary logic with quantifiers by studying expansions of MV-algebras in the spirit of polyadic and cylindric algebras. We prove for various reducts of polyadic MV-algebras of infinite dimensions that if is the free algebra in the given signature,, is in the subalgebra of generated by, is in the subalgebra of generated by and, then there exists an interpolant in the subalgebra generated by and such that. We call this a varying interpolation property because (...) the integer depends on the inequality. We also address cases where this interpolation property fails, but other weaker ones hold. One such interpolation theorem says that though an interpolant may not be found as above, an interpolant can always be found if finitely many universal quantifiers are applied to making it smaller and the same number of existential quantifiers are applied to making it bigger. This number of quantifiers also varies; it depends on the inequality. Se.. (shrink)

We characterize the model companions of universal Horn classes generated by a two-element algebra (or ordered two-element algebra). We begin by proving that given two mutually model consistent classes M and N of L (respectively L') structures, with $\mathscr{L} \subseteq \mathscr{L}'$ , M ec = N ec ∣ L , provided that an L-definability condition for the function and relation symbols of L' holds. We use this, together with Post's characterization of ISP(A), where A is a two-element algebra, to show (...) that the model companions of these classes essentially lie in the classes of posets and semilattices, or characteristic two groups and relatively complemented distributive lattices. (shrink)

In 1979, H. Lewis shows that the computational complexity of the Boolean satisfiability problem dichotomizes, depending on the Boolean operations available to formulate instances: intractable (NP-complete) if negation of implication is definable, and tractable (in P) otherwise [21]. Recently, an investigation in the same spirit has been extended to nonclassical propositional logics, modal logics in particular [2, 3]. In this note, we pursue this line in the realm of many-valued propositional logics, and obtain complexity classifications for the parameterized satisfiability problem (...) of two pertinent samples, Kleene and Gödel logics. (shrink)

We describe sets of partial Boolean functions being closed under the operations of superposition. For any class A of total functions we define the set ????(A) consisting of all partial classes which contain precisely the functions of A as total functions. The cardinalities of such sets ????(A) can be finite or infinite. We state some general results on ????(A). In particular, we describe all 30 closed sets of partial Boolean functions which contain all monotone and zero-preserving total Boolean functions.