A hierarchy of expressive power

Let us organize the standard logical connectives into a hierarchy of expressive power—which logical languages are able to express which others? Which are expressively incomparable?

Let us enlarge our discussion beyond expressive completeness and incompleteness for sets of connectives by mounting a finer analysis of the comparative expressive power of various natural fragments of propositional logic. A set of logical connectives is expressively complete when it is fully expressive, when it is able to express any logical truth function. But amongst the incomplete sets, some are more expressive than others. For example, one might wonder how does { ∧, ∨ } compare with { ∧, → } in expressive power? More generally, what is the hierarchy of expressive power of the various natural fragments of propositional logic?

In this installment, as a kind of toy project on expressivity, let us aim to classify the expressive power of all fragments of the propositional language consisting of what we have called the standard language of propositional logic, using the connectives { ∧, ∨, →, ↔, ¬ }.

With these five connectives, there are precisely thirty-two subsets, each giving rise to a corresponding language, which we shall now place into a hierarchy of expressive power.