Strongly Finite Logics: Finite Axiomatizability and The Problem of Supremium

Bulletin of the Section of Logic
Volume 8/2 (1979), pp. 99108

reedition 2010 [original edition, pp. 99111]
Piotr Wojtylak
STRONGLY FINITE LOGICS: FINITE

AXIOMATIZABILITY AND THE PROBLEM OF
SUPREMIUM
This is an extended version of a lecture read at the meeting organized
by the L
odz section of the Philosophical Society on January 20, 1979. Extended fragments of this paper will appear in Reports on Mathematical
Logic.
This paper, which in its subject matter goes back to works on strongly
finite logics (e.g. [8], [9]), is concerned with the following problems:
(1) Let Cn1 , Cn2 be two strongly finite logics over the same propositional
language. Is the supremum of Cn1 and Cn2 (noted as Cn1 Cn2 )
also a strongly finite operation?
(2) Is any finite matrix (or more precisely, the content of any finite matrix) axiomatizable by a finite set of standard rules?
The first question can be found in [9] (and also in [11]). The second conjecture was formulated by Wolfgang Rautenberg, but investigations into this
problem had been carried out earlier in works of many logicians (e.g. the
known theorem of Mordchaj Wajsberg [7], see also [5]). Moreover, Stephen
Bloom [1] posed a conjecture stronger than (2) that: the consequence determined by a finite matrix (a strongly finite consequence, see [9]) is finitely
based, i.e. it is the consequence generated by a finite set of standard rules.
This hypothesis was, however, disproved by Andrzej Wro
nski [10] (and also
by Alasdair Urquhart [6]).
In the present paper it is shown that neither (1) nor (2) holds true.
The negative answer to (2) can be viewed as a generalization of the result
given by Andrzej Wro
nski [10] (or by [6]).
100
Piotr Wojtylak
Let S 0 = (S0 , ) be the algebra of the propositional language determined by the set V = {pi ; i = 0, 1, 2, . . .} of propositional variables and
by a two-argument connective . By he we denote the extension of the
mapping e : V S0 to an endomorphism of S 0 (he Hom(S 0 , S 0 )). The
symbol V () stands for the Sset of all variables occurring in the formula
S0 . Moreover, V (X) = {V () : X} for every set X S0 . The
length of a formula is defined as follows:
Definition 1.1.
(i) l(pi ) = 1 for every pi V
(ii) l( ) = 1 + l() + l() for every , S0
(iii) l(X) = max{l() : X} for every finite set X S0
Let us take into consideration the following three matrices: K =
({0, 1}, {1}, f + ) (the matrix of the classical disjunction), L = ({0, a, 1},
{a, 1}, f = ) and M = ({0, a, 1}, {a, 1}, f ), where
f+
0
1
0
0
1
1
1
1
f=
0
a
1
0
1
0
0
a
0
0
1
1
0
1
1
f
0
a
1
0
0
0
0
a
0
0
0
1
0
0
a
The structural consequences determined by these matrices (or the so-called

matrix consequences, see [3]) will be designated by CK , CL , CM . We can
easily make the following observation:
(a) (CK CM )( ) for every S0 , where (CK CM )(X) =
CK (X) CM (X) for X S0
(b) (CL CM )(, ) = CL (, ) CM (, ) for every
, S0 .
(c) CM () = S0 if S0 and l() > 3.
Let us take X0 = {pi pj ; i 6= j} and note that:
(d) CM (X0 ) 6= S0
(e) V CK (X0 ) = 0 it suffices to consider, for every pi V , a homomorphism hi Hom(S 0 , alg(M )) such that hi (pj ) = 1 iff i 6= j.
(f) pi pi 6 CK (X0 ) for every pi V by (a) and (e).
Strongly Finite logics: Finite Axiomatizability and the Problem of ...
101
(g) V CL (X0 ) = 0 let us consider a homomorphism h Hom(S 0 ,

alg(L)) such that h(pi ) = 0 for every pi V . Then h(X) {1} and
h(V ) {0}.
(h) pi pi 6 CL (X0 ) for every pi V if hi Hom(S 0 , alg(L)) is a
homomorphism such that hi (pj ) = 1 for j 6= i and hi (pi ) = a, then
hi (pi pi ) = f = (a, a) = 0 and hi (pi pj ) = f = (a, 1) = 1 for every
j 6= i.
It immediately follows from (c) and (d) that: if CK CM (X0 ), then
3 < l(). Hence, by (e) and (f), we get
(i) (CK CM )(X0 ) = CK (X0 ) CM (X0 ) = X0
Similarly, by (c), (d), (g) and (h), we obtain
(j) (CL CM )(X0 ) = CL (X0 ) CM (X0 ) = X0
We state without proofs the following easy lemmas:
Lemma 1.2. Let Let Cn1 and Cn2 be consequence operations on S0 and
let Cn1 Cn2 be the supremum (the least upper bound in the lattice of
all consequences over S0 , see [8]) of Cn1 and Cn2 . Then, for every set
X S0 ,
\
(Cn1 Cn2 )(X) = {Y ; Y = Cn1 (Y ) = Cn2 (Y ) = Y X}.
Lemma 1.3. Let K be a class of finite matrices for S 0 and let CK be
the
T structural consequence operation determined by K (that is CK (X) =
{CN (X); N K, see [8]). Then
CK (X) k e:V {p1 ,...,pk } he () CK (he (X))
for every S0 and X S0 .
The above lemma is closely similar to the criterion of strong finiteness
given by Ryszard W
ojcicki [8].
Theorem 1.4. The consequence Cn = (CK CM ) (CL CM ) is not
strongly finite and, what is more, Cn 6= CK for any class K of finite matrices.
Proof. Suppose that e : V {p1 , . . . , pk }. Since the set {p1 , . . . , pk }
is finite, there exist pi , pj V such that i 6= j and e(pi ) = e(pj ). Thus
102
Piotr Wojtylak
he (pi pi = e(pi )e(pi ) = e(pi )e(pj ) = he (pi pj ) he (X0 ) Cn(he (X0 ))

and hence, by (a), e(pi ) Cn(he (X0 )) for some pi V . On the other hand
e(pi ) e(pk ) = he (pi pk ) he (X0 ) Cn(he (X0 )) for every pk 6= pi . So it
follows from (b) that e(pk ) Cn(he (X0 )) for every pk V . Consequently,
he (V ) Cn(he (X 0 )) for every e : V {p1 , . . . , pk }.
Let us assume, to the contrary, that Cn = CK for some class K of finite
matrices. Then, by Lemma 1.3, V Cn(X0 ). But on the other hand,
by (i), (j) and Lemma 1.2, Cn(X0 ) = X0 . Hence V X0 , which is a
contradiction.
According to the definition of a strongly finite consequence (see [8]) the
operations CK CM , CL CM are strongly finite. Therefore conjecture
(1) has been disproved.
Instead of CK CM , CL CM one can take CKM , CLM and by the
similar argument it can be shown that CKM CLM is not a strongly
finite consequence. Note that K M and L M are elementary matrices.
It can also be proved that CKM CLM is uniform, that is, there exists
an elementary matrix which is strongly adequate for CKM CLM (this
is the answer to the question posed by Wieslaw Dziobiak).
Obviously the set Cn(0) is empty, but when we extend the language
S 0 (and also the matrices K, L, M ) by adding some new connectives, then
we can easily obtain two strongly finite consequences Cn1 and Cn2 such
that Cn1 Cn2 is not strongly finite and Cn1 Cn2 (0) is not empty.
Theorem 1.4 states that the set of strongly finite logics does not form
a sublattice of the lattice of all logics on S0 . From this statement, by an
easy verification, the following theorem may also be deduced.
Theorem 1.5. The set of all strongly finite logics does not form a lattice.
It was proved in Theorem 1.4 that the supremum (CK CM ) (CL
CM ) of two strongly finite logics does not have the strongly finite model
property (the notion introduced by Ryszard Wojcicki). In particular, this
means that strengthenings of a given strongly finite consequence need not
be characterized by finite matrices (need not have the strongly finite model
property). This result was first obtained by Wieslaw Dziobiak [2].
103
.2
Let us proceed to the second conjecture. Further we will consider formulae
of the form:
() 1 (2 . . . (n1 n )) where 1 , 2 , . . . , n V .
The following definition is accepted:
Definition 2.1. The set F (), for every S0 , is defined as follows:
(i) F ()
(ii) if F () and if V , then F ()
(iii) A formula belongs to F () if it can be shown to be in F () on the
basis (i) and (ii).
Moreover, let us define an operation p : S0 V :
(i) p() = for every = V
(ii) p( ) = p() for every , S0
For every S0 and for every V , the number of occurrences of the
variable in the formula will be denoted by ind(, ), that is ind(pi , pj ) =
0 if i 6= j, ind(pi , pi ) S
= 1 and ind( , ) = ind(, ) + ind(, ). It is
easy to see that F = {F (); V } is the set of all formulae of the form
() and that p(), for F , is the initial variable of (i.e. p() = n in
()). We quote without proofs:
Lemma 2.2. For every formulae , beta S0 and every mapping e : V
S0
P
(i) l() = 2(
ind(, )) 1
V
(ii) F () l() 6 l() V () V (),

(iii) F () F () 6= 0 F () F () F () F (),
(iv) If he () F and if l(he ()) > l(), then
(a) ind(, p()) = 1
(b) e(p()) F F
(c) e(V ()\{p()}) V .
(v) If F e(P ()) F () and if the above conditions (a), (c) are
fulfilled, then he () F ().
We will consider the matrix N = ({0, 1, 2, 3, 4}, {1, 2, 3, 4}, f ) where
104
Piotr Wojtylak
f
0
1
2
3
4
0
4
0
4
4
4
1
4
2
4
0
4
2
4
2
4
0
4
3
4
0
4
4
4
4
4
4
4
4
4
The designated values in N are {1, 2, 3, 4} and hence the set of formulae
valid in N can be defined as:
E(N ) = CN (0) = { S0 ; h() 6= 0 for every h Hom(S 0 , alg(N ))}
It will be proved that E(N ) is not finitely axiomatizable by means of standard rules. Let us recall that a rule r 2S0 S0 is said to be standard
(polynomial c.f. [3]) if there exist a finite set X S0 and a formula S0
such that r = rI , where
rX = {(he (X), he ()); e : V S0 }.
Observe that rules of the form r0 , where 0 is the empty set, are also standard. Such rules are called axiomatic. Given a set R of rules we shall write
Cn(R, X) (or CR (X)) to denote the least superset of X closed under R.
We say that the matrix N is axiomatizable by a set R of rules if and only
if R(N ) = Cn(R, 0).
Lemma 2.3. For every formula S0 : 6 E(N ) F ind(, ) =
1 for some V .
Theorem 2.4.
standard rules.
The matrix N cannot be axiomatized by a finite set of
Proof. Suppose to the contrary that E(N ) = Cn(R, 0) for some finite
set R of standard rules. Thus the members of R are unfailing in the matrix
N that is:
(a) r R (X, ) r X E(N ) E(N ).
Since the set R is finite, there exists a natural number k such that
(b) k = max{l(X, ); rX R}.
Let us take 0 = p0 and n+1 = pn+1 n for every natural number n. It
is obvious that:
105
(c) V (n ) = {p0 , p1 , . . . , pn },
l(n ) = 2n + 1,
n F (p0 ) F .
Moreover, we shall prove that:
(d) F (n ) E(N ) l() > 4n + 3,
F (n ) E(N ) 6= 0.
If F (n )E(N ), then it follows from Lemma 2.2 (ii) that {p0 , . . . , pn }
V () and therefore, according to Lemma 2.3, ind(, pi ) > 2 for i =
0, . . . , n. Hence, by 2.2 (i), l() > 4n + 3. To show E(N ) F (n ) 6= 0 it
suffices to consider the formula = n (p0 /n ). From Lemma 2.2 (v) it
follows that this formula is an element of F (n ) and according to 2.3, 2.1:
p0 F (n ) E(N ).
Let us assume that the sequence:
(e) 1 , 2 , . . . , m
is a proof of a formula E(N ) F (k ) (where the natural number k is
defined in (a)) on the ground of the rules R, i.e. m = and for every
i 6 m there exist a rule r R and a set Y {1 , . . . , i1 } such that
(X, i ) r. Suppose m = 1. Then = he () and r0 R for some S0 .
But l() < k < 4k + 3 < l() by (b) and (d). Hence, it follows from
Lemma 2.2 (iv) that F and ind(, p()) = 1. Consequently 6 E(N )
by Lemma 2.3, which contradicts assumption (a). Assume that no formula
in F (k ) E(N ) has a proof on the ground of R with less than m elements
(where m > 2). Since m = , there exists X S0 , S0 and mapping
e : V S0 such that he (X) {1 , . . . , m1 } E(N ), he () = , and
rX R. Moreover, by (b) and (d), l() < l(). Thus, according to Lemma
2.2 (iv):
(f) F ,
ind(, p()) = 1,
e(V ()\{p()}) V
On the other hand e(p()) F (p()) by 2.1 and hence he () =
F (e(p())) see Lemma 2.2 (v). Since F (k ), it follows from 2.2 (ii),
(iii) that
(g) F (e(p())) F (k )
Let us consider a substitution f : V S0 such that:
106
Piotr Wojtylak
(p0 p0 ) p0
p1 p0
f () =
p0
if
if
if
6 V ()
= p()
V ()\{p()}.
It follows from 2.2 (v) and 2.3 that hf () 6 E(N ). Since rX R, there
exists X such that hf () 6 E(N ). It can be proved using 2.3, (f), (e)
that
(h) V () V (),
F and p() = p(),
ind(, p()) = 1.
The simple conclusion based on (h), (f) and Lemma 2.2 (iv) is that he ()
F (e(p())). Hence, by (g), he () F (k ) which contradicts the inductive hypothesis because he () has a proof with less than m elements. It has
been proved, by induction on the number of elements in a proof of a formula F (k )E(N ), that Cn(R, 0)F (k )E(N ) = 0. Consequently,
by (d), Cn(R, 0) 6= E(N ), which completes the proof of our theorem.
3.
Finally we shall deal with the following problem: under what condition on
strongly finite logics do the questions considered have positive answers? In
the sequel some solution of this problem is presented.
Let S = (S, , +, F1 , . . . , Fn ) be a propositional language based on the
set V = {p0 , p1 , . . . , } of propositional variables. We will assume that + and
are two-argument connectives. A consequence operation Cn on S is said
to be a disjunctive one if and only if Cn(X, ) Cn(X, ) = Cn(X, + )
for every X S and every , S (Cn D, see [5]). We say that Cn
is a consequence with the identity connective (Cn I, see [4]) when the
binary relation on S defined as follows:
iff Cn(0)
is a congruence in S consistent with Cn, that is
Cn() = Cn()
If Cn is a disjunctive operation with identity, then we will write Cn DI.
Lemma 3.1 Cn1 , Cn2 DI Cn1 Cn2 DI
107
Lemma 3.2. If Cn DI is a strongly finite consequence, then {Cn1

Struct; Cn 6 Cn1 D} is a finite subset of the set of strongly finite
consequences.
Theorem 3.3. If Cn1 , Cn2 DI are strongly finite consequences, then
Cn1 Cn2 is also a strongly finite operation.
Proof. Since Cn1 , Cn2 DI, it follows from 3.1 that Cn1 Cn2 DI
and, which is obvious, Cn1 6 Cn1 Cn2 . Thus Cn1 Cn2 is a strongly
finite consequence by Lemma 3.2.
It can also be proved that:
Theorem 3.4. If Cn DI is a strongly finite consequence, then Cn is
finitely based, that is, Cn = CR for a finite R of standard rules.
It conclusion it is worth while adding, as was mentioned after the lecture, that Jan Zygmunt had proved that: every disjunctive consequence
determined by an elementary finite matrix is finitely based.
References
[1] S. L. Bloom, A representation theorem for the lattice of standard
consequence operations, Studia Logica 34 (1975), pp. 235237.
[2] W. Dziobiak, On strongly finite consequence operations,
preprint, Institute of Mathematics, Nicholas Copernicus University, Toru
n
1979, No. 1.
[3] J. Los and R. Suszko, Remarks on sentential logics, Indagationes
Mathematicae 20 (1958), pp. 177183.
[4] R. Suszko, Identity connective and modality, Studia Logica 27
(1971), pp. 739.
[5] A. Tarski, Logics, Semantics, Metamathematics, Oxford 1956.
[6] A. Urquhart, A finite matrix whose consequence relation is not
finitely axiomatizable, Reports on Mathematical Logic 9 (1977), pp. 71
73.
[7] M. Wajsberg, Beitrage zum Metaausagenkalkul I., Monatshefte
f
ur Mathematic und Physik 42 (1935), pp. 221242.
108
Piotr Wojtylak
[8] R. W
ojcicki, Matrix approach in metodology of sentential calculi,
Studia Logica 33 (1973), pp. 739.
[9] R. W
ojcicki, Strongly finite sentential calculi, [in:] Selected papers on Lukasiewicz sentential calculi, edited by Wojcicki R. and
Malinowski G., Warszawa-Wroclaw 1977.
[10] A. Wro
nski, On finitely based consequence operations, Studia
Logica 35 (1976), pp. 453458.
[11] J. Zygmunt, Research project on strongly finite sentential calculi,
Bulletin of the Section of Logic, Polish Academy of Science, Institute
of Philosophy and Sociology, 6 (1977), pp. 8790.
Mathematical Institute
Silesian University
Katowice

Strongly Finite Logics: Finite Axiomatizability and The Problem of Supremium

Uploaded by

Copyright:

Available Formats

Strongly Finite Logics: Finite Axiomatizability and The Problem of Supremium

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Strongly Finite Logics: Finite Axiomatizability and The Problem of Supremium

Uploaded by

Copyright:

Available Formats

Bulletin of the Section of Logic

Volume 8/2 (1979), pp. 99108

STRONGLY FINITE LOGICS: FINITE

The structural consequences determined by these matrices (or the so-called

Strongly Finite logics: Finite Axiomatizability and the Problem of ...

(g) V CL (X0 ) = 0 let us consider a homomorphism h Hom(S 0 ,

he (pi pi = e(pi )e(pi ) = e(pi )e(pj ) = he (pi pj ) he (X0 ) Cn(he (X0 ))

Strongly Finite logics: Finite Axiomatizability and the Problem of ...

(ii) F () l() 6 l() V () V (),

The matrix N cannot be axiomatized by a finite set of

Strongly Finite logics: Finite Axiomatizability and the Problem of ...

Strongly Finite logics: Finite Axiomatizability and the Problem of ...

Lemma 3.2. If Cn DI is a strongly finite consequence, then {Cn1

You might also like