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: Set product projections are surjective, right?

Olli (Oct 22 2020 at 17:56):

This is kind of a beginner question and not even strictly about CT, although I got it from watching this talk that is about duality and canonical maps in the category of sets:

https://youtu.be/gUt6Sbq2U-w?t=1698

Here the presenter talks about projections from a set product being surjective, but an audience member interrupts him to give a counter example of $\pi_Y : \emptyset \times Y \rightarrow Y$ not being surjective because he claims that the function $\emptyset \rightarrow Y$ is not surjective, but to me it seems this correction is in fact incorrect. According to the usual definition of surjectivity: $\forall x \in X$, $\exists y \in Y : fx = y$, this condition is vacuously true when $X$ is the empty set.

I am pretty sure this is correct, but I just wanted to sanity check this, because the objection seems to have caught the presenter a bit off guard as well, and the issue was not really fully resolved. And perhaps I should also just confirm, that I believe this should also hold in the case where we talk about epimorphisms and products in general.

Morgan Rogers (he/him) (Oct 22 2020 at 17:57):

You've got the for all and exists the wrong way around in that definition :joy:

Morgan Rogers (he/him) (Oct 22 2020 at 18:00):

$f:X \to Y$ is surjective if $\forall y \in Y, \, \exists x \in X, \, f(x) = y$. Although category theorists prefer "epic": $f$ is epic if whenever we have $u,v: Y \rightrightarrows Z$ with $u \circ f = v \circ f$, we have $u = v$. :wink:

Morgan Rogers (he/him) (Oct 22 2020 at 18:00):

