On the Calculus of Relations

Author(s): Alfred Tarski

Source: The Journal of Symbolic Logic , Sep., 1941, Vol. 6, No. 3 (Sep., 1941), pp. 73-89
Published by: Association for Symbolic Logic

Stable URL: https://www.jstor.org/stable/2268577

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide
range of content in a trusted digital archive. We use information technology and tools to increase productivity and
facilitate new forms of scholarship. For more information about JSTOR, please contact [email protected].

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at
https://about.jstor.org/terms

Association for Symbolic Logic is collaborating with JSTOR to digitize, preserve and extend
access to The Journal of Symbolic Logic

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
THE JOURNAL OF SYMBOLIC LoGic
Volume 6, Number 3, September 1941

ON THE CALCULUS OF RELATIONS

ALFRED TARSKI

The logical theory which is called the calculus of (binary) relations, and which
will constitute the subject of this paper, has had a strange and rather capricious
line of historical development.' Although some scattered remarks regarding the
concept of relations are to be found already in the writings of medieval logicians,
it is only within the last hundred years that this topic has become the subject
of systematic investigation. The first beginnings of the contemporary theory
of relations are to be found in the writings of A. De Morgan, who carried out
extensive investigations in this domain in the fifties of the Nineteenth Century.
De Morgan clearly realized the inadequacy of traditional logic for the expres-
sion and justification, not merely of the more intricate arguments of mathematics
and the sciences, but even of simple arguments occurring in every-day life;
witness his famous aphorism, that all the logic of Aristotle does not permit us,
from the fact that a horse is an animal, to conclude that the head of a horse
is the head of an animal. In his effort to break the bonds of traditional logic and
to expand the limits of logical inquiry, he directed his attention to the general
concept of relations and fully recognized its significance. Nevertheless, De
Morgan cannot be regarded as the creator of the modern theory of relations,
since he did not possess an adequate apparatus for treating the subject in which
he was interested, and was apparently unable to create such an apparatus. His
investigations on relations show a lack of clarity and rigor which perhaps ac-
counts for the neglect into which they fell in the following years.
The title of creator of the theory of relations was reserved for C. S. Peirce. In
several papers published between 1870 and 1882, he introduced and made precise
all the fundamental concepts of the theory of relations and formulated and
established its fundamental laws. Thus Peirce laid the foundation for the theory
of relations as a deductive discipline; moreover he initiated the discussion of
more profound problems in this domain. In particular, his investigations made
it clear that a large part of the theory of relations can be presented as a calculus
which is formally much like the calculus of classes developed by G. Boole and
W. S. Jevons, but which greatly exceeds it in richness of expression and is there-
fore incomparably more interesting from the deductive point of view.
Peirce's work was continued and extended in a very thorough and systematic
way by E. Schrdder. The latter's Algebra und Logik der Relative, which appeared
in 1895 as the third volume of his Vorlesungen uiber die Algebra der Logik, is so

Received February 4, 1941. An address delivered, by invitation of the Program Com-

mittee, to a joint session of the Association for Symbolic Logic, the American Philosophical
Association (Eastern Division), and Section A of the American Association for the Advance-
ment of Science, at Philadelphia, Pennsylvania, on December 28, 1940.
1 For detailed historical information and thorough bibliographical references, see C. I.
Lewis, A survey of symbolic logic, Berkeley, California, 1918.
73

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 74 ALFRED TARSKI

far the only exhaustive account of the calculus of relations. At the same time,
this book contains a wealth of unsolved problems, and seems to indicate the
direction for future investigations.
It is therefore rather amazing that Peirce and Schr6der did not have many
followers. It is true that A. N. Whitehead and B. Russell, in Principia mathe-
matica, included the theory of relations in the whole of logic, made this theory a
central part of their logical system, and introduced many new and important
concepts connected with the concept of relation. Most of these concepts do not
belong, however, to the theory of relations proper but rather establish relations
between this theory and other parts of logic: Principia mathematics contributed
but slightly to the intrinsic development of the theory of relations as an inde-
pendent deductive discipline. In general, it must be said that-though the
significance of the theory of relations is universally recognized today-this
theory, especially the calculus of relations, is now in practically the same stag
development as that in which it was forty-five years ago.

