Definition of epimorphism and equivalence to 'surjectivity'

[Math Amateur]

I am reading Paolo Aluffi's book Algebra: Chapter 0 which takes a (moderately) category theory oriented and infused approach to algebra.

I am studying chapter 1: Set Theory and Categories and need help with formulating a definition of an epimorphism and with then proving it to be surjective.

To explain why Aluffi is taking this approach to the definition of an epimorphism, I am now providing Aluffi's definition of monomorphism and his prrof that his definition implies injectivity.

Aluffi's definition of monomorphism is as follows:

View attachment 2564

Aluffi then asks the reader to formulate a similar definition for an epimorphism and to prove that the definition is equivalent to 'surjective'

Can someone please help me with this task?

I now provide Aluffi page 14 to give MHB members the context of the task/exercise:

View attachment 2565

Peter

 

[Deveno]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

The statement you get when you "reverse the arrows" is:

$g:B \to A$ is an epimorphism if for any two morphisms $\beta_1,\beta_2:A \to Z$ we have:

$\beta_1 \circ g = \beta_2 \circ g \implies \beta_1 = \beta_2$

I believe Mr. Aluffi's intention is for you to use the results of Proposition 2.1 (2), which is Exercise 2.2. If you have not completed that exercise, you should do so, in order to mimic the result on monomorphisms.

There are some rather deep issues involved, here. First of all, in the general theory, there are 3 different things:

1. Sections (maps which have right-inverses)
2. Epimorphisms (maps which satisfy the implication given above of right-cancellation)
3. Surjective, or onto, maps

These 3 things are, rather surprisingly, not quite the same. And this may be confusing, because that is what you are currently trying to prove! They are, however (if one accepts the axiom of choice), the same thing in the category $\mathbf{Set}$. So the assumption that $g$ is a FUNCTION, is an important one, here.

If you have completed Exercise 2.2, we can continue this discussion. If not, I suggest we delay it until you do.

 

[Math Amateur]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

The statement you get when you "reverse the arrows" is:

$g:B \to A$ is an epimorphism if for any two morphisms $\beta_1,\beta_2:A \to Z$ we have:

$\beta_1 \circ g = \beta_2 \circ g \implies \beta_1 = \beta_2$

I believe Mr. Aluffi's intention is for you to use the results of Proposition 2.1 (2), which is Exercise 2.2. If you have not completed that exercise, you should do so, in order to mimic the result on monomorphisms.

There are some rather deep issues involved, here. First of all, in the general theory, there are 3 different things:

1. Sections (maps which have right-inverses)
2. Epimorphisms (maps which satisfy the implication given above of right-cancellation)
3. Surjective, or onto, maps

These 3 things are, rather surprisingly, not quite the same. And this may be confusing, because that is what you are currently trying to prove! They are, however (if one accepts the axiom of choice), the same thing in the category $\mathbf{Set}$. So the assumption that $g$ is a FUNCTION, is an important one, here.

If you have completed Exercise 2.2, we can continue this discussion. If not, I suggest we delay it until you do.

Thanks Deveno ... will definitely have a try at Exercise 2.2

Peter

 

[Math Amateur]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

The statement you get when you "reverse the arrows" is:

$g:B \to A$ is an epimorphism if for any two morphisms $\beta_1,\beta_2:A \to Z$ we have:

$\beta_1 \circ g = \beta_2 \circ g \implies \beta_1 = \beta_2$

I believe Mr. Aluffi's intention is for you to use the results of Proposition 2.1 (2), which is Exercise 2.2. If you have not completed that exercise, you should do so, in order to mimic the result on monomorphisms.

There are some rather deep issues involved, here. First of all, in the general theory, there are 3 different things:

1. Sections (maps which have right-inverses)
2. Epimorphisms (maps which satisfy the implication given above of right-cancellation)
3. Surjective, or onto, maps

These 3 things are, rather surprisingly, not quite the same. And this may be confusing, because that is what you are currently trying to prove! They are, however (if one accepts the axiom of choice), the same thing in the category $\mathbf{Set}$. So the assumption that $g$ is a FUNCTION, is an important one, here.

If you have completed Exercise 2.2, we can continue this discussion. If not, I suggest we delay it until you do.

I have attempted to prove Aluffi Proposition 2.1(2) but need some help with the second part of the proof.

Proposition 2.1(2) reads as follows:

----------------------------------------------------------------------------

"Assume that $$ A \ne \emptyset $$ and let $$ f : \ A \to B $$ be a function.

(2) f has a right-inverse $$ \Longleftrightarrow f $$ is surjective

----------------------------------------------------------------------------

Proof:

Assume that $$ f $$ has a right inverse.

Then $$ \ \exists \ \ g : \ B \to A $$ such that $$ f \circ g = id_B $$

Now, to show that $$ f : \ A \to B $$ is surjective, we need to show that for any $$ b \in B \ \ \exists \ \ a \in A $$ such that $$ f(a) = b $$.

Take arbitrary $$ b \in B $$.

