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: 3 for 2 Property

Adam Millar (Dec 10 2023 at 19:48):

Hello!
My name is Adam and I am trying to get back up to speed with category theory after a ~5 year hiatus.
image.png
A friend of mine has shared his problem sets for a course to help me practice and I wonder if anyone would be willing to ... evaluate... (which isn't to say grade) some of my solutions.
I am also very rusty with LaTeX formatting and proof styling in general, so I welcome feedback about those as well.
Am I on the right track for these 3-for-2 cases?
Is there a better setup for 'equational' reasoning?

David Egolf (Dec 10 2023 at 20:06):

What you wrote makes sense to me! (Edit: I thought I spotted a mistake, but upon reading more carefully, it looks correct to me!)

Kevin Arlin (Dec 10 2023 at 20:07):

This all looks good so far! Hopefully you've noticed that this is only a solution to part of the statement.

Kevin Arlin (Dec 10 2023 at 20:07):

I wouldn't be quite so persnickety about the formatting and justifying each equational transformation explicitly. Mathematicians actually write in paragraphs and this is often much better for understanding the core ideas of something you're working on than this laborious two-column proof format. I might rewrite your argument somewhat like this:

Kevin Arlin (Dec 10 2023 at 20:07):

Suppose $f:A\to B,g: B\to C$ are isomorphisms, with inverses $f^{-1},g^{-1}.$ Then we claim $f^{-1}\circ g^{-1} = (g\circ f)^{-1}.$ Indeed, we have $(f^{-1}\circ g^{-1})\circ (g\circ f)= f^{-1}\circ f=\mathrm{id}_A$ and $(g\circ f)\circ (f^{-1}\circ g^{-1})=g\circ g^{-1}=\mathrm{id}_C,$ which establishes the claim.

Kevin Arlin (Dec 10 2023 at 20:08):

Notice that I haven't explicitly said where I'm using the definition of the inverse of a morphism, or even restated what that definition is. You could add either of these, but it's the only thing I could possibly be using here so it's quite standard not to insist on highlighting it. This is a simple enough argument that it's counterproductive to make a big meal of it.

David Egolf (Dec 10 2023 at 20:14):

If I were to try and prove this, I would also consider proving some general things first, so that each of the three cases can be proved using a quicker argument. (But this is a matter of personal preference!)

Regarding LaTex, I really enjoy using Obsidian for typing up my (informal) math notes. I find it a lot faster and easier than using something like Overleaf.

Adam Millar (Dec 10 2023 at 21:03):

Thank your both for your replies.
Yes, I know I have two other cases to cover for the entire 3-for-2, where $g \circ f$, is assumed to be iso. For each, one of L/R inverse is fast but I am having some more trouble with the other.
I confess that Lemmon-style natural deduction proofs, and mathematical logic in general, is what sparked my love for pure mathematics, so I have a penchant for 'explicit' and 'laborious' proofs. :sweat_smile:
It's one way that I try to ensure my derivations are rigorous, but I know also that it becomes unsustainable pretty quickly.
This is also my first time using Zulip; would it be okay for me to upload images of 'hand-written' solutions?
I write them with a stylus on a tablet before transferring them to Overleaf.

Adam Millar (Dec 10 2023 at 21:36):

Here is what I meant about one side being trickier than the other

Adam Millar (Dec 10 2023 at 21:37):

image.png

Adam Millar (Dec 10 2023 at 21:37):

For this case the fact that it is a right inverse is immediate... but I am not sure how to show the left inverse.
Have I even chosen the right morphisms?
There are so few these seem like the only candidates!

Adam Millar (Dec 10 2023 at 22:21):

Here is what I came up with, and I suppose even I am now feeling the tedium of the 'one substitution at a time' equational reasoning :sweat_smile:
image.png

David Egolf (Dec 10 2023 at 23:43):

That looks alright to me, as far as I can tell after looking through it quickly!

To make things less laborious, you might find it interesting to prove these two things, which can help enable a quicker proof (I believe):

• composing any two isomorphism yields an isomorphism
• the inverse of any isomorphism is an isomorphism

If we accept (or prove!) these two things, here's how one way to quickly prove that $g$ is an isomorphism if $f$ and $h$ are:

• We know that $h = g \circ f$
• Since $f$ is an isomorphism it has an inverse $f^{-1}$. Composing on the right with $f^{-1}$ we get: $h \circ f^{-1} = g$
• Since the inverse of an isomorphism is an isomorphism, $f^{-1}$ is an isomorphism. And $h$ is an isomorphism by assumption. So $h \circ f^{-1}=g$ is given by composing two isomorphisms and hence $g$ is an isomorphism.

Adam Millar (Dec 10 2023 at 23:54):

David,
Thank you again for your responses!
The first case I proved (in the first image) shows that ‘composing two isos is iso’ correct?
For the second result, if we do not specify R/L inverse, we mean it is both, correct?
That is ‘the inverse of an iso is iso’ means ‘the (two-sided) inverse of an iso is iso?’

Adam Millar (Dec 10 2023 at 23:54):

I ask mostly because the very next exercise requires me to distinguish carefully between right and left inverses

David Egolf (Dec 11 2023 at 00:15):

You are welcome!

Yes, I think you showed above that if $f$ and $g$ are isomorphisms, then $f \circ g$ is an isomorphism. So, composing two isomorphisms gives us an isomorphism.

Regarding left and right inverses, for $f$ to be an isomorphism, it has to have a two-sided inverse. For example, in "Category Theory in Context", Riehl defines an isomorphism like this "An isomorphism in a category is a morphism $f: X \to Y$ for which there exists a morphism $g: Y \to X$ so that $g \circ f = 1_X$ and $f \circ g = 1_Y$."

In addition, if an isomorphism $f$ has a left (or right) inverse $k$, that one-sided inverse is actually a two sided inverse! (So $k = f^{-1}$). A proof is given on the nLab: here. You might also find it interesting to prove this.

Adam Millar (Dec 11 2023 at 00:27):

This last point (that left inverses of iso are also right inverses, and therefore iso) is one of the exercises!

John Baez (Dec 11 2023 at 10:11):

While thinking about such things it's fun to find the smallest category that has a morphism that has a left inverse that is not its right inverse. It only need to have one object. How many morphisms does it need to have?

John Baez (Dec 11 2023 at 10:12):

(Just throwing this out there in case anyone wants to think more about left vs. right inverses.)

Jonas Frey (Dec 11 2023 at 18:15):

I'm not sure I would call the solution you're hinting at the "smallest one" :smiley:

Adam Millar (Dec 11 2023 at 21:31):

Right by ‘small’ do we only mean the size of the class of objects?
The way you phrase it, and Jonas’ response make me think many morphisms are necessary… :sweat_smile:
Also, we mean an abstract category, and just some morphism equations?
Or is the example a concrete category where the single object has internal structure beyond its morphisms?

John Baez (Dec 11 2023 at 23:25):

By "small" I meant having the fewest objects and/or morphisms - not a very precise condition, but we'll probably recognize the winner when we see it! I slipped and suggested using one object, but I guess Jonas is hinting that then we inevitably get lots of morphisms.

John Baez (Dec 11 2023 at 23:27):

Maybe I'll give some more hints. Let's try a category with objects $x$ and $y$, and morphisms $f: x \to y$ and $g : y \to x$ such that $f$ is the left inverse of $g$:

$f g = 1_y$

but not the right inverse:

$g f \ne 1_x$

John Baez (Dec 11 2023 at 23:28):

If we go this route, what's the minimum number of morphisms our category can have?

Jason Erbele (Dec 12 2023 at 04:04):

I think there is a bigger problem with the one-object "smallest one" than the "smallest" part.

Mike Shulman (Dec 12 2023 at 04:44):

Unless any of us are telepathic or have a side channel to John, I don't think we can know which one-object category he had in mind. There certainly exist one-object categories containing such a morphism. I don't know offhand whether there are any finite ones, but at least there's an initial one (which I think is infinite) which has some claim to be called the "smallest".

Todd Trimble (Dec 12 2023 at 04:46):

I don't think there are any finite examples. It would have to be a finite monoid with a section-retraction pair. But then left multiplication by the section would be an injective function from a finite set to itself, and then...

Jason Erbele (Dec 12 2023 at 05:33):

I may be confused, but I thought any one-object category can be viewed as a group, where the morphisms of the category are the group elements, and the composition of morphisms is group multiplication. I'm pretty sure inverses in a group are always two-sided.

Mike Shulman (Dec 12 2023 at 05:35):

A monoid, not a group.

Morgan Rogers (he/him) (Dec 12 2023 at 09:09):

John Baez said:

Maybe I'll give some more hints. Let's try a category with objects $x$ and $y$, and morphisms $f: x \to y$ and $g : y \to x$ such that $f$ is the left inverse of $g$:

$f g = 1_y$

but not the right inverse:

$g f \ne 1_x$

@Adam Millar focus on this version ;)

