Halmos - Algebraic Logic

ALGEBRAIC LOGIC

P AUL R. H ALMOS

D OVER P UBLICATIONS , I NC . M INEOLA , N EW Y ORK

Bibliographical Note

This Dover edition, first published in 2016, is an unabridged republication of the work originally published by Chelsea Publishing Company, New York, in 1962.

Library of Congress Cataloging-in-Publication Data

Halmos, Paul R. (Paul Richard), 1916-2006.

Algebraic logic / Paul R. Halmos.Dover edition.

p. cm.

Originally published: New York : Chelsea Publishing Company, 1962.

Includes bibliographical references and index.

eISBN-13: 978-0-486-81041-6

1. Algebraic logic. I. Title.

QA266.H32016

511.3'24dc23

2015025415

Manufactured in the United States by RR Donnelley

801454012016

www.doverpublications.com

PREFACE

Partly because of its perpetual intrinsic interest and partly because of its surprising new applications, mathematical logic is a much discussed subject nowadays. Algebraic logic is a modern approach to some of the problems of mathematical logic, and the theory of polyadic Boolean algebras, with which this volume is mostly concerned, is intended to be an efficient way of treating algebraic logic in a unified manner.

A study of the table of contents, or even just a quick riffle through the pages, will show the reader that this is a somewhat unusual sort of book. It is, in fact, a collection of papers, namely all my papers on algebraic logic. The reasoning that brought it into existence goes as follows. The literature of polyadic Boolean algebras is, so far, not very much more extensive than this set of papers. (See the Additional Bibliography on page 265.) Any book I could write on the subject now would therefore consist, essentially, of just these papers, with, naturally, some connective tissue, and, possibly, an occasional change of terminology and notation. To print such a small modification of something already in print would cost a prohibitive amount in comparison with the novelty of the contribution it could make. On the other hand, to learn the subject from the papers in their original sources would put the learner to an unreasonable inconvenience. There are ten papers, ranging in length from one page to 70 pages; they appeared between 1954 and 1959, in eight journals, in four countries. This diversity of sources makes access to the work as a whole inconvenient and sometimes impossible. Conclusion: a good purpose might be served by publishing the papers as they stand, but collected together.

The order in which the papers appear here is one in which a reader unfamiliar with the subject might want to read them; it is not the same as their chronological order. The introductory paper, for instance, was written after several of the others were in print already, and the summary at the end consists of the abstracts and announcements that were the first to appear.

The collection in its present form and order is accessible to a general mathematical audience; no vast knowledge of algebra or logic is required. The main prerequisite is familiarity with the elementary (algebraic) properties of Boolean algebras; a few of the results are proved by reference to the (topological) duality theory of Boolean spaces. Except for this slight Boolean foundation, the volume is essentially self-contained.

I am grateful to the American Mathematical Society, the Mathematical Association of America, the National Academy of Sciences, and to the editorial committees of Compositio Mathematica, the Duke Mathematical Journal, and Fundamenta Mathematicae for permission to reproduce in this form the papers that they first published.

P. R. H.

CONTENTS

I

INTRODUCTION

THE BASIC CONCEPTS OF ALGEBRAIC LOGIC

1. Introduction. It has often happened that a theory designed originally as a tool for the study of a physical problem came subsequently to have purely mathematical interest. When that happens, the theory is usually generalized way beyond the point needed for applications, the generalizations make contact with other theories (frequently in completely unexpected directions), and the subject becomes established as a new part of pure mathematics. The part of pure mathematics so created does not (and need not) pretend to solve the physical problem from which it arises; it must stand or fall on its own merits.

Physics is not the only external source of mathematical theories; other disciplines (such as economics and biology) can play a similar role. A recent (and possibly somewhat surprising) addition to the collection of mathematical catalysts is formal logic; the branch of pure mathematics that it has precipitated will here be called algebraic logic.

Algebraic logic starts from certain special logical considerations, abstracts from them, places them into a general algebraic context, and, via the generalization, makes contact with other branches of mathematics (such as topology and functional analysis). It cannot be overemphasized that algebraic logic is more algebra than logic. Algebraic logic does not claim to solve any of the vexing foundation problems that sometimes occupy logicians. All that is claimed for it is that it is a part of pure mathematics in which the concepts that constitute the skeleton of modern symbolic logic can be discussed in algebraic language. The discussion serves to illuminate and clarify those concepts and to indicate their connection with ordinary mathematics. Whether the subject as a whole will come to be considered sufficiently interesting and sufficiently deep to occupy a place among pure mathematical theories remains to be seen.

The literature of algebraic logic is not yet very extensive, and the few items that are available are highly technical. It is for that reason that this expository paper was written; its main purpose is to kindle interest in a young but promising subject. In such a context it does not seem to be appropriate to burden the reader with the usual scholarly references and assignments of credit. At the very least, however, the names of the principal contributors should be mentioned. Here they are: Curry, Henkin, Rasiowa, Sikorski, and Tarski. Many of the ideas of algebraic logic have been in the air for several years and were known, at least subconsciously, by most logicians. The greatest contributions are those of Tarski; especially relevant is his work (with Jnsson) on Boolean algebras with operators and his theory of cylindric algebras. (Most of the latter material is unfortunately unpublished.) The reader who wishes to study the details will find exact references in two papers on algebraic logic by the present author; the first is in Compositio Mathematica (1955), and the second is to appear in Fundamenta Mathematicae (1957).

2. Boolean algebras. The father of algebraic logic is George Boole; it is appropriate that a discussion of the subject begin with a quick review of the algebras that bear his name. The shortest definition of Boolean algebras is in terms of the theory of rings: a Boolean algebra is a ring with unit in which every element is idempotent (i.e., if p is in the ring, then p2 = p). The simplest example, and one that plays a vitally important role throughout the theory, is the field of integers modulo 2; this Boolean algebra will be denoted by O.

Boolean algebras have an almost embarrassingly rich structure. It is, for instance, an easy consequence of the definition that a Boolean algebra always has characteristic 2 (