The fact just mentioned was one of the chief motives of my selecting the theory
of relations as the subject for this talk. I shall confine myself here entirely to
the theory of binary relations, since this is the only branch of the general theory
which is at all developed. Moreover I shall be interested exclusively in that part
of the theory of binary relations which is known as the calculus of relations;
and I shall indeed be concerned merely with the calculus of finite operations on
relations, as they were introduced by Peirce. I should like to acquaint you with
two different methods of setting up the foundations of this elementary calculus
in a rigorously deductive way, and I should like to discuss, or at least to formu-
late, some metalogical problems concerning this calculus.

The first method I am going to consider here consists in constructing the

calculus of relations as a part of a more comprehensive logical theory, which
corresponds approximately to the restricted functional calculus as it was given,
for example, by D. Hilbert and W. Ackermann.2
In this more comprehensive logical theory we have two kinds of variables,
individual variables and relation variables; as individual variables we use the
small letters 'x',Iy 'z', * *, and as relation variables the capital letters 'RW
'Ty * . . . We have further in our theory certain constants: first the connectives
of the sentential calculus, namely the negation sign I', the implication sign
', the equivalence sign '', the disjunction sign ' V ', and the conjunction sig
'A'; secondly the two quantifiers, the universal quantifier 'II' and the existen-
tial quantifier 'E'.
From these variables and constants we may form various expressions; among
these we distinguish certain expressions which we may call sentences, or rather
sentential functions. Expressions of the form 'xRy' (read 'x has the relation
R to y') are called elementary sentences, and we form compound sentences (as
usual) by putting in front of a sentence the negation sign, or a quantifier with a
subscript individual variable-e.g.,

III
2 GrundzUge der theoretischen Logik, Berlin 1938 (second edition), p. 45 ff.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 75