John Baez (Dec 12 2023 at 09:16):

Right, my thought of making $x = y$ was a last-minute extra twist that I soon came to regret. Focus on this version, everyone.

Adam Millar (Dec 13 2023 at 13:12):

Thank you all for your responses.
I have my solution to
"If $f$ has a left inverse $g$ that is iso, then $f$ is also iso;
image.png

Adam Millar (Dec 13 2023 at 13:15):

This is my next point of attack.
if $fg = 1_y$ but $gf \neq1_x$,
We are asking 'how many (other?) morphisms are necessary to make this true?'
Or, put another way, if $gf \neq1_x$ what DOES $gf = ?$

Morgan Rogers (he/him) said:

John Baez said:

Maybe I'll give some more hints. Let's try a category with objects $x$ and $y$, and morphisms $f: x \to y$ and $g : y \to x$ such that $f$ is the left inverse of $g$:

$f g = 1_y$

but not the right inverse:

$g f \ne 1_x$

Adam Millar focus on this version ;)

Adam Millar (Dec 13 2023 at 13:29):

Also, I made this proof.
image.png

John Baez (Dec 13 2023 at 14:41):

Great! I'm beginning to want you to tackle my puzzle (the version Morgan Rogers recommended), because in addition to proving theorems it's crucial to learn how to find examples and counterexamples. Theorems are about generality, but examples force you to master specificity.

John Baez (Dec 13 2023 at 14:43):

Even if all you want to do in life is prove theorems, finding counterexamples is crucial, because they tell you when some would-be theorem is actually false, or when a hoped-for proof can't work. This can save you lots of time.

Adam Millar (Dec 13 2023 at 14:55):

John Baez said:

Great! I'm beginning to want you to tackle my puzzle (the version Morgan Rogers recommended), because in addition to proving theorems it's crucial to learn how to find examples and counterexamples. Theorems are about generality, but examples force you to master specificity.

Oh John, you are a man after my own heart.
Even right now, in my 'intro to proof-based math' course for first year undergrads, I use almost exactly this language when exploring new topics with students.
First we make a general claim, then try to prove it wrong (produce a counterexample).
The counterexample reveals what further assumptions might be necessary to make the theorem follow in generality
To use a very basic example;
Claim; If n is divisible by 4 then it is divisible by 12.
Counterexample; If n=16 then 4|n but not 12|n
... what went wrong with 16?
Ah, it isn't divisible by 3!
Ok so THEOREM: If 4|n AND 3|n then 12|n