Chapter 1

Deductive Systems and Matrix Semantics

By a propositional language we will understand some set C of propositional

connectives. The C-formulas are built in the usual way from the proposi-

tional variables P o

?

P i ? P 2

5

- - using the connectives in C. We denote the set

of all £-formulas by Frri£. (The subscript is omitted when the language C

is clear from context.) Light faced italic letters p^q.r,..., possibly with sub-

scripts, will be used as metavariables ranging over the set of propositional

variables. An assignment a : {po5PiP25...}—» Frrtc of formulas to variables

extends naturally to a map from Frrtc into itself, also denoted by cr, by setting

cr{(j)(po,. . . , P n - i ) ) = t(po/rpo, •• .,pn-i/(rPn-i)- * is called & substitution. By

a (finitary) inference rule over £ we mean any pair (I \ ip) where T is a finite set

of formulas and (p is a single formula. (From this point of view modus ponens

would take the form ({p,p —» q}:q).) A formula tp is directly derivable from

a set A of formulas by the rule (T,(p) if there is a substitution a such that

a(f = ip and cr(r) C A; (c(T) = {TI? : I? £ T}). A deductive system S (over C)

is defined by a (possible infinite) set of inference rules and axioms; it consists of

the pair S = ( £ , h $ ) where \~s is the relation between sets of formulas and in-

dividual formulas defined by the following condition: A h$ ip iff -0 is contained

in the smallest set of formulas that includes A together with all substitution

instances of the axioms of S, and is closed under direct derivability by the

inference rules of S. In informal remarks we often refer to a deductive system

as a logical system or simply a logic. The relation h$ is called the consequence

relation of S. It is easily seen to satisfy the following three conditions for all

T, A C Fm and £ , ip G Fm:

peT=T\-sr, (i)

r h

5

(^ and r C A = A h

5

^ ; (2)

r \~s W and A h

5

ip for every ip G T = A h j y. (3)

deceived by the editor April 19, 1987.

2 Work partially supported by NSF-grant DMS-8703743.

3 For a comprehensive account of most of the topics of this chapter see Wojcicki [47],[48].

5