-Or else by combining two simpler sentences by means of one of the signs 'a',
I', V ', ' A
In a well-known fashion we single out from among all sentences a certain class
of sentences which we call axioms, we formulate further certain rules of inference
such as the rules of substitution and detachment and rules concerning the use of
quantifiers, and all sentences obtained from axioms by applying our rules of
inference any number of times we call theorems.
We are now going to subject this theory to a certain modification, or, strictly
speaking, to an extension, introducing certain constants which are specific to
the calculus of relations, altogether eleven in number. These include first four
relation constants, namely the symbol '1' for the universal relation, the symbol
'0, for the null relation, the symbol '1" for the identity relation (between indi-
viduals) and the symbol '0', for the diversity relation. Then we have further
six operation signs; namely two symbols for unary operations (on relations), the
sign of the complement '-' and the sign of the converse '"; and four symbols
for binary operations, the signs of addition '+', multiplication '. ', relative addi-
tion 'j-', and relative multiplication ';'. Finally we have the identity sign '= ',
which denotes identity between relations. We shall refer to the symbols '1',
'0o, 'y', '+', '.' and to the concepts denoted by these symbols as the absolute
(or Boolean) constants and concepts; the symbols '1", 'V', 'tw, 'J', ';' and the
corresponding concepts will be called the relative (or Peircean) constants and
concepts.
From relation variables, relation constants, and operation signs we construct
expressions of a new kind, which are called relation designations. Elementary
relation designations are relation variables and relation constants. Compound
relation designations are formed from simpler ones by putting symbols for unary
operations above them or by joining them by means of symbols for binary
operations. We obtain in this way such expressions as 'R' (read 'the converse
of R'), 'R;S' (read 'the relative product of R and S'), and so on.
The notion of a sentence which appeared in our original theory receives a
certain extension. As elementary sentences we now take expressions of the
form 'xRy' and expressions of the form 'R = Sy, where 'x' and 'y' stand f
individual variables and 'R' and 'S' for any relation designations. The ways in
which compound sentences are constructed from simpler ones remain unchanged.
To the axioms of our original theory we add as new axioms certain sentences
which are intended to explain the meanings of our new constants, and which
could for the most part be regarded as definitions if our original theory were
provided with appropriate rules of definition. Thus we have the following new
axioms:

1. II 11 xly.
X Y/

2. II -I Dcx0y.
x v

3. II xl'x.

4.- llll[(xRy A yl'z)--xRz].

1: Y Z

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 76 ALFRED TARSKI

5. lil [xy' (txly)].

x y

6- 1r ][ [x~y (d-,Ry)]
x V

7. 11 11 Axy yRx]

8.1 H ][x R+ S y -(xRy V xSy)].

9. 1 1[x RSy *+(xRy A xSy)].

10.11 II [x RtSy+- (xRz V zSy)].

X v z

11. X z
II I
12. R=S< -*H1(xRy*--*xSy).
2 y

The rules of inference remain essentially unchanged, with the exception that
the rule of substitution now allows the replacement of relation variables not only
by other relation variables but also by any relation designations.
The theory thus outlined may be called the elementary theory of (binary)
relations. If we confine ourselves to those sentences and theorems which contain
no individual variables, we obtain the fragment of this theory in which we are
here interested, namely the calculus of relations.
Let me give here some examples of theorems of this calculus:

I. (R= S A R = T) - S=T.

II. R= S -*(R+T=S+T A R.T = S.T).

III. R+S = S+R A R.S = S.R.

IV. (R+S).T = (R-T)+(S.T) A (R.S)+T (R+T).(S+T).

V. R+O=R AR.1=R.

VI. R+R = 1 A R.R =0.

VII. - I = O.

VIII. R = R.

IX. R;S = S;R.

X. R;(S;T) = (R;S);T.

XI. R;l' = R.

XII. R;1 = 1 V 1;R= 1.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 77

XIII. (R;S). T = 0 -* (S;T) . R = 0.

XIV. 0' = 1'.

XV. R?S= R;S.

The proofs of these theorems present no difficulties. The simplest way is to
transform the theorems (on the basis of axioms 1-12) into equivalent sentences
which contain no specific constants of the calculus of relations and then to prove
the resulting sentences by the usual methods of the restricted functional calculus.
As the result of such a transformation of theorem XII, for instance, we obtain a
simple theorem of the functional calculus,

( E xRy) V (II ZxRy),

which is more familiar in the following form:

(EHIxRy) - (H ExRy).
(Only the symbol '1" cannot be eliminated in this way; but the only theorems in
which this symbol occurs, namely theorems XI and XIV, follow almost imme-
diately from axioms 3-5.)

The above way of constructing the elementary theory of relations will prob-
ably seem quite natural to any one who is familiar with modern mathematical
logic. If, however, we are interested not in the whole theory of relations but
merely in the calculus of relations, we must admit that this method has certain
defects from the point of view of simplicity and elegance. We obtain the calculus
of relations in a very roundabout way, and in proving theorems of this calculus
we are forced to make use of concepts and statements which are outside the
calculus. It is for this reason that I am going to outline another method of
developing this calculus.
In constructing the calculus of relations according to the second method we
use only one kind of variables, namely relation variables, and we use the same
constants as in the first method, with the exception of the quantifiers. From
these constants and variables we construct relation designations exactly as
before. In the construction of sentences, however, certain modifications are
necessary on account of the absence of individual variables and quantifiers.
As elementary sentences we take only sentences of the form 'R = S', where
'R' and 'S' stand for relation designations; and we form compound sentences
from simpler ones by means of the connectives of the sentential calculus.
Moreover we single out certain sentences which we call axioms. These can
be divided into three groups.
The axioms of the first group characterize, so to speak, the meanings of the
sentential connectives: although all the constants occur in them, it is only the
sentential connectives which occur in them in an essential way. In order to
formulate these axioms, we take any axiom system for the sentential calculus
which contains as primitive terms all the sentential connectives previously

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 78 ALFRED TARSKI

enumerated, and substitute for the variables therein arbitrary sentences of our
calculus (in all possible ways).
The axioms of the second group serve to characterize the meanings of the
absolute constants. We obtain these axioms by taking any set of axioms for
Boolean algebra and replacing class variables by relation variables; e.g., we may
for this purpose use theorems I-VII given above.3 Thus the part of the calculus
of relations which involves only the absolute concepts coincides in its formal
structure with Boolean algebra.
The axioms of the third group are specific to the calculus of relations, and
express fundamental properties of the relative concepts. As these axioms we
may take theorems VIII-XV. The first four of these involve exclusively the
symbols '1", '"', and ';', the next two establish some connections between the
absolute and relative concepts, and the last two may be considered as definitions
of the symbols '0" and 'J'.

Since all the above axioms are theorems of the calculus of relations as con-
structed by our first method, they are undoubtedly true sentences from the point
of view of the intuitive meaning which we ascribe to the symbols occurring in
them.
We may, however, make it plausible in another way that these sentences are
true, namely by means of a geometric representation.4 Let us suppose that our
relation variables denote relations between real numbers, and let us consider a
rectangular coordinate system in the plane. Every relation R may then be
represented as a certain point set in the plane, namely as the set of all points
(x, y) such that x has the relation R to y; and conversely every point set in the
plane represents a certain relation, namely the relation which holds between two
numbers x and y if and only if the point (x, y) belongs to the set. The formula
'R= S' is valid in this geometrical representation if and only if the sets corre-
sponding to R and S are identical. The relations 1, 0, 1', 0', are represented by
certain particular point sets: viz., 1 by the whole plane, 0 by the empty point
set, the identity relation by the straight line whose equation is 'x = y', the
diversity relation by the set of all points not on this straight line. To the
operations on relations there correspond certain operations on point sets. The
absolute operations are represented by the usual set-theoretic operations on point
sets: R+ S by the union of sets, RI. S by the intersection, R by the complement.
In order to obtain the representation for R., we take the point set corresponding
to R and rotate it (in three dimensions) through an angle of 1800 about the
line x = y. Unfortunately it is more difficult to explain the meaning of the
geometrical operations which correspond to relative addition and relative multi-

3 This part of our axiom system is due essentially to E. V. Huntington; see his paper
Sets of independent postulates for the algebra of logic, Transactions of the American Mathe-
matical Society, vol. 5 (1904), p. 292 f. It is easily seen that axioms I-VII are symmetric
with respect to the absolute constants '+' and '.', as well as '1' and '0'. It would be
desirable to have a simple and independent axiom system for the whole calculus of relatio
which would be symmetric with respect to both absolute and relative constants.
4 Cf. Schr6der, op. cit., p. 52 ff.; C. Kuratowski and A. Tarski, Les operations logiques et
les ensembles projectifs, Fundamenta mathematicae, vol. 17 (1931), p. 240 ff.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 79

plication. We have to resort to three-dimensional space and to supplement our

coordinate system with a z-axis perpendicular to the xy-plane. Then, in order
to obtain the representation of R;S (in the xy-plane), we rotate the point set
corresponding to R through a right angle about the x-axis, draw through every
point of the resulting set a straight line parallel to the y-axis, and take the union
of all these straight lines; in this way we obtain the "cylindrical" point set R*.
Similarly we rotate the set corresponding to S through a right angle about the
y-axis, draw the lines parallel to the x-axis, and obtain the "cylindrical" point
set S*. Finally we take the intersection of R* and S*, and project it or-
thogonally upon the xy-plane. The projection thus obtained constitutes the
geometrical representation of R;S. The representation of the relative sum can
easily be obtained from that of the relative product, in view of axiom XV.
The construction becomes much simpler in the case that one of the terms of
the relative sum or the relative product is the universal relation or the null
relation. For example, it is easily seen that the relation R;1 holds between x
and y if and only if there is a z such that xRz (so that it is, so to speak, inde-
pendent of y); therefore, in order to obtain the geometrical representation of
R;1, we consider the set corresponding to R, draw through every point of this
set a straight line parallel to the y-axis, and take the union of all these straight
lines. The same method is applied in the case of 1;R, except that the straight
lines are drawn parallel to the x-axis.
With the aid of this geometric representation, the content of all our axioms
for the calculus of relations is easily made intuitively evident. Thus, e.g., axiom
VIII corresponds to the intuitively obvious geometric fact that, if we take any
point set and rotate it through an angle of 1800 about a given straight line, and
then rotate it again through 1800 about the same straight line, the result is the
original point set.
Let us now consider axiom XII. We have to show that either the set
representing R;1 or the set representing 1;R is the whole plane. Suppose that
the set representing R;1 is not the whole plane. As we have seen, this set is the
union of all straight lines which are parallel to the y-axis and which pass through
a point belonging to the set which represents R. If this union does not coincide
with the whole plane, there must be a line parallel to the y-axis which does not
contain any point of the set corresponding to R, and which therefore consists
exclusively of points of the set corresponding to R. If through every point of
this line we draw a straight line parallel to the x-axis and take the union of all
these parallel lines, we obtain the whole plane. Hence the relation 1;R is repre-
sented by the whole plane.

Continuing our account of the development of the calculus of relations accord-

ing to the second method, we have to describe the way in which theorems of the
calculus of relations are to be derived from our axioms. Here we proceed as in
the case of the first method; i.e., we formulate rules of inference, and we call
theorems those sentences which can be derived from axioms by applying the
rules of inference. But the situation is now simpler in that we are able to
restrict ourselves to two rules of inference-the rule of substitution and the rule
of detachment.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 80 ALFRED TARSKI

In order to illustrate the technique of this domain, we shall outline here the
proofs of several theorems of the calculus of relations. In these proofs we pre-
suppose familiarity with the sentential calculus and with Boolean algebra, and
we shall apply laws of these two theories without explicitly indicating them.

XVI. [(R;S)- T = 0*-. (S;-)-R = 01 A [(R;S). T = O*-* (t;R). = 01.

Proof. In XIII substitute 'I' for 'T'. This gives:

(1) (R;S); = 0 -> (S;Ti) = 0.

Again in XIII substitute 'S', 'p', and 'R' for 'R', 'S', and 'T' respectively, so
obtaining:

(2) (S:T) . R = 0 --. = 0.

Applying XIII for the third time, with 'R', 'S', and 'T' replaced by 'T', 'R',
and 'S' respectively, we obtain:

(3) ( ;R) * 0 --> (R;S) . = O.

Now (1)-(3) imply:

(4) [(R;S) * 4 = O?-* (S;T) R = 0] A [(R;S) = 0 <-> (T;R)* = 01.

On the other hand we have by VIII:

(5) T=T.

From (4) and (5), theorem XVI follows directly.

XVII. R.S = 0 - RP. = O.

Proof. By XI we have:

(6) R;1'= R A 9;1'

Hence obviously:

(7) (?1)* .

If now in XVI we replace 'R', 'S', and 'T' by '1?', '1", and 'C?' respectively, we
obtain, by (7):

(8) (1';A)* = 0.
By VIII we have:

(9) R-S = 0 -R". = O.

By virtue of a law of Boolean algebra, (8) and
_ _

(10) R.S = 0 -+ (1';)R = 0.

Applying XVI again, with 'R', 'S', and 'T' replaced by 'Ty, '1"', and S respec-
tively, we obtain:

(11) (R;1') O 0-* (1;9).RW = O.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 81

From (10) and (11) follows:

(12) RAM = 0 --+), = 0.

From this together with (6) we obtain XVII immediately.

XVIII. R = S -R=, R

Proof. We have the following formulae (where (13) is a well-known law of

Boolean algebra, (14) follows from XVII, and (15) is a particular case of (13)):

(13) R = S- (RAS 0 /\ SI R = 0 ).
(14) (R9=0A S.R=O)-(R.?=0 A ~R=0).
(15) R = B (Ray 0 A BAR = 0).

From these XVIII follows directly.

XIX. R+S = R+K.

Proof. For simplicity we replace 'R+~' by 'T'. Since obviously
(16) R.T=O A A T=0,

we infer by XVII that

(17) R. =OA A i=0.

Hence by virtue of VIII,

(18) Rg= OA ST= 0,

and consequently,

(19) (R + S). = 0.
If now in XVII we replace 'R' by 'R+S' and 'T' by 'p', we obtain, by (19),

(20) R+S- 0=

and hence, by VIII,

(21) R+S- T= 0, i.e., R+S R+= 0.

Since, on the other hand,

(22) R.R+S=O A S.R+S=O,

we obtain, again using XVII,

(23) R . R+S = 0 A .R+S = 0,

and hence,

(24) (R+2) * R+S = 0.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 82 ALFRED TARSKI

From (21) and (24), theorem XIX follows (cf. formula (13) in the proof of
XVIII).

XX. =0 A =1.

Proof. Applying XVII twice, the first time with 'R' replaced by 'O' and 'S'
by '6', and the second time with 'R' replaced by '1' and 'S' by '1', we obtai

(25) .=O A 1. = O.

Hence by VIII:

(26) 6.0= A 1.1=0.

Hence further:

(27) 6.1 = O 1 =O.

And from this, XX follows at once.

XXI. S.T=0-+(R;S) *R;T=O.

Proof. We have obviously:

(28) (R;T) * = O.

In XVI replace 'S' by 'T', and 'T' by 'R;T'. By (28) we obtain:

(29) (R.T - R) *X=O.

By XVII we have:

(30) SoT = O - =O.

Formulae (29), (30) imply:

(31) SIT = 0-i (R;T;R) * 0 .

Applying XVI again, with 'R;T' put in place of 'T', we obtain:

(32) (R;S)R;T=O(R;T;R) 0.

Then XXI follows immediately from (31) and (32).

XXII. S = T -R;S = R;T.

Proof. XXII can be derived from XXI in exactly the same way as XVIII
from XVII.

XXIII. R;(S+T) = (R;S)+(R;T).

Proof; For brevity we replace '(R;S)+(R;T)' by 'U'. We have obviously:

(33) (R;S)*U = 0 A (R;T).U = O.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 83

Hence by XVI we obtain:

(34) (U;R)-4 = 0 A (U;R)T = O.

Consequently:

(35) (0U;R) _.
Since, by XIX,

(36) S+T=

we infer from (35) that:

(37) (U;R) * S+ T = 0.

Now in XVI replace 'S' by 'S+T', and 'T' by 'U'. Using (37), we obtain:

(38) [R;(S+T)].U = 0, i.e., [R;(S+T)]- (R;S)+(R;T) = O.

On the other hand we have:

(39) S-S+T=0A T-S+T =O.

Hence by XXI:

(40) (R;S) * R;(S+T) = 0 A (R;T) * R;(S+T) = O.

Hence further:

(41) [(R;S)+(R;T)] R;(S+T) = O.

From (38) and (41), XXIII follows directly (cf. formula (13) in the proof of
XVIII).

XXIV. R;O = 0.

Proof. By XX we have:

(42) (l;R).6 =0.

Hence, by means of XVI (with 'S' replaced by '0' and 'T' by '1'):

(43) (R;0).1 = 0.
Then XXIV is an immediate consequence of (43).

Proofs of the four following theorems are entirely analogous to those of

XXI-XXIV:

XXV. R.S=0-(R;T) *S;T=O.

XXVI. R = S - R;T = S;T.

XXVII. (R+S);T = (R;T)+(S;T).

XXVIII. O;R = 0.

XXIX. 1' = 1'.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 84 ALFRED TARSKI

Proof. By IX and XI we have:

(44) R;1'= 1';R

and

(45) Pia't= A.
Applying XVIII to (45), we get:

(46) A;i' = A.
Hence by (44):

(47) 1';R= R.

With the aid of VIII and XXII we obtain from (47):

(48) 1';R= R.

Substituting here '1" for 'R', we get:

(49) = 1'.

On the other hand we have, by XI:

(50) = 1'.

And XXIX follows directly from (49) and (50)..

XXX. l';R = R.

Proof. Applying XXVI to XXIX, we obtain:

(51) 1';R = 1';R.

This formula together with the formula (48) (see the proof of XXIX) yields
XXX directly.

XXXI. (1;S) * T = 0 -+ (1;T) = S 0.

Proof. By XVI we have:

(52) (1;S)- T = 0 (0;1) . = 0.

By applying XXII to XX we obtain:

(53) ;1= T; L
On the other hand, IX gives:

(54) 1;T =
Formulae (52)-(54) imply:

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 85

In what follows, '(1;T). S' will be replaced by 'U'. We have obviously:

(56) Us7 1;T = 0 A U.S= 0.

Hence, applying XVII twice, we obtain:

(57) U . 1;T =0 A U[.2 = 0.

In consequence of laws of Boolean algebra, (57) leads to:

(58) t 1;T.= 0.

Hence:

(59) 1;T . 0 aE= 0.

By XVIII we have:

(60) E O

Hence in view of VIII and XX:

(61) a = 0 -+U = 0, i.e., t = 0 -+(1;T).S = O.

Formulae (55), (59), (61) together yield XXXI.

XXXII. (R 1 = 1) *-+ (1;R);l = 1.

Proof. Since

(62) R = 1 X = 0,
we have, by XXII,

(63) R 11;R= 1;0,

and hence by XXIV,

(64) R= 1 -1;R =0.

From (64) we obtain, using XXVI,

(65) R = 1 -- (1;);l = 0;1,

and hence by XXVIII,

(66) R= 1 +(1;R);l =0.

From (66) results obviously:

(67) (1;R);l = 1-+ (a. R = 1).

On the other hand we obtain from XII, replacing 'R' by '1;R":

(68) (1;R);l = 1 V 1; 1;R = 1.

From XXXI, substituting 'R' for 'S' and '1;R' for 'T', we infer:

(69) (1;1;R).R=0.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 86 ALFRED TARSKI

Hence:

(70) 1 =.
And hence:

(71) 1;1;R=1-OR=1.

Then (68) and (71) together imply:

(72) (a R = 1) (1;R);1 = 1.
And XXXII follows immediately from (67) and (72).

The theorem just proved plays a very important role in the calculus of rela-
tions, since it allows us to prove the following general metalogical theorem:

Every sentence of the calculus of relations can be transformed into an equivalent

sentence of the form 'R= S', and even of the form 'T= 1'.5

In fact, we may first, on the basis of a well-known theorem of Boolean algebra,

transform every equation
R =S

into an equation of the form

T= 1,

namely into

R.S + R.S = 1.

Now, on the basis of theorem XXXII, we may transform the negation of an

equation of the form 'T=1', i.e.,
AT= 1,

into an equation of the form 'T= 1', namely

1;T;1 = 1.

Further we are able to transform a conjunction of two such equations, i.e.,

T = 1 A U = 1,

into one equation, namely

T.U = 1.

Since it is known from the sentential calculus that it is possible to eliminate

from every sentence all sentential connectives except the signs of negation and
conjunction, it follows from the above transformations that our metalogical
theorem is valid.

This metalogical theorem suggests still another way of constructing the cal-
culus of relations. For it shows that we may confine ourselves, in developing

6 See Schroder, op. cit., p. 153.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 87

this calculus, to sentences which have the form of equations (or which even
have the form 'T=1'), thus dispensing with the concepts and theorems of the
sentential calculus. For this purpose we should have to put all our axioms into
the form of equations, and to give rules which would permit us to derive new
equations from given ones. Though this plan has not been worked out in detail,
the realization of it presents no essential difficulty.

In the further development of the calculus of relations we may introduce new

concepts definable with the help of the fundamental concepts of the calculus.
We may, for instance, distinguish certain especially important categories of rela-
tions, such as symmetric relations, transitive relations, ordering relations, one-
many relations or functions, and one-one relations or biunique functions. In
this connection the following point deserves special attention. It may be
noticed that many laws of the calculus of relations, and in particular the axioms
VIII-XI adopted under our second method, resemble theorems of the theory of
groups, relative multiplication playing the r6le of group-theoretic composition,
and the converse of a relation corresponding to the group-theoretic inverse.
Let us now consider briefly the relations satisfying the condition:

R;R = 1' A R;R = 1'.

This condition expresses in ordinary mathematical terminology that the rela-

tion R maps the class of individuals on itself in a one-to-one manner. If we
confine ourselves to relations satisfying this condition, we can easily prove that
they satisfy all the axioms of the theory of groups. Thus it turns out that the
calculus of relations includes the elementary theory of groups and is, so to
speak, a union of Boolean algebra and group theory. This fact accounts for the
deductive power and mathematical richness of the calculus.

I should like now to discuss some metalogical problems regarding the calculus
of relations.
The first problem concerns the relation between our two methods of con-
structing the calculus. It is obvious that every theorem which can be proved
by the second method can also be proved by the first method (since, as men-
tioned before, the axioms adopted under the second method can be proved as
theorems under the first method, and all the rules of inference used in the second
method were also assumed in the first method). It is, however, by no means
obvious that the converse is also true, and that consequently our two methods
are entirely equivalent. Since it follows from a result of K. Godelr that every
sentence which is true in every domain of individuals is provable by our first
method, the problem can also be put in the following way: Is it the case that
every sentence of the calculus of relations which is true in every domain of
individuals is derivable from the axioms adopted under the second method?
This problem presents some difficulties and still remains open. I can only say
that I am practically sure that I can prove with the help of the second method

6 Die Vollstandigkeit der Axiome des logischen Funktionenkalkils, Monatshefte fUr Mathe-
matik und Physik, vol. 37 (1930), pp. 349-360.

This content downloaded from

1:ffff:ffff:ffff:ffff:ffff on Thu, 01 Jan 1976 12:34:56 UTC
All use subject to https://about.jstor.org/terms
 88 ALFRED TARSKI

all of the hundreds of t

Relative.
The next problem is the so-called representation problem. Is every model
of the axiom system of the calculus of relations isomorphic with a class of binary
relations which contains the relations 1, 0, 1', O' and is closed under all the
operations considered in this calculus? As is known, the analogous problem
for Boolean algebra was raised, and solved in the affirmative, by M. H. Stone.7
For the calculus of relations the problem remains open; a particular case of it-
for an atomistic system of the theory of relations-was recently solved by J. C. C.
McKinsey.8 The two problems-that of the equivalence of our two construction
methods, and the representation problem (in its application to the axiom system
adopted under the second method)-are related to each other: from an affirma-
tive solution of the second problem we could obtain an affirmative solution of
the first.
In discussing the remaining metalogical problems we shall have in mind our
first method of constructing the calculus of relations.
The first of these problems is known as the decision problem. It can be
formulated in the following way: Is there a method which would enable us in
every particular case to decide whether a given sentence expressed in the terms
of the calculus of relations is a theorem of this calculus? We know from a
result of A. Church9 that no such method exists with regard to what we called
the elementary theory of relations-i.e., with regard to sentences which contain
not only relation variables but also individual variables. With the aid of this
result it can be shown that the solution of the decision problem is likewise nega-
tive for the calculus of relations proper.10
The next problem concerns the connection between the elementary theory of
relations-or, what is practically the same, the restricted functional calculus-
and the calculus of relations. Since the calculus of relations is only a proper
part of the theory of relations, the problem arises whether every sentence formu-
lated in the elementary theory of relations and concerned essentially only with
the properties of relations (i.e., containing only relation variables as free vari-
ables) can be transformed into an equivalent sentence of the calculus of relations.
In a less exact form this problem can be put as follows: Is it true that every
property of relations, relation between relations, operation on relations, etc.
which can be defined in the restricted functional calculus can be expressed also
in the calculus of relations? It was shown by A. Korselt that the answer. to this
question is negative."1 His proof, however, depends essentially on admitting

The theory of representations for Boolean algebras, Transactions of the American Mathe-
matical Society, vol. 40 (1936), pp. 37-111; see in particular p. 106.
8 Postulates for the calculus of binary relations, this JOURNAL, Vol. 5 (1940), pp. 85-97;
see in particular p. 94.
9 A note on the Entscheidungsproblem, this JOURNAL, Vol. 1 (1936), pp. 40-41 (and Corre
tion, ibid., pp. 101-102).
0 The proof will be given later in a separate paper.
11 Korselt's result was published in the paper of L. LMwenheim, Ober Moglichkeiten im
RelativkalkWl, Mathematische Annalen, vol. 76 (1915), pp. 447-470.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms
 ON THE CALCULUS OF RELATIONS 89

finite domains of individuals with various numbers of elements. I have shown

that the result remains valid if we confine ourselves to infinite domains of indi-
viduals. It follows from my reasoning that even the properties of relations
expressed by such simple formulae of the restricted functional calculus as

11 II >2 (xRu A yRu A zRu)

X y 2 tS

or

, Z(xRy A xRz A xRu A yRz A yRu A zRu)

X V 2 U

cannot be expressed in the terms of the calculus of relations; i.e., no sentence of

the calculus of relations is satisfied by exactly the same binary relations (between
elements of an infinite set) which satisfy either one of the above formulae.
Moreover, I have succeeded in considerably extending this result. For I have
shown that the answer remains negative even if we enrich the calculus of rela-
tions by the addition of any finite number of new constants denoting fixed rela-
tions, properties of relations, operations on relations, and so on, provided that.
all concepts introduced in this way are invariant under any one-to-one mapping
of the class of individuals on itself.10 (It follows from an earlier result by A.
Lindenbaum and myself'2 that this invariance property belongs to all concepts
definable within the restricted functional calculus, or even within much more
comprehensive logical systems, such as that of Principia mathematical
Our last metalogical problem is closely related to the preceding one. Since
there are sentences of the elementary theory of relations which cannot be trans-
formed into equivalent sentences of the calculus of relations, we may look for a
criterion which would enable us to decide in every particular case whether such a
transformation is possible. We are here confronted with a new decision problem.
This problem is so far unsolved, but it seems plausible that its solution is
negative.

The aim of this paper has been, not so much to present new results, as to
awaken interest in a certain neglected logical theory, and to formulate some new
problems concerning this theory. I do believe that the calculus of relations de-
serves much more attention than it receives. For, aside from the fact that the
concepts occurring in this calculus possess an objective importance and are in
these times almost indispensable in any scientific discussion, the calculus of rela-
tions has an intrinsic charm and beauty which makes it a source of intellectual
delight to all who become acquainted with it."3
HARVARD UNIVERSITY

12 Uber die Beschrdnktheit der Ausdrucksmittel deduktiver Theor

mathematischen Kolloquiums, no. 7 (1936), pp. 15-22. (There are several misprints in that
paper. In particular, read 'metamathematisch' and 'Metamathematik' instead of 'mathe-
matisch' and 'Mathematik.')
18 I wish to take this opportunity to express my gratitude to Dr. J. C. C. McKinsey for
his assistance in preparing this paper.

This content downloaded from

157.88.129.84 on Tue, 07 Mar 2023 15:48:52 UTC
All use subject to https://about.jstor.org/terms