Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: What is the structure of $$\mathcal{P}^{\text{fin}}(S)$$?

Joshua Meyers (Nov 03 2023 at 17:24):

Let $S$ be a (possibly infinite) set. Then what is the structure of $\mathcal{P}^{\text{fin}}(S)$, if we care about the operations of union, intersection, and set difference?

It is not a Boolean algebra because it doesn't include $S$. It is like a semiring in measure theory.

We could equivalently say that the operations we care about are intersection and symmetric difference. Then it is a $\mathbb{Z}_2$-algebra. But that's not enough! We also need the multiplication to be associative, commutative, and idempotent. Is that enough?

We could also say that it is a join-semilattice with a "difference" operation that we define somehow -- does this have a name?

Is there some better way to describe this structure?

John Baez (Nov 03 2023 at 17:31):

I may be mixed up, but I think $\mathcal{P}^{\mathrm{fin}}(S)$ is the free [[join-semilattice]] on the set $S$. There's a monad on Set for join-semilattices, since they can be described using operations obeying equations, i.e. not mentioning the order structure. See the link for how.

John Baez (Nov 03 2023 at 17:32):

The link talks more about the free join-semilattice on a poset, but I think this can be specialized to prove the result I just claimed, thinking of a set as a discrete poset.

Joshua Meyers (Nov 03 2023 at 18:48):

Yes that is true! But what if you want to consider set difference and/or symmetric difference part of the structure?

Joshua Meyers (Nov 03 2023 at 18:56):

As a matter of fact, how do you even get binary intersections this way?

Reid Barton (Nov 03 2023 at 19:32):

I don't have a canonical reference for this but I would call it a "locally Boolean algebra", meaning roughly that the elements that are $\le A$ for some fixed $A$ form a Boolean algebra (and so in particular an element $B \le A$ has a complement $A \setminus B$ within this algebra, from which we can build the other operations you mention).

Kevin Arlin (Nov 03 2023 at 19:40):

@Joshua Meyers It's just dumb luck that the free join-semilattice turns out to be a distributive lattice, basically. Well, maybe an explanation is that any finite number of elements live in a finite bounded sub-join-semilattice, and such a thing always also has meets, by, if you want to be annoying, the adjoint functor theorem.

Reid Barton (Nov 03 2023 at 19:41):

The general example of a "locally Boolean algebra" should be the compact open (hence clopen) subsets of a locally compact Hausdorff totally disconnected space. In the case of your example, that space is $S$ with the discrete topology.

Kevin Arlin (Nov 03 2023 at 19:43):

Hmm, I wonder if it's important that the full downsets are boolean algebras, rather than just that you've got a certain kind of filtered colimit of finite boolean algebras.

Reid Barton (Nov 03 2023 at 19:47):

It's a bit tricky to say how the "locally Boolean algebra" is built from the various downsets $[\bot, A]$, because the inclusion of one in a bigger one doesn't preserve the negation.

Reid Barton (Nov 03 2023 at 19:47):

Which is also why I didn't give a real definition.

Joshua Meyers (Nov 03 2023 at 19:51):

I got it!

The structure I'm looking for is "commutative associative idempotent (not-necessarily unital) $\mathbb{Z}_2$-algebra!

Joshua Meyers (Nov 03 2023 at 19:52):

(inspired by https://ncatlab.org/nlab/show/Boolean+ring)

Eric Forgy (Nov 03 2023 at 19:53):

Joshua Meyers said:

I got it!

The structure I'm looking for is "commutative associative idempotent (not-necessarily unital) $\mathbb{Z}_2$-algebra!

These are fun :blush:

Joshua Meyers (Nov 03 2023 at 20:24):

But unfortunately, the free such structure on a set $S$ is not $\mathcal{P}^{\text{fin}}(S)$ but rather $\mathcal{P}^{\text{fin}}(R)$, where $R$ is the set of indecomposable regions on a fully generic Venn diagram with one circle for each $s\in S$. More formally, $R \cong \{b: S\to \{0,1\} | b\neq 0\}$.

Joshua Meyers (Nov 03 2023 at 20:26):

Wait this only works for finite $S$

Joshua Meyers (Nov 03 2023 at 20:31):

I wish there was some way to specify that the generators are disjoint

Ralph Sarkis (Nov 03 2023 at 21:17):

Kinda related to this thread.

John Baez (Nov 03 2023 at 21:35):

Joshua Meyers said:

Yes that is true! But what if you want to consider set difference and/or symmetric difference part of the structure?

As a matter of fact, how do you even get binary intersections this way?

Those are good questions! But those operations are not natural with respect to the obvious covariant functor sending $S$ to $\mathcal{P}^{\mathrm{fin}}(S)$, right? So they're inherently different from finitary unions.

John Baez (Nov 03 2023 at 21:38):

I guess I'm suggesting that the categorical viewpoint on "the operations possessed by $\mathcal{P}^{\mathrm{fin}}(S)$" should consider the question about how these operations get along with maps.

John Baez (Nov 03 2023 at 21:44):

By the way, we can make $S \mapsto \mathcal{P}(S)$ into both a covariant and a contravariant functor from $\mathsf{Set}$ to $\mathsf{Set}$, via images and inverse images. This complicates the discussion in fascinating ways. $S \mapsto \mathcal{P}^{\textrm{fin}}(S)$ only gets to be a covariant functor from $\mathsf{Set}$ to $\mathsf{Set}$, not a contravariant one, since the inverse image of a finite subset under a function needn't be finite. But you can make it into a contravariant functor from $\mathsf{FinSet}$ to $\mathsf{FinSet}$.

James Deikun (Nov 04 2023 at 06:55):

It can also be a contravariant functor on the category with sets as objects and functions with finite fibers as morphisms. This is almost by definition so it (the category equipped with the contravariant functor) probably has some nice universal property with regard to $\mathcal{P}^{\text{fin}}$ on $\mathsf{Set}$ ...

Matteo Capucci (he/him) (Nov 04 2023 at 12:05):

It's almost the opposite of the Kleisli category