Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-27T21:32:31.074Z Has data issue: false hasContentIssue false
  • English
  • Français

Completeness of the propositional calculus

Published online by Cambridge University Press:  12 March 2014

W. V. Quine
W. V. Quine*
Affiliation:
Harvard University
Get access Rights & Permissions [Opens in a new window]

Extract

The completeness of the prepositional calculus was first proved by Post. His somewhat condensed proof has been succeeded by more detailed presentations of substantially the same argument, and also by several proofs of radically different forms. The present paper contains still another proof, offered because of its relative simplicity. In part this proof follows a plan which was sketched by Wajsberg for another purpose, viz. for proving the completeness of the sub-calculus involving only the material conditional.

For the present proof a systematization of the propositional calculus will be used which is due to Tarski, Bernays, and Wajsberg. It involves the material conditional “⊃” and the falsehood “F” as primitive; thus the formulae are recursively describable as comprising “F”, the variables “p”, “q”, “r”, …, and all results of putting formulae for “p” and “q” in “(p⊃q)”. The denial “˜p” is definable as “(p⊃F)”, and all other truth functions are then definable in familiar fashion. (Conversely, in a system admitting “˜” instead of “F” as primitive, “F” might be explained as an abbreviation of “˜(P⊃P)”.) The postulates are four:

(1) ((p⊃q)⊃((q⊃r)⊃ (p⊃ r)))

(2) (((p⊃(q⊃p)⊃p)

(3) (p⊃(q⊃p))

(4) (F⊃p).

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 3 , Issue 1 , March 1938 , pp. 37 - 40
Copyright
Copyright © Association for Symbolic Logic 1938

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1 Post, , Introduction to a general theory of elementary propositions, American journal of mathematics, vol. 43 (1921), pp. 169–173CrossRefGoogle Scholar.

2 Hilbert, and Ackermann, , Grundzüge der theoretischen Logik (Berlin 1928), pp. 9–29, 33Google Scholar; Hilbert, and Bernays, , Grundlagen der Mathematik, vol. 1 (Berlin 1934), pp. 49–67Google Scholar.

3 Łukasiewicz, , Ein Vollständigkeitsbeweis des zweiwertigen Aussagenkalküls, Comptes rendus de séances de la Société des Sciences et des Lettres de Varsavie, Classe III, vol. 24 (1931), pp. 153–183Google Scholar; Kalmár, , Ueber die Axiomatisierbarkeit des Aussagenkolküls, Acta litterarum ac scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio scientiarum mathematicarum, vol. 7 (1935), pp. 222–243Google Scholar; Hermes, and Scholz, , Ein neuer Vollständigkeitsbeweis für das reduzierte Fregesche Axiomensystem des Aussagenkalküls (Leipzig 1937, 40 pp.)Google Scholar.

4 Wajsberg, , Metalogische Beiträge, Wiadomości matematyczne, vol. 43 (1937), pp. 154–157Google Scholar.

5 See Wajsberg, op. cit., pp. 132, 157–159.

6 In my System of logistic (Cambridge, Mass., 1934), pp. 68, 72–74Google Scholar: derivation of 2·5, 2·7, 2·86, 2·87, 2·94, 2·96, 2·97, and 2·99 from 2·1, 2·2, and 2·3.

7 Concerning the notation see pp. 61–71, op. cit.

8 Concerning the metamathematical notation see my Logic based on inclusion and abstraction, this Journal, Vol. 2 (1937), pp. 145–152Google Scholar.