Truth Set Algebra: A New Way to Prove Undefinability

Studying the definability (expressibility) of logical connectives in terms of one another has a long history in logic. Proving the definability of one connective through another is usually done by providing an explicit formula that expresses one connective through others. Once such a formula is found, proving definability is usually a straightforward exercise. Proving undefinability is significantly harder and usually requires sophisticated techniques. Different domain-specific techniques have been proposed for various logical systems. Among them, the best-known is the bisimulation method for modal logics [19, 1, 2, 5, 15, 18, 4, 17, 16]. It is not clear how bisimulation can be applied to non-modal logics where completely different methods have been proposed [13, 20].