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

Tính đối xứng của phép bằng từ Eq.rec

Phát biểu

Tồn tại hạng thức Eq.symm:a=b→b=a\mathrm{Eq.symm} : a = b \to b = a chỉ dựng từ refla:a=a\mathrm{refl}_a : a = a và Eq.rec\mathsf{Eq.rec}; tính đối xứng là một định lý của CIC, không phải một tiên đề thêm.

Vì sao đúng?

Nếu phép bằng cần tiên đề riêng cho đối xứng, kết hợp, tương thích..., hạt nhân tin cẩn sẽ phình ra theo mỗi tính chất mới của ==. Suy ra tất cả từ một phép khử giữ hạt nhân nhỏ.

Phác thảo chứng minh

Cố định aa. Ta muốn một hàm nhận h:a=bh : a = b (với bb tuỳ ý) và trả về chứng minh b=ab = a. Áp dụng Eq.rec\mathsf{Eq.rec} với motive C(y,h):=(y=a)C(y, h) := (y = a) — một họ mệnh đề chỉ số theo điểm yy và chứng minh hh nối aa với yy.

Phép khử yêu cầu một chứng minh cho trường hợp gốc C(a,refl a)C(a, \mathrm{refl}\,a), tức a=aa = a; ta cấp refl a\mathrm{refl}\,a. Điều này hợp lệ vì trường hợp gốc luôn được chỉ số bởi refl\mathrm{refl} tại điểm khởi đầu aa.

Eq.rec\mathsf{Eq.rec} sau đó trả, với mọi yy và mọi h:a=yh : a = y, một chứng minh của C(y,h)=(y=a)C(y,h) = (y = a). Thay y:=b, h:=hy := b,\ h := h: ta nhận đúng chứng minh của b=ab = a.

Gói lại thành Eq.symm h:=Eq.rec (C:=λy h, y=a) (refl a) b h\mathrm{Eq.symm}\,h := \mathsf{Eq.rec}\,(C := \lambda y\, h,\, y = a)\,(\mathrm{refl}\,a)\,b\,h cho ra hạng thức kiểu Eq.symm:a=b→b=a\mathrm{Eq.symm} : a = b \to b = a. Hạt nhân chấp nhận nó chỉ bằng cách khớp phép áp dụng này với chữ ký kiểu của Eq.rec\mathsf{Eq.rec} — không cần lập luận về khái niệm "đối xứng" ở mức hạt nhân.

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