Mendefinisikan Addition Over Integer di Coq

Question

Saya mengikuti jawaban dari pertanyaan ini dalam mendefinisikan bilangan bulat di Coq, tetapi ketika mencoba untuk mendefinisikan penjumlahan di atasnya, kesalahan "Tidak dapat menebak argumen yang menurun", selalu terjadi. Saya telah mencoba beberapa definisi berbeda dan sepertinya selalu terjadi. Adakah cara untuk membuktikan kepada Coq bahwa argumennya menurun? Atau mungkin saya kehilangan beberapa cara yang jelas untuk mendefinisikan penambahan.

Inductive nat : Type := (*Natural numbers*)
| O
| S (n : nat).

Fixpoint plus (n:nat) (m:nat) : nat := (*Addition of natural numbers*)
match n with
| O => m
| S(n') => S(plus n' m) 
end.

Notation "x + y" := (plus x y).

Inductive Z := (*Integers*)
  | Positive : nat -> Z   
  | Negative : nat -> Z.  

Fixpoint plus (n:Z) (m:Z) : Z := (*Addition of integers*)
match n, m with
| Positive O , _ => m
| _, Positive O => n
| Negative O , _ => m
| _, Negative O => n
| Positive (S n'), Positive (S m') => Positive (n' + m')
| Positive (S n'), Negative (S m') => plus (Positive n') (Negative m')
| Negative (S n'), Positive (S m') => plus (Positive n') (Negative m') 
| Negative (S n'), Negative (S m') => Negative (n'+ m') 
end.

Answer 1

Dalam Coq, satu-satunya fungsi rekursif yang dapat Anda tentukan adalah fungsi yang melakukan panggilan rekursif pada sub-istilah dari argumennya. Meskipun Positive n'lebih kecil dari Positive (S n'), yang menjamin bahwa panggilan rekursif Anda aman, ini bukan merupakan sub-istilah dari Positive (S n')(satu tidak benar-benar terjadi di dalam yang lain). Dengan demikian, Coq tidak dapat mengenali bahwa fungsi Anda selalu berakhir, dan menolaknya.

Solusinya adalah dengan mendefinisikan penambahan tanpa rekursi:

Definition plusZ (n1 n2 : Z) : Z :=
  match n1, n2 with
  | Positive n1, Positive n2 => Positive (n1 + n2)
  | Negative n1, Negative n2 => Negative (n1 + n2)
  | Positive n1, Negative n2 =>
    if n2 <=? n1 then Positive (n1 - n2)
    else Negative (n2 - n1)
  | Negative n1, Positive n2 => (* Analogous to the previous case *)
  end.

Di sini, <=?mengacu pada operator perbandingan boolean aktif nat, dan n1 - n2mengacu pada pengurangan terpotong, yang menghasilkan 0 bila n1 <= n2. (Satu hal yang harus diperhatikan tentang pengkodean ini adalah pengkodean berisi dua representasi 0: Positive 0dan Negative 0. Anda mungkin ingin menyesuaikan definisi plusZsehingga yang Negative nmewakili -(n+1)daripada -n, yang memecahkan masalah ini.)