证明一系列步骤终止

Question

我有一个重写 lambda 项的小系统。它具有通常的（三个）确定性按值调用重写规则。我没有在这里列出它们。

重写被建模为 Step 从一个 Term 到另一个。我还有 reachable 项之间的 StarStep 关系，其中后者可以通过零个或多个重写步骤从第一个生成。

我现在想证明重写终止（有值或卡住）。我删除了细节，因为我认为它们在这里不重要，但如果需要我可以添加更多细节。

这里是代码（或者浏览器中 CollaCoq 中的 here）：

Variable Term: Type.
Variable Step: Term -> Term -> Prop.
Inductive StarStep: Term -> Term -> Prop :=
| StepNone : forall t, StarStep t t
| StepOne  : forall t t', Step t t' -> forall t'', StarStep t' t'' -> StarStep t t''.

Goal forall t : Term,
    ~ (forall t', StarStep t t' -> exists t'', Step t' t'') ->
    exists t', StarStep t t' /\ forall t'', ~ Step t' t''.

所以我要展示

IF it is NOT the case that "from all reachable states it is possible another step" THEN there exists a state t' that is reachable from t such that it is not possible to take a step from it.

我不知道如何进行。我是否需要更多信息，即归纳或破坏（=案例分析）t？当假设被否定时，我如何使用假设中的信息？

编辑：Here are more details about Term and Step

Answer 1

我相信这是经典推理的一个实例。该陈述类似于以下命题，在构造性设置中无法证明：

Goal forall (A : Type) (P : A -> Prop),
  ~ (forall x, P x) -> exists x, ~ P x.

因为 "it is not true that forall ..." 不会产生您需要证明某物存在的对象。

这里有一个使用经典逻辑定律的可能解决方案：

Require Import Coq.Logic.Classical_Pred_Type.
Require Import Coq.Logic.Classical_Prop.

Goal forall t : Term,
    ~ (forall t', StarStep t t' -> exists t'', Step t' t'') ->
    exists t', StarStep t t' /\ forall t'', ~ Step t' t''.
Proof.
  intros t H.
  apply not_all_ex_not in H.
  destruct H as [tt H].
  apply imply_to_and in H.
  firstorder.
Qed.

实际上，我们甚至不需要了解StarStep，因为前面命题的以下抽象版本在经典逻辑中是有效的（证明保持不变）：

Goal forall (A : Type) (P Q : A -> Prop),
    ~ (forall s, Q s -> exists t, P t) ->
    exists s, Q s /\ forall t, ~ P t.

证明一系列步骤终止

Prove that a sequence of steps terminates

lambda-calculus

coq