hide
Free keywords:
-
Abstract:
Herbrand's theorem plays a fundamental role in automated theorem proving
methods based on tableaux. The crucial step in procedures based on such methods
can be described as the \emph{corroboration} problem or the \emph{Herbrand
skeleton} problem, where, given a positive integer $m$, called
\emph{multiplicity}, and a quantifier free formula, one seeks a valid
disjunction of $m$ instantiations of that formula. In the presence of
\emph{equality}, which is the case in this paper, this problem was recently
shown to be undecidable.
The main contributions of this paper are two theorems. The first, the
\emph{Partisan Corroboration Theorem}, relates corroboration problems with
different multiplicities. The second, the \emph{Shifted Pairing Theorem}, is a
finite tree automata formalization of a technique for proving undecidability
results through direct encodings of valid Turing machine computations.
These theorems are used in the paper to explain and sharpen several recent
undecidability results related to the \emph{corroboration} problem, the
\emph{simultaneous rigid E-unification} problem and the \emph{prenex fragment
of intuitionistic logic with equality}.
