New logical foundations for 'classical' and quantum information theory

David Ellerman

Logical information theory disrupts the role of Shannon’s information theory as a foundational theory of information and repositions the Shannon theory as a specialized theory for coding and communications where it has been so successful. All the Shannon definitions of simple, joint, conditional, and mutual entropy can be derived by a uniform requantifying transformation from the logical definitions. Moreover, logical entropy is a measure (in the sense of measure theory) while Shannon entropy is not–even though Shannon carefully defined the compound notions of his entropy so that they would satisfy the usual Venn diagram formulas as if they were values of a measure on a set. Since logical entropy automatically satisfies those formulas as a (probability) measure, and the uniform requantifying transform preserves the Venn diagram relations, that answers an old question about how the Shannon notions can have those relationships without being a measure.

These developments come from the new logic of partitions (= quotient sets = equivalence relations) which is categorically dual (duality of subobjects and quotient objects) to the usual Boolean logic of subsets (usually mis-specified as the special case of propositional logic). Boole developed the quantitative version of subset logic as logical probability theory, i.e., the normalized counting measure on subsets. Similarly the quantitative version of partition logic is logical information theory, i.e., the normalized counting measure on partitions is logical entropy–when the partitions are represented as the set of distinctions that is the binary relation complementary to the equivalence relation for the partition. Symbolically:

Probability theory/Subset logic = Information theory/Partition logic.

Logical information theory captures the idea that information at the logical level is about distinctions, differences, distinguishings, and discriminations. The theory directly generalizes to also provide new foundations for quantum information theory based on distinguishing quantum states.