(if you haven't seen that before, it's a nice exercise to work out why a function is surjective if and only if it's epic as a morphism in $\mathbf{Set}$)

Morgan Rogers (he/him) (Oct 22 2020 at 18:02):

So indeed, the interjection was correct; product projections are not always epic! In $\mathbf{Set}$, the only counterexamples involve the empty set, because every other object is well-supported: the morphism to the terminal object (a set with just one element) is epic.

Olli (Oct 22 2020 at 18:06):

Oh whoops! I was so confident in my mistake I didn't even bother checking that I had the formula right. Ah well, I should remember it from now on at least.

Morgan Rogers (he/him) (Oct 22 2020 at 18:18):

I just found the interruption in the video... Eek :grimacing:
What level was this talk intended to be at?

Olli (Oct 22 2020 at 18:22):

I have no idea, I came by it randomly via the Youtube recommendation algorithm (or actually a different talk, but then I checked the other talks in the channel and this one sounded interesting to me).

Pedro Minicz (Oct 23 2020 at 18:14):

[Mod] Morgan Rogers said:

So indeed, the interjection was correct; product projections are not always epic! In $\mathbf{Set}$, the only counterexamples involve the empty set, because every other object is well-supported: the morphism to the terminal object (a set with just one element) is epic.

Very interesting. What are the necessary conditions for a product projection on an arbitrary category $C$ to be epic?

James Wood (Oct 23 2020 at 18:32):

$f × g : A × B → C × D$ is epic if $f$ and $g$ each are. Notice that $π_l : A × B → A$ is equal to $(1 × {!}) ; π_l$, where $1 : A → A$ is the identity, ${!} : B → 1$ is the map into the terminal object, and $π_l : A × 1 → A$ is an isomorphism (in this special case where we're projecting away the terminal object). So if $B$ is well supported, making ${!}$ epic, then the projection is also epic.

I think you can do this argument in reverse to show that the well supportedness criterion is necessary.

Reid Barton (Oct 23 2020 at 19:19):

Why is the first sentence true?

Reid Barton (Oct 23 2020 at 19:20):

Are you assuming something about the category (other than the existence of the products in question)?

James Wood (Oct 23 2020 at 19:31):

Uh, yeah, maybe we need to be talking about split epis rather than epis.

John Baez (Oct 24 2020 at 16:18):

Pedro Minicz said:

What are the necessary conditions for a product projection on an arbitrary category $C$ to be epic?

Note that in $\mathsf{Set}$ the product projection $\emptyset \times X \to X$ is usually not epic.

Jules Hedges (Oct 24 2020 at 18:47):

John Baez said:

Note that in $\mathsf{Set}$ the product projection $\emptyset \times X \to X$ is usually not epic.

The empty set: A source of annoying counterexamples since 1874

John Baez (Oct 24 2020 at 18:50):

Who invented the empty set and when? That's a tough question - but we can ask who invented the notation $\emptyset$ for the empty set, or who first wrote about the set $\{ \}$.

Fawzi Hreiki (Oct 24 2020 at 19:40):

John Baez said:

Who invented the empty set and when? That's a tough question - but we can ask who invented the notation $\emptyset$ for the empty set, or who first wrote about the set $\{ \}$.

The-Empty-Set-the-Singleton-and-the-Ordered-Pair.pdf

Fawzi Hreiki (Oct 24 2020 at 19:43):

Apparently it was a combination of Boole, Frege, Peano, Zermelo, and Hausdorff

John Baez (Oct 24 2020 at 20:09):

Thanks! Sounds like an old joke: how many mathematicians does it take to invent the empty set?

Fabrizio Genovese (Oct 24 2020 at 20:25):

John Baez said:

Pedro Minicz said:

What are the necessary conditions for a product projection on an arbitrary category $C$ to be epic?

Note that in $\mathsf{Set}$ the product projection $\emptyset \times X \to X$ is usually not epic.

This is one of the most unpleasing realities I've faced in the last days. I literally screamt in pain when I saw this. WTF seriously, this should be wrong.

John Baez (Oct 24 2020 at 20:27):

Heh. If only the empty set wasn't so... empty.

Fabrizio Genovese (Oct 24 2020 at 20:34):

Yea, it's absolutely terrible.

Fawzi Hreiki (Oct 24 2020 at 20:34):

It makes sense why it took us thousands of years to accept the number 0 as legitimate to begin with

Reid Barton (Oct 24 2020 at 20:36):

They say a false statement implies everything, but "$P \to *$ is epic for every set $P$" does so in a particularly direct way.

Reid Barton (Oct 24 2020 at 20:36):

(At least if you know that "epic" means "surjective".)

John Baez (Oct 24 2020 at 20:38):

Nobody should ever expect that the product projections $A \times B \to A, A \times B \to B$ are epimorphisms in all categories. The basic problem is that products are limits, and limits get along very nicely with monomorphisms, not epimorphisms.

The reason is that we can define monomorphisms using limits.

Similarly, your instinct should be that colimits get along with epimorphisms.

John Baez (Oct 24 2020 at 20:39):

When I was younger and stupider I thought that the coproduct inclusions $A \to A + B, B \to A + B$ might always be monomorphisms.

It's true in $\mathsf{Set}$ but it's false in $\mathsf{Set}^{\rm op}$, as we've just seen.

Reid Barton (Oct 24 2020 at 20:40):

Right, this is also why I was skeptical of the earlier claim that "if $f$ and $g$ are epic then so is $f \times g$" even though I don't know of a counterexample off-hand.

Martti Karvonen (Oct 24 2020 at 21:16):

John Baez said:

Who invented the empty set and when? That's a tough question - but we can ask who invented the notation $\emptyset$ for the empty set, or who first wrote about the set $\{ \}$.

The symbol $\emptyset$ for the empty set goes back to Andre Weil who apparently was quite fond of Scandinavia and repurposed a letter from the Norwegian alphabet. Bourbaki made the notation popular.

Fabrizio Genovese (Oct 25 2020 at 02:03):

John Baez said:

Nobody should ever expect that the product projections $A \times B \to A, A \times B \to B$ are epimorphisms in all categories. The basic problem is that products are limits, and limits get along very nicely with monomorphisms, not epimorphisms.

The reason is that we can define monomorphisms using limits.

Similarly, your instinct should be that colimits get along with epimorphisms.

Totally agree with this. But I would have expected them to be epic at least in Set! In Set everything is nice so I gave for granted that this was the case at least there. And, obviously, we just saw this fails for the most annoying reason. As young Italians say, "mai una gioia", "never a joy". :smile:

Oscar Cunningham (Oct 25 2020 at 11:08):

Here's another one: In $\mathbf{Set}$ every monomorphism $A\to B$ splits, except when $A$ is empty.

John Baez (Oct 25 2020 at 18:12):

Damn that empty set!

David Michael Roberts (Oct 27 2020 at 05:37):

This is why set theorists have to define the order $|A| \leq^* |B|$ on cardinalities in ZF as "there is a surjection $B\to A$ or $A = \emptyset$. It's much better to define this as "$A$ is a subquotient of $B$", and then one gets a better preorder, when removing EM.

Pedro Minicz (Oct 28 2020 at 17:02):

John Baez said:

The basic problem is that products are limits, and limits get along very nicely with monomorphisms, not epimorphisms.

That is very interesting. Could you please expand a bit on what you mean by "get along very nicely"? Does it have something to do with the preservation of certain monomorphisms?

John Baez (Oct 28 2020 at 17:14):

1) For starters, you can define monomorphisms using limits! A morphism $f: X \to Y$ is a mono iff its pullback along itself is $X$ (or more precisely, the obvious square with an $X$ in the upper left corner and identities along the top and left edges).

2) As a consequence, any functor that preserves limits preserves monomorphisms!

