Formalizing Finite Set Combinatorics in Type Theory

Mathematics can be distinguished among all the sciences due to its precise language and clear rules of reasoning. The notion of proof lies at the heart of mathematics. Typically, proof of any mathematical statement is a logical argument, that can convince anyone of the correctness of the statement. Starting with a set of assumptions a mathematical proof tries to discover new facts using a sequence of logical steps. These logical steps must correspond to the rules of reasoning which are considered correct in mathematics.

Ideally, proof should contain all the necessary information so that its veri¿cation becomes a purely mechanical job. However, the contemporary practice of writing mathematical proofs is only an approximation to this ideal, where the task of a reviewer is to use his intelligence to judge whether the proof could be expressed in a way that conforms to the valid rules of reasoning. A reviewer very often comes across inferential gaps, imprecise de¿nitions, and unstated background assumptions. In such circumstances, it is di¿cult to say whether a proof is correct or not. Even if the statement turns out to be true, judging it to be so could take a long time.

Mathematical proofs are becoming more and more complex and the length of unusually large proofs has also increased with time. If a proof is short one can check it manually. But if proof is deep and already ¿lls hundreds of journal pages very few people may have the expertise to go through it. The correctness concern of such complex proofs is further enhanced by the fact that some of these proofs rely on extensive computation.