Majority Logic: Axiomatization and Completeness

Abstract. Graded modal logic, as presented in [5], extends propositional modal systems with a set of modal operators ♦n (n ∈ N) that express “there are more than n accessible worlds such that...”. We extend ∗ GML with a modal operator W that can express “there are more than or equal to half of the accessible worlds such that...”. The semantics of W is straightforward provided there are only finitely many accessible worlds; however if there are infinitely many accessible worlds the situation becomes much more complex. In order to deal with such situations, we introduce a majority space. A majority space is a set W together with a collection of subsets of W intended to be the weak majority (more than or equal to half) subsets of W. We then extend a standard Kripke structure with a function that assigns a majority space over the set of accessible states to each state. Given this extended Kripke semantics, majority logic is proved sound and complete.