The lattices of the title generalize the concept of a De Morgan lattice. A representation in terms of ordered topological spaces is described. This topological duality is applied to describe homomorphisms, congruences, and subdirectly irreducible and free lattices in the category. In addition, certain equational subclasses are described in detail.

I was born in Auchtermuchty, a small village in Fife, Scotland, the son of a lowland mother, Meta Mowat, daughter of a country headmaster, and a highland father, William Urquhart from Lairg, Sutherland. The family business in Lairg was a butcher’s shop, known as Urquhart the Butcher, even for some years after my father’s family had given it up.

The prelims comprise: Introduction Time and Space in Computation Hierarchies and Reducibility NP‐completeness and Beyond Parallel Computation Complexity and Philosophy.

This paper defines a category of bounded distributive lattice-ordered grupoids with a left-residual operation that corresponds to a weak system in the family of relevant logics. Algebras corresponding to stronger systems are obtained by adding further postulates. A duality theoey piggy-backed on the Priestley duality theory for distributive lattices is developed for these algebras. The duality theory is then applied in providing characterizations of the dual spaces corresponding to stronger relevant logics.

This note extends earlier results on geometrical interpretations of the logic KR to prove some additional results, including a simple undecidability proof for the four-variable fragment of KR.

We prove that for sufficiently large \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $n$\end{document}, there are tautologies of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $O(n)$\end{document} that require proofs containing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\Omega( n / \log n )$\end{document} lines in axiomatic systems of propositional logic based on the rules of substitution and detachment.

Henry M. Sheffer is well known to logicians for the discovery (or rather, the rediscovery) of the ?Sheffer stroke? of propositional logic. But what else did Sheffer contribute to logic? He published very little, though he is known to have been carrying on a rather mysterious research program in logic; the only substantial result of this research was the unpublished monograph The General Theory of Notational Relativity. The main aim of this paper is to explain, as far as possible (given (...) the scanty evidence), the nature of Sheffer's program, and the reasons for its failure. The paper concludes with a discussion of Sheffer's only true logical descendant, C.H. Langford, and his contributions to model theory. (shrink)

I discuss a collection of problems in relevance logic. The main problems discussed are: the decidability of the positive semilattice system, decidability of the fragments of R in a restricted number of variables, and the complexity of the decision problem for the implicational fragment of R. Some related problems are discussed along the way.

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

This note defines Ehrenfeucht-Fraïssé games where identity is not present in the basic language. The formulation is applied to show that there is no elementary theory in the language of one binary relation that exactly characterizes models in which the relation is the identity relation.

This note provides a proof that the formula L is not equivalent to any first degree formula in the context of the quantified version of the modal logic S5. This solves a problem posed by Max Cresswell.

Craig's interpolation theorem fails for the propositional logics E of entailment, R of relevant implication and T of ticket entailment, as well as in a large class of related logics. This result is proved by a geometrical construction, using the fact that a non-Arguesian projective plane cannot be imbedded in a three-dimensional projective space. The same construction shows failure of the amalgamation property in many varieties of distributive lattice-ordered monoids.

The first part of the paper is devoted to surveying the remarks that philosophers and mathematicians such as Maddy, Hardy, Gowers, and Zeilberger have made about mathematical depth. The second part is devoted to the question of whether we can make the notion precise by a more formal proof-theoretical approach. The idea of measuring depth by the depth and bushiness of the proof is considered, and compared to the related notion of the depth of a chess combination.

An Ockham lattice is defined to be a distributive lattice with 0 and 1 which is equipped with a dual homomorphic operation. In this paper we prove: (1) The lattice of all equational classes of Ockham lattices is isomorphic to a lattice of easily described first-order theories and is uncountable, (2) every such equational class is generated by its finite members. In the proof of (2) a characterization of orderings of with respect to which the successor function is decreasing is (...) given. (shrink)

This article presents a simplified proof of the result that bounded depth propositional proofs of the pigeonhole principle are exponentially large. The proof uses the new techniques for proving switching lemmas developed by Razborov and Beame. A similar result is also proved for some examples based on graphs.

