Date: Mon, 23 Sep 1996 12:04:09 -0300 (ADT) Subject: Free complete Heyting algebras Date: Mon, 23 Sep 96 11:42 BST From: Dr. P.T. Johnstone Does anyone know whether the free complete Heyting algebra on two generators exists? That is, does it have a set rather than a proper class of elements? It's obvious that the free cHa on aleph_0 generators is a proper class, since it has the free complete Boolean algebra on the same generators as a quotient. However, when you look at the finitary theory of Heyting algebras, the free algebra on two generators already exhibits all the bad behaviour you get in larger free algebras. (By the way, the free cHa on one generator does exist: it has just one more element than the free Ha on one generator.) Peter Johnstone Date: Mon, 23 Sep 1996 15:34:42 -0300 (ADT) Subject: Re: Free complete Heyting algebras Date: Mon, 23 Sep 1996 14:27:29 -0400 (EDT) From: F William Lawvere Concerning Peter Johnstone's question about the free complete Heyting algebras on finitely many generators: 1) If the free one on one generator is presented as a finitary algebra on two generators, presumably it is infinitely related ? 2) Is the result re one generator valid in any topos ? If so, the method so effective in complex analysis might conceivably work : the n+1 generator algebra is a one generator algebra in a topos over n dimensional space ? 3) I often speculated that a useful way of picturing these things might be to consider the parallel coHeyting algebras and use Euler-Venn diagrams with a more subtle interpretation that takes boundaries seriously. 4) There is apparently a connection between this idea of achieving completeness with few elements and Andy Pitts result concerning adjoints between finitary algebras. Can this connection be spelled out more precisely ? Bill Lawvere Date: Tue, 24 Sep 1996 13:50:31 -0300 (ADT) Subject: Re: Free complete Heyting algebras Date: Tue, 24 Sep 1996 11:05:59 +0000 From: Steve Vickers >... (By the way, the free >cHa on one generator does exist: it has just one more element than the >free Ha on one generator.) /// >2) Is this result re one generator valid in any topos ? (1) Certainly not as stated: if H is the free Ha on one generator (a, say), then one new element is not enough to complete it. (2) Its completion to a frame (over H qua distributive lattice (DL)) is the ideal completion Idl(H). (Classically, there is only one non-principal ideal.) One might ask whether this is the free cHa generated by a (as it is classically), but this seems unlikely to me - though I don't quite have a definitive counterexample. Let B be a cHa with a given element b. Then there is a unique Ha homomorphism f: H -> B taking a to b, and since f is a DL homomorphism, there is a unique frame homomorphism g: Idl(H) -> B taking a (or, rather, the principal ideal generated by a) to b. If there is a cHa homomorphism taking a to b, it must be g; but it remains to prove that g is a Heyting algebra homomorphism. In Idl(H), let I be {0} u {a: p} for some proposition p. Then I -> 0 is {x in H: p => x/\a = 0} For g to preserve ->, we must have \/{b: p} -> 0 = \/{f(x): p => x/\a = 0} Hence if p => c/\b = 0 we must have c < \/{f(x): p => x/\a = 0}. Let us construct B and c as follows: let L be the DL generated by H (qua DL) and c, subject to the p-indexed set of relations c/\a = 0 (if p), and let B be Idl(L). (Note that the injection of generators H -> L -> B is different from f.) Then this concrete construction reduces the condition c < \/{f(x): p => x/\a = 0} to showing that there exists x in H such that p => x/\a = 0 and c < f(x). Classically, we take x to be /\{~a: p}, but constructively this meet is not finite and so doesn't necessarily exist in H. (3) Assuming the reasoning in (2) goes through, it still leaves open the question of whether the free cHa on one generator exists (constructed in some other way). (4) Incidentally, the original question is ambiguous, surely? To define the notion of free cHa you must define the notion of homomorphism between cHa's. Assuming that all joins must be preserved, must all meets also be preserved, or - a la frames - only finitary ones? The question doesn't arise with complete Boolean algebras, where negation is an order antiisomorphism. Steve Vickers. Date: Tue, 24 Sep 1996 13:49:36 -0300 (ADT) Subject: Re: Free complete Heyting algebras Date: Tue, 24 Sep 96 10:00 BST From: Dr. P.T. Johnstone Replies to two of Bill's questions: 1) If the free one on one generator is presented as a finitary algebra on two generators, presumably it is infinitely related ? Yes. The free cHa on one generator is not finitely presentable as a finitary Ha. 2) Is the result re one generator valid in any topos ? I don't think so: the proof that I know relies on the decidedly non-constructive fact that every subset of the free Ha on one generator (L, say) is either finite or cofinal in L - {\top}. So I don't see much hope of getting an inductive proof along the lines suggested by Bill. Peter Johnstone Date: Wed, 25 Sep 1996 10:40:12 -0300 (ADT) Subject: Re: Free complete Heyting algebras Date: Tue, 24 Sep 1996 16:22:02 -0400 (EDT) From: Peter Freyd With regard to PeterJ's answer to BillL's question 1: a quick way to see that the free cHa on one generator is not finitely presentable is to use the fact that any finitely presented Ha is residually finite. Residual finiteness is, in turn, equivalent to everything being the sup of the finite elements below it (where finite element means one with only a finite number of elements below it). Date: Wed, 25 Sep 1996 15:53:48 -0300 (ADT) Subject: Re: Free complete Heyting algebras Date: Wed, 25 Sep 1996 14:26:39 -0400 (EDT) From: F William Lawvere Peter J and Steve V offered comments which suggest the following sharpening of my vague proposal for approaching Peter's interesting problem : 1. Which toposes with free finitary algebras have also the free cocomplete HA on one generator ? 2.Do these include toposes based on free HAs as sites ? Bill Lawvere