A Constructive Algebraic Hierarchy in Coq

✍ Scribed by Herman Geuvers; Randy Pollack; Freek Wiedijk; Jan Zwanenburg

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 276 KB
• Volume: 34
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.2002.0552

✦ Synopsis

We describe a framework of algebraic structures in the proof assistant Coq. We have developed this framework as part of the FTA project in Nijmegen, in which a constructive proof of the fundamental theorem of algebra has been formalized in Coq.

The algebraic hierarchy that is described here is both abstract and structured. Structures like groups and rings are part of it in an abstract way, defining e.g. a ring as a tuple consisting of a group, a binary operation and a constant that together satisfy the properties of a ring. In this way, a ring automatically inherits the group properties of the additive subgroup. The algebraic hierarchy is formalized in Coq by applying a combination of labelled record types and coercions. In the labelled record types of Coq, one can use dependent types: the type of one label may depend on another label. This allows us to give a type to a dependent-typed tuple like A, f, a , where A is a set, f an operation on A and a an element of A. Coercions are functions that are used implicitly (they are inferred by the type checker) and allow, for example, to use the structure A := A, f, a as a synonym for the carrier set A, as is often done in mathematical practice. Apart from the inheritance and reuse of properties, the algebraic hierarchy has proven very useful for reusing notations.