First published in 1994. Routledge is an imprint of Taylor & Francis, an informa company.

This paper investigates the depth of resolution proofs, that is to say, the length of the longest path in the proof from an input clause to the conclusion. An abstract characterization of the measure is given, as well as a discussion of its relation to other measures of space complexity for resolution proofs.

This paper surveys the interactions between Russell and Gödel, both personal and intellectual. After a description of Russell’s influence on Gödel, it concludes with a discussion of Russell’s reaction to the incompleteness theorems.

This paper shows that model structures for R+, the system of positive relevant implication, can be constructed from ordered geometries. This extends earlier results building such model structures from projective spaces. A final section shows how such models can be extended to models for the full system R.

Quine has argued that modal logic began with the sin of confusing use and mention. Anderson and Belnap, on the other hand, have offered us a way out through a strategy of nominahzation. This paper reviews the history of Lewis's early work in modal logic, and then proves some results about the system in which "A is necessary" is intepreted as "A is a classical tautology.".

This has been a great century for logic and the foundations of mathematics. Ewald's excellent sourcebook is a welcome addition to the literature on the exciting developments of this and the past two centuries. The richness of the material on which Ewald is drawing is shown by the fact that he has assembled a broad and representative selection without once duplicating anything to be found in the famous sourcebooks of van Heijenoort and Benacerraf/Putnam.

Hans Herzberger as a philosopher and logician has shown deep interest both in the philosophy of Gottlob Frege, and in the topic of the inexpressible and the ineffable. In the fall of 1982, he taught at the University of Toronto, together with André Gombay, a course on Frege's metaphysics, philosophy of language, and foundations of arithmetic. Again, in the fall of 1986, he taught a seminar on the philosophy of language that dealt with 'the limits of discursive symbolism in several (...) domains of human experience.' The course description continues by saying: 'Special attention will be given to the paradoxes underlying various doctrines of the inexpressible and the tensions inherent in those paradoxes. Some doctrines of .. (shrink)

