rederivability

Re-derivability is a term used in proof theory and formal rewriting contexts to denote the property that a result produced by a derivation can be derived again under a specified notion of equivalence or transformation. Broadly, a statement φ is rederivable if, from the same axioms or premises, there exists an alternative derivation of φ, or if a given derivation of φ can be transformed into another valid derivation of φ that preserves the intended conclusions and dependencies.

Formally, let S be a formal system with a set of axioms A and a set of inference rules R. A derivation D of φ from A is rederivable if there exists a map T that, for every D in Deriv(S, A, φ), produces a derivation D' of φ from A such that D' is equivalent to D under a chosen relation E on derivations (for example permutation of commutable rules, normalization, or elimination of redundancies).

In practice, rederivability is used to study redundancy of proofs, the stability of derivations under change of presentation, and the reliability of proof-search strategies. It is also relevant in automated theorem proving when a proof is reconstructed after preprocessing or transformation phases.

Example: in a sequent calculus, derivations can often be permuted to reorder rule applications; a rederivation might witness that such permutations do not affect the final sequent and that a canonical form exists.

Because rederivability is not a widely standardized term, its precise meaning varies by authors and context. Related notions include derivability, derivational equivalence, and normalization.