Metatheorem

A metatheorem is a theorem about an object language. This is a very general statement, but metatheorem is a very general term. Many interesting metatheorems can be posed as ∀∃-statements, and these are the kind of metatheorems that can be verified in STELF. Another kind of metatheorem is a totality assertion; these are more limited because any totality assertion can also be posed as a ∀∃-statement.

STELF can prove ∀∃-metatheorems in one of two ways. The first method, the theorem prover, is incomplete and not currently recommended for use. It allows the user to directly specify a ∀∃-statement about LF terms, and then ask STELF to verify that statement. The other method is to write out a proof of the ∀∃ statement in STELF, and then use STELF’s ability to state and verify totality assertions to show that the proof is correct.

Object language

The object language is “the object of study”: a logic, programming language, or other deductive system that the user wishes to reason about with STELF. Simple examples of object languages are natural numbers and the simply-typed lambda calculus, more complex examples can be found in the case studies or research projects using STELF. Object languages like the simply-typed lambda calculus and first-order logic demonstrate the power of STELF’s higher-order abstract syntax, but the example of natural numbers with addition is used here for its simplicity. The syntax and judgments over the natural numbers can be simply presented in Backus-Naur form:

$\textit{nat} ::= 0 \,|\, \texttt{s}(\textit{nat})$

We then declare $\texttt{plus}(\textit{nat},\textit{nat},\textit{nat})$ to be a judgment that relates three natural numbers. We can define what kind of judgments we are allowed to relate by using inference rules:

${\qquad \over \texttt{plus}(0,N,N)}{\mbox{p-z}}$ ${\texttt{plus}(N_1,N_2,N_3) \over \texttt{plus}(\texttt{s}(N_1),N_2,\texttt{s}(N_3))}{\mbox{p-s}}$

Theorems

The usual interpretation of inference rules like the ones above is that we can consider some fact A to be true if we can create a complete derivation that has A a result. Truths that can be verified by writing a derivation are called theorems. If the object language is the natural numbers, then the following is a theorem theorem proving that 2 + 1 = 3.

{\mbox{p-z}} \over {\mbox{p-s}}}{\mbox{p-s}}

Similarly, if the object language is the simply-typed lambda calculus, then a theorem might state that the expression $(\lambda x : \texttt{unit}. x) \langle\rangle$ steps to $\texttt{}\langle\rangle$. This can be shown by using the rules step_app_beta and value_empty.

Totality assertions

The term “metatheorem,” as previously stated, is a very general term. We first want to think about a specific kind of metatheorem, a totality assertion.

A totality assertion for the informal deductive system presented above might be that, for any two natural numbers $\texttt{}N_1$ and $\texttt{}N_2$, there is a natural number $\texttt{}N_3$ for which $\texttt{plus}(N_1,N_2,N_3)$ is derivable. This means that the judgment $\texttt{plus}(N_1,N_2,N_3)$ forms a total relation, mapping any inputs in the first and second positions of the relation to some output in the third position. Note that the output need not be unique; the totality assertion holds even if there are many such numbers.

The totality assertions in STELF establish a stronger property. The STELF encoding of the $\texttt{plus}(N_1,N_2,N_3)$ judgment can be run as a logic program, and totality assertions that are verified by %total directives verify that, if an encoding is run as a higher-order logic program in STELF, it will act as a function that, given appropriate inputs, will find an output in a finite amount of time. STELF’s totality analysis is incomplete in that some relations that are total cannot be verified by a %total declaration.

STELF, when used in this way, can be thought of as a “theorem prover” in the limited sense that it proves that a relation is total by doing a program analysis that shows that, given appropriate inputs, it produces outputs when run as a logic program in STELF. However, it is more common to describe STELF as verifying the totality assertions, both because STELF does not produce a proof witness and because the analysis is not as sophisticated as most theorem proving procedures. Usually, the relations about which programmers intend to prove totality assertions are specifically constructed to be analyzable by STELF’s %total directive. These relations often correspond closely to an informal proof by structural induction of the same fact, making STELF’s process of verifying totality similar to the human process of verifying that a proof is valid.

∀∃-statements

Totality assertions seem very limited in scope. We have merely shown that, given a judgment like $\texttt{plus}$, we can interpret as the judgment as a relation from some inputs to some outputs and prove that the relation, given inputs, have rules that will always allow us to find outputs. But we can’t, for instance, write a totality assertion on $\texttt{plus}$ that will allow us to prove that the relation is commutative or associative.

