When was Compactness Theorem for propositional logic first proven?

189 Views Asked by At

Compactness for first-order predicate logic was first proven as a corollary of (Gödel 1930). Does anyone know a reference for the first proof of the compactness of propositional logic?

This (https://math.stackexchange.com/a/2681301/387521) answer suggests that it was never given a formal proof prior to 1930. If so, what can we make of earlier results (for example, Lowenheim's 1915 proof of the Lowenheim-Skolem theorem) which contain gaps fillable by an appeal to propositional compactness? Is there any evidence that propositional compactness or an equivalent result would have been considered self-evident at the time?

2

There are 2 best solutions below

3
On

See John Dawson, The Compactness of First-order Logic From Gödel to Lindström (HPL,1993), page 18:

After 1934, [...] the only person who seems to have recognized the importance of compactness was the Russian A. I. Maltsev. Beginning in 1936, he published 'a seminal run' of papers in what would now be called model-theoretic algebra, papers in which he 'obtained applications [of logic] to group theory of greater technical virtuosity than the possibly more basic applications to algebra later on found [...] by Henkin and Abraham Robinson' (Sabbagh 1991). Three of those papers (1936,1940 and 1941) are of interest here.

In his first published work, written in German, Maltsev 1936 [Maltsev, A.I. 1936 'Untersuchungen aus dem Gebiete der mathematischen Logik', Matematicheskii Sbornik, n.s., 1, 323-336.] devoted his efforts to generalizing two theorems, one for the propositional calculus and the other for the restricted functional calculus. The theorems in question were Godel's compactness theorem and Skolem's result that no denumerable set of formulas of first-order logic can completely characterize the structure of the natural numbers.

See English translation into: A.I. Mal'cev, The Metamathematics of Algebraic Systems: Collected Papers 1936-1967 (North Holland, 1971), page 1:

This article is devoted to generalizing two theorems, one for propositional calculus (PC) and the other for first-order predicate logic (FOPL). The first theorem is due to Gödel [K. Gödel, Die Vollsthdigkeit der Axiome des logischen Funktionenkalkuls (1936),] and can be formulated as follows:

For any countable system of formulas of PC to be consistent, it is sufficient that every finite part of the system be consistent.

Finally, see also On a General Method for Obtaining Local Theorems in Group Theory by A. Mal'cév, Review by Leon Henkin and Andrzej Mostowski (Jsl, 1959):

Historical note. The formulation and proof of the "general local theorem" [If every finite subset of a given (possibly non-denumerable) set of first-order sentences is satisfiable, then so is the whole set] for denumerable sets of first-order sentences is of course due to Gödel in 1930. The corresponding result for non-denumerable sets of formulas of propositional calculus was given by Mal'cev in 1936.


The result can be easily derived from A.Tarski's 1930 paper (On some fundamental concepts of Metamathematics, published in German in 1931) were it is stated (without proof) as Theorem 11, expressing the Finiteness property of the consequence relation: thus, it was "obviously" applicable to propositional calculus.

0
On

The situation appears to be the following:

The propositional compactness theorem is first implicitly proved in $1921$ in the form of the propositional completeness theorem, but it's not until Godel's work on first-order logic that compactness was identified as an interesting property in its own right.


The earliest treatment of propositional logic from the now-standard "provability vs. truth" perspective was surprisingly late to the party. As far as I can tell, the first paper to really lay this out was Emil Post's $1921$ paper Introduction to a general theory of elementary propositions. To quote Beziau's article An unexpected feature of classical propositional logic in the Tractatus, page $387$:

After Peirce who proved that all the $16$ [binary] connectives can be defined by only one (joint work with his student Christine Ladd-Franklin) [..., Post's paper] is the first work with important mathematical results: completeness, functional completeness and Post completeness. In mathematics results work together with conceptualization. In Post's paper we find for the first time a clear distinction between proof and truth in [classical propositional logic], distinction on which basis the completeness theorem which is herein presented makes sense.

Compactness is such an easy corollary of completeness that it's arguably implicit in Post's results; however, at a glance it does not seem to be stated explicitly. One possible reason for this is that - as far as I can tell - infinite propositional theories weren't even objects of explicit study until circa Godel, so compactness didn't have a chance to arise.