A Formal Proof in Coq of Cantor-Bernstein-Schroeder’s Theorem without axiom of choice
Yaoshun Fu, Tianyu Sun, Wensheng Yu · 2019
This paper describes a formal proof of Cantor-Bernstein-Schroeder’s Theorem based on Morse-Kelley axiomatic set theory, which use inductive without axiom of choice in the proof assistant Coq. Firstly, we formalize a few definitions, axioms and theorems from the axiomatic set theory, just needed for formal proof. Furthermore, some new definition were added to make the system self-closed. Then, some reusable lemmas and Integrated strategy are given to make the code simpler and more automated. At last, we give a formal proof of the theorem in detail. All the proofs are formally checked by Coq proof assistant. The formalizations embody that mechanical proving of mathematical theorem based on Coq has the characteristics of readability and interactivity. Every step proves to normalized, rigorous and credible. The Cantor-Bernstein-Schroeder’s Theorem is the key result in the set theory that allows comparison of infinite sets, and its formalization lay a foundation for formal proof of lots of important theorems and puzzles in set theory.