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: subobject classifiers and topos theory

David Egolf (Jan 04 2022 at 04:12):

The concept of "subobject classifier" seems nice for thinking about properties of objects! (We can think of a subobject as the part of the original object that has some value for some property of interest). The concept of subobject classifier appears to show up in the context of "topos theory". I read that the category of sets is a topos in the nlab article, but otherwise that article is fairly mysterious to me.
What is another example of a topos, ideally one that I might be able to understand with a little work?

Todd Trimble (Jan 04 2022 at 05:07):

You might consider the topos of $G$-sets where $G$ is a group or monoid. Another might be the category whose objects are functions between sets and whose morphisms are commutative squares.

David Egolf (Jan 04 2022 at 05:19):

Thanks, that's interesting!

David Egolf (Jan 04 2022 at 05:38):

I think the second example of a topos above is called $Set^2$ in the book "Sheaves In Geometry And Logic". From that book apparently $Set^N$ is also a topos - here the objects are sequences of $N$ functions between sets, and the morphisms are corresponding sequences of commutative squares, I think. Generalizing further, apparently $Set^{C^{op}}$ for a small category $C$ is also a topos. Here the objects are contravariant functors from $C$ to $Set$, and the morphisms are natural transformations.
Interestingly, a while ago I was thinking about modelling an imaging process as a sequence of processing steps, together with some other people on this zulip. At one point, we were considering functor categories $Vect^N$, where $N$ refers to the category that looks like $1 \to 2 \to \dots \to N$. I wonder if this is also an example of a topos.

Zhen Lin Low (Jan 04 2022 at 06:26):

A category with a zero object is almost never a topos.

John Baez (Jan 04 2022 at 06:58):

David Egolf said:

Generalizing further, apparently $Set^{C^{op}}$ for a small category $C$ is also a topos. Here the objects are contravariant functors from $C$ to $Set$, and the morphisms are natural transformations.

Yes, this is called a presheaf topos and this has as special case both examples Todd just mentioned: the topos of $G$-sets and the topos of functions.

John Baez (Jan 04 2022 at 07:01):

If you want to understand topoi I recommend paying special attention to presheaf topoi. There's a lot about them in Sheaves in Geometry in Logic.

If you don't know about sheaves, you'll have a fair amount of trouble thinking of any topos that's not of the form $Set^{C^{\rm op}}$.

John Baez (Jan 04 2022 at 07:03):

David Egolf said:

At one point, we were considering functor categories $Vect^N$, where $N$ refers to the category that looks like $1 \to 2 \to \dots \to N$. I wonder if this is also an example of a topos.

Nope. $Vect$ isn't a topos and neither is $Vect^{C^{\rm op}}$ in general, though it is when $C$ is the empty category - a thoroughly boring example.

John Baez (Jan 04 2022 at 07:34):

