Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

Paradox is a logical phenomenon. Usually, it is produced in type theory, on a type Ω of “truth values”. A formula Ψ (i.e., a term of type Ω) is presented, such that Ψ↔¬Ψ (with negation as a term¬∶Ω→Ω)-whereupon everything can be proved: In Sect. 1 we describe a general pattern which many constructions of the formula Ψ follow: for example, the well known arguments of Cantor, Russell, and Gödel. The structure uncovered behind these paradoxes is generalized in Sect. 2. This (...) allows us to show that Reynolds' [R] construction of a typeA ≃℘℘A in polymorphic λ-calculus cannot be extended, as conjectured, to give a fixed point ofevery variable type derived from the exponentiation: for some (contravariant) types, such a fixed point causes a paradox.Pursueing the idea that $$\frac{{{\text{type theory}}}}{{{\text{categorical interpretation}}}} = \frac{{{\text{(propositional) logic}}}}{{{\text{Lindebaum algebra}}}}$$ the language of categories appears here as a natural medium for logical structures. It allows us to abstract from the specific predicates that appear in particular paradoxes, and to display the underlying constructions in “pure state”. The essential role of cartesian closed categories in this context has been pointed out in [L]. The paradoxes studied here remain within the limits of the cartesian closed structure of types, as sketched in this Lawvere's seminal paper — and do not depend on any logical operations on the type Ω. Our results can be translated in simply typed λ-calculus in a straightforward way (although some of them do become a bit messy). (shrink)

Let C be a small Barr-exact category, Reg the category of all regular functors from C to the category of small sets. A form of M. Barr's full embedding theorem states that the evaluation functor e : C →[Reg, Set ] is full and faithful. We prove that the essential image of e consists of the functors that preserve all small products and filtered colimits. The concept of κ-Barr-exact category is introduced, for κ any infinite regular cardinal, and the natural (...) generalization to κ-Barr-exact categories of the above result is proved. The treatment combines methods of model theory and category theory. Some applications to module categories are given. (shrink)

Three principal varieties of mathematical structuralism are compared: set-theoretic structuralism (‘STS’) using model theory, Shapiro's ante rem structuralism invoking sui generis universals (‘SGS’), and the author's modal-structuralism (‘MS’) invoking logical possibility. Several problems affecting STS are discussed concerning, e.g., multiplicity of universes. SGS overcomes these; but it faces further problems of its own, concerning, e.g., the very intelligibility of purely structural objects and relations. MS, in contrast, overcomes or avoids both sets of problems. Finally, it is argued that the modality (...) of MS or a close cousin appears at crucial junctures in both STS and SGS, so that the above outcome is not obviously tendentious. (shrink)

Category theory and topos theory have been seen as providing a structuralist framework for mathematics autonomous vis-a-vis set theory. It is argued here that these theories require a background logic of relations and substantive assumptions addressing mathematical existence of categories themselves. We propose a synthesis of Bell's many-topoi view and modal-structuralism. Surprisingly, a combination of mereology and plural quantification suffices to describe hypothetical large domains, recovering the Grothendieck method of universes. Both topos theory and set theory can be carried out (...) relative to such domains; puzzles about ‘large categories’ and ‘proper classes’ are handled in a uniform way, by relativization, sustaining insights of Zermelo. (shrink)

2014 Reprint of 1962 Edition. Full facsimile of the original edition, not reproduced with Optical Recognition Software. In "Algebraic Logic" Halmos devised polyadic algebras, an algebraic version of first-order logic differing from the better known cylindric algebras of Alfred Tarski and his students. An elementary version of polyadic algebra is described in monadic Boolean algebra. This book addresses some of the problems of mathematical logic and the theory of polyadic Boolean algebras in particular. It is intended to be an efficient (...) way of treating algebraic logic in a unified manner. (shrink)

We investigate the problem of characterizing the classes of Grothendieck toposes whose internal logic satisfies a given assertion in the theory of Heyting algebras, and introduce natural analogues of the double negation and De Morgan topologies on an elementary topos for a wide class of intermediate logics.

A precise notion of ‘mathematical structure’ other than that given by model theory may prove fruitful in the philosophy of mathematics. It is shown how the language and methods of category theory provide such a notion, having developed out of a structural approach in modern mathematical practice. As an example, it is then shown how the categorical notion of a topos provides a characterization of ‘logical structure’, and an alternative to the Pregean approach to logic which is continuous with the (...) modern structural approach in mathematics. (shrink)

Category Theory has developed rapidly. This book aims to present those ideas and methods which can now be effectively used by Mathe­ maticians working in a variety of other fields of Mathematical research. This occurs at several levels. On the first level, categories provide a convenient conceptual language, based on the notions of category, functor, natural transformation, contravariance, and functor category. These notions are presented, with appropriate examples, in Chapters I and II. Next comes the fundamental idea of an adjoint (...) pair of functors. This appears in many substantially equivalent forms: That of universal construction, that of direct and inverse limit, and that of pairs offunctors with a natural isomorphism between corresponding sets of arrows. All these forms, with their interrelations, are examined in Chapters III to V. The slogan is "Adjoint functors arise everywhere". Alternatively, the fundamental notion of category theory is that of a monoid -a set with a binary operation of multiplication which is associative and which has a unit; a category itself can be regarded as a sort of general­ ized monoid. Chapters VI and VII explore this notion and its generaliza­ tions. Its close connection to pairs of adjoint functors illuminates the ideas of universal algebra and culminates in Beck's theorem characterizing categories of algebras; on the other hand, categories with a monoidal structure lead inter alia to the study of more convenient categories of topological spaces. (shrink)