Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

February 5, 2014

Galois Correspondences and Enriched Adjunctions

Posted by Simon Willerton

This is the fourth post in a series on categorical ideas related to formal concept analysis (the other posts are linked below). I want to bring together the ideas of the previous posts and tell you what relations and Galois correspdonences have to do with profunctors and nuclei. To do that I have to tell you what happens when you think of posets as categories enriched over the category of truth values.

Here is a picture of a poset, with xyx\le y if you can climb up the arrows from xx to yy.

a poset

The picture can also be interpreted as representing a thin category, that is a category with at most one morphism between each pair of objects.

Most people who know what a category is know that a thin category is the same thing as a poset; with an arrow xyx\to y corresponding to the relation xyx\le y. However, despite being well-known, this fact is also not strictly true. You have to be wary of the antisymmetry axiom.

In a poset the antisymmetry axiom asserts that if aba\le b and bab\le a then a=ba=b, but this translates in a thin category to having morphisms aba\to b and bab\to a implying that a=ba=b and that is not true in general, all you can say is that aa is isomorphic to bb.

A poset-without-antisymmetry is called a preorder, and the true fact is that thin categories correspond to preorders (and posets correspond to skeletal, thin categories).

Less well-known than the above not-entirely-true fact, at least according to my unscientific straw poll of mathematicians, is that a category enriched over truth values is the same thing as a preorder. Although this seems, superficially, to be the same as the previous fact, it does have some deeper connotations due to the depths of enriched category theory. It is some of these depths that I want to start to explore here.

This follows on from three previous posts, but doesn’t require you to have read the other ones — unless you want to appreciate the punchline!

  1. In The Nucleus of a Profunctor: Some Categorified Linear Algebra I gave a construction which starts with an enriched profunctor between two enriched categories and gives rise to an adjoint equivalence between certain presheaves and copresheaves on the two enriched categories. This is the nucleus construction.

  2. In Formal Concept Analysis I gave a construction which starts with a relation between two sets and gives rise to a Galois correspondence between certain sets of subsets of the two sets.

  3. In Classical Dualities and Formal Concept Analysis I gave examples of this construction popping up all over mathematics.

In this post I’ll try to convince you that the second construction is just an example of the first. I’ll do this by explaining what familiar (?!) concepts from ordinary category theory become when you work in categories enriched over truth values. This is summarized in the following dictionary.

category preorder functor order preserving map set of natural transformations domination relation internal hom object in Set logical implication in Truth presheaf downward closed subset (downset) copresheaf upward closed subset (upset) category of presheaves downsets ordered by inclusion category of opcopresheaves upsets ordered by containment category of presheaves on a set powerset of a set ordered by inclusion category of opcopresheaves on a set powerset of a set ordered by containment adjunction Galois connection profunctor relation nucleus of a profunctor Galois correspondence from a relation     \array {\arrayopts{ \colalign{left left} \rowlines{solid} } \\ \text{category }&\text{ preorder}\\ \text{functor }&\text{ order preserving map}\\ \text{set of natural transformations}&\text{domination relation}\\ \text{internal hom object in Set }&\text{ logical implication in Truth}\\ \text{presheaf }&\text{ downward closed subset (downset)}\\ \text{copresheaf }&\text{ upward closed subset (upset)}\\ \text{category of presheaves }&\text{ downsets ordered by inclusion}\\ \text{category of opcopresheaves }&\text{ upsets ordered by containment}\\ \text{ category of presheaves on a set }&\text{ powerset of a set ordered by inclusion}\\ \text{ category of opcopresheaves on a set } & \text {powerset of a set ordered by containment}\\ \text{adjunction }&\text{ Galois connection}\\ \text{profunctor }&\text{ relation}\\ \text{nucleus of a profunctor }&\text{ Galois correspondence from a relation}\\  &   }

In the rest of this post (which has got quite long) I will just explain how the translation arises. It is basic enriched category theory, so if you already understand the above dictionary you can stop reading now!

Next time I hope to explain when you apply the nucleus construction when you enrich over things more like the real numbers.

The enriching category Truth\mathrm{Truth}

The category of truth values, Truth\mathrm{Truth}, has two objects: true\mathrm{true} and false\mathrm{false}. The morphisms correspond to ‘logical entailment’ which is what working mathematicians would usually refer to as ‘implication’ but logicians reserve ‘implication’ for logical operation, we’ll see this below. Entailment is written \vdash (pronounced ‘entails’), so we have falsetrue\mathrm{false}\vdash \mathrm{true} corresponds to the only non-identity morphism in Truth\mathrm{Truth}. So the category can be simply pictured as follows. falsetrue \mathrm{false}\longrightarrow \mathrm{true} We can make this category of truth values into a monoidal category by using logical ‘and’ as the monoidal product; I’ll write this as \wedge .