In lieu of an abstract, here is a brief excerpt of the content:Reviews 91 THE ROOTS OF MODERN LOGIC ALASDAIR URQUHART Philosophy/ U. ofToronto Toronro, ON, Canada M5S IAI URQUHART@CS.TORONTO.EDU I. Grattan-Guinness. The Searchfor Mathematical Roots,r870--r940: logics, Set Theoriesand the Foundations of Mathematicsfrom Cantor through Russellto Godel Princeron: Princeton U. P.,2000. Pp. xiv,690. us$45.oo. Grattan-Guinness's new hisrory of logic is a welcome addition to the literature. The title does not quite do justice ro the book, since it (...) begins with the prehistory of English work in algebraic logic, including the work of the French analycicalschool, and extends to just after Godel's great incompleteness paper of 1931.The core of the book, though, is the philosophical and mathematical developmems leading up to and immediately following from chework ofWhicehead and Russell.Russell is ac chehearcof che book, and as a whole che hisrory forms an imporranr conrribucion ro Russell scudies. Commemarors on Russell have often confined themselves to a rather narrow hisrorical perspeccivein which Russell is seen as the (problemacic) heir of Gottlob Frege, and few ocher hisrorical figures (ocher than Peano) emer imo che picture. Graccan-Guinness corrects chis hisrorica.limbalance by placing Russell in che mucl1 wider context of the development of machemacics on che continent, and in parricu.laremphasizing strongly che key influence of Camor on 92 Reviews Russell's work. Cantor has usually received short shrift from philosophers, as unlike Frege,he appears rarher naive from rhe philosophical point of view. The story proper begins in Chaprer 2 wirh L-igrange'sversion of analysis in which rhe basic concepts were to be defined in rerms of algebraic manipularion of power series. This lead to rhe founding of rhe Analyrical Socierywhere Babbage, Herschel and Peacock were active. It is in chis English tradicion of algebraic analysis char rhe pioneering work of De Morgan and Boole found irs roors. Grarran-Guinness givesa derailed account of the work of both logicians, although his discussion of Boole's merhods does not seem entirely adequate. The question is:what are we to make of Boole'spuzzling insistence chat expressions like x + y are "uninterpretable", while he nevertheless manipulated them freely in his mathematical derivations? It is not correct to say that the addition sign can only link disjoint class symbols, since ir is belied by Boole's formal pracrice. A possible solution has been suggested by Hailperin, in his book on Boole's logic, in which he proposes interpreting the "uninterpretable" expressions as denoting signed mulrisets. Oddly, Grattan-Guinness refers to Hailperin 's work,' bur elsewhere (p. 42) adopts rhe view that Boole's addition sign could only link disjoint classes.The chapter concludes with brief accounts of the work of Cauchy, Weierstrass and Bolz.'lno. The next chapter is a detailed account of rhe work of Cantor and his creation of Mengenlehre. The origins of set theory in the theory of trigonometrical series, and rhe ensuing discoveryof rransfinire ordinal and cardinal numbers, are described clearly and succinctly. In addition, the chapter contains an account of Dedekind's philosophy of arithmetic and Cantor's philosophy of mathematics. Cantor's philosophy is an uneasy blend of formalism, platonism and idealism, and has tmderstandably aroused little enthusiasm among philosophers of matl1ematics, alrhough Michael Hallerr has recently smdied it in detail. GrammGuinness emphasizes, rhough, Cantor's magnificent marhematica.l achievements, in defining and clarifying basic conceprs such as measure, dimension and cardinality of sets. Chaprer 4 is a rather miscellaneous chapter, in which six partly independent, partly interrwined stories are told. It begins with developments in sectheory in Germany and France up to the turn of rhe century, goes on to discuss American logic in rhe work of C. S. Peirce and his students, and continues the rheme of algebraic logic with Schroder and his logic of relatives. The remainder of the chapter is given over to Frege, Husserl and Hilbert. The section on Frege is one of rhe more idiosyncratic parts of the book. Grattan-Guinness distinguishes berween Frege, "a mathematician who wrore in ' T Hailperin, Book's logic and Probability, 2nd ed. (Amsterdam: North-Holland, 1986). Reviews 93 German, in a markedly Platonic spirit", and Frege, "a philosopher of language and founder of... (shrink)

What I wish to propose in the present paper is a new form of “career induction” for ambitious young logicians. The basic problem is this: if we look at the n-variable fragments of relevant propositional logics, at what point does undecidability begin? Focus, to be definite, on the logic R. John Slaney showed that the 0-variable fragment of R (where we allow the sentential con- stants t and f) contains exactly 3088 non-equivalent propositions, and so is clearly decidable. In the (...) opposite direction, I claimed in my paper of 1984 that the five variable fragment of R is undecidable. The proof given there was sketchy (to put the matter charitably), and a close examination reveals that although the result claimed is true, the proof given is incorrect. In the present paper, I give a detailed and (I hope) correct proof that the four variable fragments of the principal relevant logics are undecidable. This leaves open the question of the decidability of the n-variable fragments for n = 1, 2, 3. At what point does undecidability set in? (shrink)

I am deeply grateful to everybody who has contributed to the volume, and wish to express my heartfelt thanks to my old friends and colleagues Ivo Düntsch and Ed Mares who have worked so hard to produce a volume in my honour. I’ve done research in a lot of areas in logic, and the selection of authors provides a good cross-section of my preoccupations.

Around 1989, a striking letter written in March 1956 from Kurt Gödel to John von Neumann came to light. It poses some problems about the complexity of algorithms; in particular, it asks a question that can be seen as the first formulation of the P=?NP question. This paper discusses some of the background to this letter, including von Neumann's own ideas on complexity theory. Von Neumann had already raised explicit questions about the complexity of Tarski's decision procedure for elementary algebra (...) and geometry in a letter of 1949 to J. C. C. McKinsey. The paper concludes with a discussion of why theoretical computer science did not emerge as a separate discipline until the 1960s. (shrink)