CSI (29-Oct class):

Transcript of ChatGPT session in class concerning the proof of fact (81) of the slides.

NB: after the class chatGPT was enquired about the circular argument that we had spot in class. The reply to this third question is also given.

Critical thinking:

1. Check these proofs;
2. If ok, compare them with our (1 slide long) proof given in the course slides.

---

Transcript

---

Question - Can you please give me the simplest proof you can find for the following fact: wherever $f \cdot g = id$ holds, then f is surjective and g is injective. Thank you.

---

Of course! 😊 The proof is very simple.

Suppose $f:A\to B$ and $g:B\to A$, and assume that

\[f\circ g=\mathit{id}_B.\]

We want to prove that $f$ is surjective and $g$ is injective.

1. Proof that $f$ is surjective

Take any $y\in B$.

Let $x=g(y)$. Then

\[f(x)=f(g(y))=y.\]

Thus, for every $y\in B$, there exists $x\in A$ such that $f(x)=y$.

Therefore, $f$ is surjective. $\square$

2. Proof that $g$ is injective

Suppose $g(y_1)=g(y_2)$, where $y_1,y_2\in B$.

Applying $f$ to both sides gives

\[f(g(y_1))=f(g(y_2)).\]

Since $f\circ g=\mathit{id}_B$, we obtain

\[y_1=y_2.\]

Therefore, $g$ is injective. $\square$

The key idea: Since $f(g(y))=y$, every element of $B$ is reached by $f$, and two elements of $B$ cannot have the same image under $g$ unless they are equal.} \end{bmatrix}

---

Question - Can you do the same in the point-free style, that is, without handling variables x and y explicitly?

---

Certainly! We can prove both facts directly from $f\circ g=\mathit{id}_B$, without explicitly handling elements.

1. $f$ is surjective

Since

\[f\circ g=\mathit{id}_B,\]

we have

\[\mathit{im}(f\circ g)=B.\]

But

\[\mathit{im}(f\circ g)\subseteq \mathit{im}(f).\]

Hence $\mathit{im}(f)=B$, so $f$ is surjective. $\square$

2. $g$ is injective

Using $f\circ g=\mathit{id}_B$, we obtain

\[\begin{aligned} g\circ f\circ g&=g\circ\mathit{id}_B\\ &=g. \end{aligned}\]

Thus $g\circ f\circ g=g$. By the criterion that a map $g$ is injective if it admits a left inverse, we conclude that $g$ is injective.

More directly, the same identity shows that $g$ has a left inverse, namely $f$, since $f\circ g=\mathit{id}_B$. $\square$

---

Question - But… can you rely on the “criterion that a map g is injective if it admits a left inverse”? Isn’t this what we are trying to prove, after all?

---

You’re absolutely right! We shouldn’t invoke a criterion that is essentially the very fact we’re trying to establish. Thank you for pointing that out.

Here is a genuinely point-free proof, using only composition of functions.

Assume $f\circ g=\mathit{id}_B$, where $f:A\to B$ and $g:B\to A$.

1. $f$ is surjective

We have

\[f\circ g=\mathit{id}_B.\]

Since $f\circ g$ factors through $f$, every element of $B$ lies in the image of $f$. Thus

\[\mathit{im}(f)=B,\]

so $f$ is surjective. $\square$

2. $g$ is injective

Recall that a function $g:B\to A$ is injective precisely when its kernel pair is trivial; equivalently, in the category of sets, the diagonal map

\[\Delta_B:B\to B\times B\]

is the only map needed to express equality of elements.

Now observe that

\[f\circ g=\mathit{id}_B.\]

Consequently,

\[(g\times g)\circ\Delta_B =\Delta_A\circ g.\]

Hence $g$ is injective. $\square$

A small caveat: The second argument, as written, uses categorical language without fully establishing the implication. If you want a completely rigorous point-free proof in the category of sets, we can instead use the fact that $g$ is a split monomorphism and prove directly from the definition of monomorphism that it is injective.

---