Date: Sun, 28 Aug 1994 13:01:35 +0500 (GMT+4:00) From: categories Subject: distributivity Date: Sat, 27 Aug 94 14:47:55 EDT From: Michael Barr I pass on to you a curious fact that was mentioned to me by Richard Squire and he credited it to Jim Loveys. Let P and Q be quantifiers. (What is a quantifier? Well as a first approximation it is a map from X--o L to L which is in some obscure (to me) sense polymorphic. Limits (both in categories and posets), integrals and, evidently, univeral and existential quantifiers in logic, where L is the object of truth values. Looking at all the examples, you realize immediately that polymorphism is certainly not functoriality and if some of them give inequalities or morphisms, they do so in different directions (say SUP vs INF or A vs E).) Well, anyway, P and Q are quantifiers. Say that P distributes over Q if there is an equation P(x:X).Q(y:Y).f(x,y) = Q(s:X--o Y).P(x:X).f(x,s(x)) One aspect of polymorphism is that this makes sense. Here f: X x Y --> L and if treat this as a map Y --> (X--o L), then the LHS makes sense. As for the RHS, we are doing the same thing with X x (X--o Y) --> X x Y --> L, where the first map is and the second is f. Here are 2 1/2 examples: If P is universal quantification, Q is existential and L is the object of truth values in a topos, then this is the axiom of choice. If P is sup in a lattice and Q is inf and if X and Y are restricted to finite sets, then this is the statement of distributivity. If P is SUP in a complete lattice and Q is INF, then this is the complete distributivity identity. Now here is the startling fact. In all three cases, the distributivity of P over Q implies that of Q over P! For the lattices, these facts are well-known. For the AC, it is easy to see (at least in a boolean topos) since you can negate and replace f by its complementary relation. (Yes a topos that satisfies AC is boolean, but it does not immediately follow that these two complementary conditions are equivalent, since perhaps only one of them implies AC in the non-boolean case.) This doesn't always hold. For example, in a topos, finite products distribute over (finite) sums, but the converse is certainly false. Date: Tue, 30 Aug 1994 20:20:42 +0500 (GMT+4:00) From: categories Subject: re: distributivity Date: Tue, 30 Aug 1994 12:56:51 -0400 (EDT) From: Andreas Blass This is a comment tangential to Michael Barr's message about quantifiers. His 2 1/2 examples can be improved to 3, because the condition he calls complementary to AC also implies classical logic. Recall that this condition reads: (exists x:X) (forall y:Y) f(x,y) iff (forall s: X --> Y) (exists x:X) f(x,s(x)). (*) The left-to-right implication here is trivial, but I claim the right-to-left implication implies (not not u) ==> u and thus Boolean logic. The easiest proof proceeds as follows in the internal logic. Given an arbitrary truth value u , let X={.|u}, i.e., X has at most one element and it's inhabited iff u, and let Y be empty. Then (not not u) implies the right side of (*) [vacuously: the existence of such an s implies not u ], while the left side of (*) implies u . For people who would like to banish the empty set at the cost of some simplicity (universal algebraists?), there is an alternate argument using only inhabited sets. Again, let a truth value u be given, let Y=2, i.e., a set with exactly two, definitely distinct elements, and let X be the quotient of Y in which the two elements have been identified iff u . Let f(x,y) mean that the canonical projection from Y to X sends y to x. Again, one can check that (not not u) implies the right side of (*) and that the left side of (*) implies u. It is curious that the same X, Y, and f as in this second proof are also used for the (internal) proof of Diaconescu's theorem that AC implies classical logic. Andreas Blass ablass@umich.edu Date: Wed, 31 Aug 1994 09:09:35 +0500 (GMT+4:00) Subject: Re: distributivity Date: Tue, 30 Aug 1994 22:55:07 -0300 From: Richard Wood Here is another comment somewhat tangential to Mike's post about distributivity. If a lattice is completely distributive, CD, then the fact that the opposite distributivity holds might be written AC==>(CD<==>CD^op), for at least some aspect of choice seems to be necessary. Write CCD, "constructive complete distributivity", for the apparent weakening of CD that requires distributivity, in the sense Mike posted, of infs over sups of down-closed subsets. Then AC<==>(CD<==>CCD). On the other hand, writing BOO for the axiom which states that the object of truth values is Boolean, one has BOO<==>(CCD<==>CCD^op). Combining these results gives an indirect proof of AC==>BOO. The fact that BOO is necessary for CCD<==>CCD^op is, at first, surprising. The equivalence of CCD and CCD^op rests entirely on whether or not the object of truth values, which is always CCD, is CCD^op. In set^2, the object of truth values being 3--->2, one expects a counterexample to the claim. The pitfall here is that distributivity of binary sup over binary inf does not extend to distributivity of sups over infs of up-closed subobjects. To sketch a proof of the necessity of BOO, show that CCD==>HEY. Unlike the situation for general Heyting algebras, it follows from a lemma attributed to both Benabou and Reyes that if the opposite of the object of truth values is Heyting then it is Boolean. These observations are simplified by the fact that CCD(L) is equivalent to the statement that sup:DL--->L has a left adjoint, where DL is the lattice of down-closed subobjects of L, and DL is equivalent to ord(L^op, Omega), where Omega is the object of truth values. RJ