Then since $$ f \circ g = id_B $$ we have $$ f(g(b)) = b $$, so then there exists $$ a = g(b)$$ such that f(a) = f(g(b)) = b which shows that f is surjective.

Now, assume $$ f : \ A \to B $$ is surjective.

Require to show $$ \ \exists \ \ $$ function g such that $$ f \circ g = id_B $$.

But how to proceed?

Can someone please help?

Peter

 

[Deveno]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

Well, this is kind of tricky.

Consider the family of sets:

$\{f^{-1}(b): b \in B\}$.

If we knew that for each set $f^{-1}(b)$, for a particular $b$, we could choose an element $x \in f^{-1}(b) \subseteq A$, then we could define the function:

$g: B \to A$ by $g(b) = x$. Note that since $f$ is surjective, we know at least that every pre-image set $f^{-1}(b)$ is non-empty.

Now, for such a function $g$ (which is called a CHOICE function for the collection $\{f^{-1}(b): b \in B\}$), we have:

$(f\circ g)(b) = f(g(b)) = f(x) = b$ (since $x \in f^{-1}(b)$ so $f(x) = b$), that is:

$f \circ g = 1_B$.

So, the entire argument here rests on the plausibility of defining the "choice function" $g$. It turns out that for an ARBITRARY collection of non-empty sets, there is no "well-defined" method of defining $g$. In the end, mathematicians have thrown their hands up in the air, and said: "well, this OUGHT to be true, and therefore we'll just say it's true". This admission of defeat is known as the Axiom of Choice, and is neither affirmed nor denied by the other axioms of set theory.

Many important statements in math are actually equivalent to the axiom of choice, including:

