The logic of Reverse Mathematics

This post is about a research idea I have been thinking about which is quite different from my usual research. It’s an example of a project with an “old fashioned” feel to it, as if it could have been studied 50 years ago. It’s almost a toy problem, so I haven’t spent too long digging through references yet. For all I know it was solved 50 years ago.

Background: Damir Dzhafarov developed the Reverse Mathematics Zoo a while back. This is a program that takes a data file containing Reverse Mathematics results and produces a supposedly complete list of all the other results that can be deduced from the given ones. Here “results” means both implications and non-implications:

  • \( RT^2_2 \) implies \( CAC \)
  • \(ACA_0\) implies \(RT^2_2\)
  • \( RT^2_2 \) does not imply \(WKL_0\)

From these we are supposed to deduce results such as:

  • \( ACA_0\) implies \( CAC \)
  • \( CAC \) does not imply \( WKL_0 \)

Problem: It’s clear there is an internal logic here, the “logic of Reverse Mathematics”. What logic is it? This is the sort of question that logicians should be able to answer, in principle. Much of the 20th century was devoted to developing the tools that should be needed.

This fall, I advised a student, Sean Sovine, who wrote an undergraduate capstone in which he analyzed the logic just for statements of the particular forms \( A \to B\) and \(A \not \to B\). We discovered that just two inference rules seem to suffice for these statements:

  1. From \( A \to B \) and \( B \to C \) deduce \( A \to C \)
  2. From \( A \to B \) and \( X \to Y \) and \( A \not\to Y\) deduce \( B \not \to X \)

Both of these rules are sound for the intended “Reverse Mathematics interpretation” of the statements, and the first is complete for positive statements. Completeness for negative statements is more tricky. The natural sense of an “interpretation” of a theory in this logic is a collection of propositional valuations, each of which satisfies all the positive statements in the theory, and such that each negative statement in the theory is witnessed by at least one valuation. In Reverse Mathematics these valuations come from particular models of second-order arithmetic. If we cannot prove a positive implication, we can show there is a potential valuation in which that interpretation fails; this is a completeness theorem. But if we cannot prove a negative implication, it is not clear if this is only due to us not having the right counter-model. So the best we can prove is that if a negative implication is not provable, then we do not know of a model where it holds, which is a very weak form of completeness.

Somewhat surprisingly, if we close a given set of statements \( S \) under the first rule to get \( S_1\), and then apply the second rule as much as possible to \( S_1 \), the resulting set is closed under both rules, with no need to iterate the closure process. So it is possible to form the closure of a set of results in polynomial time. Sovine wrote code to do this, which is much faster than the original Zoo code, although it only works for statements of those two special forms.

It appears that what is needed to cover the existing corpus of “natural” Reverse Mathematics results is to extend this work to cover Horn clauses (statements of the form \(A_1 \land \cdots \land A_n \to B\)) and their negations. One example of a nontrivial Horn clause in the literature is the result that \( SRT^2_2 \land COH \to RT^2_2 \). This extension seems like it could be routine, if the details work out correctly; I haven’t had the opportunity to write it up yet to see.

The thing that strikes me about this is that I feel like it should already be known. Exactly the same logic arises in artificial intelligence (“every cat is an animal” and “not every cat is striped” imply “not every animal is striped”), and so I suspect that something about a complete set of inference rules should be known in that context. The tricky thing, as always, is the negative statements, which are about the existence of counterexamples.

For example, Prolog was designed essentially to handle this task for positive Horn clauses. But the inclusion of negated Horn clauses in the corpus of Reverse Mathematics results means that Prolog itself can’t directly implement the Reverse Mathematics Zoo. Even inference rules that are complete for propositional logic, such as resolution, don’t seem to work directly with the meaning of negative implications in this new logic. Modal logic can be used to get a closer fit, with \( \Box (A \to B)\) meaning that every model of \( A\) is a model of \(B\), but this seems like overkill, since there is no nesting of modal operators in the logic of Reverse Mathematics.

Sovine’s paper is available on request, although it’s not published anywhere online at the moment.

This entry was posted in Musings, Research and tagged , , . Bookmark the permalink.

6 Responses to The logic of Reverse Mathematics

  1. François says:

    I wonder if some kind of resolution calculus might be a better way to think about this. I am able to get both rule 1 and rule 2 just from the resolution rule.

    The resolution rule is sound for validity: if \(A \lor B_1 \lor \cdots \lor B_m\) and \(\lnot A \lor C_1 \lor \cdots \lor C_n\) are both valid, then so is \(B_1 \lor \cdot \lor B_m \lor C_1 \lor \cdots \lor C_n\). Rule 1 is a direct instance of this: from \(\lnot A \lor B\) and \(\lnot B \lor C\) infer \(\lnot A \lor C\).

    You get rule 2 by backtracking. Start with \(\lnot X \lor Y\), \(\lnot A \lor B\), and \(\lnot B \lor X\). Resolving on \(B\), we get \(\lnot X \lor Y\) and \(\lnot A \lor X\). Resolving on \(X\), we get \(\lnot A \lor Y\), which is known not to be valid. Backtracking, one clause at each step had to be false in whatever model witnesses that \(\lnot A \lor Y\) is not valid. At the top level, \(\lnot B \lor X\) is the only clause which is not known to be valid, so it must be false in that model.

    It’s quite possible that rules 1 and 2 are complete if everything is a Horn clause, but resolution will probably get a bit more in the general case. Then again, principles in reverse mathematics have a positive bias (e.g., since \(RT^2_2\) is true it is more likely to be a hypothesis than \(\lnot RT^2_2\)) so Horn clauses are probably sufficient for most purposes. In any case, it might be interesting to implement a resolution-based Zoo engine for comparison purposes.

    • Carl Mummert says:

      My concern is with rules that are OK in reverse math but inconsistent classically, like \( (A \not \to B) \land (B \not\to A) \). I got the email you sent me; you might have a way to handle this with resolution that I didn’t see.

  2. Jason Rute says:

    I just discovered your blog. I hope you continue updating it. I wanted to point out that your link to the reverse math zoo is outdated (as well as Damir’s website).

Leave a Reply

Your email address will not be published. Required fields are marked *