The Logic of Commuting Equivalence Relations
David Finberg, Matteo Mainetti, Gian‐Carlo Rota, Roberto Magari · 2017
This chapter describes one way of visualizing polynomials in joins and meets of subspaces of a vector space, and develops the logical theory that goes with such visualization. A linear lattice is a sublattice of the lattice of partitions of a set, with the property that the equivalence relations associated with any two partitions in the lattice commute, in the sense of composition of relations. Equivalence relations that commute under composition can be explicitly characterized in terms of the blocks of the corresponding partitions, by a theorem due to Mme. The presentation of the chapter is self contained, and requires no more knowledge than the definition of a lattice. No previous knowledge of commuting equivalence relations is required. The most important example of commuting equivalence relations comes from information theory. Expressions involving joins and meets of subspaces of a vector spaces may be translated into expressions in terms of joins and meets of partitions, whose associated equivalence relations commute.