Hostname: page-component-7479d7b7d-68ccn Total loading time: 0 Render date: 2024-07-15T21:28:50.293Z Has data issue: false hasContentIssue false
  • English
  • Français

Some structure results for propositional calculi1

Published online by Cambridge University Press:  12 March 2014

Ronald Harrop
Ronald Harrop*
Affiliation:
University of Newcastle Upon Tyne, England Simon Fraser University, Burnaby, B.C., Canada
Get access Rights & Permissions [Opens in a new window]

Extract

1. Introduction. Since this paper is a written version of one presented as a survey lecture at a meeting of the Association for Symbolic Logic, its form and content have been essentially determined by the form and content of that lecture, and these latter were themselves considerably influenced by a deliberate attempt to avoid the lecture consisting essentially either of a catalogue of results in some fairly wide field or of the presentation of detailed proofs of a few particular results in a very limited field, with, in either case, a consequential serious limitation of the time available for discussion of the motivation for the results and of the connections between them. There is thus no attempt to cover, even in outline, the full range of topics which could reasonably fall within the scope of its title.

The paper consists mainly of a general discussion of some results concerned with finite models of axiomatically defined calculi of propositional form, with particular reference to the occurrence of such models in proofs that certain propositional calculi are decidable. In addition, there is an account of some results concerned with the existence of undecidable propositional calculi and of others connected with the decidability or undecidability of certain structure problems which relate either to sets of propositional calculi or to different presentations of the same calculus.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 30 , Issue 3 , September 1965 , pp. 271 - 292
Copyright
Copyright © Association for Symbolic Logic 1965

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.)

Footnotes

1

Paper presented by invitation at a meeting of the Association for Symbolic Logic held in Bristol, England, July 1964.

References

REFERENCES

