Harrop formula

In intuitionistic logic, the Harrop formulae, named after Ronald Harrop, are the class of formulae inductively defined as follows: ^{[1] [2] [3]}

• Atomic formulae are Harrop, including falsity (⊥);
• ${\displaystyle A\wedge B}$ is Harrop provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle \neg F}$ is Harrop for any well-formed formula ${\displaystyle F}$;
• ${\displaystyle F\rightarrow A}$ is Harrop provided ${\displaystyle A}$ is, and ${\displaystyle F}$ is any well-formed formula;
• ${\displaystyle \forall x.A}$ is Harrop provided ${\displaystyle A}$ is.

By excluding disjunction and existential quantification (except in the antecedent of implication), non-constructive predicates are avoided, which has benefits for computer implementation.

Discussion

Harrop formulae are "well-behaved" also in a constructive context. For example, in Heyting arithmetic ${\displaystyle {\mathsf {HA}}}$, Harrop formulae satisfy a classical equivalence not generally satisfied in constructive logic: ^[1]

${\displaystyle \neg \neg A\leftrightarrow A.}$

There are however ${\displaystyle \Pi _{1}}$-statements that are ${\displaystyle {\mathsf {PA}}}$-independent, meaning these are simple ${\displaystyle \forall x.A}$ statements for which excluded middle is not ${\displaystyle {\mathsf {HA}}}$-provable. Indeed, while intuitionistic logic proves ${\displaystyle \neg \neg (P\lor \neg P)}$ for any ${\displaystyle P}$, the disjunction will not be Harrop.

Hereditary Harrop formulae and logic programming

A more complex definition of hereditary Harrop formulae is used in logic programming as a generalisation of Horn clauses, and forms the basis for the language λProlog. Hereditary Harrop formulae are defined in terms of two (sometimes three) recursive sets of formulae. In one formulation: ^[4]

• Rigid atomic formulae, i.e. constants ${\displaystyle r}$ or formulae ${\displaystyle r(t_{1},...,t_{n})}$, are hereditary Harrop;
• ${\displaystyle A\wedge B}$ is hereditary Harrop provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle \forall x.A}$ is hereditary Harrop provided ${\displaystyle A}$ is;
• ${\displaystyle G\rightarrow A}$ is hereditary Harrop provided ${\displaystyle A}$ is rigidly atomic, and ${\displaystyle G}$ is a G-formula.

G-formulae are defined as follows: ^[4]

• Atomic formulae are G-formulae, including truth(⊤);
• ${\displaystyle A\wedge B}$ is a G-formula provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle A\vee B}$ is a G-formula provided ${\displaystyle A}$ and ${\displaystyle B}$ are;
• ${\displaystyle \forall x.A}$ is a G-formula provided ${\displaystyle A}$ is;
• ${\displaystyle \exists x.A}$ is a G-formula provided ${\displaystyle A}$ is;
• ${\displaystyle H\rightarrow A}$ is a G-formula provided ${\displaystyle A}$ is, and ${\displaystyle H}$ is hereditary Harrop.

History

Harrop formulae were introduced around 1956 by Ronald Harrop and independently by Helena Rasiowa. ^[2] Variations of the fundamental concept are used in different branches of constructive mathematics and logic programming.

See also

• Realizability

References

1. Dummett, Michael (2000). Elements of Intuitionism (2nd ed.). Oxford University Press. p. 227. ISBN   0-19-850524-8.
2. A. S. Troelstra; H. Schwichtenberg (27 July 2000). Basic proof theory. Cambridge University Press. ISBN   0-521-77911-1.
3. Ronald Harrop (1956). "On disjunctions and existential statements in intuitionistic systems of logic". Mathematische Annalen . 132 (4): 347–361. doi:10.1007/BF01360048. S2CID   120620003.
4. Dov M. Gabbay, Christopher John Hogger, John Alan Robinson, Handbook of Logic in Artificial Intelligence and Logic Programming: Logic programming, Oxford University Press, 1998, p 575, ISBN   0-19-853792-1