Math Labs
Định lýĐã chứng minh

Tính kết hợp của phép bằng từ Eq.rec

Phát biểu

Tồn tại hạng thức Eq.trans:a=b→b=c→a=c\mathrm{Eq.trans} : a = b \to b = c \to a = c chỉ dựng từ Eq.rec\mathsf{Eq.rec}.

Vì sao đúng?

Nối các phép bằng (a=b=ca=b=c nên a=ca=c) được dùng trong hầu như mọi chứng minh; nếu đây là tiên đề thay vì hạng thức suy ra được, hạt nhân phải tin tiên đề đó thay vì xác nhận nó bằng tính toán.

Phác thảo chứng minh

Cố định a,ba,b và h1:a=bh_1 : a = b. Cho h2:b=ch_2 : b = c với cc tuỳ ý, ta muốn chứng minh a=ca = c. Áp dụng Eq.rec\mathsf{Eq.rec} lên h2h_2 với motive C(y,h):=(a=y)C(y, h) := (a = y), chỉ số theo điểm yy và chứng minh hh nối bb với yy.

Trường hợp gốc cần là C(b,refl b)C(b, \mathrm{refl}\,b), tức a=ba = b — chính là h1h_1. Vậy h1h_1 là chứng minh trường hợp gốc cấp cho Eq.rec\mathsf{Eq.rec}.

Eq.rec\mathsf{Eq.rec} sau đó trả, với mọi cc và mọi h2:b=ch_2 : b = c, một chứng minh của C(c,h2)=(a=c)C(c, h_2) = (a = c), đúng như ta cần.

Vậy Eq.trans h1 h2:=Eq.rec (C:=λy h, a=y) h1 c h2\mathrm{Eq.trans}\,h_1\,h_2 := \mathsf{Eq.rec}\,(C := \lambda y\, h,\, a = y)\,h_1\,c\,h_2 có kiểu Eq.trans:a=b→b=c→a=c\mathrm{Eq.trans} : a = b \to b = c \to a = c. Chú ý mẫu hình chung với đối xứng: cả hai chứng minh đều "vận chuyển" một sự kiện theo một phép bằng bằng cách chọn motive CC phù hợp, rồi để quy tắc rút gọn cố định của hạt nhân cho Eq.rec\mathsf{Eq.rec} trên refl\mathrm{refl} làm việc thật.

Chủ đề chứa định lý này

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

  1. Leonardo de Moura, Sebastian Ullrich (2021). The Lean 4 Theorem Prover and Programming Language
  2. Xavier Leroy (2009). Formal verification of a realistic compiler
  3. Terence Tao, et al. (2023). A Proof of the Polynomial Freiman-Ruzsa Conjecture · arXiv:2311.05762