[1]Boone, W. W., Partial results regarding word problems and recursively enumerable degrees of unsolvability, Bulletin of the American Mathematical Society, vol. 68 (1962), pp. 616–623.CrossRefGoogle Scholar
[2]Bull, R. A., The implicational fragment of Dummett's LC, this Journal, vol. 27 (1962), pp. 189–194.Google Scholar
[3]Bull, R. A., A note on the modal calculi S4.2 and S4.3, Zeitschrift für matitematische Logik und Grundlagen der Mathematik, vol. 10 (1964), pp. 53–55.CrossRefGoogle Scholar
[4]Bull, R. A., Some results for implicational calculi, this Journal, vol. 29 (1964), pp. 33–39.Google Scholar
[5]Bull, R. A., A class of extensions of the modal system S4 with the finite model property, to appear in Zeitschrift für mathematische Logik und Grundlagen der Mathematik.Google Scholar
[6]Bull, R. A., An algebraic study of Diodorean modal systems, this Journal, vol. 30 (1965), pp. 58–64.Google Scholar
[7]Church, A., Introduction to mathematical logic I, Princeton (Princeton University Press), 1956.Google Scholar
[8]Clapham, C. R. J., Finitely presented groups with word problems of arbitrary degrees of insolubility, Proceedings of the London Mathematical Society (3), vol. 14 (1964), pp. 633–676.CrossRefGoogle Scholar
[9]Davis, M., Computability and unsolvability, New York, Toronto and London (McGraw Hill), 1958.Google Scholar
[10]Dugundji, J., Note on a property of matrices for Lewis and Langford's calculi of propositions, this Journal, vol. 5 (1940), pp. 150–151.Google Scholar
[11]Dummett, M., A propositional calculus with denumerable matrix, this Journal, vol. 24 (1959), pp. 97–106.Google Scholar
[12]Dummett, M. A. E. and Lemmon, E. J., Modal logics between S4 and S5, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 250–264.CrossRefGoogle Scholar
[13]Gentzen, G., Untersuchungen über das logische Schliessen, Mathematische Zeitschrift, vol. 39 (1934), pp. 176–210, 403–431.Google Scholar
[14]Gladstone, M. D., Some remarks on formal systems, Ph.D. thesis, University of Bristol, 1964.Google Scholar
[15]Gladstone, M. D., Proportional calculi with decision problems of any required recursively enumerable degree of unsolvability, Notices of the American Mathematical Society, vol. 11 (1964), p. 454 (Abstract).Google Scholar
[16]Gladstone, M. D., Some ways of constructing a propositional calculus of any required degree of unsolvability, to appear in Transactions of the American Mathematical Society.Google Scholar
[17]Gödel, K., Zum intuitionistischen Aussagenkalkül, Akademie der Wissenschaffen in Wien, Mathematisch-naturwissenschaftliche Klasse, Anzeiger, vol. 69 (1932), pp. 65–66. Reprinted in Ergebnisse eines mathematischen Kolloquiums, Heft 4 (for 1931–2, pub. 1933), p. 40.Google Scholar
[18]Halldén, S., Results concerning the decision problem of Lewis's calculi S3 and S6, this Journal, vol. 14 (1950), pp. 230–236.Google Scholar
[19]Harrop, R., On disjunctions and existential statements in intuitionistic systems of logic, Mathematische Annalen, vol. 132 (1956), pp. 347–361.CrossRefGoogle Scholar
[20]Harrop, R., On the existence of finite models and decision procedures for propositional calculi, Proceedings of the Cambridge Philosophical Society, vol. 54 (1958), pp. 1–13.CrossRefGoogle Scholar
[21]Harrop, R., The finite model property and subsystems of classical propositional calculus, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 29–32.CrossRefGoogle Scholar
[22]Harrop, R., A relativization procedure for propositional calculi and some applications, this Journal, vol. 28 (1963), p. 263 (Abstract).Google Scholar
[23]Harrop, R., A relativization procedure for propositional calculi with an application to a generalized from of Post's theorem, Proceedings of the London Mathematical Society (3), vol. 14 (1964), pp. 595–617.CrossRefGoogle Scholar
[24]Harrop, R., Some generalizations and applications of a relativization theory for propositional calculi, Formal systems and recursive functions: Proceedings VIII Logic Colloquium, Oxford 1963, edited by Crossley, J. N. and Dummett, M. A. E., Amsterdam (North Holland), 1964, pp. 10–39.Google Scholar
[25]Heyting, A., Die formalen Regeln der intuitionistischen Logik, Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, 1930, pp. 42–56.Google Scholar
[26]Hiż, H., Extendible sentential calculus, this Journal, vol. 24 (1959), pp. 193–202.Google Scholar
[27]Ihrig, A. H., Post-Linial theorems for r.e.d.u., Notices of the American Mathematical Society, vol. 11 (1964), p. 456 (Abstract).Google Scholar
[28]Ihrig, A. H., Coincidence of partial propositional calculi, Notices of the American Mathematical Society, vol. 11 (1964), p. 457 (Abstract).Google Scholar
[29]Ihrig, A. H., Classes of partial propositional calculi and r.e.d.u.'s, Notices of the American Mathematical Society, vol. 11 (1964), p. 669 (Abstract).Google Scholar
[30]Jankov, V. A., Some superconstructive propositional calculi, Soviet Mathematics, vol. 4 (1963), pp. 1103–1105 (translated from Doklady Akademii Nauk SSSR, vol. 151 (1963), pp. 796–798).Google Scholar
[31]Jaśkowski, S., Recherches sur le système de la logique intuitioniste, Actes du Congrès International de Philosophie Scientifique VI, Philosophie des Mathématiques, Actualités Scientifiques et Industrielles, no. 393, Paris (Hermann), 1936, pp. 58–61.Google Scholar
[32]Kleene, S. C., Introduction to metamathematics, Amsterdam (North Holland), Groningen (Noordhoff), New York, Toronto (Van Nostrand), 1952.Google Scholar
[33]Kreisel, G. and Putnam, H., Eine Unableitungsbeweismethode für den intuitionistischen Aussagenkalkül, Archiv für mathematische Logik und Grundlagenforschung, vol. 3 (1957), pp. 74–78.CrossRefGoogle Scholar
[34]Kripke, S. A., Semantical analysis of modal logic I. Normal modal propositional calculi, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 9 (1963), pp. 61–96.CrossRefGoogle Scholar
[35]Kuznecov, A. V., Undecidability of the general problems of completeness, solvability and equivalence of propositional calculi (Russian), Akademija Nauk SSSR, Sibirskoe Otdelenie Institut Matematiki. Algebra i Logika Seminar (Novosibirsk), vol. 2 no. 4 (1963), pp. 47–66 (see Mathematical Reviews, vol. 28 (1964), # 3935).Google Scholar
[36]Lemmon, E. J., An extension algebra and the modal system T, Notre Dame Journal of Formal Logic, vol. 1 (1960), pp. 3–12.CrossRefGoogle Scholar
[37]Lewis, C. I. and Langford, C. H., Symbolic Logic, New York and London (Century), 1932.Google Scholar
[38]Linial, S. and Post, E. L., Recursive unsolvability of the deducibility, Tarski's completeness and independence of axioms problems of the propositional calculus, Bulletin of the American Mathematical Society, vol. 55 (1949), p. 50 (Abstract).Google Scholar
[39]Łukasiewicz, J., O logice trojwartosciowej (On three-valued logic), Ruch filozoficzny (Lwow), vol. 5 (1920), pp. 169–171.Google Scholar
[40]Łukasiewicz, J. and Tarski, A., Untersuchungen über den Aussagenkalkül, Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Classe III, vol. 23 (1930), pp. 30–50.Google Scholar
[41]McKinsey, J. C. C., A solution of the decision problem for the Lewis systems S2 and S4 with an application to topology, this Journal, vol. 6 (1941), pp. 117–134Google Scholar
[42]McKinsey, J. C. C. and Tarski, A., On closed elements in closure algebras, Annals of Mathematics, vol. 47 (1946), pp. 122–162.CrossRefGoogle Scholar
[43]McKinsey, J. C. C. and Tarski, A., Some theorems about the sentential calculi of Lewis and Heyting, this Journal, vol. 13 (1948), pp. 1–15.Google Scholar
[44]Post, E. L., Introduction to a general theory of elementary propositions, American Journal of Mathematics, vol. 43 (1921), pp. 163–185.CrossRefGoogle Scholar
[45]Prior, A. N., Formal Logic, Oxford (Clarendon), second edition 1962.Google Scholar
[46]Rasiowa, H., O Pewnym Fragmencie Implikacyjnego Rachunku Zdań (On a fragment of implicative propositional calculus) (Polish with Russian and English summaries), Studia Logica, vol. 3 (1955), pp. 208–226.CrossRefGoogle Scholar
[47]Rose, G. F., Jaskowski's truth-tables and realizability, Ph.D. thesis, University of Wisconsin, 1952.Google Scholar
[48]Rose, G. F., Propositional calculus and realizability, Transactions of the American Mathematical Society, vol. 75 (1953), pp. 1–19.CrossRefGoogle Scholar
[49]Scroggs, S. J., Extensions of the Lewis system S5, this Journal, vol. 16 (1951), pp. 112–120.Google Scholar
[50]Singletary, W. R., A complex of problems proposed by Post, Bulletin of the American Mathematical Society, vol. 70 (1964), pp. 105–109.CrossRefGoogle Scholar
[51]Singletary, W. E., Recursive unsolvability of a complex of problems proposed by Post, Ph.D. thesis, University of Illinois, 1964.CrossRefGoogle Scholar
[52]Smiley, T., The independence of connectives, this Journal, vol. 27 (1962), pp. 426–436.Google Scholar
[53]Umezawa, T., On intermediate many-valued logics, Journal of the Mathematical Society of Japan, vol. 11 (1959), 116–128.CrossRefGoogle Scholar
[54]Yntema, M. K., A detailed argument for the Post-Linial theorems, to appear in Notre Dame Journal of Formal Logic, vol. 5 (1964).CrossRefGoogle Scholar