3) Third, the pullback of a mono along any morphism is a mono: see Prop. 3.2 here.

John Baez (Oct 28 2020 at 17:15):

4) Fourth, the product of monos is a mono: if $f : X \to Y$ and $f': X' \to Y'$ are monos so is $f \times f' : X \times X' \to Y \times Y'$.

John Baez (Oct 28 2020 at 17:16):

5) Fifth, any equalizer is a mono.

6) Sixth, any morphism out of a terminal object, say $f: 1 \to X$, is a mono.

John Baez (Oct 28 2020 at 17:17):

These are some of the relations I know connecting limits and monomorphisms. There are probably a bunch more - maybe people here know more.

John Baez (Oct 28 2020 at 17:22):

All of these results have nice duals, connecting epimorphisms and colimits. For example you can define epis using colimits, so any functor that preserves colimits preserves epis.

Kim-Ee Yeoh (Oct 28 2020 at 22:56):

Olli said:

I was so confident in my mistake I didn't even bother checking that I had the formula right. Ah well, I should remember it from now on at least.

You did have the formula right, just for someting else. For the original formula: $\forall x \in X$, $\exists y \in Y : fx = y$ explains the adjective in “a well-defined function.”

Kim-Ee Yeoh (Oct 28 2020 at 23:04):

Fabrizio Genovese said:

John Baez said:

Note that in $\mathsf{Set}$ the product projection $\emptyset \times X \to X$ is usually not epic.

This is one of the most unpleasing realities I've faced in the last days. I literally screamt in pain when I saw this. WTF seriously, this should be wrong.

Honestly curious, do you also scream in pain that we can't divide by zero? Decategorified to its core, that set product is almost but not quite epic projects down to how multiplication on the naturals is almost but not quite (left-)invertible.

John Baez (Oct 29 2020 at 01:57):

Kim-Ee Yeoh said:

Honestly curious, do you also scream in pain that we can't divide by zero?

You weren't asking me, but: I should have done this at some point. But I can't even remember when I learned you can't divide by zero.

I can remember the time when I found this exciting: assume $a = b$, then

$a^2 = ab$

$a^2 - b^2 = ab - b^2$

$(a+b)(a-b) = b(a-b)$

$a+ b = b$

$a = 0$

so every number equals zero. It was a long time ago!

John Baez (Oct 29 2020 at 03:34):

Can anyone think of a cute category-theoretic "paradox" one gets from assuming the projection $p: S \times T \to S$ in Set is always surjective?

Jason Erbele (Oct 29 2020 at 06:34):

John Baez said:

Kim-Ee Yeoh said:

Honestly curious, do you also scream in pain that we can't divide by zero?

You weren't asking me, but: I should have done this at some point. But I can't even remember when I learned you can't divide by zero.

I can remember the time when I found this exciting: assume $a = b$, then
[...]
$a = 0$

so every number equals zero. It was a long time ago!

But if you count how many days ago it was, this proves that it wasn't even yesterday! :upside_down:

I think I was seven when I first encountered (a variation of) that calculation. All these years later, though, who's to stop us from dividing by zero anyway?

Fabrizio Genovese (Oct 29 2020 at 10:57):

Kim-Ee Yeoh said:

Fabrizio Genovese said:

John Baez said:

Note that in $\mathsf{Set}$ the product projection $\emptyset \times X \to X$ is usually not epic.

This is one of the most unpleasing realities I've faced in the last days. I literally screamt in pain when I saw this. WTF seriously, this should be wrong.

Honestly curious, do you also scream in pain that we can't divide by zero? Decategorified to its core, that set product is almost but not quite epic projects down to how multiplication on the naturals is almost but not quite (left-)invertible.

Way less, because I have a clearer intuition of why this is not possible coming from calculus

Fabrizio Genovese (Oct 29 2020 at 10:58):

Essentially if you see division as a function of real numbers you see that it diverges at 0, and that for any fixed value on the nominator left and right limits do not coincide. I find this convincing enough to think that dividing by zero could be a bad idea

Fabrizio Genovese (Oct 29 2020 at 10:59):

Still, if by "division" you mean "multiplicative inverse" as in field theory then yes, I find fields very unsatisfying, especially because you cannot really make sense of them using universal algebra. Meadows are way more pleasing in this sense, imho.