Algebras of the partial-map classifier monad in 1-toposes

Algebras of the partial-map classifier monad in 1-toposes

[Martin Escardo]

[-- Attachment #1: Type: text/plain, Size: 2735 bytes --]

Dear 1-topos theorists,

Anders Kock has a nice paper from the last millennium (1990), about

Algebras for the partial map classifier monad
https://link.springer.com/chapter/10.1007/BFb0084225<https://url.au.m.mimecastprotect.com/s/wVLaCmO5wZsjM8gvRSBigFRC8TE?domain=link.springer.com>
https://tildeweb.au.dk/au76680/jonna5.pdf<https://url.au.m.mimecastprotect.com/s/iGtBCnx1Z5U7WgPn6UZsxFJser6?domain=tildeweb.au.dk>

As he remarks and is well known, and also trivial, in a boolean topos,
all algebras are free. Then he goes on to say many interesting things
that hold in all 1-toposes.

Jon Sterling recently conjectured that, in an arbitrary topos, not all
algebras are free.

I came up with an example. My question is whether this example is well
known, and, moreover, whether more examples are known.

First of all, the subobject classifier Ω is a free algebra on one generator.

If you think of Ω as the powerset of the terminal object 𝟙, then the
structure map of Ω as a free algebra is *union*.

(†) But, you can check, also *intersection* exhibits Ω = 𝓟 𝟙 as an algebra.

I have proved that this algebra is free if and only if the principle of
excluded middle holds, that is, the topos is boolean.

Is this known?

Then I wanted to find more counter-examples to "every algebra is a free
algebra".

I tried, first, exponential powers of Ω. But they are free in all toposes.

Then I tried, more generally, arbitrary products of free algebras. But,
again, they are free in all toposes.

Does anybody know a source of more counter-examples? At the moment, the
only counter-example I know is (†).

It is embarrasing to know only one counter-example.

Best wishes,
Martin
PS. I have written my proofs (on paper and) in a proof assistant, namely
Agda (and this is publicly available and advertised in various forums).
So this gives some confidence regarding the above claims. I still have
to write a human-readable version for public consumption, but here I am
more interested in knowning what people already know about this.


You're receiving this message because you're a member of the Categories mailing list group from Macquarie University. To take part in this conversation, reply all to this message.

View group files<https://outlook.office365.com/groups/groupsubscription?source=EscalatedMessage&action=files&smtp=categories%40mq.edu.au&bO=true&GuestId=4eb9b40c-9b3a-48a5-9781-836e5a171e8b>   |   Leave group<https://outlook.office365.com/groups/groupsubscription?source=EscalatedMessage&action=leave&smtp=categories%40mq.edu.au&bO=true&GuestId=4eb9b40c-9b3a-48a5-9781-836e5a171e8b>   |   Learn more about Microsoft 365 Groups<https://aka.ms/o365g>


[-- Attachment #2: Type: text/html, Size: 4802 bytes --]

Re: Algebras of the partial-map classifier monad in 1-toposes

[Richard Garner]

Hi Martin,

Maybe one can look at the Sierpinski topos. In there, if my calculations
are correct, the partial map classifier takes A ---> B to 1+A+B --->
1+B, and an algebra for this monad is a map p: A-->B equipped with a
section s together with points in A and B which are preserved by p and
s.

In this case, Omega seems to have exactly two non-isomorphic algebra
structures, which can be realised by union and intersection.

But for a general p: A-->B, I think there are either:

- no algebra structures (if B is empty or p is non-surjective), or else
- exactly one non-isomorphic algebra structure for each distinct
  cardinality possessed by one of the fibres of p

Indeed, in the second case, pick an element of B whose fibre has the
given cardinality. This is your B-point *. Then use AC to pick a section
s of p, and take the point in A to be s(*). If you chose a different
section, you get an isomorphic algebra. If you chose a different
basepoint in B of the same cardinality, you will again get an isomorphic
algebra.

In particular, Omega(Omega(1)) has one fibre of cardinality 1, one of
cardinality 2 and one of cardinality 3, and so should have three
distinct algebra structures.

All the best,

Richard


Martin Escardo <escardo.martin@gmail.com> writes:

> Dear 1-topos theorists,
>
> Anders Kock has a nice paper from the last millennium (1990), about
>
> Algebras for the partial map classifier monad
> https://link.springer.com/chapter/10.1007/BFb0084225⚠️
> https://tildeweb.au.dk/au76680/jonna5.pdf⚠️
>
> As he remarks and is well known, and also trivial, in a boolean topos, 
> all algebras are free. Then he goes on to say many interesting things 
> that hold in all 1-toposes.
>
> Jon Sterling recently conjectured that, in an arbitrary topos, not all 
> algebras are free.
>
> I came up with an example. My question is whether this example is well 
> known, and, moreover, whether more examples are known.
>
> First of all, the subobject classifier Ω is a free algebra on one generator.
>
> If you think of Ω as the powerset of the terminal object 𝟙, then the 
> structure map of Ω as a free algebra is *union*.
>
> (†) But, you can check, also *intersection* exhibits Ω = 𝓟 𝟙 as an algebra.
>
> I have proved that this algebra is free if and only if the principle of 
> excluded middle holds, that is, the topos is boolean.
>
> Is this known?
>
> Then I wanted to find more counter-examples to "every algebra is a free 
> algebra".
>
> I tried, first, exponential powers of Ω. But they are free in all toposes.
>
> Then I tried, more generally, arbitrary products of free algebras. But, 
> again, they are free in all toposes.
>
> Does anybody know a source of more counter-examples? At the moment, the 
> only counter-example I know is (†).
>
> It is embarrasing to know only one counter-example.
>
> Best wishes,
> Martin
> PS. I have written my proofs (on paper and) in a proof assistant, namely 
> Agda (and this is publicly available and advertised in various forums). 
> So this gives some confidence regarding the above claims. I still have 
> to write a human-readable version for public consumption, but here I am 
> more interested in knowning what people already know about this.

Re: Algebras of the partial-map classifier monad in 1-toposes

[Martin Escardo]

[-- Attachment #1: Type: text/plain, Size: 5121 bytes --]

Hi Richard,

Thanks! This is very interesting and nice.

Although I didn't say this explicitly in my original message, I am
looking for algebras that can be defined in any (elementary) topos (by
diagrams or in the internal language) that are not free in all toposes.

Do you also have examples of those? (Other than the one I gave in the
opening message of this thread.)

I am sure there should be a plentiful supply of algebras that one can
define in all toposes, but which are not free in all toposes.

I guess that such an exploration would lead to a better understanding of
the algebras of this monad in an arbitrary topos. In particular, we may
ask whether Anders Kock's characterization of the algebras as posets
that are complete in a certain way may help to shed light on this question.

Best,
Martin

On 07/01/2026 01:07, Richard Garner wrote:
> Hi Martin,
>
> Maybe one can look at the Sierpinski topos. In there, if my calculations
> are correct, the partial map classifier takes A ---> B to 1+A+B --->
> 1+B, and an algebra for this monad is a map p: A-->B equipped with a
> section s together with points in A and B which are preserved by p and
> s.
>
> In this case, Omega seems to have exactly two non-isomorphic algebra
> structures, which can be realised by union and intersection.
>
> But for a general p: A-->B, I think there are either:
>
> - no algebra structures (if B is empty or p is non-surjective), or else
> - exactly one non-isomorphic algebra structure for each distinct
> cardinality possessed by one of the fibres of p
>
> Indeed, in the second case, pick an element of B whose fibre has the
> given cardinality. This is your B-point *. Then use AC to pick a section
> s of p, and take the point in A to be s(*). If you chose a different
> section, you get an isomorphic algebra. If you chose a different
> basepoint in B of the same cardinality, you will again get an isomorphic
> algebra.
>
> In particular, Omega(Omega(1)) has one fibre of cardinality 1, one of
> cardinality 2 and one of cardinality 3, and so should have three
> distinct algebra structures.
>
> All the best,
>
> Richard
>
>
> Martin Escardo <escardo.martin@gmail.com> writes:
>
>> Dear 1-topos theorists,
>>
>> Anders Kock has a nice paper from the last millennium (1990), about
>>
>> Algebras for the partial map classifier monad
>> https://link.springer.com/chapter/10.1007/BFb0084225⚠️<https://url.au.m.mimecastprotect.com/s/t2jTC2xMRkUpQWNw2TBiQH598-s?domain=link.springer.com>
>> https://tildeweb.au.dk/au76680/jonna5.pdf⚠️<https://url.au.m.mimecastprotect.com/s/y6cTC3QNl1Spvo5QgTDspHQIcSw?domain=tildeweb.au.dk>
>>
>> As he remarks and is well known, and also trivial, in a boolean topos,
>> all algebras are free. Then he goes on to say many interesting things
>> that hold in all 1-toposes.
>>
>> Jon Sterling recently conjectured that, in an arbitrary topos, not all
>> algebras are free.
>>
>> I came up with an example. My question is whether this example is well
>> known, and, moreover, whether more examples are known.
>>
>> First of all, the subobject classifier Ω is a free algebra on one generator.
>>
>> If you think of Ω as the powerset of the terminal object 𝟙, then the
>> structure map of Ω as a free algebra is *union*.
>>
>> (†) But, you can check, also *intersection* exhibits Ω = 𝓟 𝟙 as an algebra.
>>
>> I have proved that this algebra is free if and only if the principle of
>> excluded middle holds, that is, the topos is boolean.
>>
>> Is this known?
>>
>> Then I wanted to find more counter-examples to "every algebra is a free
>> algebra".
>>
>> I tried, first, exponential powers of Ω. But they are free in all toposes.
>>
>> Then I tried, more generally, arbitrary products of free algebras. But,
>> again, they are free in all toposes.
>>
>> Does anybody know a source of more counter-examples? At the moment, the
>> only counter-example I know is (†).
>>
>> It is embarrasing to know only one counter-example.
>>
>> Best wishes,
>> Martin
>> PS. I have written my proofs (on paper and) in a proof assistant, namely
>> Agda (and this is publicly available and advertised in various forums).
>> So this gives some confidence regarding the above claims. I still have
>> to write a human-readable version for public consumption, but here I am
>> more interested in knowning what people already know about this.


You're receiving this message because you're a member of the Categories mailing list group from Macquarie University. To take part in this conversation, reply all to this message.

View group files<https://outlook.office365.com/groups/groupsubscription?source=EscalatedMessage&action=files&smtp=categories%40mq.edu.au&bO=true&GuestId=4eb9b40c-9b3a-48a5-9781-836e5a171e8b>   |   Leave group<https://outlook.office365.com/groups/groupsubscription?source=EscalatedMessage&action=leave&smtp=categories%40mq.edu.au&bO=true&GuestId=4eb9b40c-9b3a-48a5-9781-836e5a171e8b>   |   Learn more about Microsoft 365 Groups<https://aka.ms/o365g>


[-- Attachment #2: Type: text/html, Size: 7841 bytes --]

Re: Algebras of the partial-map classifier monad in 1-toposes

[Richard Garner]

Hi Martin,

Oh right, I see! That's a very interesting question. I think I have a
source of examples of algebras, though I'm not sure if they are free or
not (I would guess not in general).

Write L for the partial map classifier monad.

Write P for the power-object monad.

The unit map X >--> LX is monic for any object, and each PX is
injective. So for each X, we can extend the map P(eta^L_X): PX --> PLX
along the monic eta^L_{PX}: PX >---> LPX to get a map LPX --> PLX.

If we do this extension in a random way, there would be no particular
reason for it to be well-behaved. But there is an "obvious" way to take
extensions into P, and I *think* if we take this way, it gives a
distributive law of the endofunctor P over the monad L.

The unit axiom is obvious (it's how we defined things). For the axiom
expressing compatibility with the multiplication of L, my argument
involves figuring out what postcomposition with LPX ---> PLX does.

A map A ---> LPX is a partial map A <--< A' ---> PX, which means giving
a subobject A' <= A together with a relation R <= A' x X. On the other
hand, a map A ---> PLX is a relation S <= A x LX.

If I have this right, postcomposition with LPX --> PLX acts by sending
(A', R) to the relation

R >---> A' x X >---> A x X >--1 x eta--> A x LX

and now we can use this to show that both composites LLPX ---> PLX are
the same map.

Assuming this is right, P lifts to an endofunctor on the category of
L-algebras (it doesn't lift to a monad, because the distributive law
axiom expressing compatibility with the unit of P doesn't hold -- which
doesn't seem that surprising, since the power-set monad on Set doesn't
distribute over itself for the same reason).

Now my guess (based off feels) is that if you take the terminal
L-algebra 1 and hit it with P, you get Omega with the meet L-algebra
structure. The analogy is with the distributive law of P over the
commutative monoid monad in Set: if you see P as adding all meets, then
for a monoid X the monoid structure on PX is given by \bigwedge U .
\bigwedge V = \bigwedge {uv : u \in U, v in V}. Similarly in this case I
would guess that the L-algebra "join" operation on P1 (indexed by a
subobject phi <= 1) is given by

  "Join"_{x in phi} psi_x
= "Join"_{x in phi} \bigwedge_{y in psi_x} {*}
= \bigwedge_{f: \bigwedge_{x in phi} psi_x} "Join"_{x in phi} {*}
= \bigwedge_{f: \bigwedge_{x in phi} psi_x} {*}
= \bigwedge_{x in phi} psi_x

(here line 2 to line 3 is the application of the distributive law, and 3
to 4 is the trivial L-algebra structure of 1). Note that the terminal
L-algebra 1 = L0 is free. So potentially applying P to other free
L-algebras gives more examples of non-free L-algebras!

Richard



Martin Escardo <escardo.martin@gmail.com> writes:

> Hi Richard,
>
> Thanks! This is very interesting and nice.
>
> Although I didn't say this explicitly in my original message, I am 
> looking for algebras that can be defined in any (elementary) topos (by 
> diagrams or in the internal language) that are not free in all toposes.
>
> Do you also have examples of those? (Other than the one I gave in the 
> opening message of this thread.)
>
> I am sure there should be a plentiful supply of algebras that one can 
> define in all toposes, but which are not free in all toposes.
>
> I guess that such an exploration would lead to a better understanding of 
> the algebras of this monad in an arbitrary topos. In particular, we may 
> ask whether Anders Kock's characterization of the algebras as posets 
> that are complete in a certain way may help to shed light on this question.
>
> Best,
> Martin
>
> On 07/01/2026 01:07, Richard Garner wrote:
>> Hi Martin,
>>
>> Maybe one can look at the Sierpinski topos. In there, if my calculations
>> are correct, the partial map classifier takes A ---> B to 1+A+B --->
>> 1+B, and an algebra for this monad is a map p: A-->B equipped with a
>> section s together with points in A and B which are preserved by p and
>> s.
>>
>> In this case, Omega seems to have exactly two non-isomorphic algebra
>> structures, which can be realised by union and intersection.
>>
>> But for a general p: A-->B, I think there are either:
>>
>> - no algebra structures (if B is empty or p is non-surjective), or else
>> - exactly one non-isomorphic algebra structure for each distinct
>> cardinality possessed by one of the fibres of p
>>
>> Indeed, in the second case, pick an element of B whose fibre has the
>> given cardinality. This is your B-point *. Then use AC to pick a section
>> s of p, and take the point in A to be s(*). If you chose a different
>> section, you get an isomorphic algebra. If you chose a different
>> basepoint in B of the same cardinality, you will again get an isomorphic
>> algebra.
>>
>> In particular, Omega(Omega(1)) has one fibre of cardinality 1, one of
>> cardinality 2 and one of cardinality 3, and so should have three
>> distinct algebra structures.
>>
>> All the best,
>>
>> Richard
>>
>>
>> Martin Escardo <escardo.martin@gmail.com> writes:
>>
>>> Dear 1-topos theorists,
>>>
>>> Anders Kock has a nice paper from the last millennium (1990), about
>>>
>>> Algebras for the partial map classifier monad
>>> https://link.springer.com/chapter/10.1007/BFb0084225⚠️⚠️
>>> https://tildeweb.au.dk/au76680/jonna5.pdf⚠️⚠️
>>>
>>> As he remarks and is well known, and also trivial, in a boolean topos,
>>> all algebras are free. Then he goes on to say many interesting things
>>> that hold in all 1-toposes.
>>>
>>> Jon Sterling recently conjectured that, in an arbitrary topos, not all
>>> algebras are free.
>>>
>>> I came up with an example. My question is whether this example is well
>>> known, and, moreover, whether more examples are known.
>>>
>>> First of all, the subobject classifier Ω is a free algebra on one generator.
>>>
>>> If you think of Ω as the powerset of the terminal object 𝟙, then the
>>> structure map of Ω as a free algebra is *union*.
>>>
>>> (†) But, you can check, also *intersection* exhibits Ω = 𝓟 𝟙 as an algebra.
>>>
>>> I have proved that this algebra is free if and only if the principle of
>>> excluded middle holds, that is, the topos is boolean.
>>>
>>> Is this known?
>>>
>>> Then I wanted to find more counter-examples to "every algebra is a free
>>> algebra".
>>>
>>> I tried, first, exponential powers of Ω. But they are free in all toposes.
>>>
>>> Then I tried, more generally, arbitrary products of free algebras. But,
>>> again, they are free in all toposes.
>>>
>>> Does anybody know a source of more counter-examples? At the moment, the
>>> only counter-example I know is (†).
>>>
>>> It is embarrasing to know only one counter-example.
>>>
>>> Best wishes,
>>> Martin
>>> PS. I have written my proofs (on paper and) in a proof assistant, namely
>>> Agda (and this is publicly available and advertised in various forums).
>>> So this gives some confidence regarding the above claims. I still have
>>> to write a human-readable version for public consumption, but here I am
>>> more interested in knowning what people already know about this.

Re: Algebras of the partial-map classifier monad in 1-toposes

[Morgan Rogers]

[-- Attachment #1: Type: text/plain, Size: 15548 bytes --]

Dear Martin and Richard,

My PhD student Quentin Schroeder reminded me that I had written something related about the maybe monad (i.e. X maps to X + 1) some time ago in the n-cat-cafe<https://url.au.m.mimecastprotect.com/s/z7H_Cyoj8Pur3qw3VINt7Hxfm_8?domain=golem.ph.utexas.edu>.
The relevance is that the maybe monad coincides with the partial map classifier monad in a Boolean topos, and I showed there that all algebras of the maybe monad are free if and only if a topos is Boolean.

My proof at the link above doesn't generalize: it's not so straightforward to construct an algebra for the partial map classifier monad in an arbitrary elementary topos using just a subobject. So here are some insights orthogonal to Richard's. (I hope that the mixed formatting of in-line math is readable...)

An algebra structure for \tilde{-} on an object A determines a way to extend partial maps into A into total maps, naturally in the domain. The unit condition guarantees that total maps are unchanged. The associativity condition ensures that if we have a partial map X ---/ A given by X <--< X" ---> A and we expand it with an intermediate subobject X <--< X' <--< X" ---> A then extending the intermediate partial map X' ---/ A to a total map X' ---> A and then extending the resulting partial map X ---/ A to a total map produces the same result as extending the original partial map.

Consider 2 (= 1 + 1, not the subobject classifier in a non-Boolean topos!). When does 2 admit an algebra structure?

A partial map from an object A to 2 amounts to a choice of subobject B >--> A and a decomposition of B as a coproduct, B = B' + B". Equivalently, this is a choice of an ordered pair of disjoint subobjects of A, so the partial map classifier on 2 is \tilde{2} := {(U',U") \in \Omega \times \Omega | U' \wedge U" = \bot}, which is to say the equalizer of the conjunction arrow and the constant arrow at bottom \Omega \times \Omega \to \Omega. (This generalizes to the n-fold coproduct of 1 easily.)

We won't need this explicit presentation yet, though, since it's easier to reason in terms of extending maps. Indeed, an algebra structure on 2 is a way to extend any pair of disjoint subobjects (B', B") of an object A to a decomposition A = A' + A" such that A' contains B' and A" contains B". If the topos we're working in is de Morgan (no relation! https://ncatlab.org/nlab/show/De+Morgan+topos<https://url.au.m.mimecastprotect.com/s/OFDnCzvkmpfMzQZzVhwupH92WVC?domain=ncatlab.org>), then we have two canonical ways of doing this. The first is to send (B',B") to (\neg\neg B',\neg B'). The alternative is dual, sending (B',B") to (\neg B", \neg\neg B"). While these two don't coincide, they are clearly isomorphic, so I'll consider just the first one. Thanks to David Egolf, I know that the converse holds: if a topos fails to be de Morgan, then there is necessarily an object (witnessing the failure of de Morgan-ness) with disjoint subobjects which cannot be extended to a decomposition of the whole object in this way. So the existence of an algebra structure on 2 for the partial map classifier monad corresponds to a topos being de Morgan.

Jonas Frey, my office mate, came up with an internal argument of this equivalence in terms of Kock's shallow posets: suppose that 2 = {0,1} has a shallow poset structure. I'll keep writing (U',U") for subobjects of 2. Suppose without loss of generality that we have sup(\bot,\bot) = 0. Given a proposition \phi, consider (\bot,\phi). If sup(\bot,\phi)=0, then (\neg\phi); otherwise, sup(\bot,\phi)=1, so \phi \not\subseteq {0}, and hence (\neg\neg\phi). That is, (\neg\phi) or (\neg\neg\phi) holds, internally. I find this challenging to get my head around, so I'm going to stick with my external descriptions for the rest of this.

Returning to Martin's question, is this algebra free? That is, is 2 the partial map classifier of some object X?

If so, the unit X >--> \tilde{X} = 2 presents X as a disjoint union of two subterminal objects, say X' + X", such that the two global points of \tilde{X} represent the respective coproduct inclusions (cf. the diagram at the link below [1<https://url.au.m.mimecastprotect.com/s/8FdaCvl1g2S7Zp5ZVsXhYHQ5AN2?domain=q.uiver.app>]). We can compute explicitly that the partial map classifier is \tilde{X'+X"} = {(U',U") | U' \subseteq X', U" \subseteq X", U' \wedge U" = \bot} (compare with the description of the pmc for 1+1 above), and in this notation the points specified above are thus the pairs (X',\bot) and (\bot,X"), respectively. At this point, it would appear that X' and X" could have non-trivial intersection as subterminal objects, living as they do in distinct copies of 1. However, bringing the algebra map (B',B") |--> (\neg\neg B',\neg B') into the fold, to actually have 2 being \tilde{X} this must be a retraction for the image under the pmc monad of the unit. That is, it must be that (U',U") \in \tilde{X} |--> (\neg\neg U', \neg U') \in 1+1 should be an isomorphism. But note that both (\bot,X") and (\bot,\bot) are mapped to (\bot,\top) by this mapping! In other words, X" must have been trivial all along. [This shortcuts a longer argument I figured out with Quentin showing that X' and X" must be disjoint subterminal objects, independently of the choice of algebra map.]

So we are left with a subterminal object X (= X') such that for any object Z, the subobjects of Z \times X are in bijection with the complemented subobjects of Z via double negation (in Z); note that this bijection is necessarily order-preserving. In particular, X >---> 1 \times X is a maximal complemented subobject of X, so \neg\neg X (in 1) is 1.

Allow me to rephrase that: we want a subterminal object X such that E/X is Boolean and X is dense, so E/X is a dense subtopos. There is a unique subtopos with these properties: the double negation subtopos! Thus such an X exists if and only if the double-negation subtopos is an open subtopos, and such an X is necessarily unique. I'll leave a proof (or disproof!) that the existence of such a subterminal object in a de Morgan topos is sufficient to the dedicated reader.

We need not have X=1 : if we present a poset as B \times {0} + B \times {1} / {(b,0) < (b,1), (\bot,0) = (\bot,1)}, where B is a Boolean algebra (and take sheaves on this poset for the canonical topology so that it becomes the poset of subterminals). Our X will be the element (\top,0). For instance, the 3-element Heyting algebra is of this form, taking B to be the 2-element Boolean algebra (X is the middle element); there is also a 7-element Heyting algebra obtained in this way by taking B to be the 4-element Boolean algebra.

I should also note that I don't think that the existence of such a subterminal object implies that a topos is de Morgan; these feel like they may be independent properties.

Best regards,
Morgan Rogers


[1] https://q.uiver.app/#q=WzAsNixbMSwxLCJcXHRpbGRle1h9Il0sWzAsMSwiMSJdLFsyLDEsIjEiXSxbMSwwLCJYIl0sWzAsMCwiWCciXSxbMiwwLCJYJyciXSxbMywwLCJcXGV0YSIsMCx7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6Im1vbm8ifX19XSxbMSwwLCIoWCcsXFxib3QpIiwyLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoibW9ubyJ9fX1dLFsyLDAsIihcXGJvdCxYJycpIiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoibW9ubyJ9fX1dLFs0LDEsIiIsMix7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6Im1vbm8ifX19XSxbNCwzLCIiLDAseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJtb25vIn19fV0sWzUsMywiIiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoibW9ubyJ9fX1dLFs1LDIsIiIsMix7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6Im1vbm8ifX19XSxbNSwwLCIiLDAseyJzdHlsZSI6eyJuYW1lIjoiY29ybmVyIn19XSxbNCwwLCIiLDAseyJzdHlsZSI6eyJuYW1lIjoiY29ybmVyIn19XV0=<https://url.au.m.mimecastprotect.com/s/8FdaCvl1g2S7Zp5ZVsXhYHQ5AN2?domain=q.uiver.app>

On 11.01.2026 22:20, Richard Garner wrote:
Hi Martin,

Oh right, I see! That's a very interesting question. I think I have a
source of examples of algebras, though I'm not sure if they are free or
not (I would guess not in general).

Write L for the partial map classifier monad.

Write P for the power-object monad.

The unit map X >--> LX is monic for any object, and each PX is
injective. So for each X, we can extend the map P(eta^L_X): PX --> PLX
along the monic eta^L_{PX}: PX >---> LPX to get a map LPX --> PLX.

If we do this extension in a random way, there would be no particular
reason for it to be well-behaved. But there is an "obvious" way to take
extensions into P, and I *think* if we take this way, it gives a
distributive law of the endofunctor P over the monad L.

The unit axiom is obvious (it's how we defined things). For the axiom
expressing compatibility with the multiplication of L, my argument
involves figuring out what postcomposition with LPX ---> PLX does.

A map A ---> LPX is a partial map A <--< A' ---> PX, which means giving
a subobject A' <= A together with a relation R <= A' x X. On the other
hand, a map A ---> PLX is a relation S <= A x LX.

If I have this right, postcomposition with LPX --> PLX acts by sending
(A', R) to the relation

R >---> A' x X >---> A x X >--1 x eta--> A x LX

and now we can use this to show that both composites LLPX ---> PLX are
the same map.

Assuming this is right, P lifts to an endofunctor on the category of
L-algebras (it doesn't lift to a monad, because the distributive law
axiom expressing compatibility with the unit of P doesn't hold -- which
doesn't seem that surprising, since the power-set monad on Set doesn't
distribute over itself for the same reason).

Now my guess (based off feels) is that if you take the terminal
L-algebra 1 and hit it with P, you get Omega with the meet L-algebra
structure. The analogy is with the distributive law of P over the
commutative monoid monad in Set: if you see P as adding all meets, then
for a monoid X the monoid structure on PX is given by \bigwedge U .
\bigwedge V = \bigwedge {uv : u \in U, v in V}. Similarly in this case I
would guess that the L-algebra "join" operation on P1 (indexed by a
subobject phi <= 1) is given by

  "Join"_{x in phi} psi_x
= "Join"_{x in phi} \bigwedge_{y in psi_x} {*}
= \bigwedge_{f: \bigwedge_{x in phi} psi_x} "Join"_{x in phi} {*}
= \bigwedge_{f: \bigwedge_{x in phi} psi_x} {*}
= \bigwedge_{x in phi} psi_x

(here line 2 to line 3 is the application of the distributive law, and 3
to 4 is the trivial L-algebra structure of 1). Note that the terminal
L-algebra 1 = L0 is free. So potentially applying P to other free
L-algebras gives more examples of non-free L-algebras!

Richard



Martin Escardo <escardo.martin@gmail.com<mailto:escardo.martin@gmail.com>> writes:

Hi Richard,

Thanks! This is very interesting and nice.

Although I didn't say this explicitly in my original message, I am
looking for algebras that can be defined in any (elementary) topos (by
diagrams or in the internal language) that are not free in all toposes.

Do you also have examples of those? (Other than the one I gave in the
opening message of this thread.)

I am sure there should be a plentiful supply of algebras that one can
define in all toposes, but which are not free in all toposes.

I guess that such an exploration would lead to a better understanding of
the algebras of this monad in an arbitrary topos. In particular, we may
ask whether Anders Kock's characterization of the algebras as posets
that are complete in a certain way may help to shed light on this question.

Best,
Martin

On 07/01/2026 01:07, Richard Garner wrote:
Hi Martin,

Maybe one can look at the Sierpinski topos. In there, if my calculations
are correct, the partial map classifier takes A ---> B to 1+A+B --->
1+B, and an algebra for this monad is a map p: A-->B equipped with a
section s together with points in A and B which are preserved by p and
s.

In this case, Omega seems to have exactly two non-isomorphic algebra
structures, which can be realised by union and intersection.

But for a general p: A-->B, I think there are either:

- no algebra structures (if B is empty or p is non-surjective), or else
- exactly one non-isomorphic algebra structure for each distinct
cardinality possessed by one of the fibres of p

Indeed, in the second case, pick an element of B whose fibre has the
given cardinality. This is your B-point *. Then use AC to pick a section
s of p, and take the point in A to be s(*). If you chose a different
section, you get an isomorphic algebra. If you chose a different
basepoint in B of the same cardinality, you will again get an isomorphic
algebra.

In particular, Omega(Omega(1)) has one fibre of cardinality 1, one of
cardinality 2 and one of cardinality 3, and so should have three
distinct algebra structures.

All the best,

Richard


Martin Escardo <escardo.martin@gmail.com<mailto:escardo.martin@gmail.com>> writes:

Dear 1-topos theorists,

Anders Kock has a nice paper from the last millennium (1990), about

Algebras for the partial map classifier monad
https://link.springer.com/chapter/10.1007/BFb0084225⚠️⚠️<https://url.au.m.mimecastprotect.com/s/jskGCwV1jpSGnJmnrT9i8HJ_Qsz?domain=link.springer.com>
https://tildeweb.au.dk/au76680/jonna5.pdf⚠️⚠️<https://url.au.m.mimecastprotect.com/s/7gqKCxngGkf1jnVjNTwsAHyIXy3?domain=tildeweb.au.dk>

As he remarks and is well known, and also trivial, in a boolean topos,
all algebras are free. Then he goes on to say many interesting things
that hold in all 1-toposes.

Jon Sterling recently conjectured that, in an arbitrary topos, not all
algebras are free.

I came up with an example. My question is whether this example is well
known, and, moreover, whether more examples are known.

First of all, the subobject classifier Ω is a free algebra on one generator.

If you think of Ω as the powerset of the terminal object 𝟙, then the
structure map of Ω as a free algebra is *union*.

(†) But, you can check, also *intersection* exhibits Ω = 𝓟 𝟙 as an algebra.

I have proved that this algebra is free if and only if the principle of
excluded middle holds, that is, the topos is boolean.

Is this known?

Then I wanted to find more counter-examples to "every algebra is a free
algebra".

I tried, first, exponential powers of Ω. But they are free in all toposes.

Then I tried, more generally, arbitrary products of free algebras. But,
again, they are free in all toposes.

Does anybody know a source of more counter-examples? At the moment, the
only counter-example I know is (†).

It is embarrasing to know only one counter-example.

Best wishes,
Martin
PS. I have written my proofs (on paper and) in a proof assistant, namely
Agda (and this is publicly available and advertised in various forums).
So this gives some confidence regarding the above claims. I still have
to write a human-readable version for public consumption, but here I am
more interested in knowning what people already know about this.


You're receiving this message because you're a member of the Categories mailing list group from Macquarie University. To take part in this conversation, reply all to this message.

View group files<https://outlook.office365.com/groups/groupsubscription?source=EscalatedMessage&action=files&smtp=categories%40mq.edu.au&bO=true&GuestId=4eb9b40c-9b3a-48a5-9781-836e5a171e8b>   |   Leave group<https://outlook.office365.com/groups/groupsubscription?source=EscalatedMessage&action=leave&smtp=categories%40mq.edu.au&bO=true&GuestId=4eb9b40c-9b3a-48a5-9781-836e5a171e8b>   |   Learn more about Microsoft 365 Groups<https://aka.ms/o365g>


[-- Attachment #2: Type: text/html, Size: 19982 bytes --]