# Just because 2 things are opposites, doesn't mean they're just the same but flipped

post by Alok Singh (OldManNick) · 2024-04-03T08:59:43.667Z · LW · GW · 18 comments

This is a link post for https://alok.github.io/2024/03/29/broken-dualities/

## Contents

  The 2 Aspects
warmup: 0 -> 1
Broken Symmetries
None
18 comments


# The 2 Aspects

There’s 2 Aspects to things in general. I will call them Mapping Out and Mapping In, in titlecase so you know they’re distinct concepts.

## warmup: 0 -> 1

Here, 0 is an initial object and 1 is a terminal object. 0 is Mapped Out of because it’s 0 -> and not -> 0. 1 is Mapped Into because it’s -> 1 and not 1 ->. The defining property of an initial object is that it has 1 map to every other object. The defining property of a terminal object (1) is that it has 1 map from every other object.

## Broken Symmetries

• Injective functions have inverses. But the dual statement, that surjective functions always have (at least 1) inverse, is equivalent to the Axiom of Choice!
• a AND (NOT a) = false is just the law of noncontradiction. A simple theorem (unless you’re Graham Priest), but the dual statement a OR (NOT a) = true is the Law of Excluded Middle, which can be derived from a form of the Axiom of Choice, and in particular is not constructively valid.
• Freyd’s Adjoint Functor Theorem sometimes fails to have a left adjoint (Mapping Out), but for foundations-of-mathematics-y reasons: If the left adjoint existed, it would be too big to be a set. No such difficulty for right.
• Googling epimorphism too large to form set gives a lot of stuff. Nothing similar for monomorphism too large to form set

The following is from Paul Garrett, Section 2:

When we look at colimits and coproducts here, it is important to see that, while at an abstract level these things are just the arrows-reversed versions of limits and products, for many classes of naturally-occurring objects there is a sharp asymmetry. For example, while limits are subobjects of products, colimits are quotients of coproducts. In many situations, quotients are more abstract entities than are subobjects. This can be explained from a set-theoretic viewpoint, since elements of a subset are the same sort of thing as elements of the original set, since they are elements of the original set, while elements of quotients are sets of elements of the original.

In particular, in many cases colimits are fragile, and need further details or hypotheses to give us helpful outcomes. For example, while all subspaces of Hausdorff topological spaces are Hausdorff, quotients of Hausdorff topological spaces need not be Hausdorff.

submodules of finitely-generated free modules over principal ideal domains are still free, while quotients certainly need not be.

Indeed, the smooth general use of products and limits is not matched by any similar smoothness in treatment of the arrow-reversed coproducts and colimits, below.

## 18 comments

Comments sorted by top scores.

comment by Algon · 2024-04-03T19:29:19.880Z · LW(p) · GW(p)

This strikes me as deeply puzzling. Why is this the case?

Replies from: alexander-gietelink-oldenziel, tailcalled, OldManNick
comment by Alexander Gietelink Oldenziel (alexander-gietelink-oldenziel) · 2024-04-04T22:23:42.684Z · LW(p) · GW(p)

You are right to think it is puzzling! I am biased but I am of the opinion there are very deep phenomena lurking under these seemingly unimportant oddities.

To the a first degree the answer mostly boils down to the assymmetry in Set, the category of sets. Set certainly doesn't treat limits and colimits the same, so concepts built on top of it (like limits and colimits for ordinary categories) inherit its assymmetry.

As a very concrete instance of the assymmetry in Set: The initial object 0 in Set is the empty set, which has a unique map to any other set (the empty map). The terminal object 1 in set is the set containing one element. Every set X has a unique map to 1.

What about the other way around? Given a set X, what about the maps 1-> X? They exactly correspond to elements x of X ! Cool! Then what about maps X -> 0 ? Ah. Not so interesting. There are none, unless X=0 is empty.

As pointed out by tailcalled, the opposite category of Set can be described as the category of complete atomic boolean algebras, a quite interesting category unto itself... but not equivalent to Set.

Cool, that's all very good but it doesn't explain why Set was assymetric in the first place.

Is this intrinsic? There are certainly natural categories that are equivalent to their opposites (the category of relations is a good examples).

To really understand what's going on here we need to dig deeper. We need to step outside the traditional framework of set theory, and re-examine the foundations of type theory. If we do, we will find that even the very notion of category itself has an underlying bias, a broken duality. To be continued...

Replies from: Algon, tailcalled
comment by Algon · 2024-04-06T10:00:39.525Z · LW(p) · GW(p)

This is an interesting post and I hope that you'll continue it.

comment by tailcalled · 2024-04-05T13:39:01.272Z · LW(p) · GW(p)

