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: symmetric difference

Nick Smith (Jun 03 2021 at 00:58):

What does symmetric difference look like in Set or FinSet? Is there some "cool formula" for how it relates to intersection/pullbacks and coproducts? This is another case where Google isn't helping, and I can't quite figure it out myself. There's surely some universal property involved.

Nick Smith (Jun 03 2021 at 02:01):

Or is the answer as simple as: the intersection of two sets is the pullback of a cospan whose legs represent the two sets, and if you consider the pullback's morphism to be one of the coprojections of a coproduct (whose object is the apex of the original cospan), then the symmetric difference is just the other coprojection.

Nick Smith (Jun 03 2021 at 02:01):

But the apex also has to be the "smallest" such apex that the above holds. (Can the "smallest" apex be defined more precisely as the pushout of the pullback?)

Nick Smith (Jun 03 2021 at 02:02):

Or is that all garbage :stuck_out_tongue:

John Baez (Jun 03 2021 at 05:44):

I don't know a truly exciting answer, but notice: the symmetric difference of sets is $A \cup B - A \cap B$, and union and intersection can be nicely understood using pushout and pullback, so it suffices to understand set subtraction in a good way.

John Baez (Jun 03 2021 at 05:46):

Note in category theory we don't usually talk about the union of two sets; instead we talk about other things, like the union of two subsets of a given set. (If you don't understand this, then I'll dare to say: this is a lot more important than symmetric differences of sets!)

John Baez (Jun 03 2021 at 05:52):

Similarly for intersections.

John Baez (Jun 03 2021 at 05:53):

Unions of subsets of $X$ are coproducts in the Heyting algebra of subobjects of $X$, while intersections are products in this Heyting algebra.

John Baez (Jun 03 2021 at 05:54):

Subtraction of subsets of a given set is best understood as yet another operation in this Heyting algebra.

John Baez (Jun 03 2021 at 05:55):

So: talking about the Heyting algebra of subobjects of an object in a topos is one common way to tackle your question, and related questions.

Nick Smith (Jun 03 2021 at 08:56):

Whelp, I know nothing about Heyting algebras, so I guess I’ve got a lot more learning to do! I thought there might be a simpler explanation just in terms of basic (co)limits in Set. Thanks for the pointers.

Morgan Rogers (he/him) (Jun 03 2021 at 09:15):

The issue is that unless the sets you're talking about are expressed as subsets of some common larger set, we can replace one of them with an isomorphic set which is disjoint from the other (giving a symmetric difference which is just their union) or replace one of them with an isomorphic set which is contained in the other (giving a symmetric difference which is the complement of one in the other).
In other words, symmetric difference is not a categorically well-defined operation on sets.
Once we are working with subsets, however, changing the elements in the larger set results in consistent changes in the subsets, so we do have something well-defined. Using Heyting operations, we can describe the symmetric difference of $B$ and $C$ as, $(B \cup C) \cap ((B \cap C) \rightarrow \bot)$. If you've ever seen the negation of $X$ defined as $X \rightarrow \bot$, you might be able to make sense of that even without a detailed understanding of Heyting operations :)

Nick Smith (Jun 03 2021 at 10:41):

The “subsets” approach is also employed to view pullbacks as set intersection, right? You have a cospan of sets A and B injecting into a common set C which sets up a correspondence (in the lay-sense) between their elements. You pull that back to “reveal” their common elements. Set union is then just the dual of all this.

This was the starting point from which I was trying to think what symmetric difference would be like. I had no idea I wanted to be looking at Heyting algebras instead. Of course, the extent of my CT knowledge is a couple of chapters of Seven Sketches :innocent:

Jens Hemelaer (Jun 03 2021 at 12:02):

In topology, a nice example of a Heyting algebra is the family of open subsets. The meet and join of the Heyting algebra correspond to the intersection and union respectively of open subsets. Alternatively, you can think of the open sets as forming a category (with inclusions as morphisms), and then intersection and union are given by product and coproduct respectively. The Heyting implication $U \Rightarrow V$ for open subsets is defined as the interior of $U^c \cup V$ (here $U^c$ denotes the complement of $U$).

Using @Morgan Rogers (he/him) 's formula above, you can then compute the symmetric difference in this case.

Mike Shulman (Jun 04 2021 at 00:39):

A different kind of "set difference" is a cofiber in pointed sets. If $A\subseteq C$ is a subset, and we add a disjoint basepoint to each of them to get a monomorphism $A_+ \hookrightarrow C_+$ in $Set_*$, then its cofiber is its pushout along the map $A_+ \to 0$. This is $C_+$ with all the elements of $A$ identified with the basepoint, which can be identified with $(C\setminus A)_+$.

Nick Smith (Jun 04 2021 at 04:40):

Thanks everyone, I will ponder these approaches :smile:

John Baez (Jun 04 2021 at 06:42):

Nick Smith said:

Whelp, I know nothing about Heyting algebras, so I guess I’ve got a lot more learning to do! I thought there might be a simpler explanation just in terms of basic (co)limits in Set. Thanks for the pointers.

When I said "Heyting algebra" I could have just said "the power set of a set" - that is, the collection of all subsets of a set. This is a poset and thus a category. Union of subsets is the coproduct in this category, while intersection is the product. So we're not looking at (co)limits in Set, but we're doing the next simplest thing: we're looking at (co)limits in the poset of subsets of a fixed set.

These ideas can (and should) be generalized to the poset of subobjects of a fixed object in any topos, and that kind of poset is called a Heyting algebra. But you shouldn't try to understand that until you understand the previous paragraph!

Nick Smith (Jun 04 2021 at 08:16):

That definitely sounds a lot simpler! Thanks for simplifying :smile: