再帰でCoCを拡張して誘導を導くことは可能ですか?

原始的な再帰でCoCを拡張したとします。つまり、μxという用語を追加しました。等価性が再帰的な言い回しを許可するように、

Γ |- µ x . a : *    Γ |- b : *    Γ |- a [a/x] == b
---------------------------------------------------
Γ |- a == b

そして、引数に再帰的な項を適用すると、それが展開されました:

((µ x . a : T) q) ~> (a[a/x] q)

このようにしても誘導を導くことはできないようです。私は以下を試みました(Morteish構文を使用して):

NAT =
  ∀ (P : *) ->
  ∀ (Zero : P) ->
  ∀ (Succ : NAT -> P) ->
  P

Zero =
  λ (P : *) ->
  λ (Zero : P) ->
  λ (Succ : NAT -> P) ->
  Zero

Succ =
  λ (n : NAT) ->
  λ (P : *) ->
  λ (Zero : P) ->
  λ (Succ : NAT -> P) ->
  Succ n

induction =
  λ (P : NAT -> *) ->
  λ (Z : P Zero) ->
  λ (S : ∀ (n : NAT) -> P n -> P (Succ n)) ->
  λ (n : NAT) ->
  n (P n) Z (λ (pred : NAT) -> S n (induction P Z S pred))

ここで問題となるのは、誘導の定義で n
のパターンマッチングを行うときに、戻り値の型を指定する必要があるということです。 P n
に指定すると、エラーが発生します。これは、最初のケースでは、

Z : P Zero

しかし、する必要があります:

Z : P n

そして、2番目のケースでは、

(λ (p : NAT) -> S p (induction P Z S p)) : ∀ (p : NAT) -> P (Succ p)

しかし、する必要があります:

(λ (p : NAT) -> S p (induction P Z S p)) : ∀ (x : NAT) -> P n

問題の原因は、システムが次のことを認識していないように見えることです。

case n of
  Zero   -> ... here, n == Zero   ...
  Succ p -> ... here, n == Succ p ...

つまり、変数 n:NATZero
としてパターンマッチングした後、システムは nゼロ。同様に、
Succ(pred n)== n
を理解できません。そこには何らかの固有の理由がありますか?これを確認するための拡張はありますか?

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です