在 Welder 中执行双感应

Question

我正在尝试使用 Welder 通过双感应来证明属性。定义取自 here. A related question that gives more details of the theory can be found here。不管怎样，我只需要一部分来说明我的问题：

基本上，我使用的是整数形式的表达式，POP(i,p) 和 POW(i,p,q)。他们称之为 n 的属性常态。我想证明如果 n(x) && n(y) 那么 n(x+y).

我们看具体情况x = POP(i,p)，y = POP(j,q)那么x+y定义如下：

if i = j then pop(i,p+q)
if i > j then pop(j,POP(i-j,p)+q)
if i < j then pop(i,POP(j-i,q)+p)

其中 pop 是一个模仿 POP 构造的函数，但存在一些细微差别。

我在Welder中用双归纳法证明如下：

def property(x: Expr) = {
  forall("y" :: shf){ case (y) => 
    (n(x) && n(y)) ==> n(x+y)
  } 
}
structuralInduction(property _, "x" :: shf) { case (ihs1, goal1) =>
  val xi = ihs1.expression
  xi match{
  ...

我想关注的相关案例如下：

case C(`POP_ID`,i,pshf) =>
  def popproperty(y: Expr) = { 
    n(y) ==> n(xi+y) 
  }
  structuralInduction(popproperty _, "y" :: shf) { case (ihs2, goal2) =>
   val yi = ihs2.expression
   implI(n(yi)){ axioms2 =>
    yi match{
     case C(`constshfID`, fc) => andI(ihs1.hypothesis(pshf),axioms1)
     case C(`POP_ID`,j,qshf) => 
      andI(
       implE(forallE(normpop1Lemma)(i,normadd(pshf,qshf)))( g => 
        andI(implE(forallE(ihs1.hypothesis(pshf))(qshf))( g => 
         andI(axioms1,axioms2)), axioms1, axioms2)),
       implI(i > j){ gt => 
        implE(forallE(normpop1Lemma)(i,normadd(POP(i-j,pshf),qshf)))( g => 
         andI(implE(ihs2.hypothesis(qshf))(g => axioms2),axioms1,axioms2,gt))                            
       },
       implI(i < j){ lt => 
        implE(forallE(normpop1Lemma)(i,normadd(POP(j-i,pshf),qshf)))( g => 
         andI(implE(ihs2.hypothesis(qshf))(g => axioms2),axioms1,axioms2,lt))
                            
    }
   )

此处 normpop1Lemma 声明要获得 n(pop(i,p))，您需要 i 自然而 p 正常。但是，我发现第二种情况没有得到证明。事实上，我需要将第二个属性概括为

def popproperty(y: Expr) = { 
  forall("x" :: shf){
   n(y) ==> n(x+y) 
  }
}

但是我是不是违反了归纳法？我真的可以通过这样做来解决案例 i > j 和 i < j 吗？（我实验时还会有更多）

编辑

目前，我可以先在 y 上归纳，然后在 x 上归纳，对于 POP-POP 情况，我可以展示 i = j 和 i > j 但 i < j 不是的情况.我认为它可以通过使用 POP(j-i,q) + p = p + POP(j-i,q) 但它没有。

相反，现在我正在尝试证明两个不同的属性，假设其中一个情况不能成立（i < j 或 i > j）。

Answer 1

嗯，我希望你的证明看起来更像这样：

structuralInduction((x: Expr) =>
  forall("y" :: shf)(y => (n(x) && n(y)) ==> n(x+y)), "x" :: shf
) { case (ihs1, g1) =>
  structuralInduction((y: Expr) =>
    (n(ihs1.expression) && n(y)) ==> n(ihs1.expression+y), "y" :: shf
  ) { case (ihs2, g2) =>
    implI(n(ihs1.expression) && n(ihs2.expression)) { normalXY =>
      (ihs1.expression, ihs2.expression) match {
        case (C(`POP_ID`,i,pshf), C(`POP_ID`,j,qshf)) => andI(
           ... // case (i == j)
           ... // case (i > j)
           implI(i < j) { iLtJ =>
             andI(
               ... // stuff using normprop1Lemma
               implE(forallE(ihs1.hypothesis(pshf))(normadd(POP(j-i,qshf)) {
                 g => // the reason why n(normadd(POP(j-i,qshf)) and n(pshf)
               },
               ... // invoke some lemma showing x+y == y+x
             )
           }
        )
      }
    }
  }
}

这里我们使用来自外部归纳的归纳假设，因为我们正在对 p \in x 进行归纳。我假设 normprop1Lemma 告诉你 normadd(POP(j-i,qshf)) 是正常形式。如果 x 是正常形式，你可能需要一些引理说明 p \in x 是正常形式。

希望对您有所帮助！

在 Welder 中执行双感应

Performing double induction in Welder

leon