Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-20T00:14:06.427Z Has data issue: false hasContentIssue false
  • English
  • Français

Two variable implicational calculi of prescribed many-one degrees of unsolvability

Published online by Cambridge University Press:  12 March 2014

Charles E. Hughes
Charles E. Hughes*
Affiliation:
University of Tennessee, Knoxville, Tennessee 37916
Get access Rights & Permissions [Opens in a new window]

Abstract

A constructive proof is given which shows that every nonrecursive r.e. many-one degree is represented by the family of decision problems for partial implicational propositional calculi whose well-formed formulas contain at most two distinct variable symbols.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 1 , March 1976 , pp. 39 - 44
Copyright
Copyright © Association for Symbolic Logic 1976

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

REFERENCES

[1] Gladstone, M. D., On the number of variables in the axioms, Notre Dame Journal of Formal Logic, vol. 11 (1970), pp. 1–15.CrossRefGoogle Scholar
[2] Hughes, C. E., Two variable implicational calculi, this Journal, vol. 39 (1974), p. 403. Abstract.Google Scholar
[3] Hughes, C. E. and Singletary, W. E., Triadic partial implicational propositional calculi, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 21–28.CrossRefGoogle Scholar
[4] Overbeek, Ross, The representation of many-one degrees by decision problems of Turing machines, Proceedings of the London Mathematical Society (3), vol. 26 (1973), pp. 167–183.CrossRefGoogle Scholar
[5] Singletary, W. E., Recursive unsolvability of a complex of problems proposed by Post, Journal of the Mathematical Society of Japan, vol. 14 (1967), pp. 25–58.Google Scholar
[6] Wajsberg, M., Axiomatization of the three-valued propositional logic, Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie Classe II, vol. 24 (1931).Google Scholar
[7] Yntema, M. K., A detailed argument for the Post-Linial theorems, Notre Dame Journal of Formal Logic, vol. 5 (1964), pp. 37–51.CrossRefGoogle Scholar