Every vector space has a basis.
Every ring (with identity $1 \neq 0$) has a maximal ideal (Krull's Theorem).
Every product of compact spaces is compact (Tychonoff's Theorem).
Every small category has a skeleton.

 

[Math Amateur]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

Well, this is kind of tricky.

Consider the family of sets:

$\{f^{-1}(b): b \in B\}$.

If we knew that for each set $f^{-1}(b)$, for a particular $b$, we could choose an element $x \in f^{-1}(b) \subseteq A$, then we could define the function:

$g: B \to A$ by $g(b) = x$. Note that since $f$ is surjective, we know at least that every pre-image set $f^{-1}(b)$ is non-empty.

Now, for such a function $g$ (which is called a CHOICE function for the collection $\{f^{-1}(b): b \in B\}$), we have:

$(f\circ g)(b) = f(g(b)) = f(x) = b$ (since $x \in f^{-1}(b)$ so $f(x) = b$), that is:

$f \circ g = 1_B$.

So, the entire argument here rests on the plausibility of defining the "choice function" $g$. It turns out that for an ARBITRARY collection of non-empty sets, there is no "well-defined" method of defining $g$. In the end, mathematicians have thrown their hands up in the air, and said: "well, this OUGHT to be true, and therefore we'll just say it's true". This admission of defeat is known as the Axiom of Choice, and is neither affirmed nor denied by the other axioms of set theory.

Many important statements in math are actually equivalent to the axiom of choice, including:

Every vector space has a basis.
Every ring (with identity $1 \neq 0$) has a maximal ideal (Krull's Theorem).
Every product of compact spaces is compact (Tychonoff's Theorem).
Every small category has a skeleton.

Thanks Deveno ... most helpful and interesting ... particularly regarding the Axiom of Choice!

Are you able to help with the original question concerning a category theoretic definition of an epimorphism and a proof that it is equivalent to surjectivity.

Peter

 

[Deveno]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

Suppose $g: B \to A$ is surjective, so that it has a right-inverse, so there is a function $f: A \to B$ with:

$g \circ f = 1_A$.

Now if $\beta_1,\beta_2:A \to Z$ are any two functions such that:

$\beta_1 \circ g = \beta_2 \circ g$, then certainly:

$(\beta_1 \circ g) \circ f = (\beta_2 \circ g) \circ f$ whence:

$\beta_1 \circ (g \circ f) = \beta_2 \circ (g \circ f)$ (by associativity of composition)

$\beta_1 \circ 1_A = \beta_2 \circ 1_A$ and so:

$\beta_1 = \beta_2$, that is: $g$ is an epimorphism.

Proving that an epimorphism is surjective is a bit trickier: we need to find the "right" pair of functions to compose with $g$. So define:

$\beta_1 : A \to \{0,1\}$ by $\beta_1(a) = 1$ if $a \in g(B)$, and $\beta_1(a) = 0$, otherwise.

(this function is called the "characteristic function of $g(B)$", as it detects membership in that set), and define:

$\beta_2 : A \to \{0,1\}$ by $\beta_2(a) = 1$, for all $a \in A$ (this is just a constant function).

Now, it is clear that:

$(\beta_1 \circ g)(b) = \beta_1(g(b)) = 1 = \beta_2(g(b)) = (\beta_2 \circ g)(b)$ for all $b \in B$, so $\beta_1 \circ g = \beta_2 \circ g$.

Since $g$ is an epimorphism, we must have $\beta_1 = \beta_2$, which can only be the case if $g(B) = A$, that is: $g$ is surjective.

********************

The above proof highlights the special role played by two-element sets in the category $\mathbf{Set}$: we can identify (up to set-isomorphism, that is, via a bijection) a subset $A$ of another set $S$ as a FUNCTION:

$\chi_A:S \to \{0,1\}$

by $\chi_A(s) = 1 \iff s \in A$

This establishes a "natural" (you will encounter a more precise definition of this adjective later) isomorphism:

$2^S \leftrightarrow \mathcal{P}(S)$

between functions from $S$ to a a 2-element set $2 = \{0,1\}$ (this "definition of 2" is, by the way, consistent with the standard set-theoretic definition of natural numbers, where the successor of a set $x$ is defined as $s(x) = x \cup \{x\}$) and the power set of $S$. Explicitly, for any $A \in \mathcal{P}(S)$, this correspondence is:

$\chi_A \leftrightarrow A$.

Because of this bijection, the two-element set $2$ is called a sub-object classifier in the category $\mathbf{Set}$. There are two very special arrows in $\mathbf{Set}$, which have many uses in logic and computer science:

$\mathbf{true}:\{0\} \to \{0,1\}$ which sends $0 \to 1$
$\mathbf{false}:\{0\} \to \{0,1\}$ which sends $0 \to 0$

because of these two arrows, the object 2 is sometimes also called "the truth-object".

********************

You might be thinking, after reading all this: "well, how was I supposed to come up with the characteristic function?". It's a fair question: it may seem like I pulled a rabbit out of a hat. The connections I have outlined above suggest that something very deep, something essential​ is going on here. You would do well to reflect on this a bit-it will make what lies ahead much easier going.

 

[Math Amateur]

Re: Definition of epimorphism amd equivalence to 'surjectivity'

Suppose $g: B \to A$ is surjective, so that it has a right-inverse, so there is a function $f: B \to A$ with:

$g \circ f = 1_A$.

Now if $\beta_1,\beta_2:A \to Z$ are any two functions such that:

$\beta_1 \circ g = \beta_2 \circ g$, then certainly:

$(\beta_1 \circ g) \circ f = (\beta_2 \circ g) \circ f$ whence:

$\beta_1 \circ (g \circ f) = \beta_2 \circ (g \circ f)$ (by associativity of composition)

$\beta_1 \circ 1_A = \beta_2 \circ 1_A$ and so:

$\beta_1 = \beta_2$, that is: $g$ is an epimorphism.

Proving that an epimorphism is surjective is a bit trickier: we need to find the "right" pair of functions to compose with $g$. So define:

$\beta_1 : A \to \{0,1\}$ by $\beta_1(a) = 1$ if $a \in g(B)$, and $\beta_1(a) = 0$, otherwise.

(this function is called the "characteristic function of $g(B)$", as it detects membership in that set), and define:

$\beta_2 : A \to \{0,1\}$ by $\beta_2(a) = 1$, for all $a \in A$ (this is just a constant function).

Now, it is clear that:

$(\beta_1 \circ g)(b) = \beta_1(g(b)) = 1 = \beta_2(g(b)) = (\beta_2 \circ g)(b)$ for all $b \in B$, so $\beta_1 \circ g = \beta_2 \circ g$.

Since $g$ is an epimorphism, we must have $\beta_1 = \beta_2$, which can only be the case if $g(B) = A$, that is: $g$ is surjective.

********************

The above proof highlights the special role played by two-element sets in the category $\mathbf{Set}$: we can identify (up to set-isomorphism, that is, via a bijection) a subset $A$ of another set $S$ as a FUNCTION:

$\chi_A:S \to \{0,1\}$

by $\chi_A(s) = 1 \iff s \in A$

This establishes a "natural" (you will encounter a more precise definition of this adjective later) isomorphism:

$2^S \leftrightarrow \mathcal{P}(S)$

between functions from $S$ to a a 2-element set $2 = \{0,1\}$ (this "definition of 2" is, by the way, consistent with the standard set-theoretic definition of natural numbers, where the successor of a set $x$ is defined as $s(x) = x \cup \{x\}$) and the power set of $S$. Explicitly, for any $A \in \mathcal{P}(S)$, this correspondence is:

$\chi_A \leftrightarrow A$.

Because of this bijection, the two-element set $2$ is called a sub-object classifier in the category $\mathbf{Set}$. There are two very special arrows in $\mathbf{Set}$, which have many uses in logic and computer science:

$\mathbf{true}:\{0\} \to \{0,1\}$ which sends $0 \to 1$
$\mathbf{false}:\{0\} \to \{0,1\}$ which sends $0 \to 0$

because of these two arrows, the object 2 is sometimes also called "the truth-object".

********************

You might be thinking, after reading all this: "well, how was I supposed to come up with the characteristic function?". It's a fair question: it may seem like I pulled a rabbit out of a hat. The connections I have outlined above suggest that something very deep, something essential​ is going on here. You would do well to reflect on this a bit-it will make what lies ahead much easier going.

Thanks for the extensive help, Deveno

Just working carefully through your post now ...

Most grateful for the help!

Peter