HELENA RASIOWA, 1917 - 1994

by

W. Bartol, E. Orłowska, A. Skowron

Algebraic Logic

The study of the relationship between logic and algebra, originated by the work of George Boole and continued by A.Lindenbaum, A.Tarski, M.H.Stone, R.McKinsey, A.Mostowski and L.Henkin - to mention only a few - was the main research subject of Helena Rasiowa. One of the crucial moments in the development of algebraic study of logic was the introduction of Lindenbaum's and Tarski's method for treating equivalence classes of formulas as elements of an abstract algebraic system. This provided a link between theories based on classical logic and Boolean algebras. An analogous correspondence between intuitionistic logic and pseudo-complemented lattices was established by Stone and Tarski, while the application of algebraic methods to modal logics was originated by McKinsey and Tarski (1944 - 1948). Another important idea leading to the emergence of the field of algebraic logic was the treatment of formulas as algebraic functions in certain algebras, initiated by Ł ukasiewicz and Post with their generalization of truth tables.

Helena Rasiowa became very active in these areas in the early fifties. Her research work on algebraic logic was aimed at finding a precise description for the mathematical structure of formalised logical systems. Her early papers contain several examples of algebras associated with logical systems as well as algebraic proofs of some of their properties. Jointly with Roman Sikorski she presented the first algebraic proof of the Gödel completeness theorem for classical predicate logic ([4]). Next, she algebraically proved analogous theorems for intuitionistic and modal logics ([5]). In the papers [9, 13, 14, 16, 18, 21, 22, 23, 24, 25, 26] she turned to other nonclassical logics, applying with success the algebraic tools she had developed. All these investigations led her to a synthesis of the results hitherto obtained; she developed a general framework for an algebraic presentation of propositional and first order logics. In particular, she established elegant formal techniques for associating classes of algebras with logical systems and for providing their algebraic semantics. In the following we shall briefly outline the basic elements of her method for an algebraization of logics.

Rasiowa's first monograph The Mathematics of Metamathematics ([31]) written jointly with R.Sikorski, contains a comprehensive survey of algebraic theories of logical calculi. Algebraization is applied to classical, intuitionistic, modal and positive logics. The book focuses on metalogical theorems on the predicate calculi of these logics and on an investigation of elementary theories based on them. The main idea underlying the concept of associating algebraic systems with logical calculi is the following: Let $L$ be a first order language such that $V$ is its set of individual variables, MATH are the binary propositional connectives of $L$, $\neg$ is a unary propositional connective and $\exists, \forall$ are the quantifiers of $L.$ Let MATH be a complete algebra such that MATH are binary operations, $-$ is a unary operation and $\bigcup$ and $\bigcap$ are infinitary operations the common domain of which is the class of all nonempty subsets of $A.$ By a realization of the language $L$ in a nonempty set $J$ and in the algebra $A$ we mean any mapping $R$ which assigns a function MATH to each function symbol $f$ of $L$ and a function MATH to any predicate symbol $P$ of $L.$ The realization $R$ is then extended to all the terms and all the formulas of $L.$ Let $v \in J^V$ be a valuation of individual variables in a set $J.$ Then we define:

{} $x_{R}(v)=v(x)$ for any individual variable $x,$

{} MATH

{} MATH

{} MATH

{} MATH

{} MATH

{} MATH

{} MATH where $v_{j}\in J^{V}$ and $v_{j}(x)=j,$
$v_{j}(y)=v(y)$ for all $y\neq x,$

{} MATH where $v_{j}\in J^{V}$ is as above.

The algebraic semantics of the classical predicate logic is determined by the class of realizations of the language $L$ in Boolean algebras. We say that a formula is true in a realization $R$ whenever $F_R(v)=1$ for every valuation $v,$ where 1 is the unit element of the underlying Boolean algebra. A formula $F$ is valid in the classical predicate logic if and only if $F$ is true in all realizations in any Boolean algebra. Similarly, the semantics of intuitionistic logic is given by realizations in Heyting algebras, positive first order logic is associated with realizations in the class of relatively pseduocomplemented lattices. Modal logic, also considered in the book, is semantically determined by the class of realizations in what is known as topological Boolean algebras, i.e. Boolean algebras endowed with a unary operation behaving like an interior operator.

In the next monograph An Algebraic Approach to Non-classical Lo-gics ([49]) Helena Rasiowa develops a general algebraization theory for propositional logical systems. Within the framework of this theory she presents algebraizations of a number of non-classical logics such as: classical and positive implicative logics, logics weaker than positive implicative logic, minimal logic, positive logic with semi-negation, constructive logic with strong negation and many-valued Post logics. The fundamental idea behind algebraization is the following: Let $S=(L,C)$ be a propositional logic, where $L$ is a propositional language that includes implication as a binary connective and $C$ is a consequence operation determined by the axioms and inference rules. As usual, for a set $X$ of formulas we denote by $C(X)$ the least set of formulas which contains the axioms and the set $X$ and is closed with respect to the inference rules. In particular, $C(\emptyset)$ is the set of all the theorems of $S.$ An algebra associated with $S$ is any algebra of a type similar to that of the algebra of formulas of $S$ and endowed with a distinguished element 1. Elements of such an algebra are interpreted as truth values, whereas 1 represents the value true. Let $V$ be the set of propositional variables of $L.$ By a valuation in an algebra $A$ associated with $S$ we mean any mapping $v \in A^V.$ Every formula $F$ of the language $L$ induces a mapping MATH defined as follows:

{} $p_{A}(v)=v(p)$ for any propositional variable $p$,

{} MATH for every unary propositional connective $\#$ of $L,$

{} MATH for every binary connective $\#$ of $L,$

A formula $F$ is said to be true in $A$ if and only if $F_A(v)=1$ for every $v \in A^V.$

Any propositional logic $S$ determines thus a class of $S$-algebras, where an $S$-algebra is an algebra $A$ associated with $S$ such that for every formula $F \in C(\emptyset)$ we have $F_A(v)=1$ for every $v \in A^V.$ The completeness theorem states that if $S$ is consistent, then the set $C(\emptyset)$ is equal to the set of all formulas which are true in each $S$-algebra.

Helena Rasiowa paid very much attention to many-valued Post logics. She introduced several generalizations of the standard $m$-valued Post logics; she considered the propositional and predicate versions of $\omega ^{+}$-valued Post logics and used them in her reasoning on programs. The following section describes some of these applications in more detail.