Published online by Cambridge University Press: 12 March 2014
The object of this note is to show that there is no finite characteristic matrix for any one of Lewis and Langford's systems.
Theorem I. There is no finite characteristic matrix for any one of the systems S1–S5.
Proof. Let M be a matrix with less than n elements for which all the provable formulas in S1, or S2, or S3, or S4, or S5, are satisfied. Let Fn represent the formula
where ∑ stands for a ∨-chain, and the pi, are variables in any one of the calculi. Using M, there is always at least one summand in Fn where pi and pk have the same value. Therefore, Fn can always be written in the form (a = a)∨ B, and thus will give, for any B, a “designated” value, since the formula (p = p) ∨ q is provable in any one of the systems S1–S5.
Give to any one of the systems S1–S5, the following matrix, due to Henle:
1. Elements: all possible classes formed from the integers 1, 2, 3, …, n.
2. “Designated” element: the class {1, 2, 3, …,n}.
3. Boole-Schröder algebra on the elements.
4.
◊N = N (N the null class)
◊A = {1, 2, …, n} (A any non-null class).5
1 By a finite characteristic matrix for a propositional calculus L is meant a matrix of a finite number of elements (truth values) which satisfies those, and only those, formulas which are provable in L.
2 For the definitions of these systems, see Lewis, and Langford, , Symbolic Logic, pp. 500–501Google Scholar.
3 The method used here originated with K. Gödel. See his Zum intuitionislischen Aussagenkalkül, Ergebnisse eines mathematischen Kolloquiums, no. 4 (1933), p. 40Google Scholar. Its use in the present connection was suggested by Dr. J. C. C. McKinsey.
4 See Lewis and Langford, loc. cit., p. 492.
5 If A and B are any two classes, then “A = B” reduces to the value {1, 2, 3, …, n} when A and B are the same class, and to the value N otherwise. Also, “N ∨ N” reduces to the value N. These two results will be used in the paper.