Categories

A category enriched over Truth\mathrm{Truth}, 𝒞\mathcal{C}, consists of a set ob𝒞\text {ob}\mathcal{C} and for each c,c𝒞c,c'\in \mathcal{C} we have the ‘hom-object’ 𝒞(c,c){true,false}\mathcal{C}(c,c')\in \{ \mathrm{true}, \mathrm{false}\} . We should think of 𝒞(c,c)\mathcal{C}(c,c') as being the truth of a relation ccc\le c'. We need composition morphisms in this category, so for each triple, c,c,cob𝒞c,c',c''\in \text {ob}\mathcal{C} we need a morphism in truth values 𝒞(c,c)𝒞(c,c)𝒞(c,c); \mathcal{C}(c',c'')\otimes \mathcal{C}(c,c')\to \mathcal{C}(c,c''); in this context it means we have an entailment 𝒞(c,c)𝒞(c,c)𝒞(c,c), \mathcal{C}(c',c'')\wedge \mathcal{C}(c,c')\vdash \mathcal{C}(c,c''), or, in other words, if ccc\le c' and ccc'\le c'' then ccc\le c''. So we have a transitive relation. We also need an identity for each c𝒞c\in \mathcal{C}, generally speaking this means we need a morphism (where 11 is the monoidal unit) 1𝒞(c,c); 1\to \mathcal{C}(c,c); in this context it means true𝒞(c,c), \mathrm{true}\vdash \mathcal{C}(c,c), or, in other words, ccc\le c. So the relation is also reflexive. Thus we have a preorder.

Conversely, a preorder gives rise to a Truth\mathrm{Truth} category.

Slogan: Truth\mathrm{Truth}-categories correspond to preorders.

Functors

There is a notion of an enriched functor which we can look at in this context. If we have two Truth\mathrm{Truth}-categories 𝒞\mathcal{C} and 𝒟\mathcal{D} then a Truth\mathrm{Truth}-functor consists of a function F:ob𝒞ob𝒟F\colon \text {ob}\mathcal{C}\to \text {ob}\mathcal{D} and, for each pair c,cob𝒞c,c'\in \text {ob}\mathcal{C}, a morphism in Truth\mathrm{Truth} 𝒞(c,c)𝒟(F(c),F(c)); \mathcal{C}(c,c')\to \mathcal{D}(F(c),F(c')); using square brackets to mean ‘the truth value of’ this is the same as [cc][F(c)F(c)], [c\le c']\vdash [F(c)\le F(c')], or, in other words, FF preserves the order.

Slogan: Truth\mathrm{Truth}-functors correspond to order preserving maps.

Natural transformation objects

Enriched category theory is richer if we enrich over a complete closed, symmetric monoidal category. If the category is complete then we means that we can make the collection of enriched functors between two enriched categories into an enriched category. If we have F,G:𝒞𝒟F,G\colon \mathcal{C}\to \mathcal{D} then we have a hom-object [𝒞,𝒟](F,G)[\mathcal{C},\mathcal{D}](F,G) and this is given by an end [𝒞,𝒟](F,G)= c𝒟(F(c),G(c)). [\mathcal{C},\mathcal{D}](F,G)=\int _{c} \mathcal{D}(F(c),G(c)). In the context of enriching over Truth\mathrm{Truth}, this end is just a big ‘and’, or a ‘for all’, if you prefer. [𝒞,𝒟](F,G)= c𝒟(F(c),G(c)). [\mathcal{C},\mathcal{D}](F,G)=\bigwedge _{c} \mathcal{D}(F(c),G(c)). Rewriting this is terms of truth values of the relations we get that this means [FG] c[F(c)G(c)]. [F\le G] \coloneqq \bigwedge _{c} [F(c)\le G(c)]. In other words, given preorders 𝒞\mathcal{C} and 𝒟\mathcal{D}, there is a canonical preorder on the set of order preserving functions 𝒞𝒟\mathcal{C}\to \mathcal{D}, and this is FGF\le G if and only if F(c)G(c)F(c)\le G(c) for all cc. We can say that FF is dominated by GG if FGF\le G.

Slogan: The Truth\mathrm{Truth}-natural transformation object corresponds to the domination relation.

The closed structure

If the enriching category is closed then it can be considered as a category enriched over itself. There is a small problem here with type checking and we should be more precise. If 𝒱\mathcal{V} is closed then there is an internal hom functor [,]:𝒱 op×𝒱𝒱[-,-]\colon \mathcal{V}^{\mathrm{op}}\times \mathcal{V}\to \mathcal{V}. We form a 𝒱\mathcal{V}-category 𝒱¯\overline{\mathcal{V}} with the same objects as 𝒱\mathcal{V} but with the hom-object given by the internal hom 𝒱¯(v,w):=[v,w]\overline{\mathcal{V}}(v,w):=[v,w]. People often use the same notation for 𝒱\mathcal{V} and 𝒱¯\overline{\mathcal{V}}; this is potentially confusing, but so you should do this with some care.

The category of truth values, Truth\mathrm{Truth}, is closed and the internal hom is given by ‘logical implication’: [a,b]:=ab[a,b]:=a\Rightarrow b. Here implication is understood in the logical operation sense and not the deductive sense (that’s what we are using entails for). So, using brackets purely for clarity, (truetrue) =true; (truefalse) =false; (falsetrue) =true; (falsefalse) =true. \begin{aligned} (\mathrm{true}\Rightarrow \mathrm{true}) &=\mathrm{true};& (\mathrm{true}\Rightarrow \mathrm{false})&=\mathrm{false};\\ (\mathrm{false}\Rightarrow \mathrm{true})&=\mathrm{true};& (\mathrm{false}\Rightarrow \mathrm{false})&=\mathrm{true}. \end{aligned}

Slogan: Internal hom for Truth\mathrm{Truth} is implication.

We know that Truth\mathrm{Truth}-categories are the same as preorders, so this gives a natural preorder on the set {true,false}\{ \mathrm{true},\mathrm{false}\} .

Slogan: The Truth\mathrm{Truth}-category structure on Truth\mathrm{Truth} corresponds to the preorder falsetrue\mathrm{false}\le \mathrm{true}.

Presheaves and copresheaves

As we are considering a closed enriching category 𝒱\mathcal{V}, we can think of 𝒱\mathcal{V} as a 𝒱\mathcal{V}-category and consider 𝒱\mathcal{V}-functors into 𝒱\mathcal{V}. This is like considering scalar valued functions on a vector space.

A presheaf on 𝒞\mathcal{C} is a 𝒱\mathcal{V}-functor P:𝒞 op𝒱P\colon \mathcal{C}^{\mathrm{op}}\to \mathcal{V} and a copresheaf is a 𝒱\mathcal{V}-functor Q:𝒞𝒱Q\colon \mathcal{C}\to \mathcal{V}. In the context of preorders and truth values, a presheaf is an order-reversing function P:𝒞{true,false}P\colon \mathcal{C}\to \{ \mathrm{true},\mathrm{false}\} and a copresheaf is an order-preserving function Q:𝒞{true,false}Q\colon \mathcal{C}\to \{ \mathrm{true},\mathrm{false}\} .

Knowing a function to {true,false}\{ \mathrm{true},\mathrm{false}\} is the same as knowing the preimage of true\mathrm{true}, so we can identify a function P:𝒞{true,false}P\colon \mathcal{C}\to \{ \mathrm{true},\mathrm{false}\} with the subset P˜=P 1(true)𝒞\tilde{P}=P^{-1}(\mathrm{true})\subseteq \mathcal{C}. The order reversing condition if cc then P(c)P(c) \text {if }\, c\le c' \, \text { then } \, P(c')\le P(c) translates into if cc and cP˜ then cP˜. \text {if }\, c\le c'\, \text { and }c'\in \tilde{P}\, \text { then }\, c\in \tilde{P}. So P˜\tilde{P} is a downward closed subset of the preorder 𝒞\mathcal{C} and all downward closed subsets arise in this way.

Similarly if Q:𝒞TruthQ\colon \mathcal{C}\to \mathrm{Truth} is a copresheaf then it corresponds to an upward closed subset Q˜=Q 1(true)\tilde{Q}=Q^{-1}(\mathrm{true}).

Because presheaves are Truth\mathrm{Truth}-functors, we canonically have the domination relation between them. Given presheaves P,P:𝒞 opTruthP,P'\colon \mathcal{C}^{\mathrm{op}}\to \mathrm{Truth} then PPif and only ifP(c)P(c) for all c𝒞, P\le P'\quad \text {if and only if}\quad P(c)\le P'(c)\text { for all }c\in \mathcal{C}, which when translated to downward closed sets becomes PPif and only ifP˜P˜. P\le P'\quad \text {if and only if}\quad \tilde{P}\subseteq \tilde{P'}.

Slogan: The poset of presheaves on a preorder can be identified with the set of downward closed subsets equipped with the subset ordering.

Similarly, the domination relation on copresheaves corresponds to inclusion of the associated upward closed subsets. However, it is usually the opposite of the category of copresheaves that crops up, so this has the opposite relation.

Slogan: The poset of opcopresheaves on a preorder can be identified with the set of upward closed subsets equipped with the superset ordering.

Sets can be thought of as discrete posets, that is to say, where ccc\le c' if and only if c=cc=c. In that case all subsets are both upward closed and downward closed. In this case, then, the set of copresheaves and the set of presheaves can both be identified with the powerset of the original set.

Slogan: The poset of presheaves on a set is the powerset with the subset ordering; the poset of opcopresheaves on a set is the powerset with the superset ordering

Adjunctions

An enriched adjunction consists of a pair of enriched functors F:𝒞𝒟:G F\colon \mathcal{C}\leftrightarrows \mathcal{D}\colon G together with an isomorphism in 𝒱\mathcal{V}, natural in c𝒞c\in \mathcal{C} and d𝒟d\in \mathcal{D} 𝒟(F(c),d)𝒞(c,G(d)). \mathcal{D}(F(c),d)\cong \mathcal{C}(c,G(d)). This means that when we enrich over the category of truth values we get a Truth-adjunction being a pair of order-preserving maps between posets F:𝒞𝒟:G F\colon \mathcal{C}\leftrightarrows \mathcal{D}\colon G with the condition that F(c)d if and only if cG(d). F(c)\le d \, \text { if and only if }\, c\le G(d). In other words we have the following slogan.

Slogan: A Truth-adjunction is precisely a Galois connection between preorders.

Then the adjoint equivalence induced on the fixed sets is precisely the Galois correspondence induced on the fixed set of the Galois connection.

Profunctors

A profunctor between 𝒱\mathcal{V}-categories 𝒞\mathcal{C} and DD is an a 𝒱\mathcal{V}-functor I:𝒞 op𝒟𝒱. I\colon \mathcal{C}^{\mathrm{op}}\otimes \mathcal{D}\to \mathcal{V}. We should remind ourselves what the definition of the tensor product of 𝒱\mathcal{V}-cateogries is. The set of objects of 𝒜\mathcal{A}\otimes \mathcal{B} is the set of ordered pairs ob𝒜×ob\text {ob}\mathcal{A}\times \text {ob}\mathcal{B} and the hom-sets are given by 𝒜((a,b),(a,b)):=𝒜(a,a)(b,b). \mathcal{A}\otimes \mathcal{B}((a,b),(a',b')):=\mathcal{A}(a,a')\otimes \mathcal{B}(b,b'). It is perhaps worth noting that in order to define composition we will need that 𝒱\mathcal{V} has some extra structure such as being symmetric or braided.

When enriching over truth values, this means that for preorders 𝒜\mathcal{A} and \mathcal{B} the preorder on 𝒜×\mathcal{A}\times \mathcal{B} is given by (a,b)(a,b) if and only if aaandbb. (a,b)\le (a',b')\quad \text { if and only if }\quad a\le a' \, \, \text {and}\, \, b\le b'. A profunctor in the Truth\mathrm{Truth} case can then be identified with a subset of 𝒞×𝒟\mathcal{C}\times \mathcal{D} which is upward closed. Writing cdc\preceq d for I(c,d)I(c,d), we have: ifcdand(c,d)(c,d)thencd. \text {if}\, \, c\preceq d\, \, \text {and}\, \, (c,d)\le (c',d')\, \, \text {then}\, \, c'\preceq d'. This can make more sense if we expand it out: ifccddthencd. \text {if}\, \, c'\le c\preceq d \le d' \, \, \text {then}\, \, c'\preceq d'. Slogan: Profunctors between preorders correspond to relations extending the preorders

Nuclei

In the first post in this sequence I showed that a profunctor II gives rise to an adjunction between presheaves and opcopresheaves, and thus to an adjoint equivalence between the fixed sets of the adjunction.

In the third post I showed how a relation between sets gives rise to a Galois connection between the powersets and thus to a Galois correspondence between the sets of closed subsets. I also gave several examples of correspondences around different areas of maths that arise in this way.

I will leave it to the interested reader to show that the Galois correspondence construction is what you get when you apply the profunctor nucleus construction to the situation of discrete Truth\mathrm{Truth}-categories. It should drop out from the dictionary.

Slogan: The nucleus of a profunctor between discrete categories corresponds to the Galois correspondence between the closed subsets coming from a relation between two sets.

That’s not a very snappy slogan to end with, I grant you.

Next time

In the next post I will show how costructing the nucleus of a profunctor when you enrich over something like the real numbers instead of truth values gives rise to some dualities in other areas of maths.

Posted at February 5, 2014 11:04 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2692

16 Comments & 1 Trackback

Re: Galois Correspondences and Enriched Adjunctions

Hi Simon. I just sent the following by email, which perhaps I shouldn’t have done as I’m on strike, and got back an autoreply saying that you wouldn’t be reading your email as you’re on strike. But perhaps you’ll read this…

Could you make the inserted graphic in your latest post a bit narrower? This is what happens on my browser. The graphic doesn’t appear until below the bottom of the right-hand menu bar, which means I have to scroll down five times in order to see it (and the rest of the Cafe front page). If the image was about 10% narrower, it would be fine, but who knows what happens with other people’s browsers. I guess it could be about 50% of its current width and still be legible.

Thanks!

Tom

Posted by: Tom Leinster on February 6, 2014 12:04 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Sorry, I got impatient and did it myself. It’s now 300 pixels wide, down from 400. Hope you don’t mind.

Posted by: Tom Leinster on February 6, 2014 12:19 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Oooh, you are impatient! Of course, that’s absolutley fine. I’m usually quite careful about such things, but not this time, apparently.

Posted by: Simon Willerton on February 6, 2014 5:07 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Mr Willerton, it’s funny how often I find that you are the author of the posts I find more interesting here on nn-cafe’ (this, the entry about ends, “Nucleus of a profunctor”,…). This time the sensation is even stronger: like in the case of ends, I really would have liked to write a note on the same spirit of this post, since it is kind of “evident” to my intuition that there’s a thin line connecting all these arguments (profunctors, the calculus of ends and the “negative thinking” you exploited here).

So I must say: thank you! You confirm this sensation (and the taste of an expert is far better than any tentative explanation I could have written)! :)

Posted by: Fosco Loregian on February 6, 2014 8:04 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Fosco, thank you for your kind words. It’s nice to know someone is reading and enjoying this stuff! One good thing about the Café – and other joint blogs – is that you get various different perspectives and more chances of finding someone of similar tastes.

Posted by: Simon Willerton on February 6, 2014 9:24 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

This is great! It is actually making me think I understand something–so feel free to disabuse me of that notion. I want to define entailment as follows: “A compound statement S entails a second compound statement P” when the implication “S implies P” is a tautology: true for all values (true/false) of the inputs to the two compound statements S and P.

Thus the tautology “((S implies P) and (P implies Q)) implies (S implies Q)” can be rephrased “((S implies P) and (P implies Q)) entails (S implies Q)”, and that describes composition in the closed category Truth.

Posted by: stefan on February 6, 2014 11:33 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Stefan, when talking about logic I’m on slightly shakey ground. However, let me give you my thoughts on the matter.

You would normally understand what entailment means in your logic first. So the compound statement SS entails the compound statement PP if you can deduce PP from SS using the rules of deduction in your logical system.

And we define SPS \implies P to be true unless PP is false and SS is true in which case we define it to be false.

Given those definitions, it then follow that implication is adjoint to the ‘and’ operation \wedge : RSPprecisely whenR(SP). R\wedge S \vdash P\quad \text {precisely when}\quad R\vdash (S\implies P). This is known as the Deduction (Meta-)Theorem.

As you say, there is a tautology ((SP)(PQ))(SQ). ((S \implies P) \wedge (P \implies Q)) \implies (S \implies Q). Being a tautology means we can deduce it from ‘nothing’, which means we can deduce it from the fact that true is a tautology: true((SP)(PQ))(SQ). \mathrm{true}{\vdash }((S \implies P) \wedge (P \implies Q)) \implies (S \implies Q). By the adjunction this is equivalent to true((SP)(PQ))(SQ). \mathrm{true}\wedge ((S \implies P) \wedge (P \implies Q)) {\vdash }(S \implies Q). In other words, this is (SP)(PQ)(SQ), (S \implies P) \wedge (P \implies Q) {\vdash }(S \implies Q), which is indeed the composition for the internal hom in the closed category Truth\mathrm{Truth}.

Does that help?

Posted by: Simon Willerton on February 9, 2014 4:12 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

That does help. So in propositional logic, entailment arises from tautology: if for compound statements PP and QQ the implication PQP\Rightarrow Q is a tautology, then PP entails QQ.

I guess other logics would have different interpretations of the concept of entailment.

Posted by: stefan on February 10, 2014 9:54 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

So in propositional logic, entailment arises from tautology

I think that’s backwards. It’s true that in propositional logic with an implication connective, entailment and implication are inter-relatable, but entailment is the basic notion of the deductive system, while implication (hence tautology) is a connective that is part of the system like conjunction, disjunction, etc.

Posted by: Mike Shulman on February 10, 2014 10:57 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Ok, right. Maybe I should have said that the judgementPP entails QQ” about two statements in the propositional logic can be restated as the equivalent judgement “the statement PQP\Rightarrow Q is a tautology.” (that is, true for any truth values of the components of PP and QQ).

Posted by: stefan on February 11, 2014 8:56 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

One pervasive comcept in posets are those that are chain-complete (cpo), which I think is equivalently directed complete (dcpo). Do they fit into this framework?

Posted by: Mozibur Ullah on February 9, 2014 12:16 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

The short answer is I don’t know! I have seen dcpos mentioned in various places, but haven’t got round to figuring out what they are. I suspect someone round here will know whether or not they relate to this framework though.

Posted by: Simon Willerton on February 9, 2014 4:17 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Here is a question that I should try to answer myself, but in case it is obvious I’ll put it here!

A downset of a preorder PP is connected if there is a chain of relations between any two elements, that is, connected in the digraph picture.

A downset of a preorder PP is filled if whenever it contains all the elements covered by xPx\in P, it must also contain either xx or some yPy\in P that covers the same elements as xx.

So are these concepts easily added to the dictionary? I should mention that the first is in common use, I think, but the second is just in one paper (mine!).

Posted by: stefan on February 11, 2014 9:19 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Oops–I shouldn’t have said “chain,” just string.

Posted by: stefan on February 11, 2014 9:22 PM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

I usually find it a little confusing when people draw a distinction between entailment and logical implication. Logical implication is a proposition in a propositional calculus, and entailment is a metalanguage statement about propositions, is that how it goes?

Also, in your dictionary, you call the relation in an opcopresheaf “containment”. Then in your text it seems like you are describing what I would call “reverse inclusion”. For me, {1,{2}}\{1,\{2\}\} contains {2}\{2\} but does not include it (denoted {2}{1,{2}}\{2\}\in\{1,\{2\}\}, but {2}{1,{2}}\{2\}\nsubseteq\{1,\{2\}\}), and it includes {1}\{1\} but does not contain it (denoted {1}{1,{2}}\{1\}\subseteq\{1,\{2\}\}, but {1}{1,{2}}\{1\}\notin\{1,\{2\}\}), and hence I would say that {1}\{1\} reverse includes, or “is included in” {1,{2}}\{1,\{2\}\}. But do you intend “containment” to be synonymous with my “reverse inclusion”?

Posted by: Joe Hannon on March 12, 2014 12:51 AM | Permalink | Reply to this

Re: Galois Correspondences and Enriched Adjunctions

Joe, I too get confused about the distinction between entailment and implication, but am learning to get less confused.

Logical implication is a proposition in a propositional calculus, and entailment is a metalanguage statement about propositions, is that how it goes?

Well, logical implication is a connective in propositional calculus, so makes a new proposition out of two olds ones, but, essentially, yes, what you write is the case. We had a discussion about this at the post Entailment and Implication. [I’ve recently started to think about certain kinds of generalized logic and am starting to get more confused again…]

Also, in your dictionary, you call the relation in an opcopresheaf “containment”.

As you point out, this is probably not the best choice of words! I wanted something opposite to inclusion, ‘AA contains BB’ is opposite to ‘AA is included in BB’. Unfortunately, ‘AA contains BB’ is not opposite to ‘AA includes BB’! I can’t think of a better term off the top of my head now.

Posted by: Simon Willerton on March 15, 2014 3:25 PM | Permalink | Reply to this
Read the post Fuzzy logic and enriching over the category [0,1]
Weblog: The n-Category Café
Excerpt: Watch me try to understand fuzzy logic from an enriched category theory perspective
Tracked: March 15, 2014 6:01 PM

Post a New Comment