The theorem “addition is commutative” can be specified more precisely like this: for all natural numbers $\texttt{}N_1$, $\texttt{}N_2$, $\texttt{}N_3$ and derivation of the judgment $\texttt{plus}(N_1,N_2,N_3)$, there exists a derivation of the judgment $\texttt{plus}(N_2,N_1,N_3)$. The previous statement, at a high level, said “for all (some things) there exist (some other things.” Statement with this forms are called ∀∃-statement.

The page about STELF’s theorem prover shows how the theorem prover could be used to state, and prove, this statement, but the currently recommended way of doing this is by using a totality assertion. The series of tutorials on proving metatheorems with STELF explain in detail how to do this; the remainder of this article will only give a very general view based on the notes from [http://www.cs.cmu.edu/~fp/courses/lp/lectures/18-proofs.html Lecture 18] of Frank Pfenning’s course on Logic Programming.

Simple types

First, think back at our presentation of the structure of natural numbers:

$\textit{nat} ::= 0 \,|\, \texttt{s}(\textit{nat})$

We will now think of this BNF grammar as defining the members of the type $\texttt{}\textit{nat}$. In this view $\texttt{}0$ is an object of type $\textit{nat}$, and $\texttt{s}$ is a constructor that, given an object of type $\textit{nat}$, produces an object of type $\textit{nat}$.

Proof terms

Now, look back at this derivation

{\mbox{p-z}} \over {\mbox{p-s}}}{\mbox{p-s}}

and notice that applying the rule $\texttt{p-s}$ twice to the rule $\texttt{p-z}$, as we do here, gives us a way to derive $\texttt{plus}(\texttt{s}(\texttt{s}(0)),\;N,\;\texttt{s}(\texttt{s}(N)))$ for any natural number N; in the example above, N happens to be $\texttt{s}(0)$.

Natural numbers are objects, and we can think of derivations as objects as well: we can represent this process of applying the rule $\texttt{p-s}$ twice to the rule $\texttt{p-z}$ using standard notation for application: $\texttt{p-s}(\texttt{p-s}(\texttt{p-z}))$. These objects are called generally called proof terms, and the type of a proof term is the judgment it can produce. This idea that judgments can be types is one of the important observations of the Curry-Howard isomorphism.

The proof term $\texttt{p-s}(\texttt{p-s}(\texttt{p-z}))$ can be thought of as having the type $\texttt{plus}(\texttt{s}(\texttt{s}(0)),\;\texttt{s}(0),\;\texttt{s}(\texttt{s}(\texttt{s}(0))))$, but it can also be thought of as having the type $\texttt{plus}(\texttt{s}(\texttt{s}(0)),\;0,\;\texttt{s}(\texttt{s}(0)))$. Remembering our analysis above, we can see that the most general type we can give the proof object $\texttt{p-s}(\texttt{p-s}(\texttt{p-z}))$ is $(\forall N:\textit{nat}.\;\texttt{plus}(\texttt{s}(\texttt{s}(0)),\;N,\;\texttt{s}(\texttt{s}(N))))$.

Proving ∀∃-statements using totality assertions

Recall that when we first defined the judgment $\texttt{plus}$, we mentioned the type of objects that it related:

$\texttt{plus}(\textit{nat},\textit{nat},\textit{nat})$

We will now write a judgment that, instead of relating objects with type $\texttt{}\textit{nat}$, relates derivations of $\texttt{plus}(N_1,N_2,N_3)$ and $\texttt{plus}(N_2,N_1,N_3)$. Call this derivation $\texttt{plus-comm}$.

$\forall N_1:\textit{nat} . \;\forall N_2:\textit{nat} . \;\forall N_3:\textit{nat} . \;\texttt{plus-comm}(\texttt{plus}(N_1,N_2,N_3),\;\;\texttt{plus}(N_2,N_1,N_3))$

Describing the rules that define this judgment is beyond the scope of this article; see Frank Pfenning’s notes [http://www.cs.cmu.edu/~fp/courses/lp/lectures/18-proofs.html notes] for a continuation of this approach, or proving metatheorems with STELF for a description that is closer to how STELF is used in practice. However, without describing these rules, if they were written and written correctly, we could verify a totality assertion that stated that plus-comm is a total relation with derivations of $\texttt{plus}(N_1,N_2,N_3)$ as an input and derivations of $\texttt{plus}(N_2,N_1,N_3)$ as an output.

This means that, for any three natural numbers $\texttt{}N_1$, $\texttt{}N_2$, and $\texttt{}N_3$, and any proof object with the type $\texttt{plus}(N_1,N_2,N_3)$, there is a proof object with type $\texttt{plus}(N_2,N_1,N_3)$. This is equivalent to the ∀∃-statement for the commutativity of addition that we started out with; the only difference is that we are now speaking in terms of proof objects and types instead of derivations and judgments.