Jerzy Perzanowski

Tarski and modal logic

Spread the love

TARSKI AND MODAL LOGIC

JERZY PERZANOWSKI

Department of Logic, N. Copernicus University
& Department of Logic, Jagiellonian University
e-mail: jperzan@cc.uni.torun.pl

0. Bibliography of Alfred Tarski includes ca. 93 original papers (excluding abstracts, etc. After Bibliography of Jan Zygmunt included in the first volume of Polish Edition of Tarski’s collected works).
10 of them are connected, either immediately or in some indirect way with modal logic. Five papers are co-authored – 3 with J. C. C. McKinsey, 2 with B. Jтnsson.

1. Two types of works: these which are motivated by Tarski’s own ideas and research and these influenced by works of Gцdel, Stone and Birkhoff as well as by a seminal work of Mordchaj Wajsberg.

WORKS MOTIVATED BY TARSKI’S OWN RESEARCH

A. Investigation of methodology of deductive systems and in later period research concerning logics of suitable lattices of such logics.

B. Comparison of logics with algebras and suitable topological spaces.

C. Starting steps in systematical investigations of algebraic semantics for modal logics.

D. Investigation of relational algebras, in particular representation problem for Boolean algebras with operators by means of suitable relational frames.
E. Investigation of Post – complete overlogics in a given class of modal logics. Uniqueness conditions.

INVESTIGATIONS MOTIVATED BY WORKS OF OTHER SCHOLARS

F. Work of Kurt Gцdel: Comparison of Intuitionistic Logic and Lewis calculus S4, translation of McKinsey and Tarski

G. Work of Mordchaj Wajsberg “Ein erweiterter Klassenkalk_l”, 1933: Similarity between modalities and quantifiers (algebraization of quantifiers). Completeness theorems in power – set Boolean algebras (so-called Scott-Montague semantics). Number of modalities. Decidability.

H. Work of Marshall Stone: Representation theorems!

OUTLINE AND SHORT COMMENTS

2. Ad A.

Investigation concerning the theory of deductive systems and – in later time – logics defined by suitable lattices of such systems. Cf. Alfred Tarski “Gr_ndzuge der Systemkalk_ls”, 1936 oraz “Der Auusagenkalk_l und die Topologie”, 1938.
Tarski investigated a calculus of deductive system with counterparts of classical (or Intuitionistic) logic functors. Let us consider the family of all systems closed on detachment (but not logics – which are aditionally closed on substitution).

(1) Tarski’s Theorem.
Theorems of Intuitionistic Calculus are characterized by means of pseudoboolean algebra dense in itself, metrizable and nonempty
topological space.

Recall that S is dense in itself iff xC(S-{x}).

Many similar theorems!
Characterization of some other systems, including semantics for the calculus of “weak law of the excluded middle” built up from finitely aximatizable systems.
Wojciech Dzik in his Ph. D. Dissertation “On the Content of Lattices of Logics”, RML, nry 13 i 14 (1981,1982) gave some natural generalizations of Tarski type theorems.
Let me mention here only his remarkable result: Intuitionistic logic is the lattice of all theories of classical logic.

3. Ad B i C.

Alfred Tarski started systematic investigation of algebraic semantics for modal logics. He offered their comparison with abstract algebras with operators, putting special emphasis on set-theoretical algebras, and with suitable topological spaces. Cf. A. Tarski and J. C. C. McKinsey papers: “The algebra of topology”, 1944, “On closed elements in closure algebras” as well as Tarski’s work “A remark on functionally free algebras”.
In these papers, starting with matrices (algebras) of Lindenbaum – Tarski for S4 closure algebras were characterized (later called topological algebras), giving, inter alia, conditions for their embedding into subalgeras built on appropriate topological spaces.
Among other results their obtained:

(2) The closure algebra of any zero-dimensional dense-in-itself subspace of Euclidean space (e. g., Cantor discontinuum or the space of points with rational coordinates) includes isomorphic copies of all finite closure algebras as subalgebras.

(3) Every finite closure algebra is isomorphic embeddable into the closure algebra of subsets of some open subset of Euclidean space.

(4) An equation that is satisfied by the closure algebra of any Euclidean space is satisfied by every closure algebra.

(5) An equation that is satisfied by all finite closure algebras is satisfied by every closure algebra (it is an algebraic counterpart of McKinsey finite model property for S4).
(6) The algebra of open (i. e. Ix=x) elements of a closure algebra form a sublattice that is a model of Intuitionistic logic.

(7) They characterize also free closure algebras (inter alia, they are infinite), as well as

(8) Consider the family of functionally complete algebras (which satisfy only identities of a given variety):
 no such algebra is finitely generated:
 closure algebra over each normal, dense-in-itself topological space with denumerable basis is functionally complete. ETC.

In the second of these papers a strong connection between closure algebras and Brouwerian algebras were described, including characterization of free algebras in both classes, the role of regular elements. Their mutual duality was also described.
Let me mention here that these investigation were developed in 50-ties and 60-ties in Warsaw by Late Professor Helena Rasiowa and her co-workers (including Late Prof. Cecylia Rauszer).

4. Ad D.

