A calculus for set-based program development part I: mathematical foundations

We propose an algebraic core calculus for naive or intuitive set theory. We reconstruct a fragment of set theory via atomic distributive lattices. Semantically, atomic distributive lattices extend boolean reasoning about sets by element-wise reasoning; the ontological commitment to a universal set is avoided. Operationally, reasoning with atomic distributive lattices yields abtract, concise, elegant proofs for sets from a few elementary principles. We also present an algebraic treatment of extensionality in terms of a lattice congruence. Our results are particularly suited for automated proof search in set theory. Main application is the proof support for set-based program development methods like B or Z