Predicate-functors and the limits of decidability in logic.
Aris Noah · Notre Dame Journal of Formal Logic · 1980
In this paper,* we use predicate-functor logic to probe the limits of decidability.Quine's assertion that polyadic logic remains decidable as long as there are no permutations or recurrences of predicate places is given precise formulation and tested through consideration of two well-defined subsystems of Quine's full system of predicate-functor logic.Quine's rationale for developing predicate-functor logic (see [3] and [4]) is that predicate-functors provide a tool for a discriminating analysis of various syntactical functions carried out by the bound variables of quantification.Distinct functions are apportioned to distinct functors, whose combined use can express exactly what can be expressed in the quantifier-variable notation of first-order quantification theory.Quine's analysis has led him to the conclusion that the essential services of the variable are the permutation of predicate places and the linking of predicate places by identity.The permutation job is discharged in our predicate-functor logic by the functors '/?/', and the linking job by the self functor i S\ . . .The existential force of quantification, at any rate, is no essential or distinctive service of the variable; it is carried as well by the cropping functor 'J' and, for that matter, by the Boolean ' =£ A'. ([3], p. 304).*I would like to give full credit to Fred Sommers of Brandeis University for setting me on the track which led to the results presented in this paper.Sommers has developed a very interesting algebraic system of logic.Part of his algebra is very closely analogous to what is here called "restricted predicate-functor logic", and it was the study of that system that led me to the isolation and exploration of the restricted system of predicate-functor logic.I would also like to thank W. V. Quine for reading a draft of this paper and suggesting a number of helpful revisions.