{"id":2152,"date":"2019-12-23T16:02:00","date_gmt":"2019-12-23T15:02:00","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2152"},"modified":"2022-11-19T15:05:00","modified_gmt":"2022-11-19T14:05:00","slug":"the-rasiowa-sikorski-lemma-and-the-baire-property","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=2152","title":{"rendered":"The Rasiowa-Sikorski lemma and the Baire property"},"content":{"rendered":"\n

Well, first, a Merry Christmas and a Happy New Year!<\/p>\n\n\n\n

Let L<\/em><\/span> be a bounded distributive lattice. Given any element u<\/em> of L<\/em>, and any element v<\/em> of L<\/em> such that u<\/em>\u2270v<\/em>, there is a (join-)prime filter containing u<\/em> and that does not contain v<\/em>. That is an easy application of Zorn’s Lemma. We consider the set Filt<\/strong>(L<\/em>) of filters in L<\/em>, ordered by inclusion. This is a dcpo, where directed suprema are computed as unions. The subset of those filters F<\/em> \u2208 Filt<\/strong>(L<\/em>) such that u<\/em> \u2208 F<\/em> and v<\/em> \u2209 F<\/em> is closed under those directed suprema, hence has a maximal element (Zorn). Let us call that maximal element F<\/em>. That F<\/em> is prime is a standard exercise, using the fact that L<\/em> is distributive in a crucial way. (Exercise!)<\/p>\n\n\n\n

Can we ask more properties of that prime filter F<\/em>? For example, can we ask it to be Scott-open?<\/p>\n\n\n\n

Spatial frames<\/h2>\n\n\n\n

If L<\/em> is a complete<\/em> distributive lattice, then a prime, Scott-open filter is a completely prime filter, namely a point<\/em> of F<\/em>, or again, an element of the space pt<\/strong>(L<\/em>) obtained through Stone duality from L<\/em>. Proposition 8.1.17 of the book<\/a> says that we can indeed require F<\/em> to be Scott-open (and prime, containing u<\/em> but not v<\/em>) provided L<\/em> is a spatial frame. In fact, when L<\/em> is a frame, it is equivalent to require that all pairs of elements u<\/em>\u2270v<\/em> of L<\/em> are separated by a prime, Scott-open filter F<\/em> (u<\/em> \u2208 F<\/em> and v<\/em> \u2209 F<\/em>) and to require that L<\/em> be spatial.<\/p>\n\n\n\n

But what happens when L<\/em> is not spatial, or when L<\/em> is not even complete?<\/p>\n\n\n\n

The Rasiowa-Sikorski Lemma<\/h2>\n\n\n\n

The Rasiowa-Sikorski Lemma<\/em> [1] states that, if L<\/em> is a Boolean algebra, then for every pair u<\/em>\u2270v<\/em> in L<\/em>, one can find a prime filter F<\/em> separating u<\/em> and v<\/em> and satisfying a local form of Scott-openness.<\/p>\n\n\n\n

Hence, as promised, we no longer assume L<\/em> to be complete. Requiring L<\/em> to be a Boolean algebra is more demanding than being just a bounded distributive lattice, but we will see later that this is not required.<\/p>\n\n\n\n

Here is what this local form of Scott-openness is. A sup situation<\/em> is a family D<\/em> of elements of L<\/em> that has a supremum sup D<\/em> in L<\/em>. (In a Boolean algebra, we cannot assume that all families, even just directed families, have a supremum.) F<\/em> respects the sup situation D<\/em> if and only if (sup D<\/em> \u2208 F<\/em> implies that some element of D<\/em> is in F<\/em>). Hence F<\/em> is Scott-open if and only if it respects every directed sup situation. F<\/em> is completely prime if and only if it respects every sup situation.<\/p>\n\n\n\n

The Rasiowa-Sikorski Lemma states that, given any countable<\/em> family of sup situations in a Boolean algebra L<\/em>, we can require the prime filter F<\/em> separating u<\/em> and v<\/em> to respect all the sup situations from that countable family. That is crucial in the applications to logic that Rasiowa and Sikorski were interested in, and I will say a brief word about it in the next section.<\/p>\n\n\n\n

In the meantime, notice that this is yet another case where countability enters the stage in a surprising way.<\/p>\n\n\n\n

The surprise should dwindle down once you realize that the Rasiowa-Sikorski Lemma is a consequence of the Baire property, as realized by R. Goldblatt [2]… and I will explain how this works.<\/p>\n\n\n\n

First-order logic<\/h2>\n\n\n\n

Please allow me not to be overly explicit here. This is not a blog on logic, and I wish to shy away from the technical details unrelated to topology. I assume you all know what a formula is. The formulae of first-order logic are built from so-called atomic formulae P<\/em>(t<\/em>1<\/sub>,…,t<\/em>n<\/em><\/sub>) (where P<\/em> is a so-called predicate symbol of arity n<\/em>, and t<\/em>1<\/sub>,…,t<\/em>n<\/em><\/sub> are so-called terms) using conjunction \u22c0, disjunction \u22c1, negation \u00ac, truth \u22a4, falsity \u22a5, universal quantification \u2200 and existential quantification \u2203. Terms are built from variables and applications f<\/em>(t<\/em>1<\/sub>,…,t<\/em>n<\/em><\/sub>) (where f<\/em> is a so-called function symbol of arity n<\/em>, and t<\/em>1<\/sub>,…,t<\/em>n<\/em><\/sub> are terms, recursively). A sentence<\/em> is a formulae whose variables are all quantified. For example, \u2200x<\/em>.\u2203y<\/em>.P<\/em>(x<\/em>,y<\/em>) is a sentence, and \u2203y<\/em>.P<\/em>(x<\/em>,y<\/em>) is a formula that is not a sentence.<\/p>\n\n\n\n

I will assume that there are at most countably many predicate symbols and function symbols. This entails that there are only countably many sentences.<\/p>\n\n\n\n

Importantly, formulae have no meaning per se<\/em>. They are just inert pieces of syntax. To give a meaning to formula, we need to define a semantics<\/em>.<\/p>\n\n\n\n

The semantics of first-order logic is given by so-called first-order structures<\/em>. A structure S<\/em> is the data of: (1) a non-empty set X<\/em>, over which terms are interpreted, (2) for each predicate symbol P<\/em> (of arity n<\/em>), an n<\/em>-ary relation over X<\/em>, (3) for each function symbol (of arity n<\/em>), a function from X<\/em>n<\/em><\/sup> to X<\/em>. We can then define a satisfaction relation \u22a8, so that S<\/em> \u22a8 F<\/em> (for every formula F<\/em>), if and only if F<\/em> is true in S<\/em>. For example, S<\/em> \u22a8 \u2200x<\/em>.\u2203y<\/em>.P<\/em>(x<\/em>,y<\/em>) if and only if for every value a<\/em> (of x<\/em>) in X<\/em>, there is a b<\/em> in X<\/em> such that (a<\/em>,b<\/em>) is related by the relation associated with the symbol P<\/em> by S<\/em>.<\/p>\n\n\n\n

Formulae are proved in a so-called proof system<\/em>, given by deduction rules<\/em>. There are plenty of proof systems available. All reasonable proof systems are sound<\/em>: if you can prove F<\/em> in this proof system, then S<\/em> \u22a8 F<\/em> for every first-order structure S<\/em>, namely, F<\/em> is valid<\/em>. The real question is completeness<\/em>: is every valid sentence provable?<\/p>\n\n\n\n

This question was solved first by Kurt G\u00f6del [6] in 1930. That obviously depends on your proof system, but here is a generic completeness argument. By generic, I mean that it will apply to any proof system, provided it satisfies some assumptions which I will enumerate along the way.<\/p>\n\n\n\n

We start by assuming that our proof system specifies an entailment<\/em> relation, which I will write as \u2264, and that entailment is a preordering. This induces an equivalence relation \u2261 on sentences (F<\/em>\u2261G<\/em> if and only if F<\/em>\u2264G<\/em> and G<\/em>\u2264F<\/em>; known as logical equivalence). Let [F<\/em>] be the equivalence class of F<\/em>. The quotient of the set of all formulae by \u2261 is a poset L<\/em>, with (the trace of) \u2264 as ordering. L<\/em> is called the Lindenbaum algebra<\/em> of the proof system.<\/p>\n\n\n\n

We will assume that the proof system has enough deduction rules so that L<\/em> is a Boolean algebra, with bottom element [\u22a5], top element [\u22a4], complement implemented by \u00ac (i.e., the complement of [F<\/em>] is [\u00acF<\/em>]), binary infimum implemented by \u2228 (i.e., the inf of [F<\/em>] and [G<\/em>] is [F<\/em> \u2228 G<\/em>]), and binary supremum implemented by \u2227. Explicitly, for the latter, we should have rules that allow us to show that F<\/em> \u2227 G<\/em> entails F<\/em>, that F<\/em> \u2227 G<\/em> entails G<\/em><\/i><\/span>, and that if H<\/em> entails F<\/em> and also entails G<\/em>, then H<\/em> entails F<\/em> \u2227 G<\/em>. (The first two are the so-called elimination rules for conjunction, and the third one is the introduction rule for conjunction, in natural deduction.)<\/p>\n\n\n\n

This is enough to deal with the propositional connectives \u2227, \u2228, \u00ac, \u22a4, \u22a5. In order to deal with the quantifiers, we will also assume that [\u2200x<\/em>.F<\/em>(x<\/em>)] is the infimum of the family of elements [F<\/em>(t<\/em>)], where t<\/em> ranges over the so-called closed terms (closed meaning without any variable, e.g., f<\/em>(a<\/em>,b<\/em>), where a<\/em> and b<\/em> are constants, namely function symbols of arity 0), and that [\u2203x<\/em>.F<\/em>(x<\/em>)] is the supremum of the family of elements [F<\/em>(t<\/em>)], where t<\/em> ranges over the closed terms. (Technically, that requires one to add so-called Henkin constants<\/em> to the language. This is a clever, but rather hackish trick. Please allow me not to say anything more about it.)<\/p>\n\n\n\n

Because we have negation, we do not need to consider, say, the first constraint on universal quantifications, and we simply assume that [\u2200x<\/em>.F<\/em>(x<\/em>)] = [\u00ac\u2203x<\/em>.\u00acF<\/em>(x<\/em>)], and that [\u2203x<\/em>.F<\/em>(x<\/em>)] = sup {[F<\/em>(t<\/em>)] | t<\/em> closed}, instead.<\/p>\n\n\n\n

Now we are set. Imagine that F<\/em> is an unprovable sentence. We need to find a first-order structure S<\/em> such that S<\/em> \u22a8 F<\/em> is wrong. The set X<\/em> is simply the set of all closed terms (the so-called Herbrand universe<\/em>). Instead of finding the relations associated with each predicate symbol P<\/em>, we will directly define the family of all sentences T<\/em> that are true in S<\/em>. Here are our requirements on that family:<\/p>\n\n\n\n

    \n
  1. T<\/em> should not contain [F<\/em>];<\/li>\n\n\n\n
  2. T<\/em> should be closed under entailment, namely: if [G<\/em>] is in T<\/em> and G<\/em>\u2264H<\/em> then [H<\/em>] is in T<\/em>;<\/li>\n\n\n\n
  3. T<\/em> should mimic the semantics: it should contain [\u22a4] but not [\u22a5] (not containing [\u22a5] is automatic from 1 and 2); it contains [G<\/em> \u2227 H<\/em>] if and only if it contains [G<\/em>] and [H<\/em>] (hence T<\/em> should be a filter), it contains [G<\/em> \u2228 H<\/em>] if and only if it contains [G<\/em>] or [H<\/em>] (hence T<\/em> should be a prime filter), it contains [\u00acG<\/em>] if and only if it does not contain [G<\/em>] (hence T<\/em> is an ultrafilter\u2014that is a useless requirement since, in a Boolean algebra, ultrafilters and prime filters coincide), and it contains [\u2203x<\/em>.G<\/em>(x)] if and only if it contains [G<\/em>(t<\/em>)] for some closed term t<\/em>.<\/li>\n<\/ol>\n\n\n\n

    Note that, since I have assumed that [\u2200x<\/em>.G<\/em>(x<\/em>)] = [\u00ac\u2203x<\/em>.\u00acG<\/em>(x<\/em>)], I do not need to assume the symmetric statement that T<\/em> contains [\u2200x<\/em>.G<\/em>(x<\/em>)] if and only if T<\/em> contains [G<\/em>(t<\/em>)] for every closed term t<\/em>.<\/p>\n\n\n\n

    If you look at it closely, you will realize that the requirement “T<\/em> contains [\u2203x<\/em>.G<\/em>(x)] if and only if it contains [G<\/em>(t<\/em>)] for some closed term t<\/em>” is equivalent to saying “T<\/em> respects the sup situations {[G<\/em>(t<\/em>)] | t<\/em> closed}, for every formula G<\/em>(x<\/em>) with at most one unquantified variable x<\/em>“.<\/p>\n\n\n\n

    There are only countably many formulae, so there are only countably many such sup situations to respect. Recapitulating, we need to find a prime filter T<\/em> that contains [\u22a4], does not contain [F<\/em>], and which respects countably many sup situations {[G<\/em>(t<\/em>)] | t<\/em> closed}. This is exactly what the Rasiowa-Sikorski lemma states the existence of. T<\/em> describes a first-order structure S<\/em> such that S<\/em> \u22a8 F<\/em> is wrong. Hence our proof system is complete. <\/p>\n\n\n\n

    Oh, before I go on, you will almost never find this argument, in papers or books of logic. Completeness is usually proved by building the ultrafilter T<\/em> by hand, directly, using the fact that L<\/em><\/i> itself is countable. The process is rather ad hoc: essentially we initialize T<\/em> to {\u00acF<\/em>}, then we add new formulae to T<\/em> as long as they do not contradict the current set of formulae in T<\/em>. There are additional difficulties, notably all formulae must be dealt with eventually, and the quantifications present specific difficulties as well. That argument looks more like a hack, but it is elementary, and this is perhaps why it is preferred nowadays.<\/p>\n\n\n\n

    But we are interested in topology, right? The point here is that, as R. Goldblatt noticed [2], the Rasiowa-Sikorski lemma is a consequence of Stone duality and the Baire property.<\/p>\n\n\n\n

    The G\u00f6rnemann-Rauszer-Sabalski Lemma<\/h2>\n\n\n\n

    I will in fact explain a more general result than the Rasiowa-Sikorski result, and that is (half of) a result by G\u00f6rnemann [3] and Rauszer and Sabalski [4]. My exposition is a variant on Goldblatt’s [2], as you may have guessed.<\/p>\n\n\n\n

    Here is the setting. We return to the case of a bounded distributive lattice L<\/em>. A sup situation D<\/em> in L<\/em> is distributive<\/em> if and only if, for every u<\/em> in L<\/em>, u<\/em> \u22c0 sup D<\/em> = sup {u<\/em> \u22c0 v<\/em> | v<\/em> \u2208 D<\/em>}. (The theorem will not work without that extra assumption. But it will be automatic in Boolean algebras.) Then we have:<\/p>\n\n\n\n

    Theorem [3,4].<\/strong> Let L<\/em> be a bounded distributive lattice, and E<\/em> be a countable family of distributive sup situations in L<\/em>. For every pair u<\/em>\u2270v<\/em> in L<\/em>, there is a prime filter F<\/em> that contains u<\/em>, does not contain v<\/em>, and respects all the sup situations in E<\/em>.<\/p>\n\n\n\n

    I said “half of” the G\u00f6rnemann-Rauszer-Sabalski theorem. The authors of [3] and [4] also consider so-called distributive inf<\/em> situations. An inf situation is a family A<\/em> with a greatest lower bound inf A<\/em>. It is distributive if and only if, for every u<\/em> in L<\/em>, u<\/em> \u22c1 inf A<\/em> = inf {u<\/em> \u22c1 v<\/em> | v<\/em> \u2208 A<\/em>}. F<\/em> respects an inf situation A<\/em> if and only if (A<\/em> \u2286 F<\/em> implies inf A<\/em> \u2208 F<\/em>). The full result is that we can find a prime filter F<\/em> that contains u<\/em>, does not contain v<\/em>, and respects both the sup situations and the inf situations from two countable sets, one of distributive sup situations, the other one of distributive inf situations. I will not bother to consider inf situations here. The argument is similar.<\/p>\n\n\n\n

    The proof (2\/5): the sets Oa<\/sub><\/em><\/h3>\n\n\n\n

    The open subsets of the topology on pt<\/strong>(I<\/strong>(L<\/em>)) are the sets OI<\/sub><\/em>={x<\/em> \u2208 pt<\/strong>(I<\/strong>(L<\/em>)) | I<\/em> \u228a x<\/em>}, where I<\/em> ranges over I<\/strong>(L<\/em>), still following Corollary 8.1.21. Let me write Oa<\/sub><\/em> for O\u2193a<\/sub><\/em>, for every a<\/em> in L<\/em>. Then Oa<\/sub><\/em> is {x<\/em> \u2208 pt<\/strong>(I<\/strong>(L<\/em>)) | a<\/em> \u2209 x<\/em>}, and the sets Oa<\/sub><\/em> form a basis of the topology on pt<\/strong>(I<\/strong>(L<\/em>)). Indeed, for every ideal I<\/em>, OI<\/sub><\/em> is the union of the sets Oa<\/sub><\/em> where a<\/em> ranges over the elements of I<\/em>.<\/p>\n\n\n\n

    Those sets Oa<\/sub><\/em> are not just open. They are compact open<\/em>. The short argument is as follows. The finite elements of the lattice of open sets O<\/strong>(Y<\/em>) of any topological space Y<\/em> are its compact open subsets. When Y<\/em>=pt<\/strong>(I<\/strong>(L<\/em>)), O<\/strong>(Y<\/em>) is isomorphic to I<\/strong>(L<\/em>), because O <\/strong>\u22a3 pt<\/strong> is an equivalence (Exercise 9.5.5). Explicitly, I<\/em> \u21a6 OI<\/sub><\/em> is an order isomorphism. But the finite elements of I<\/strong>(L<\/em>) are the principal filters \u2193a<\/em>, a<\/em> in L<\/em>, and we are done.<\/p>\n\n\n\n

    The proof (3\/5): translating the statement into topological terms<\/h3>\n\n\n\n

    Now what does it mean for a prime ideal x<\/em> to contain v<\/em>? That means that x<\/em> is not in Ov.<\/sub><\/em> And what does it mean to fail to contain u<\/em>? That means that x<\/em> is in Ou<\/sub><\/em>. Hence we are looking for an element x<\/em> of pt<\/strong>(I<\/strong>(L<\/em>)) in Ou<\/sub><\/em>\u2013Ov<\/sub><\/em>, and which respects all the sup situations in the countable family E<\/em>.<\/p>\n\n\n\n

    Note, for future reference, that since Ou<\/sub><\/em> is open and Ov<\/sub><\/em> is compact saturated, Ou<\/sub><\/em>\u2013Ov<\/sub><\/em> is patch-open. Recall that a patch-open set is one that is open in the patch topology. We will freely use the names “patch-closed”, “patch-compact”, “patch-dense”, and so on as well.<\/p>\n\n\n\n

    Note also that Ou<\/sub><\/em>\u2013Ov<\/sub><\/em> is non-empty. Otherwise, Ou<\/sub><\/em> would be included in Ov<\/sub><\/em>. Since I<\/em> \u21a6 OI<\/sub><\/em> is an order isomorphism, that would imply \u2193u<\/em> \u2286 \u2193v<\/em>, hence u<\/em>\u2264v<\/em>, which would contradict our assumption that u<\/em>\u2270v<\/em>.<\/p>\n\n\n\n

    Finally, what does it mean for a prime ideal x<\/em> to respect a sup situation D<\/em>? This is the condition (D<\/em> \u2286 x<\/em> implies sup D<\/em> \u2208 x<\/em>), or equivalently (if for every d<\/em> in D<\/em>, x<\/em> is not in Od,<\/em><\/sub> then x<\/em> is not in Osup D<\/em><\/sub>). By taking contrapositives, this means (if x<\/em> is in Osup D<\/em><\/sub> then x<\/em> is in Od <\/em><\/sub>for some d<\/em> in D<\/em>), or alternatively, (x<\/em> is in UD<\/sub><\/em> imp<\/strong> VD<\/sub><\/em>), where UD<\/sub><\/em> is the open set Osup D<\/em><\/sub> and VD<\/sub><\/em> is the open set obtained as the union of the open sets Od,<\/em><\/sub> d <\/em>in D<\/em>. Recall the notation U<\/em> imp<\/strong> V<\/em>, meaning the set of points x<\/em> such that (x<\/em> is in U<\/em> implies x<\/em> is in V<\/em>), and which we have introduced for so-called UCO sets in the post on countably presented locales<\/a>.<\/p>\n\n\n\n

    We will reflect on the fact that UD<\/sub><\/em> imp<\/strong> VD<\/sub><\/em> is a UCO set later (and very briefly). For now, we remark that UD<\/sub><\/em> imp<\/strong> VD<\/sub><\/em> is the union of the open set VD<\/sub><\/em>, and of the complement of UD<\/sub><\/em> = Osup D<\/em><\/sub>. That last complement is the complement of a compact open set, hence it is open in the de Groot dual of pt<\/strong>(I<\/strong>(L<\/em>)). It follows that both VD<\/sub><\/em> and the complement of UD<\/sub><\/em> are patch-open. Hence UD<\/sub><\/em> imp<\/strong> VD<\/sub><\/em> is also patch-open.<\/p>\n\n\n\n

    The proof (4\/5): patch-density<\/h3>\n\n\n\n

    UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em> is a UCO set, it is patch-open, good. It is also patch-dense<\/em>, as we now claim. This is where we use that D<\/em> is a distributive sup situation.<\/p>\n\n\n\n

    In order to see this, we consider a non-empty patch-open subset V<\/em> of pt<\/strong>(I<\/strong>(L<\/em>)), and we must show that it intersects UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em>. We use Theorem 9.5.24 of the book<\/a>: the patch topology of pt<\/strong>(I<\/strong>(L<\/em>)) has a base of sets of the form K<\/em>\u2013K’<\/em>, where K<\/em> and K’<\/em> range over the compact open subsets of pt<\/strong>(I<\/strong>(L<\/em>)). We remember that the compact open sets are the sets Oa<\/sub><\/em>, a<\/em> in L<\/em>. Hence V<\/em> is a union of sets of the form Oa<\/sub><\/em>\u2013Ob<\/sub><\/em>, with a<\/em>, b<\/em> \u2208 L<\/em>. At least one of them must be non-empty. We pick one, Oa<\/sub><\/em>\u2013Ob<\/sub><\/em>. It is non-empty, so there is a point x<\/em> in Oa<\/sub><\/em>\u2013Ob<\/sub><\/em>. We need to show that Oa<\/sub><\/em>\u2013Ob<\/sub><\/em> intersects UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em>.<\/p>\n\n\n\n

    We imagine it does not. If that is the case, then (Oa<\/sub><\/em>\u2013Ob<\/sub><\/em>) \u2229 (UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em>) is empty. By distributing the union implicit in the imp<\/strong> operator with intersection, this means: (1) Oa<\/sub><\/em>\u2013Ob<\/sub><\/em> \u2286 UD<\/sub><\/em>, and (2) Oa<\/sub><\/em>\u2013Ob<\/sub><\/em> \u2229 VD<\/sub><\/em> is empty. Equivalently: (1) Oa<\/sub><\/em> \u2286 Ob<\/sub><\/em> \u222a UD<\/sub><\/em>, and (2) Oa<\/sub><\/em> \u2229VD<\/sub><\/em> \u2286 Ob<\/sub><\/em>.<\/p>\n\n\n\n

    We rewrite (2) as follows. VD<\/sub><\/em> is the union of the open sets Od,<\/em><\/sub> d <\/em>in D<\/em>, so (2) states that Oa<\/sub><\/em> \u2229 Od<\/em><\/sub> \u2286 Ob<\/sub><\/em> for every d<\/em> in D<\/em>. Since I<\/em> \u21a6 OI<\/sub><\/em> is an order isomorphism, Oa<\/sub><\/em> \u2229 Od<\/em><\/sub> = O\u2193a<\/sub><\/em> \u2229 O\u2193d<\/em><\/sub> = O\u2193a<\/sub><\/em> \u2229 <\/sub>\u2193d<\/sub><\/em> = O\u2193<\/sub><\/em>(<\/sub>a<\/sub><\/em> \u22c0 <\/sub>d<\/sub><\/em>)<\/sub> is included in Ob<\/sub><\/em> if and only if a<\/em> \u22c0 d<\/em> \u2264 b<\/em>. Hence (2) states that a<\/em> \u22c0 d<\/em> \u2264 b<\/em> for every d<\/em> in D<\/em>.<\/p>\n\n\n\n

    Oh, but D<\/em> is a distributive<\/em> sup situation! so a<\/em> \u22c0 sup D<\/em> = sup {a<\/em> \u22c0 d<\/em> | d<\/em> \u2208<\/em> D<\/em>}, and therefore a<\/em> \u22c0 sup D<\/em> \u2264 b<\/em>.<\/p>\n\n\n\n

    We haven’t used (1) yet. Since x<\/em> is in Oa<\/sub><\/em>, by (1) it is in Ob<\/sub><\/em> or in UD<\/sub><\/em>. We claim that x<\/em> is in Ob<\/sub><\/em>. It suffices to show this if x<\/em> is in UD<\/sub><\/em> = Osup D<\/em><\/sub>. If so, then x<\/em> is in Oa<\/sub><\/em> \u2229 Osup D<\/em><\/sub> = Oa<\/sub><\/em> \u22c0 sup <\/sub>D<\/em><\/sub>.<\/em> Since a<\/em> \u22c0 sup D<\/em> \u2264 b<\/em>, Oa<\/sub><\/em> \u22c0 sup <\/sub>D<\/em><\/sub><\/em> is included in Ob<\/sub><\/em>, so x<\/em> is in Ob<\/sub><\/em>. All right, so x<\/em> is in Ob<\/sub><\/em>, whichever case is true. But that is impossible, since we have taken x<\/em> from Oa<\/sub><\/em>\u2013Ob<\/sub><\/em>.<\/p>\n\n\n\n

    Hence UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em> is patch-dense, as we claimed.<\/p>\n\n\n\n

    The proof (5\/5): invoking Baire<\/h3>\n\n\n\n

    Let us repeat a few of the things we have already said. First, pt<\/strong>(I<\/strong>(L<\/em>))patch<\/sup> is compact Hausdorff. Second, Ou<\/sub><\/em>\u2013Ov<\/sub><\/em> is patch-open and non-empty. Third, UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em> is patch-open, and patch-dense for every distributive sup situation D<\/em>. We are also given a countable family E<\/em> of distributive sup situations.<\/p>\n\n\n\n

    Every compact Hausdorff space is Baire. In fact, every sober locally compact space is Choquet-complete, hence Baire (Theorem 8.3.24 in the book<\/a>). Therefore pt<\/strong>(I<\/strong>(L<\/em>))patch<\/sup> is Baire.<\/p>\n\n\n\n

    The intersection of the sets UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em>, where D<\/em> ranges over E<\/em>, is a countable intersection of dense subsets of pt<\/strong>(I<\/strong>(L<\/em>))patch<\/sup>, hence it is dense, by the Baire property. Hence it intersects the non-empty open subset Ou<\/sub><\/em>\u2013Ov<\/sub><\/em> of pt<\/strong>(I<\/strong>(L<\/em>))patch<\/sup>.<\/p>\n\n\n\n

    Let x<\/em> be a point in the intersection. It is in Ou<\/sub><\/em>\u2013Ov<\/sub><\/em>, so u<\/em> is not in x<\/em>, and v<\/em> is in x<\/em>, as we have already argued. For every sup situation D<\/em> in E<\/em>, x<\/em> is in UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em>, and we have already said that this means that x<\/em> respects the sup situation D<\/em>. This finishes the proof. \u2610<\/p>\n\n\n\n

    The Rasiowa-Sikorski lemma as a corollary<\/h2>\n\n\n\n

    In summary, we have shown: Let L<\/em> be a bounded distributive lattice, and E<\/em> be a countable family of distributive sup situations in L<\/em>; for every pair u<\/em>\u2270v<\/em> in L<\/em>, there is a prime filter F<\/em> that contains u<\/em>, does not contain v<\/em>, and respects all the sup situations in E<\/em>.<\/p>\n\n\n\n

    It follows that, if L<\/em> is a Boolean algebra, then all sup situations are distributive. We obtain the Rasiowa-Sikorski lemma:<\/p>\n\n\n\n

    Corollary [1].<\/strong> Let L<\/em> be a Boolean algebra, and E<\/em> be a countable family of sup situations in L<\/em>. For every pair u<\/em>\u2270v<\/em> in L<\/em>, there is a prime filter F<\/em> that contains u<\/em>, does not contain v<\/em>, and respects all the sup situations in E<\/em>.<\/p>\n\n\n\n

    And beyond…<\/h2>\n\n\n\n

    Let us look back at the proof of the (“half of”) G\u00f6rnemann-Rauszer-Sabalski theorem. We have built a subset Y<\/em> of pt<\/strong>(I<\/strong>(L<\/em>)) as the intersection of the sets UD<\/sub> <\/em>imp <\/strong>VD<\/sub><\/em>, where D<\/em> ranges over a given countable set of distributive sup situations E<\/em>. We have seen that Y<\/em> is patch-dense, and that was the key to the proof.<\/p>\n\n\n\n

    Y<\/em> is also a \u03a0<\/strong>0<\/sup>2<\/sub> subset<\/a> of pt<\/strong>(I<\/strong>(L<\/em>)). Indeed, recall that sets of the form UD<\/sub><\/em> imp<\/strong> VD<\/sub><\/em> are UCO (union of closed and open subset), and that \u03a0<\/strong>0<\/sup>2<\/sub> subsets are countable intersections of UCO subsets by definition.<\/p>\n\n\n\n

    pt<\/strong>(I<\/strong>(L<\/em>)) is a spectral space, hence is in particular sober and locally compact. If L<\/em> is countable (as in the case of the Lindenbaum algebra of first-order logic), then the base of open sets Oa<\/sub><\/em> of pt<\/strong>(I<\/strong>(L<\/em>)) is countable, hence pt<\/strong>(I<\/strong>(L<\/em>)) is second countable. Every second countable, sober locally compact space is quasi-Polish, and every \u03a0<\/strong>0<\/sup>2<\/sub> subset of a quasi-Polish space is quasi-Polish [5]. That is extra structure that allows one to prove some more completeness results, especially on probabilistic logics. A remarkable paper in that respect is [7], which uses a variant of this (and other things…) in a crucial way.<\/p>\n\n\n\n

      \n
    1. Helena Rasiowa and Roman Sikorski, The Mathematics of Metamathematics. PWN\u2013PolishScientific Publishers, Warsaw, 1963.<\/li>\n\n\n\n
    2. Robert Goldblatt. 2012. Topological Proofs of some Rasiowa-Sikorski Lemmas. Studia Logica, 100, 1\u201318.<\/li>\n\n\n\n
    3. Sabine G\u00f6rnemann. 1971. A Logic Stronger than Intuitionism. Journal of Symbolic Logic, 36(2), 249\u2013261.<\/li>\n\n\n\n
    4. Cecylia Rauszer and Bogdan Sabalski. 1975. Notes on the Rasiowa-Sikorski Lemma. Studia Logica, 34(3), 265\u2013268.<\/li>\n\n\n\n
    5. Matthew de Brecht.  Quasi-Polish spaces<\/a>.  Annals of Pure and Applied Logic, Volume 164, Issue 3<\/a>, March 2013, pages 356-381. <\/li>\n\n\n\n
    6. Kurt G\u00f6del. Die Vollst\u00e4ndigkeit der Axiome des logischen Funktionenkalk\u00fcls. Monatshefte f\u00fcr Mathematik<\/a><\/em> (in German). Volume 37<\/strong>, Issue 1, 1930, 349\u2013360.<\/li>\n\n\n\n
    7. Dexter Kozen<\/a>, Kim G. Larsen<\/a>, Radu Mardare<\/a>, and Prakash Panangaden<\/a>.  Stone duality for Markov processes<\/a>.  In 28th Annual ACM\/IEEE Symposium on Logic in Computer Science<\/a>.  IEEE Computer Society Press, 2013, 321\u2013330. <\/li>\n<\/ol>\n\n\n
      \n
      \"jgl-2011\"<\/figure>\n<\/div>\n\n\n

      \u2014 Jean Goubault-Larrecq<\/a> (December 23rd, 2019)<\/p>\n","protected":false},"excerpt":{"rendered":"

      Well, first, a Merry Christmas and a Happy New Year! Let L be a bounded distributive lattice. Given any element u of L, and any element v of L such that u\u2270v, there is a (join-)prime filter containing u and … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_crdt_document":"","footnotes":""},"class_list":["post-2152","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/2152","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2152"}],"version-history":[{"count":24,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/2152\/revisions"}],"predecessor-version":[{"id":5906,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/2152\/revisions\/5906"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2152"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

    If L<\/em> is a Boolean algebra, then L<\/em> is, in particular, a bounded distributive lattice. In fact, all suprema that exist automatically distribute over \u22c0. This is because every Boolean algebra is a Heyting algebra (see Exercise 9.5.22 in the book<\/a>), with u<\/em> \u21d2 v<\/em> defined as \u00acu<\/em> \u22c1 v<\/em>. Recall that residuation \u21d2 is uniquely determined by the fact that for every d<\/em> in L<\/em>, u<\/em> \u22c0 d<\/em> \u2264 v<\/em> if and only if d<\/em> \u2264 u<\/em> \u21d2 v<\/em>. In other words, u<\/em> \u22c0 _ is left adjoint to u<\/em> \u21d2 _. And left adjoints preserve all colimits (all suprema, here). Explicitly, imagine that D<\/em> is a family with a supremum sup D<\/em>, and let u<\/em> be any element of L<\/em>. Then u<\/em> \u22c0 sup D<\/em> is an upper bound of {u<\/em> \u22c0 d<\/em> | d<\/em> \u2208 D<\/em>}. Given any other upper bound v<\/em> of {u<\/em> \u22c0 d<\/em> | d<\/em> \u2208 D<\/em>}, we have u<\/em> \u22c0 d<\/em> \u2264 v<\/em> for every d<\/em> in D<\/em>, hence d<\/em> \u2264 u<\/em> \u21d2 v<\/em> for every d<\/em> in D<\/em>, namely sup D<\/em> \u2264 u<\/em> \u21d2 v<\/em>, and therefore u \u22c0 sup D<\/em> \u2264 v<\/em>.<\/p>\n\n\n\n

    The proof (1\/5): Stone enters the stage<\/h3>\n\n\n\n

    We now prove this. First, instead of looking for a (join-)prime filter, we will look for a (meet-)prime ideal. This is equivalent, in the sense that the complement of a meet-prime ideal is a join-prime filter. (Exercise!)<\/p>\n\n\n\n

    Now, what we are looking for, modulo that change of point of view, is a (meet-)prime ideal x<\/em> that contains v<\/em>, does not contain u<\/em>, and respects all the sup situations D<\/em> in L<\/em>, in the sense that (D<\/em> \u2286 x<\/em> implies sup D<\/em> \u2208 x<\/em>).<\/p>\n\n\n\n

    What is (meet-)prime ideal? That is an element of the space pt<\/strong>(I<\/strong>(L<\/em>)), the Stone dual of I<\/strong>(L<\/em>), if you follow Corollary 8.1.21 of the book<\/a>. (This is why I wrote it as x<\/em> above: this is really a point of a topological space.)<\/p>\n\n\n\n

    If you have a look at Exercise 9.5.12 in the book<\/a>, you will see that I<\/strong>(L<\/em>) is an algebraic fully arithmetic complete lattice, and Exercise 9.5.19 says (among other things) that pt<\/strong>(I<\/strong>(L<\/em>)) is a spectral space. Goldblatt looks directly at its patch space, which is a Priestley space (see Theorem 9.5.24 in the book<\/a>). We will make good use of that wealth of structure. Notably, pt<\/strong>(I<\/strong>(L<\/em>))patch<\/sup> is compact Hausdorff.<\/p>\n\n\n\n