Investigations of relational algebras with the problem
of representation for Boolean algebras with operators.

In 1941 A. Tarski gave description of relation algebras. The problem of their representation was investigated during the forthcoming decades. It was discovered that in the original formulation of Tarski these algebras have no general Representation Theorem.

More particular cases were therefore investigated, including the most famous case of Boolean algebras with operators (cf. B. Jтnsson i A. Tarski “Boolean algebras with operators I & II” 1951 & 1952). This paper as occurred later contains all metamathematics necessary for relational semantics for modal logics!

Let me start with preliminary definitions:
Function F: Un U is called:
normal — F() = 0 iff i xi = 0
additive — F(x+y) = F(x)+F(y)

Boolean algebra with operators :
x+(y+z) = (x+y)+z
x = y+(x+y)
x•(y+z) = x•y +x•z
x•(y•z) = (x•y)•z
x•y = y•x
x•x = x, whereas
Fi are additive.

One of its main results can be expressed as follows:

We investigate regular field of sets. A is therefore the family of all subset of a given set U!
If RUm+1, then R(X) = {y: R for some xX0_…_Xm-1}

(9) Theorem
i) R is normal i completely additive
ii) If F is normal and completely additive, the there is just one relation RUm+1 such that F = R

Reversely, , for given function F we can define its conjugate relation R putting R* ={: xUm, yF({x0},…,{xm-1}).

(10) Theorem 3.9 (Representation theorem)
Any normal, complete and atomic Boolean algebra with operator is isomorphic with the algebra of the following form
.

Particular cases of the above construction are correspondence conditions introduced few years later in relational semantics:
(11) Theorem 3.5
Let F: A  A be such that F is normal and completely additive. Then the above pairs of conditions on functions and respective conditions for relation are equivalent:
A. (i) XF(X)
(ii) F(F(X))F(X)
(iii) F jest self-conjugate, i. e. F(X)Y =  iff F(Y)X = ; etc.

B. (i’) R reflexive, dom(R) = U
(ii’) R transitive
(iii’) R symmetric, etc.

The above correspondence is the fundament of relational semantics.

Relational algebras as the source of suitable semantics for modal logics were considered in a general way in 80-ties by Prof. Ewa Or_owska and her co-workers.

Notice, that the main result of Jonsson and Tarski was their Extension Theorem which says that any Boolean algebra with operators can be embedded isomorphically into a complete and atomic Boolean algebra with operators which they called a perfect extension of the starting algebra. For lack of time I omit details here.

5. Ad E.

Investigation of Post – complete logics in given classes of logics. Uniqueness Conditions

In his work “_ber der Erweiterungen der unvollstandingen Systeme des Aussagenkalk_ls”, 1936, A. Tarski started investigation of the number Post-complete extensions of a given logic, with particular emphasis put on conditions for their uniqueness.

He proved, among other things, his famous criterion

(12) Theorem 2
If X a consistent, purely implicational system based on Modus Pones including
p(qp)
p((pq)q)
(gr)((pq)(pr))
then classical implicational logic is its the only one Post-complete extension.

This work has influenced many researchers for investigation of Post-complete logics in other classes of logics, in particular in the lattice of modal logics (McKinsey. Makinson, Segerberg, Perzanowski and others)
which is one of the main pillar of contemporary knowledge of the lattice of modal logics.

6. Ad F

The last common work of Tarski and McKinsey was their seminal paper “Some theorems about the sentential calculi of Lewis and Heyting”, 1948. It was inspired by short but very important paper of K. Gцdel from early 30-ties.
It was devoted to very detailed investigation of correspondence between Intuitionistic Logic and modal calculus S4 and their characteristic
disjunction property.

Its main results are following ones:
(13) Proof that S4 jest normal, i.e., is closed on G_del’s Rule of Necessitation : A/A ;

(14) That there exists overlogic of S4, so-called calculus of McKinsey and Soboci_ski S4[AA] which is not normal, hence discovering that the lattice of normal logics is included into the class of quasi-normal logics.

(15) Proof that both Int and S4 join disjunction property.

(16) Investigation of transformation introduced by Gцdel which connects Intuitionistic Calculus with S4 (with two variants).
To be more exact, let
T: FOR (RInt)  FOR(S4), with the following clauses
T(p) := p
T(AB) := (TATB)
T(¬A) := ¬TA
The we have

(17) Theorem Int _ A iff S4 _ T(A)

Let me mention that this transformation was investigated and modified by quite a lot of researchers. Particularly important are

(18) Observation of I. Hacking from 60-ties (“What is a Strict Implication?”) showing that S4 can be replaced in (17) by a weaker calculus S3.

Beautiful and deep result of Leo Esakia from 70-ties

(18) Let P be normal overlogic of S4. Then
Int _ A iff P _ A  S4  P  S4GRZ
where S4GRZ = S4[L(L(p  LP)  p)  p]

Conclusion

Works of Alfred Tarski in modal logic clearly are not the most important between his contributions to logic and metamathematics. Anyway, they are done by giant. Therefore, in retrospective, they must be considered as ones of the most important and classic works in modal logic done in the past century.

JERZY PERZANOWSKI

 

Skomentuj

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

*

code