I think exponentials and coexponentials are relevant here, since they are good at shuffling things back and forth between the sides of morphisms, which matters for limits and colimits as they are adjunctions (and a particularly nice kind of adjunction, at that).

comment by tailcalled · 2024-04-03T21:44:18.496Z · LW(p) · GW(p)

I wonder if it is related to exponentials vs coexponentials, since categories with both exponentials and coexponentials are posetal. I don't have any particular argument for how that'd work, though.

Replies from: alexander-gietelink-oldenziel, Algon
comment by Alexander Gietelink Oldenziel (alexander-gietelink-oldenziel) · 2024-04-04T22:27:27.174Z · LW(p) · GW(p)

Do you have a reference for this statement? I suppose it is related to Joyal's result that a Boolean category is always a poset, preventing a naive categorical analysis of classical proof theory.

Replies from: tailcalled
comment by tailcalled · 2024-04-05T13:11:23.110Z · LW(p) · GW(p)

I can't remember the entire proof, and maybe I misstated it, but IIRC part of the logic goes as follows:

With exponentials, you can prove that 0 x A ≈ 0, because any morphism 0 x A -> B curries into 0 -> B^A, of which by the universal property of 0, there's only one.

Similarly, with coexponentials, you can prove that 1 + A ≈ 1, because any morphism A -> B+1 cocurries into A-B -> 1, of which there is only one.

So this at least proves that all the objects built out of 0, 1, x and + are trivial. I think there was something funky where you made use of the fact that A -> B can be expressed as 1-(B^A) -> 0 and 1 -> 0^(B-A) to further prove all morphisms trivial, but I can't remember it exactly.

Replies from: tailcalled
comment by tailcalled · 2024-04-05T18:14:22.725Z · LW(p) · GW(p)

Ahh, now I've got it:

First, each morphism f : A -> 0 induces a unique morphism f . pr1 : A x 0 -> 0. Proof: suppose f . pr1 = g . pr1. Then we have f = f . pr1 . (id, f) = g . pr1 . (id, f) = g.

Corollary: if you have exponential objects, then if you have any f : A -> 0, then A ≈ 0, because there's only one morphism 0 -> 0^A.

But, if you have coexponential objects, any hom set A -> B can instead be expressed as a hom set A-B -> 0. This shows A-B ≈ 0, and also all homs are equal.

comment by Algon · 2024-04-03T22:23:23.636Z · LW(p) · GW(p)

Not a category theorist, I only understood this post through set theory analogies, so I have no idea what you just said.

Replies from: tailcalled
comment by tailcalled · 2024-04-04T08:28:45.532Z · LW(p) · GW(p)

Do you know programming? A coexponential  is intuitively roughly speaking an  together with a return position where you can place a . It's how function calls are implemented in computers, as morphisms , corresponding to the fact that you have the parameters  and the call stack .

(More formally: given a coproduct (~disjoint union) , a coexponential  is defined based on  being equivalent to .)

Replies from: Algon
comment by Algon · 2024-04-04T20:11:19.638Z · LW(p) · GW(p)

OK, that explanation helped me understand coexponentials a bit but I'm unsure how it's relevant to the assymetry between the examples Alok gave.

comment by Alok Singh (OldManNick) · 2024-04-03T19:31:04.424Z · LW(p) · GW(p)

"This" is the broken duality phenomenon?

Replies from: Algon
comment by Algon · 2024-04-03T20:15:39.774Z · LW(p) · GW(p)

Yeah.

comment by Alexander Gietelink Oldenziel (alexander-gietelink-oldenziel) · 2024-04-03T10:29:19.802Z · LW(p) · GW(p)

A simple yet peculiar truth :

A category is not generically isomorphic to its opposite.

Replies from: tailcalled
comment by tailcalled · 2024-04-03T11:15:19.506Z · LW(p) · GW(p)

A notable counterexample is FinVect, which has an equivalence of categories FinVect -> FinVect^op.

comment by tailcalled · 2024-04-03T09:52:53.030Z · LW(p) · GW(p)

Are you familiar with the category of complete atomic boolean algebras?

Replies from: OldManNick
comment by Alok Singh (OldManNick) · 2024-04-03T18:12:46.514Z · LW(p) · GW(p)

Through stone duality. What about them in particular?

Replies from: tailcalled
comment by tailcalled · 2024-04-03T18:19:16.393Z · LW(p) · GW(p)

Trivially, a co-X in C^op is the same but flipped as an X in C.

Then as you know, Stone duality says that CABA = Set^op.

So a co-X in CABA is the same but flipped as an X in Set.

(I think it works constructively too if one replaces Boolean with Heyting?)