monadic predicate calculus

The absence of polyadic relation symbols severely restricts what can be expressed in the monadic predicate calculus. It is so weak that, unlike the full predicate calculus, it is decidable—there is a decision procedure that determines whether a given formula of monadic predicate calculus is logically valid (true for all nonempty domains).Heinrich Behmann, Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem, in Mathematische Annalen (1922)Löwenheim, L. (1915) "Über Möglichkeiten im Relativkalkül," Mathematische Annalen 76: 447-470. Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879-1931. Harvard Univ. Press: 228-51. Adding a single binary relation symbol to monadic logic, however, results in an undecidable logic.

The need to go beyond monadic logic was not appreciated until the work on the logic of relations, by Augustus De Morgan and Charles Sanders Peirce in the nineteenth century, and by Frege in his 1879 Begriffsschrift. Prior to the work of these three, term logic (syllogistic logic) was widely considered adequate for formal deductive reasoning.

Inferences in term logic can all be represented in the monadic predicate calculus. For example the argument

: All dogs are mammals.

: No mammal is a bird.

: Thus, no dog is a bird.

can be notated in the language of monadic predicate calculus as

: $[(\backslash forall\; x\backslash ,D(x)\backslash Rightarrow\; M(x))\backslash land\; \backslash neg(\backslash exists\; y\backslash ,M(y)\backslash land\; B(y))]\; \backslash Rightarrow\; \backslash neg(\backslash exists\; z\backslash ,D(z)\backslash land\; B(z))$

where $D$, $M$ and $B$ denote the predicates{{clarification needed|date=January 2023|reason=

Presumably "predicates" is used here synonymously with "relations"? If so, it would be good to state that explicitly given that the synonymy of "relation" and "predicate" is not necessarily inherently obvious without background knowledge.

}} of being, respectively, a dog, a mammal, and a bird.

Conversely, monadic predicate calculus is not significantly more expressive than term logic. Each formula in the monadic predicate calculus is equivalent to a formula in which quantifiers appear only in closed subformulas of the form

:$\backslash forall\; x\backslash ,P\_1(x)\backslash lor\backslash cdots\backslash lor\; P\_n(x)\backslash lor\backslash neg\; P\text{'}\_1(x)\backslash lor\backslash cdots\backslash lor\; \backslash neg\; P\text{'}\_m(x)$

or

:$\backslash exists\; x\backslash ,\backslash neg\; P\_1(x)\backslash land\backslash cdots\backslash land\backslash neg\; P\_n(x)\backslash land\; P\text{'}\_1(x)\backslash land\backslash cdots\backslash land\; P\text{'}\_m(x),$

These formulas slightly generalize the basic judgements considered in term logic. For example, this form allows statements such as "Every mammal is either a herbivore or a carnivore (or both)", $(\backslash forall\; x\backslash ,\backslash neg\; M(x)\backslash lor\; H(x)\backslash lor\; C(x))$. Reasoning about such statements can, however, still be handled within the framework of term logic, although not by the 19 classical Aristotelian syllogisms alone.

Taking propositional logic as given, every formula in the monadic predicate calculus expresses something that can likewise be formulated in term logic. On the other hand, a modern view of the problem of multiple generality in traditional logic concludes that quantifiers cannot nest usefully if there are no polyadic predicates to relate the bound variables.

The formal system described above is sometimes called the pure monadic predicate calculus, where "pure" signifies the absence of function symbols. Allowing monadic function symbols changes the logic only superficially{{citation needed|reason=Not obvious. Exact meaning unclear|date=August 2014}}{{clarification needed|date=January 2023|reason=Not obvious, given that monadic function letters can be interpreted as a special kind of binary relation symbols. So it is definitely not obvious that allowing only special binary relations (monadic functions) would retain decidability but allowing all binary relations would lead to undecidability. A citation or an explanation could be helpful.}}, whereas admitting even a single binary function symbol results in an undecidable logic.

Monadic second-order logic allows predicates of higher arity in formulas, but restricts second-order quantification to unary{{clarification needed|date=January 2023|reason=Is "unary predicate" a synonym (and e.g. not a hyper- or hypo-nym) of "monadic predicate" or "monadic relation"? I assume so, but it's never stated explicitly.}} predicates, i.e. the only second-order variables allowed are subset variables.

{{Portal|Philosophy}}

{{Mathematical logic}}

Category:Predicate logic

Category:Logical calculi