Mechanization of Analytic Reasoning About Sets

Abstract

Resolution reasoners, when applied to set theory problems, typically suffer from “lack of focus.” MARS is a program that attempts to rectify this difficulty by exploiting the definition-like character of the set theory axioms. As in the case of its predecessor, SLIM, it employs a tableau proof procedure based on binary resolution, but MARS IS enhanced by an equality substitution rule and a device for introducing previously proved theorems as lemmas. MARS’s performance compares favorably with that of other existing automated reasoners for this domain. MARS finds proofs for many basic facts about functions, construed as sets of ordered pairs. MARS is being used to attack the homomorphism test problem, the theorem that the composition of two group homomorphisms is a group homomorphism.