如何在 Coq 中证明半融合意味着融合?
How to prove that semi-confluence implies confluence in Coq?
我使用 Coq.Relations
提供的定义,我有以下定义:
Definition joinable (x:A) (y:A) : Prop :=
exists z, (clos_refl_trans A R x z) /\ (clos_refl_trans A R y z).
Notation "X ↓ Y" := (joinable X Y) (at level 70, right associativity).
Notation "X → Y" := (R X Y) (at level 75, right associativity).
Notation "X →* Y" := (clos_refl_trans A R X Y) (at level 75, right associativity).
Notation "X ⇆ Y" := (clos_refl_sym_trans A R X Y) (at level 75, right associativity).
Definition confluent : Prop := forall x y1 y2, (x →* y1 /\ x →* y2) -> (y1↓y2).
Definition semi_confluent : Prop := forall x y1 y2, (x → y1 /\ x →* y2) -> (y1↓y2).
这是我的资料:
Theorem semi_confluent_confluent : semi_confluent -> confluent.
Proof.
unfold confluent, semi_confluent, joinable.
intros. destruct H0. induction H0.
- apply H with (x := x). split. auto. auto.
- exists y2. split. auto. auto.
- admit.
Admitted.
我尝试在 :
上使用归纳法
- H0 : x →* y1
但我似乎卡在了最后一种情况(传递性)上。对于最后一个案例,我尝试了几种方法,比如对 (x →* z) 进行归纳,但它似乎让我得出了一个无法证明的陈述。
我认为通过对clos_refl_trans_1n
关系(等价于clos_refl_trans
)的归纳来证明定理会更容易一些。
因为它给了我们两种情况:自反情况和我们实际 "make an R
-step" 并且我们可以轻松使用半融合 属性 的情况,这需要 R
步。
我稍微更改了 confluent
和 semi_confluent
的定义以避免 wrappings/unwrappings 与连词相关。这不会影响任何东西,因为结果在逻辑上等同于原始结果。
我还应该指出,在许多情况下,我们需要在执行归纳之前概括我们的陈述。
Definition confluent : Prop := forall x y1 y2, x →* y1 -> x →* y2 -> (y1↓y2).
Definition semi_confluent : Prop := forall x y1 y2, x → y1 -> x →* y2 -> (y1↓y2).
Hint Constructors clos_refl_trans.
Theorem semi_confluent_confluent : semi_confluent -> confluent.
Proof.
intros Hsemi x y1 y2 Hxy1 Hxy2.
unfold semi_confluent, joinable in *.
generalize dependent y2.
induction (clos_rt_rt1n _ _ _ _ Hxy1) as [| x y1' y1 HRxy1' Hy1'y1 IH]; intros y2 Hxy2.
- now exists y2.
- apply clos_rt1n_rt in Hy1'y1.
specialize (Hsemi x y1' y2 HRxy1' Hxy2) as (z & Hy1'z & Hy2z).
specialize (IH Hy1'y1 z Hy1'z) as (w & Hy1w & Hzw).
exists w.
split; auto.
now apply rt_trans with (y := z).
Qed.
我使用 Coq.Relations
提供的定义,我有以下定义:
Definition joinable (x:A) (y:A) : Prop :=
exists z, (clos_refl_trans A R x z) /\ (clos_refl_trans A R y z).
Notation "X ↓ Y" := (joinable X Y) (at level 70, right associativity).
Notation "X → Y" := (R X Y) (at level 75, right associativity).
Notation "X →* Y" := (clos_refl_trans A R X Y) (at level 75, right associativity).
Notation "X ⇆ Y" := (clos_refl_sym_trans A R X Y) (at level 75, right associativity).
Definition confluent : Prop := forall x y1 y2, (x →* y1 /\ x →* y2) -> (y1↓y2).
Definition semi_confluent : Prop := forall x y1 y2, (x → y1 /\ x →* y2) -> (y1↓y2).
这是我的资料:
Theorem semi_confluent_confluent : semi_confluent -> confluent.
Proof.
unfold confluent, semi_confluent, joinable.
intros. destruct H0. induction H0.
- apply H with (x := x). split. auto. auto.
- exists y2. split. auto. auto.
- admit.
Admitted.
我尝试在 :
上使用归纳法- H0 : x →* y1
但我似乎卡在了最后一种情况(传递性)上。对于最后一个案例,我尝试了几种方法,比如对 (x →* z) 进行归纳,但它似乎让我得出了一个无法证明的陈述。
我认为通过对clos_refl_trans_1n
关系(等价于clos_refl_trans
)的归纳来证明定理会更容易一些。
因为它给了我们两种情况:自反情况和我们实际 "make an R
-step" 并且我们可以轻松使用半融合 属性 的情况,这需要 R
步。
我稍微更改了 confluent
和 semi_confluent
的定义以避免 wrappings/unwrappings 与连词相关。这不会影响任何东西,因为结果在逻辑上等同于原始结果。
我还应该指出,在许多情况下,我们需要在执行归纳之前概括我们的陈述。
Definition confluent : Prop := forall x y1 y2, x →* y1 -> x →* y2 -> (y1↓y2).
Definition semi_confluent : Prop := forall x y1 y2, x → y1 -> x →* y2 -> (y1↓y2).
Hint Constructors clos_refl_trans.
Theorem semi_confluent_confluent : semi_confluent -> confluent.
Proof.
intros Hsemi x y1 y2 Hxy1 Hxy2.
unfold semi_confluent, joinable in *.
generalize dependent y2.
induction (clos_rt_rt1n _ _ _ _ Hxy1) as [| x y1' y1 HRxy1' Hy1'y1 IH]; intros y2 Hxy2.
- now exists y2.
- apply clos_rt1n_rt in Hy1'y1.
specialize (Hsemi x y1' y2 HRxy1' Hxy2) as (z & Hy1'z & Hy2z).
specialize (IH Hy1'y1 z Hy1'z) as (w & Hy1w & Hzw).
exists w.
split; auto.
now apply rt_trans with (y := z).
Qed.