Блог

В следующем коде оператор add'_commut принимается Coq, но add_commut отклоняется из-за несоответствия юниверса.

 Set Universe Polymorphism.

Definition nat : Type := forall (X : Type), X -> (X -> X) -> X.

Definition succ (n : nat) : nat := fun X z s => s (n X z s).

Definition add' (m n : nat) : nat := fun X z s => m X (n X z s) s.

Definition nat_rec (z : nat) (s : nat -> nat) (n : nat) : nat := n nat z s.
Definition add (m n : nat) : nat := nat_rec n succ m.

Definition equal (A : Type) (a : A) : A -> Type := fun a' => forall (P : A -> Type), P a -> P a'.

Lemma add'_commut (m n : nat) : equal nat (add' m n) (add' n m).
Admitted.

Lemma add_commut (m n : nat) : equal nat (add m n) (add n m).
(*
In environment
m : nat
n : nat
The term "add n (fun X : Type => m X)" has type
 "nat@{Top.1078 Top.1079}"
while it is expected to have type
 "nat@{Top.1080 Top.1078}" (universe inconsistency).
*)
  

Как заставить это пройти?

Церковные цифры работают, только если вы включаете функцию непредикативности Set , вводя -arg -impredicative-set в свой _CoqProject файл или используя -impredicative-set опцию командной строки. Затем определите nat как:

 Definition nat : Set := forall (X : Set), X -> (X -> X) -> X.
  

Impredicative Set позволяет nat иметь точно такой же тип, Set по которому он определяет количество. Без непредсказуемости nat должен иметь более высокий уровень вселенной, чем тот, который он определяет количественно, хотя уровни скрыты от вас, пока вы не получите ошибку, подобную в вопросе.

Обратите внимание, что непредикативность Set несовместима с классической логикой.