Chứng minh tài sản thay thế của người thừa kế trên sự bình đẳng

Question

Tôi đang cố gắng hiểu các loại quy nạp từ chapter 7 of "theorem proving in lean".

tôi đặt ra cho mình một nhiệm vụ chứng minh rằng người kế nhiệm của các số tự nhiên có một tài sản thay thế trên bình đẳng:

inductive natural : Type 
| zero : natural 
| succ : natural -> natural 

lemma succ_over_equality (a b : natural) (H : a = b) : 
    (natural.succ a) = (natural.succ b) := sorry 

Sau khi một số phỏng đoán và khá toàn diện tìm kiếm tôi đã có thể đáp ứng các trình biên dịch với một vài khả năng:

lemma succ_over_equality (a b : natural) (H : a = b) : 
    (natural.succ a) = (natural.succ b) := 
    eq.rec_on H (eq.refl (natural.succ a)) 
    --eq.rec_on H rfl 
    --eq.subst H rfl 
    --eq.subst H (eq.refl (natural.succ a)) 
    --congr_arg (λ (n : natural), (natural.succ n)) H 

Tôi không hiểu bất kỳ bằng chứng nào tôi vừa thực sự hoạt động.

1. Định nghĩa đầy đủ của loại eq (quy nạp) là gì? Trong VSCode tôi có thể thấy chữ ký loại eq là eq Π {α : Type} α → α → Prop, nhưng tôi không thể thấy các nhà xây dựng cá nhân (quy nạp) (tương tự của zero và succ từ natural). Điều tốt nhất tôi có thể tìm thấy trong mã nguồn doesn't look quite right.
2. Tại sao eq.subst vui lòng chấp nhận bằng chứng là (natural.succ a) = (natural.succ a) để cung cấp bằng chứng là (natural.succ a) = (natural.succ b)?
3. higher order unification là gì và cách áp dụng cho ví dụ cụ thể này?
4. ý nghĩa của lỗi tôi nhận được khi tôi gõ #check (eq.rec_on H (eq.refl (natural.succ a))), đó là [Lean] invalid 'eq.rec_on' application, elaborator has special support for this kind of application (it is handled as an "eliminator"), but the expected type must be known eq.rec_on : Π {α : Sort u} {a : α} {C : α → Sort l} {a_1 : α}, a = a_1 → C a → C a_1

Answer 1

1. eq được quy định tại https://github.com/leanprover/lean/blob/master/library/init/core.lean#L120 là inductive eq {α : Sort u} (a : α) : α → Prop | refl : eq a Ý tưởng là gì là hạn bất kỳ bằng chính nó, và cách duy nhất cho hai thuật ngữ là bằng nhau là cho cùng một thuật ngữ. Điều này có thể cảm thấy như một chút ma thuật ITT. Vẻ đẹp đến từ recursor được tạo tự động cho định nghĩa này: eq.rec : Π {α : Sort u_2} {a : α} {C : α → Sort u_1}, C a → Π {a_1 : α}, a = a_1 → C a_1 Đây là nguyên lý thay thế cho sự bình đẳng. "Nếu C giữ a và a = a_1 thì C giữ a_1." (Có cách giải thích tương tự nếu C có giá trị kiểu thay vì Giá trị được ưu tiên.)

2. eq.subst đang lấy bằng chứng là a = b cùng với bằng chứng là succ a = succ a. Lưu ý rằng eq.subst về cơ bản là một sự cải cách của eq.rec ở trên. Giả sử rằng thuộc tính C, được tham số hóa trên biến x, là succ a = succ x. C giữ cho a theo phản xạ và kể từ a = b, chúng tôi có C khoản giữ là b.

3. Khi bạn viết eq.subst H rfl, Lean cần tìm ra thuộc tính (hoặc "động cơ") C được cho là vậy. Đây là một ví dụ về sự thống nhất bậc cao hơn: biến không xác định cần phải hợp nhất với một biểu thức lambda. Có một cuộc thảo luận về điều này trong phần 6.10 trong https://leanprover.github.io/theorem_proving_in_lean/theorem_proving_in_lean.pdf và một số thông tin chung tại https://en.wikipedia.org/wiki/Unification_(computer_science)#Higher-order_unification.

4. Bạn đang yêu cầu Lean thay thế a = b thành succ a = succ a mà không nói cho bạn biết những gì bạn đang cố gắng chứng minh. Bạn có thể đang cố gắng chứng minh succ b = succ b hoặc succ b = succ a hoặc thậm chí succ a = succ a (bằng cách thay thế hư không).Lean không thể suy ra động cơ C trừ khi nó có thông tin này.

Nói chung, làm thay "bằng tay" (với eq.rec, subst, vv) là khó khăn, vì trật tự thống nhất cao hơn là khó tính và tốn kém. Bạn sẽ thường thấy rằng nó là tốt hơn để sử dụng chiến thuật như rw (viết lại): lemma succ_over_equality (a b : natural) (H : a = b) : (natural.succ a) = (natural.succ b) := by rw H

Nếu bạn muốn được thông minh, bạn có thể tận dụng trình biên dịch phương trình nạc, và thực tế là "chỉ" bằng chứng về a=b là rfl: lemma succ_over_equality : Π (a b : natural), a = b → (natural.succ a) = (natural.succ b) | ._ _ rfl := rfl