I tell my students: if you don't know much topos theory, and you're wondering if something is a topos, here's a good rule of thumb: it's not. (Unless it's a presheaf or sheaf topos.)

Jens Hemelaer (Jan 04 2022 at 08:49):

However, $Vect^N$ is a Grothendieck category. These are precisely the abelian counterparts of Grothendieck toposes. A Grothendieck topos is a category of sheaves on a site, while a Grothendieck category is a category of "$\mathbb{Z}$-linear sheaves" on a "$\mathbb{Z}$-linear site".

If you have a Grothendieck topos, then you can turn it in a Grothendieck category by taking the category of abelian group objects in the topos. But not every Grothendieck category is of this form (I believe yours isn't). Intuitively, Grothendieck toposes are a generalization of topological spaces, and Grothendieck categories are a generalization of schemes.

Todd Trimble (Jan 04 2022 at 14:50):

David Egolf said:

I think the second example of a topos above is called $Set^2$ in the book "Sheaves In Geometry And Logic". From that book apparently $Set^N$ is also a topos - here the objects are sequences of $N$ functions between sets, and the morphisms are corresponding sequences of commutative squares, I think. Generalizing further, apparently $Set^{C^{op}}$ for a small category $C$ is also a topos. Here the objects are contravariant functors from $C$ to $Set$, and the morphisms are natural transformations.
Interestingly, a while ago I was thinking about modelling an imaging process as a sequence of processing steps, together with some other people on this zulip. At one point, we were considering functor categories $Vect^N$, where $N$ refers to the category that looks like $1 \to 2 \to \dots \to N$. I wonder if this is also an example of a topos.

Yes, it's $Set^2$. One reason I chose that example is that one can work out by hand what the subobject classifier is like, and that's a useful exercise. It shows in particular actually that "logic" in a topos doesn't have to be Boolean. Similarly, for the topos of directed graphs, you can try working out by hand what the subobject classifier is there. (As a start: what's $C$ for that case? Try not to look at the answer in the back of the book!)

Often I find that beginning students in topos theory want to go for the abstraction, but working out by hand humble little examples is invaluable and intuition-building.

John Baez (Jan 04 2022 at 20:32):

It's also fun - at least if you can momentarily stop reaching for the sky.

David Egolf (Jan 04 2022 at 22:55):

Thanks to everyone for all your interesting comments!

Todd Trimble said:

Yes, it's $Set^2$. One reason I chose that example is that one can work out by hand what the subobject classifier is like, and that's a useful exercise. It shows in particular actually that "logic" in a topos doesn't have to be Boolean.

I'm trying to work out what the subobject classifier is in $Set^2$.

First, we need to figure out what a monic morphism looks like in this setting. It seems to be a morphism that is monic in each of its components. So, in this case, a morphism $h: f \to g$ is monic exactly when its two component functions $h_1$ and $h_2$ are injective.

Next, we need to figure out the terminal object. It appears that the function $\{*\} \to \{*\}$ is terminal.

Next, I wanted to figure out $\Omega$, working from this definition:
subobject classifier

However, I got a little confused here. The motivating example provided earlier in the text was in the case of ${Set}$:
subobject classifier in Set

Here we see that $2 = \{0, 1\}$ plays the role of $\Omega$. The idea is that $\phi_S$ is labelling each part of $X$, telling us if it is in $S$ or not:
characteristic function

However, I don't immediately see why we couldn't have $3 = \{0, 1, 2\}$ play the role of $\Omega$.
Oh, I see! The right side of the diagram sends every element to a single truth value (which is taken to be "0" in this example in $Set$). The labelling function $\phi_S$ has to send every $x \in X$ to 0 if it is in $S$. However, if there are more than two values in $\Omega$, then we have options of how to define $\phi_S$ on elements of $X$ that are not in $S$. If we set $\Omega = \{0,1,2\}$, then $\phi_S$ could send elements of $X$ not in $S$ to either 1 or 2. That means that $\phi_S$ wouldn't be uniquely determined by the subobject $m: S \to X$ anymore.

(I wrote this all up to explain how I got stuck, and then I got unstuck - I think. I'm posting it anyways in case someone finds it interesting. I'm still working on figuring out $\Omega$ in $Set^2$).

David Egolf (Jan 04 2022 at 23:37):

Hmmm. I've concluded that figuring out the subobject classifier in $Set^2$ is a bit hard for me at the moment. It might make sense for me to learn some more about working with pullbacks first, for example.

Todd Trimble said:

Similarly, for the topos of directed graphs, you can try working out by hand what the subobject classifier is there. (As a start: what's $C$ for that case? Try not to look at the answer in the back of the book!)

With regards to directed graphs, I think the category of directed graphs is given by $Set^{D}$ where $D$ is the category having two objects, and two morphisms from the first object to the second one. This is because each directed graph is specified by two functions from a set of arrows to a set of vertices, namely the source and target functions.
I don't know how to efficiently find the subobject classifier in this setting either, unfortunately.

Todd Trimble (Jan 05 2022 at 02:44):

David Egolf said:

Hmmm. I've concluded that figuring out the subobject classifier in $Set^2$ is a bit hard for me at the moment. It might make sense for me to learn some more about working with pullbacks first, for example.

Todd Trimble said:

Similarly, for the topos of directed graphs, you can try working out by hand what the subobject classifier is there. (As a start: what's $C$ for that case? Try not to look at the answer in the back of the book!)

With regards to directed graphs, I think the category of directed graphs is given by $Set^{D}$ where $D$ is the category having two objects, and two morphisms from the first object to the second one. This is because each directed graph is specified by two functions from a set of arrows to a set of vertices, namely the source and target functions.
I don't know how to efficiently find the subobject classifier in this setting either, unfortunately.

We could start with a simpler problem. Let's define an element of an object $X$ to be a morphism $1 \to X$ (officially, that's called a "global element"). Here $1$ is terminal. Can you figure out how many elements there are of $\Omega$ in $Set^2$? Use the definition of subobject classifier to find out!

Todd Trimble (Jan 05 2022 at 02:46):

Maybe a hint: they call it a subobject classifier because...? There's a one-to-one correspondence between somethings and somethings else, encoded in the notion of subobject classifier. What is that correspondence?

David Egolf (Jan 05 2022 at 05:36):

Thanks @Todd Trimble for helping out with this.
I'm still struggling with this simpler problem. Here's what I've got so far, though:

Let's start with the definition of subobject classifier:
subobject classifier

You defined an element of an object $X$ to be a morphism $1 \to X$, where $1$ is a terminal object.
We want to figure out how many morphisms there are from $1$ to $\Omega$, as we want to determine how many elements it has.
We know $\Omega$ has at least one element, because by definition we have the morphism $1 \to_{true} \Omega$.

You note a correspondence between two things indicated in the definition of subobject classifier. We have for every monomorphism $f: S \to X$ a unique morphism $\phi: X \to \Omega$ so that the square is a pullback square. If we set $S = 1$ and $X = \Omega$, we find that for each element $f: 1 \to \Omega$ of $\Omega$, there is a unique morphism $\phi: \Omega \to \Omega$ so that the square is a pullback square. This seems to suggest some link between the endomorphisms of $\Omega$ and its number of elements.

However, you mention a "one-to-one" correspondence is involved. If $f: S \to X$ and $g: S \to X$ are distinct morphisms, must the corresponding induced $\phi_f$ and $\phi_g$ be distinct? I'm pretty sure that this is actually false, based on an example I tried in $Set$. If $f: S \to X$ and $g: S \to X$ are isomorphic as subobjects, then I suspect we will have $\phi_f = \phi_g$. This problem doesn't actually show up, though, when we are considering morphisms from $1 \to \Omega$. Distinct morphisms from $1$ correspond to distinct (non-isomorphic) elements of $\Omega$, I think.

So, we might ask instead the following question in an attempt to obtain a one-to-one correspondence. If $f: 1 \to X$ and $g: 1 \to X$ are distinct morphisms, must the corresponding induced $\phi_f$ and $\phi_g$ be distinct? I think this is true, although I am having trouble proving it nicely. Say we accept this for now.

If we accept the premise of the previous paragraph, then distinct elements of $X$ correspond to distinct induced $\phi$ maps from $X$ to $\Omega$. This would be a one-to-one relationship. In the case of $\Omega = X$, we have that distinct elements $f: 1 \to \Omega$ of $\Omega$ yield distinct induced $\phi$ maps $\phi: \Omega \to \Omega$. I don't immediately see how this helps us count distinct morphisms to $\Omega$ from 1.

I'm getting tired, so I'll stop here for now. I'll plan on coming back to this tomorrow.

David Egolf (Jan 05 2022 at 06:03):

I did spot this, which seems to indicate that this relationship between elements of $\Omega$ and pullback-induced endomorphisms of $\Omega$ is actually a bijection:
bijection

(The idea is to set $X = \Omega$ and $S=1$ in the above statement).

Maybe I will try to prove that in the morning. Since it is stated without proof here, hopefully that means it is simple enough for me to figure out!

Todd Trimble (Jan 05 2022 at 14:27):

Yes, this is a key thing to focus on. Do you know what the equivalence relation is here? After you answer this, a follow-up question: in the case of $Set$, what's a simpler name for an equivalence class of monomorphisms?

David Egolf (Jan 05 2022 at 15:26):

Todd Trimble said:

Yes, this is a key thing to focus on. Do you know what the equivalence relation is here? After you answer this, a follow-up question: in the case of $Set$, what's a simpler name for an equivalence class of monomorphisms?

The equivalence class of each monic $f: S \to X$ consists of monomorphisms that are isomorphic in $C/X$. That is, we say monomorphisms $f_1: S_1 \to X$ and $f_2: S_2 \to X$ are in the same equivalence class, exactly when there is an isomorphism $g: S_1 \to S_2$ so that $f_2 \circ g = f_1$. I believe we say the equivalence class of a monic $f: S \to X$ is the subobject described by $f$.

In $Set$, an equivalence class of monomorphisms from $S \to X$ corresponds to a subset of $X$. We can see this by noting that each of the monomorphisms isomorphic in $Set/X$ are forced to have the same image in $X$.

Todd Trimble (Jan 05 2022 at 15:45):

Yes, exactly right. Similarly, for any category, a simpler name for an equivalence class of monomorphisms into an object $X$ is subobject of $X$.

Thus, putting some things together, there is a natural bijection between maps $X \to \Omega$ and subobjects of $X$.

Now apply this to $X = 1$ in $Set^2$. See if you can determine the subobjects for this case.

David Egolf (Jan 05 2022 at 16:40):

Todd Trimble said:

Thus, putting some things together, there is a natural bijection between maps $X \to \Omega$ and subobjects of $X$.

I was hoping to prove that this really is a bijection before going further. That is, the map $\theta_X: Sub_C(X) \to C(X, \Omega)$ that sends the equivalence class $[m]$ of a monic $m: S \to X$ to its induced characteristic morphism $\phi$ is actually a bijection between the subobjects of $X$ and morphisms $X \to \Omega$.

First, we want to show that $\theta_X$ is injective. Let $\theta_X([m]) = \theta_X([m'])$. We want to show then that $[m] =[m']$. If $\phi = \theta_X([m]) = \theta_X([m'])$, that means that both $m$ and $m'$ are pullbacks of $true$ along $\phi$, which means that they are isomorphic as pullbacks. This implies that $m$ and $m'$ are isomorphic as subobjects, and so indeed $[m] = [m']$. This shows that $\theta_X$ is injective.

Next, we want to show that $\theta_X$ is surjective. So, for any $\phi: X \to \Omega$, we want to show there is a subobject $[m]$ of $X$ which is the equivalence class of a monomorphism $m: S \to X$, where $m$ is a pullback of $true$ along $\phi$. We are guaranteed such an $m$ exists, because pullbacks always exist in the category we are working in, and the pullback of any monic morphism (such as $true$) is always monic.

I think this shows that $\theta_X$ is bijective. This is really interesting!
You mention that the bijection is natural, but I will hold off on proving that until it's needed.

David Egolf (Jan 05 2022 at 16:56):

This means there is a bijection between maps $1 \to \Omega$, which are elements of $\Omega$, and subobjects of $1$. Let me try this out in $Set$. In $Set$, $1$ is the singleton set $\{0\}$, $\Omega$ is the set $\{0,1\}$ and $true: 1 \to \Omega$ sends $0 \mapsto 0$. There are two elements of $\Omega$, 0 and 1. So, we expect there to be two subobjects of $\{0\}$. I was worried at first, because this set only has one element. However, it does have two subobjects, corresponding to the subsets $\{0\}$ and the empty subset $\{\}$.

As a related example in $Set$, we expect a bijection between the subobjects (subsets) of $\Omega$ and the endofunctions $f: \Omega \to \Omega$. For a set with $n$ elements, there are $n^n$ endofunctions and $2^n$ subsets. So, $\Omega$ in $Set$ must have $n$ elements such that $n^n = 2^n$. So, $\Omega$ in $Set$ must have two elements, which indeed it does.

Now, we just need to do this sort of thing in $Set^2$...

David Egolf (Jan 05 2022 at 17:18):

We can now figure out the number of elements of $\Omega$ in $Set^2$, using the fact that these are in bijection with subobjects of a terminal object $1$. The object $\{0\} \to \{0\}$ is terminal in $Set^2$, and so we want to find its subobjects. Each morphism in $Set^2$ is a pair of functions that makes the resulting square commute. As noted earlier, I think this means that a monomorphism in $Set^2$ is a pair of injective functions that make the resulting square commute. We have a monomorphism from each of $\{0\} \to \{0\}$, $\{\} \to \{0\}$ and $\{\} \to \{\}$ to $\{0\} \to \{0\}$, if I am remembering how functions from the empty set work. I believe these correspond to the distinct subobjects.

So, I think there are 3 subobjects of $1$ in $Set^2$, which would mean that there are 3 elements of $\Omega$ in $Set^2$.

David Egolf (Jan 07 2022 at 01:46):

Now, let's try to figure out $\Omega$ by using the subobject maps into $1$.
For every such subobject map, we know there needs to exist a unique map $1 \to \Omega$ so that the square in the definition of the subobject classifier commutes and is a pullback square.
I tried to construct such an $\Omega$ that would satisfy this. I think this one works, although I haven't checked it super carefully: $\{0,1,2\} \to_f \{0,1\}$ with $f(0) = 0$, $f(1) = 0$ and $f(2) = 1$. To get this, I defined the map $true: 1 \to \Omega$ so that each function of $true$ maps to 0 in the corresponding set of $\Omega$.
Any thoughts or insights @Todd Trimble or others might wish to offer would be appreciated.
At any rate, this has been interesting and I feel like I got some good practice with these ideas. Thanks again to everyone who's helped me out with this!

Todd Trimble (Jan 08 2022 at 16:13):

Sorry for not getting back sooner.

Nice work! You have succeeded in describing the underlying object of $\Omega$ in $Set^2$.

Here's another thing to work out: can you describe the negation operator $\neg: \Omega \to \Omega$?

This will go some distance toward making clear that the internal propositional logic for this topos is intuitionistic.

David Egolf (Jan 09 2022 at 21:40):

Oh, that sounds interesting to do as well!
Working on this has lead me to discover Boolean algebras and Heyting algebras. I hadn't realized before that we can talk about logic with similar-ish tools as we talk about subsets of a topological space! This connection between the study of space and the study of logic is unexpected and beautiful to me! I wonder if we can generate a system of propositions and implications between them from a given topological space.
(Still a bit of background reading/learning to do before I take a stab at working out negation in $Set^2$, as I've not taken any classes on this sort of thing...)

John Baez (Jan 09 2022 at 23:35):

Yes, the connection between topology and logic given by the fact that open subsets of a topological space form a Heyting algebra is a marvelous thing, and it's a step toward topos theory, since for any topos the subobject classifier gives a Heyting algebra.

John Baez (Jan 09 2022 at 23:37):

A pretty good intuition, if you're ready for it, is that a Heyting algebra is a "0-topos" while a topos is a "1-topos" - the next thing up the ladder of n-categories.

John Baez (Jan 09 2022 at 23:44):

Or if that's too funky, you can say something similar this way: topos theory has the theory of Heyting algebras built in very much like how classical set theory has the theory of Boolean algebras built in.

John Baez (Jan 09 2022 at 23:45):

So classical set theory is a "step up" from Boolean logic, and topos theory is a parallel "step up" from Heyting algebra logic.

David Egolf (Jan 11 2022 at 00:32):

Thanks @John Baez for your comments. The n-category stuff goes over my head at this point, but the idea that topos theory has Heyting algebras "built in", in a way that classical set theory has Boolean algebras "built in" is interesting.
To my understanding, the subobjects of a given object in a topos form a Heyting algebra. Presumably the subsets of a given set form a Boolean algebra?

David Egolf (Jan 11 2022 at 00:37):

I've been trying to figure out how logic (and negation in particular) work in a topos, without actually having to learn a ton of the basics of topos theory. So far my "topos tourism plan" has not had a lot of success.
I did spot this, though (in "Sheaves in Geometry and Logic"):
subobjects as a place for logic

The authors go on to explicitly describe how "and", "or", "implication", and "negation" work with respect to subobjects of a given object. However, I think these are all maps between subobjects of a given object. I'm not immediately seeing how this gives a negation operator that acts between objects, instead of subobjects.

I will probably keep chipping away at this, but hints are always appreciated.

John Baez (Jan 11 2022 at 00:45):

David Egolf said:

To my understanding, the subobjects of a given object in a topos form a Heyting algebra. Presumably the subsets of a given set form a Boolean algebra.

Yes! Here's a fancy-ass way to see this fact. $\mathsf{Set}$ is a topos, so the subsets of a given set form a Heyting algebra. But a Boolean algebra is the same as a Heyting algebra where $\neg(\neg p) = p$. And the complement of the complement of a subset is that subset (at least in classical logic - there are intuitionists around here who don't like thinking this way). So the subsets of a given set form a Boolean algebra.

There are also tons of other ways to see this fact, because there are tons of equivalent definitions of "Boolean algebra". Take your favorite definition of "Boolean algebra", and check that the collection of subsets of a set form a Boolean algebra.

John Baez (Jan 11 2022 at 00:47):

Boolean algebras are how we reason about truth values in classical logic, so we're seeing here a connection between classical logic and traditional set theory.

John Baez (Jan 11 2022 at 00:48):

I'm not immediately seeing how this gives a negation operator that acts between objects, instead of subobjects.

Good! There isn't one!

John Baez (Jan 11 2022 at 00:48):

There's no such thing as the negation of a set.

David Egolf (Jan 11 2022 at 01:35):

The nLab gives us an explicit definition of a Boolean algebra:
boolean algebra

Let's take a set $U$, and see if its set of subsets, ordered under inclusion, forms a Boolean algebra. If it does, then we will have a way of and-ing, or-ing, and negating its subsets.

First we need to check that the subsets of $U$ forms a partially ordered set under inclusion. Let $a \leq b \iff a \subseteq b$ for any subsets $a, b$ of $U$.
Checking reflexivity: $a \subseteq a \implies a \leq a$ for any subset $a$.
Checking transitivty: $a \leq b$ and $b \leq c$ implies $a \subseteq b$ and $b \subseteq c$ which means $a \subseteq c$ and so $a \leq c$.
Checking antisymmetry: $a \leq b$ and $b \leq a$ means $a \subseteq b$ and $b \subseteq a$ which implies $a=b$.

Next, we need to find a $\top$ element so $x \leq \top$ holds for any subset $x$ of $U$.
Set $\top = U$. Then $x \subseteq U$ for any $x$, and so $x \leq \top$ for any $x$.

Next, we need to find a $\bot$ element so $\bot \leq x$ holds for any subset $x$ of $U$.
Setting $\bot = \emptyset$ will work, since the empty set is a subset of any set.

Next, for any $a,b \subseteq U$, we need to define $a \wedge b$ so that $x \leq a \wedge b$ iff $x \leq a$ and $x \leq b$.
Set $a \wedge b = a \cap b$. Then, if $x \subseteq a \cap b$, we have $x \subseteq a$ and $x \subseteq b$. In addition, if $x \subseteq a$ and $x \subseteq b$ then $x \subseteq a \cap b$.

David Egolf (Jan 11 2022 at 01:37):

Next, for any $a,b \subseteq U$, we need to define $a \vee b$ so that $a \vee b \leq x$ iff $a \leq x$ and $b \leq x$.
Set $a \vee b = a \cup b$. Then if $a \cup b \subseteq x$, we have $a \subseteq x$ and $b \subseteq x$. In addition, if $a \subseteq x$ and $b \subseteq x$, then $a \cup b \subseteq x$.

Next, for any $a \subseteq U$, we need to define $\neg a$ so that $a \wedge \neg a \leq \bot$ and and $\top \leq a \vee \neg a$.
Let $\neg a = a^c$, the complement of $a$ in $U$. This is the subset of $U$ containing exactly the elements of $U$ that $a$ does not contain.
Does this satisfy the required properties?
We have $a \cap a^c \subseteq \emptyset$, which implies $a \wedge \neg a \leq \bot$, as needed.
We have $U \subseteq a \cup a^c$, which implies $\top \leq a \vee \neg a$, as needed.

Finally, for any $a,b,c \subseteq U$, we need $a \wedge (b \vee c) \leq (a \wedge b) \vee (a \wedge c)$.
This would be implied by $a \cap (b \cup c) \subseteq (a \cap b) \cup (a \cap c)$.
I see from Wikipedia's article "Algebra of Sets", that this holds (under the heading "distributive property").

So, it appears that the subsets of $U$, ordered by inclusion, do indeed form a Boolean algebra!

David Egolf (Jan 11 2022 at 01:40):

John Baez said:

I'm not immediately seeing how this gives a negation operator that acts between objects, instead of subobjects.

Good! There isn't one!

I just want to emphasize that this kind of comment is incredibly helpful. It's rather easy to get a wrong idea of where one is trying to head when learning things, and to worry about not reaching a non-existent destination. So, this really helps a lot.

John Baez (Jan 11 2022 at 01:48):

Great! I'm glad you checked that nuts-and-bolts definition of Boolean algebra for subsets of a set $U$.

I see from Wikipedia's article "Algebra of Sets", that this holds (under the heading "distributive property").

Yes, it holds with an equal sign: $a \cap (b \cup c) = (a \cap b) \cup (a \cup c)$. For example,

"I want a dog that's black and either friendly or really cute"

is the same as

"I want a dog that's either black and friendly or black and really cute".

(Here I'm describing a subset of the set of dogs in two ways.)

John Baez (Jan 11 2022 at 01:52):

We also have the dual law

$a \cup (b \cap c) = (a \cup b) \cap (a \cup c)$

David Egolf (Jan 11 2022 at 01:56):

I was wondering why we didn't need to check both of those laws. I'm guessing this is related to the statement that a Boolean algebra is "self-dual" made by the nlab. (So that, presumably, one law holding implies the other holds).

John Baez (Jan 11 2022 at 02:12):

Yes, you can prove one from the other using DeMorgan duality:

$\neg(a \cup b) = \neg a \cap \neg b$

which is equivalent to

$\neg(a \cap b) = \neg a \cup \neg b$

using $\neg(\neg a) = a$

John Baez (Jan 11 2022 at 02:13):

However, it's also true that one implies the other in any "lattice" (that is, a poset with a top and bottom element, where any two elements have a meet $\wedge$ and a join $\vee$).

John Baez (Jan 11 2022 at 02:19):

The lattice of subspaces of a vector space, with its usual ordering (inclusion) is a nice example of a nondistributive lattice.

David Egolf (Jan 12 2022 at 01:39):

Todd Trimble said:

Here's another thing to work out: can you describe the negation operator $\neg: \Omega \to \Omega$?

This will go some distance toward making clear that the internal propositional logic for this topos is intuitionistic.

As mentioned above, the subobjects of an object in a topos form a Heyting algebra, which lets us talk about negation of subobjects. I am trying to understand what @Todd Trimble says above, where he mentions a negation map $\neg: \Omega \to \Omega$. It seems like he could be referring to a map on the subobjects of $\Omega$, $\neg: Sub(\Omega) \to Sub(\Omega)$. Any clarification is appreciated!

(Or perhaps somehow negation in the context of subobjects of a given object is induced by some corresponding morphism from $\Omega$ to $\Omega$?)

Reid Barton (Jan 12 2022 at 01:49):

David Egolf said:

(Or perhaps somehow negation in the context of subobjects of a given object is induced by some corresponding morphism from $\Omega$ to $\Omega$?)

:this:

Reid Barton (Jan 12 2022 at 01:50):

It's not a "corresponding" morphism, though. There is just one negation operator $\neg : \Omega \to \Omega$.

Reid Barton (Jan 12 2022 at 01:51):

For any object $X$, the subobjects of $X$ correspond to maps $X \to \Omega$. If we compose a map $f : X \to \Omega$ with an operator $g : \Omega \to \Omega$, we get a new map $gf : X \to \Omega$. The negation operator is the map $\not : \Omega \to \Omega$ such that the corresponding operation on subobjects of $X$ is complementation, for any $X$.

Todd Trimble (Jan 12 2022 at 01:52):

Yes, there is an important principle here: operations on subobject lattices $Sub(X) \to Sub(X)$ that are natural in $X$ are in bijection with corresponding operations on $\Omega$.

(I don't expect this to be understood right away by beginners, but it follows from the Yoneda lemma.)

But in the example we were looking at, $\Omega$ in $Set^2$, it's possible to figure out what $\neg: \Omega \to \Omega$ looks like as a commutative square (remember that morphisms in this topos are commutative squares), and since $\Omega$ itself is a function from a 3-element set to a 2-element set, this example is small enough that one can make this commutative square very explicit.

Reid Barton (Jan 12 2022 at 01:53):

This is a funny but very powerful way of encoding all of the complementation operations at once by a single map $\neg : \Omega \to \Omega$--it's not immediately obvious that this should be possible.

John Baez (Jan 12 2022 at 01:57):

It's funny in a way, but in another way we could expect it from the description in $\mathsf{Set}$ where we say "$x$ is in the complement of $S \subseteq X$ iff $x$ is not in $S$."

John Baez (Jan 12 2022 at 01:58):

That "not" winds up being the negation operator $\neg : \Omega \to \Omega$.

John Baez (Jan 12 2022 at 01:58):

(I know Reid knows this, but I'm hoping this helps David a bit.)

Reid Barton (Jan 12 2022 at 01:58):

Right, internally it's the operation of negating a proposition. Externally, it might be a bit mysterious.

David Egolf (Jan 12 2022 at 02:01):

Thanks everyone, this is making a lot more sense. I'll work out the details soon-ish in $Set^2$.
I'm getting the intuition that each subobject of an object corresponds to a "labelling" of that object, which is the corresponding map to $\Omega$ from the object. Then, the map $\neg: \Omega \to \Omega$ swaps these labels, at least in $Set$. The subobject that corresponds to this swapped labelling of the object is then the negation of the subobject.

John Baez (Jan 12 2022 at 02:05):

Yes, you're right: just think about the category $\mathsf{Set}$. A subset of a set $S$ amounts the same as map from $S$ to $\Omega = \{T,F\}$, called the characteristic function of the subset. Taking the complement changes this characteristic function by composing it with $\neg : \Omega \to \Omega$.

John Baez (Jan 12 2022 at 02:07):

To understand lots of basic stuff in topos theory you just copy what works in $\mathsf{Set}$. The surprises come when things work differently.

John Baez (Jan 12 2022 at 02:09):

A lot of the surprises from the fact that $\neg \circ \neg \ne 1_{\Omega}$, in general.

David Egolf (Jan 13 2022 at 22:18):

I didn't realize this when I started looking at topos stuff, but it's more immediately connected to applied category theory than I thought. In particular, knowing that the functor category $Set^{C^{op}}$ is a topos when $C$ is a small category helps motivate the "schemas" discussed in Seven Sketches. This is because schemas correspond to small categories (seeking to describe data organization), and functors from schemas correspond to particular realizations of this data organization (e.g. a particular database). So we can expect to get a sort of logic on databases in this way, because the functor category of these databases will be a topos.

John Baez (Jan 13 2022 at 23:37):

Yes, these so-called presheaf categories $\mathsf{Set}^{C^{\mathrm op}}$ are the main topoi used by us working applied category theorists. By the way, @Evan Patterson and @James Fairbanks wanted to work with categories like $\mathsf{Set}^{C}$ instead. It's no big deal, since one man's $C$ is another man's $C^{\rm op}$. An object in $\mathsf{Set}^{C}$ is sometimes called a copresheaf, but Evan and James found that strange term a bit disgusting for such a simple thing, so they started calling it a $C$-set.

So, if you ever read their work, when they're talking about $C$-sets those are objects in a topos... which the topos of presheaves on $C^{\rm op}$.

Todd Trimble (Jan 14 2022 at 00:35):

I'm think I've seen $C$-sets before for this concept, somewhere...

John Baez (Jan 14 2022 at 00:43):

Okay, good. Maybe they didn't make up that term. Of course it's a generalization of $G$-sets for a group $G$, which is a really common expression, and $M$-sets for a monoid $M$, which I'd also seen. So it's quite natural.

Evan Patterson (Jan 14 2022 at 00:43):

Yeah, we didn't make it up, which made me feel somewhat better about using it. The term is used in the book on topos theory by Reyes, Reyes, and Zolfaghari, admittedly for presheaves rather than copresheaves.

John Baez (Jan 14 2022 at 00:44):

Ugh! The evil op!

John Baez (Jan 14 2022 at 00:44):

For groups you have "left and right $G$-sets" as a way of talking about whether you put the op in or not.

Evan Patterson (Jan 14 2022 at 00:45):

I really wish people said "covariant and contravariant" instead of "left and right" $G$-sets, $C$-sets, etc., but that's another rant!

John Baez (Jan 14 2022 at 00:57):

You're not going to get me to stop saying "left and right" $G$-set in the case of groups, since that's just how mathematicians talk, but I've never heard anyone say "left and right" $C$-set and don't feel the urge to start.

Evan Patterson (Jan 14 2022 at 01:04):

Haha, fair enough. BTW, the book I referenced, despite being a bit idiosyncratic, is really helpful when learning topos theory because it does a lot of concrete calculations in presheaf toposes such as those of graphs and "evolutive sets". After the book went out of print, the authors put it online: https://marieetgonzalo.files.wordpress.com/2004/06/generic-figures.pdf

David Egolf (Jan 19 2022 at 17:51):

I wanted to note for anyone who may read this thread later - chapter 7 of Seven Sketches in Compositionality seems like an accessible resource for learning about toposes.