Options

Introduction: David P. Ellerman

edited April 12 in Chat

I am a retired mathematician and mathematical logician (BS, MIT '65, and PhD. Boston U. '71) associated as a Visiting Scholar at the University of California at Riverside (John Baez's home base too). My mentor in mathematics was Gian-Carlo Rota of MIT who died prematurely in 1999 (age 66). I then focused on one of his unfinished projects which was to develop a logic of equivalence relations = partitions = quotient sets, which would be a type of dual to the usual Boolean logic of subsets (usually mis-specified as the special case of propositional logic) since quotient sets are categorically dual to subsets. Dedekind had defined the join and meet of partitions in the 19th century, but one needs at least an implication operation on partitions to warrant calling it a "logic of partitions." After figuring out how to define the implication and further seeing the algorithm to translate all the Boolean operations on subsets over to partitions, the long paper developing partition logic (along with correctness and completeness theorems for a system of semantic tableaus for partitions) was published in the Review of Symbolic Logic. I gave the definition of implication for partitions in a comment on Lesson 11. A shorter and better introduction to partition logic was later published in the Logic Journal of the IGPL.

The quantitative version of Boole's logic of subsets is just finite logical probability theory as developed by Boole in his Laws of Thought. Rota always held that probability (i.e., the normalized size of a subset) is to subsets as information is to partitions.

$$\frac{\text{Probability}}{\text{Subsets}}=\frac{\text{Information}}{\text{Partitions}}$$ The key to working that out was to see the analogy between an "element of a subset" and a "distinction of a partition," where a distinction or dit of a partition is an ordered pair of elements of the underlying set \(X\) that are in different blocks or parts of the partition. The indistinctions or indits of a partition are the ordered pairs of elements in the same block or part of the partition. Hence the set of all indits of a partition is just the binary equivalence relation associated with the partition, and the set of all dits of a partition, the ditset \(dit(P)\), is the complementary binary relation called an apartness relation or just a partition relation. The logical entropy \(h(P)\) of a partition is just the normalized size of the ditset:

$$h(P)=\frac{|dit(P)|}{|X^2|}.$$ Logical entropy is related in a definite way to Shannon entropy. All the Shannon definitions of simple, joint, conditional, and mutual entropy can be obtained by a uniform requantifying transformation from the corresponding definitions in logical information theory. Moreover, logical entropy (unlike Shannon entropy) is a measure in the sense of measure theory, and thus the logical definitions of simple, joint, conditional, and mutual logical entropy of partitions is just the measure applied respectively to the ditsets, the union of ditsets, the difference of ditsets, and the intersection of ditsets. Indeed, logical entropy is a probability measure with the interpretation that \(h(P)\) is the probability of getting a distinction in two independent draws from the set \(X\). The basic paper developing logical information theory (and spelling out the comparisons with the closely related Shannon theory) was also published in the Logic Journal of the IGPL.

I went into a little detail about logical information theory as the quantitative version of partition logic since it bears on the question of which of the opposite partial orderings, the coarseness ordering or the refinement ordering, should be used on partitions. Since refinement increases the number of distinctions, it increases logical (and Shannon) entropy so the refinement ordering seems best if one is emphasizing the ordering of partitions according to their information content measured by logical or Shannon entropy.

Another topic of my research has been "heteromorphisms" which are morphisms between the objects of different categories, e.g., the canonical injection of the set of generators into the free group on that set. Homomorphisms may be treated formally by hom-functors, and heteromorphisms are treated formally by the "het-functors" or profunctors that appear later in the course. For one reason or another, Mac Lane and Eilenberg did not include heteromorphisms in their basic "ontology" for category theory even though they are just as much a tool for the proverbial "working mathematician" (referenced in the title of Mac Lane's text) as are homomorphisms. The French school of category theory, e.g., the Grothendieck school, is much less prudish and let hets 'out of the closet' as just "morphisms" routinely. The differing attitude about hets comes out in the treatment of adjoint functors. The simpler and I think more natural treatment of adjoints was developed by Bodo Pareigis in the late 60's and published in his text translated into English as: Pareigis, Bodo. 1970. Categories and Functors. New York: Academic Press. It also comes out in what one takes as more important or more basic: adjoint functors or representable functors. Grothendieck gives representable functors the pride of place, whereas the American school puts the emphasis on adjoint functors. Hets, representable functors, and adjoints are all tied together in the Pareigis treatment of adjoints. Take the het-functor whose value \(\text{het}(X,G)\) is the set of set-to-group maps from a set \(X\) to a group \(G\). The underlying set functor is just the right-representation of those hets by homs in the category of sets, and the free-group functor is just the left-representation of those same hets by homs in the category of groups. Thus one has the natural isomorphisms:

$$ \text{hom}(F(X),G)\cong \text{het}(X,G)\cong \text{hom}(X,U(G)).$$ The heterophobic American school always leaves out the middle term of hets and just defines an adjunction using the natural isomorphism between the hom-sets. All left- and right-representations of a het-functor define a pair of adjoint functors, and given a pair of adjoint functors, there is a het-functor so that the given adjoints are isomorphic to the left- and right-representations of the het-functor. All this holds as well for adjunctions on preorders or Galois connections. An introductory paper is here.

Comments

  • 1.

    It's an honor to have you here, David!

    Comment Source:It's an honor to have you here, David!
  • 2.

    Hi, David! It's an interesting coincidence thaty former student Brendan Fong started using partitions - under the guise of corelations - in our work on network theory. That's why I'm talking a bit about the logic of partitions here.

    Comment Source:Hi, David! It's an interesting coincidence thaty former student Brendan Fong started using partitions - under the guise of corelations - in our work on network theory. That's why I'm talking a bit about the logic of partitions here.
  • 3.

    Nice to know that you're here, David! I remember reading your paper on heteromorphisms, which is how I first learned about profunctors. I'm a big fan of this perspective, as well as of closely related structures like proarrow equipments.

    Comment Source:Nice to know that you're here, David! I remember reading your paper on heteromorphisms, which is how I first learned about profunctors. I'm a big fan of this perspective, as well as of closely related structures like [proarrow equipments](https://ncatlab.org/nlab/show/2-category+equipped+with+proarrows).
  • 4.

    Hello David, thanks a lot ..very interesting post ..

    Comment Source:Hello David, thanks a lot ..very interesting post ..
  • 5.

    Tobias, I first learned about profunctors when I wrote the paper on heteromorphisms, and John pointed out that I had reinvented profunctors so I added those references...

    Comment Source:Tobias, I first learned about profunctors when I wrote the paper on heteromorphisms, and John pointed out that I had reinvented profunctors so I added those references...
  • 6.

    In this thread, I think I just learned that heteromorphisms are profunctors and corelations are partitions. There's frankly no way I'd ever have figured that out on my own unless I were working on a project that centered around those ideas to begin with.

    This sort of thing is precisely why I signed up for this course, but is there something out there like a list of equivalent or closely-related terms from different branches of the literature?

    Comment Source:In this thread, I think I just learned that heteromorphisms are profunctors and corelations are partitions. There's frankly no way I'd ever have figured that out on my own unless I were working on a project that centered around those ideas to begin with. This sort of thing is precisely why I signed up for this course, but is there something out there like a list of equivalent or closely-related terms from different branches of the literature?
  • 7.
    edited May 7

    Robert - I find that Wikipedia and the nLab are pretty good about pointing out the links between concepts. So that's where I often start. But talking to people is even better, which is why I "waste my time" blogging so much.

    By the way: a corelation is not exactly the same as a partition: a corelation \(f : X \to Y\) is the same as a partition of \(X + Y\) (that is, the disjoint union of \(X\) and \(Y\)). That's different enough to deserve a different name.

    On the other hand, partitions of a set \(X\) are in one-to-one correspondence with equivalence relations on \(X\)... so "partition" and "equivalence relation" are really just two different ways of thinking about the same thing. It's probably a useful difference, but it may fool some people into not noticing the unity of the concepts.

    Comment Source:Robert - I find that Wikipedia and the nLab are pretty good about pointing out the links between concepts. So that's where I often start. But talking to people is even better, which is why I "waste my time" blogging so much. By the way: a corelation is not exactly the same as a partition: a corelation \\(f : X \to Y\\) is the same as a partition of \\(X + Y\\) (that is, the disjoint union of \\(X\\) and \\(Y\\)). That's different enough to deserve a different name. On the other hand, partitions of a set \\(X\\) are in one-to-one correspondence with equivalence relations on \\(X\\)... so "partition" and "equivalence relation" are really just two different ways of thinking about the same thing. It's probably a useful difference, but it may fool some people into not noticing the unity of the concepts.
  • 8.

    Thanks, John! I've found that Wikipedia is sometimes a little sparse, and the nLab is not exactly written with the novice in mind. Certainly talking to people is the way to go for a lot of these things, but I don't want to waste anyone's time! On that note, and related to your clarifying remark about corelations, do you happen to know of any terms that I should take note of when considering two partitions on the same set (rather than what I'm understanding as one partition on two sets)?

    Comment Source:Thanks, John! I've found that Wikipedia is sometimes a little sparse, and the nLab is not exactly written with the novice in mind. Certainly talking to people is the way to go for a lot of these things, but I don't want to waste anyone's time! On that note, and related to your clarifying remark about corelations, do you happen to know of any terms that I should take note of when considering two partitions on the same set (rather than what I'm understanding as one partition on two sets)?
  • 9.

    On that note, and related to your clarifying remark about corelations, do you happen to know of any terms that I should take note of when considering two partitions on the same set (rather than what I'm understanding as one partition on two sets)?

    In game theory, overlapping partitions are sometimes referred to as information partitions. Each partition corresponds to a particular player. This leads to a notion of common knowledge Robert Aumann introduces in his 1976 Agreeing to Disagree. The Stanford Encyclopedia of Philosophy has a nice article about this.

    Comment Source:> On that note, and related to your clarifying remark about corelations, do you happen to know of any terms that I should take note of when considering two partitions on the same set (rather than what I'm understanding as one partition on two sets)? In game theory, overlapping partitions are sometimes referred to as *information partitions*. Each partition corresponds to a particular player. This leads to a notion of common knowledge Robert Aumann introduces in his 1976 *Agreeing to Disagree*. The [Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/common-knowledge/#2.3) has a nice article about this.
  • 10.

    "hets 'out of the closet'" - I love it!

    Comment Source:"hets 'out of the closet'" - I love it!
  • 11.

    I only barely understand this stuff (possibly I may a bit from an intuitive level but the mathematical details leave me in the dust--i know basics but can't do the proofs) but one of the most interesting papers I ever read was by G C Rota (co-author) in PNAS 1993--'stochastic interpretation of the Reimann Zeta function'. There are stochastic interpretations of Ricci flow too, among others. 'Randomness vs determinism'.

    Comment Source:I only barely understand this stuff (possibly I may a bit from an intuitive level but the mathematical details leave me in the dust--i know basics but can't do the proofs) but one of the most interesting papers I ever read was by G C Rota (co-author) in PNAS 1993--'stochastic interpretation of the Reimann Zeta function'. There are stochastic interpretations of Ricci flow too, among others. 'Randomness vs determinism'.
Sign In or Register to comment.