Home > Archive > Functional > June 2007 > monomorphisms, epimorphisms, and isomorphisms
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
monomorphisms, epimorphisms, and isomorphisms
|
|
| Thant Tessman 2007-06-11, 10:05 pm |
|
I'm trudging my way through Pierce's "Basic Category Theory for Computer
Scientists," and I definitely think I'm missing some background material.
In particular, I'm having a hard time understanding epimorphisms.
Pierce defines 'monomorphism' like so:
"An arrow f : B -> C in a category C is a monomorphism if, for any pair
of C-arrows g : A -> B and h : A -> B, the equality f o g = f o h
implies that g = h."
First off, is the "C" in "category C" different than the "C" in "f : B
-> C"?
Second, why the goofy formulation? Why the need to compose g and h with
f? Is it because in category theory we don't talk about the objects but
only the arrows? Or is it to account for some very strange category
where a goofy f might not bother to distinguish in some way between g
and h, and therefore they are, in some sense, equal?
Anyway, I think I see how the definition of monomorphism implies that
the only time a function can evaluate to the same value is if it is
provided the same argument--what he refers to as an "injective function"
in set theory. That is, unique arguments always produce unique results.
Here is 'epimorpism':
"An arrow f : A -> B is an epimorphism if, for any pair of arrows g : B
-> C, and h : B -> C, the equality g o f = h o f implies g = h."
He says that in set theory, this corresponds to surjective functions. a
function is surjective if for each b element of B there is an a element
of A for which f(a) = b. I understand this to mean that every element in
the codomain can be produced by the function f given the right unique
element in the domain.
I don't understand how this follows from the definition of epimorphism,
and I don't understand how an epimorphism is different than an
isomorphism. The example he gives about how there are epimorphisms that
*aren't* surjective doesn't seem to distinguish epimorphisms from
monomorphisms. So I'm  .
Are there books I need to have read before reading this one? Is this the
right group to ask a question like this?
-thant
| |
| Chris Smith 2007-06-11, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Pierce defines 'monomorphism' like so:
>
> "An arrow f : B -> C in a category C is a monomorphism if, for any pair
> of C-arrows g : A -> B and h : A -> B, the equality f o g = f o h
> implies that g = h."
>
> First off, is the "C" in "category C" different than the "C" in "f : B
> -> C"?
Yes. The non-bold-C is an object in the category bold-C.
> Second, why the goofy formulation? Why the need to compose g and h with
> f? Is it because in category theory we don't talk about the objects but
> only the arrows?
Remember that in category Set, the objects are sets. The objects are
NOT members of sets. The "goofy" definition is because the set-
theoretic definition of an injection, which the "monomorphism" concept
is approximating, has to do with members of sets. In category theory we
don't talk about members of sets, because they may not exist. The sets
themselves are fine things to talk about -- because they're just
objects. Monomorphism, though, is defined for all categories regardless
of whether they have "members", so you can NOT talk about members.
Most of the standard categories (sets, posets, monoids, etc.) all have
members of their objects. Don't let that confuse you; Pierce has
already, by now, given several examples of categories where there is no
concept of "members" of the objects -- e.g., the single-poset-as-
category example.
> Anyway, I think I see how the definition of monomorphism implies that
> the only time a function can evaluate to the same value is if it is
> provided the same argument--what he refers to as an "injective function"
> in set theory. That is, unique arguments always produce unique results.
You are either just being sloppy with your words, or are
misunderstanding something fundamental. Arrows are not functions. They
are just arrows; that's all. They come from an object, and go to an
object, and they are related by this 'o' operator. If you can ignore
that the source is confusingly called a "domain", or that the
destination is confusingly called a "codomain", things will be clearer.
In particular, arrows do not take "arguments" or "evaluate" to anything.
> Here is 'epimorpism':
>
> "An arrow f : A -> B is an epimorphism if, for any pair of arrows g : B
> -> C, and h : B -> C, the equality g o f = h o f implies g = h."
>
> He says that in set theory, this corresponds to surjective functions. a
> function is surjective if for each b element of B there is an a element
> of A for which f(a) = b. I understand this to mean that every element in
> the codomain can be produced by the function f given the right unique
> element in the domain.
Right (in set theory; none of this has meaning for arbitrary
categories).
> I don't understand how this follows from the definition of epimorphism,
> and I don't understand how an epimorphism is different than an
> isomorphism.
I found the correspondence to surjective functions in the category Set a
little tricky, as well. A way to think of it is this. If g o f = h o f
implies g = h, then f can't leave g or h any room to differ. If f were
not surjective, then g and h could do something different for the
results not produced by f, so f wouldn't be an epimorphism. On the
other hand, if f is surjective, then it exercises all possible inputs to
g and h. If g and h evaluate to the same thing for all inputs then they
are equal, so f is an epimorphism.
> Are there books I need to have read before reading this one? Is this the
> right group to ask a question like this?
This group is probably fine. sci.math could work, too, if you're
willing to ignore the 90% of trollish posts about the Cantorian
conspiracy to take over the world and crush "brilliant" amateur
mathematicians.
--
Chris Smith
| |
| Jose Juan Mendoza Rodriguez 2007-06-11, 10:05 pm |
| Hi,
> is the "C" in "category C" different than the "C" in "f : B -> C"?
Yes, they are different. The first one is the name of the category,
and it is probably written in boldface or some other special font.
The second is the name of an object.
> Why the need to compose g and h with f? Is it because in category
> theory we don't talk about the objects but only the arrows?
It is because we don't talk about elements, but only about objects
and arrows. Think of "f o g = f o h" as being "f(g) = f(h)",
only that g and h are "variable elements". In this way you obtain
the definition of an injective function in the category of sets and
functions. As you have vaguely noticed, f "confuses" the structure
of the object B, and therefore cannot distinguish between g and h.
> I don't understand how an epimorphism is different than an isomorphism.
Simple: the categorical definitions are different, and so the concepts
are different. You are confusing abstract definitions with the particular
situation in the category of sets and functions. It will be useful for
you to think of a category as being just a (possibly infinite) graph,
where objects correspond to nodes and paths to morphisms. In fact,
any graph can be turned into a category in this way.
> The example he gives about how there are epimorphisms that
> *aren't* surjective doesn't seem to distinguish epimorphisms from
> monomorphisms.
I don't have a copy of Pierce's book, but I am sure that the example
he gives does not refer to the category of sets. In Set, a function
is surjective if, and only if, it is epi. You are confusing
different categories. In the category of monoids and monoid
homomorphisms, a morphism might be epi without being surjective,
but I insist that this is a *different* category.
Kind regards.
--
Jose Juan Mendoza Rodriguez
let me=josejuanmr in
let privacy=iespana in
let net=es in
me@privacy.net
| |
| Thant Tessman 2007-06-11, 10:05 pm |
| Chris Smith wrote:
> You are either just being sloppy with your words, or are
> misunderstanding something fundamental.
The latter, no question!
Chris Smith wrote:
> Remember that in category Set, the objects are sets. The objects are
> NOT members of sets. The "goofy" definition is because the set-
> theoretic definition of an injection, which the "monomorphism" concept
> is approximating, has to do with members of sets. [...]
and
> Arrows are not functions. They
> are just arrows; that's all. They come from an object, and go to an
> object, and they are related by this 'o' operator.
and elsewhere, Jose Juan Mendoza Rodriguez:
> It is because we don't talk about elements, but only about objects
> and arrows. Think of "f o g = f o h" as being "f(g) = f(h)",
> only that g and h are "variable elements". [...]
Okay, so 'f' is the arrow and 'g' and 'h' are the objects? And the
objects can be functions, but that I shouldn't let functional
programming confuse me about what's really going on here? And when we're
talking monomorphism, epimorphism, and isomorphism, we're really talking
about the nature of 'f', not 'g' and 'h' as such?
And all this talk of injection and surjection is merely metaphor?
Okay, I think I gotta start the book all over.
Elsewhere, Marshall:
> I still can't figure out for the life of me what it's *for.*
:-)
There's something later in the book that might be relevant to something
I've been thinking about for a while. Then again, it might not. I'll let
you know...
Thanks for all the replies. I will ponder them.
-thant
| |
| Jose Juan Mendoza Rodriguez 2007-06-11, 10:05 pm |
| Hi,
> Okay, so 'f' is the arrow and 'g' and 'h' are the objects?
I said "elements", not "objects". Sets are particular instances
of objects. Functions are particular instances of morphisms.
Elements are just constant functions, and so they are also morphisms.
By the way, I made a mistake in my message
<466d7b1d$0$90274$14726298@news.sunsite.dk>
> f "confuses" the structure of the object B, and therefore
> cannot distinguish between g and h.
That sentence should be negative: if f : B -> C is a monomorphism,
then f preserves the structure of the object B.
Kind regards.
--
Jose Juan Mendoza Rodriguez
let me=josejuanmr in
let privacy=iespana in
let net=es in
me@privacy.net
| |
| Neelakantan Krishnaswami 2007-06-11, 10:05 pm |
| In article <<f4jn0q$61d$1@news.xmission.com>>,
Thant Tessman <adm@standarddeviance.com> wrote:
>
> I'm trudging my way through Pierce's "Basic Category Theory for Computer
> Scientists," and I definitely think I'm missing some background material.
>
> In particular, I'm having a hard time understanding epimorphisms.
>
> Pierce defines 'monomorphism' like so:
>
> "An arrow f : B -> C in a category C is a monomorphism if, for any pair
> of C-arrows g : A -> B and h : A -> B, the equality f o g = f o h
> implies that g = h."
>
> First off, is the "C" in "category C" different than the "C" in "f : B
> -> C"?
Yes. The B and the C are objects, namely the domain and codomain of
the arrow f.
The category C is a category. They're different types, so they have to
be different.
> Second, why the goofy formulation? Why the need to compose g and h
> with f? Is it because in category theory we don't talk about the
> objects but only the arrows?
This is almost right. In category theory, we can talk about both
objects and arrows, because a category has both. What we can't
generically talk about are the *elements* of an object -- because the
objects of a particular category might not have any.
For example, you can take a graph and build a category from it by
taking the objects as vertices and paths from one vertex to another as
the arrows. But obviously, a vertex doesn't have any elements, so an
object in this category doesn't have elements.
So when you have an arrow f : B -> C, you can't talk about applying f
to anything, because you don't have any elements to apply f to. What
you can do is *compose* f with another arrow, because a category
always supports the composition of arrows.
Now, a general strategy in category theory is to take a useful concept
from set theory, and figure out how to express it in categorical
terms, and now you have a version that works for all categories. I'll
demonstrate how to do this with the concept of an injective function,
and show how this gets you monomorphisms.
Normally, we say a function f : A -> B is injective when:
for all a, a' in A. f(a) = f(a') implies a = a'.
Now, if we want to formulate this idea in categorical terms, we can't
refer to elements of A, and so we can't use function application. What
can we do?
Let's start with a sleazy trick. Instead of talking about elements of
A, let's talk about the functions from the unit set to A. The unit
set is the one element set {*}, and a function from {*} to A will
map * to a particular element of A. This means that every element
of this set of functions can be written as:
const[a] == (lambda x. a) : unit -> A
Now, notice that composing f : A -> B with const[a] is itself a
constant function of type unit -> B.
f o (const[a]) = f o (lambda x. a) definition of const
= lambda y. f((lambda x.a) y) definition of (f o g)
= lambda y. f(a) eval (lambda x.a) y
This lets change our definition a little:
for all const[a], const[a'] in unit -> A.
f o const[a] = f o const[a'] implies const[a] = const[a']
Notice that we are not talking about applying functions to elements of
A -- we are composing arrows with morphisms from {*} to A. We are now
almost at the definition of monomorphisms.
Picking just the functions from the unit set is an arbitrary choice,
especially since an arbitrary category might not have the equivalent
of a unit set. So we can generalize this definition a bit more, and
say that we want this identity to hold for ALL arrows:
for all g, g'. f o g = f o g' implies g = g'
And this is just the definition of a monomorphism!
> I don't understand how this follows from the definition of epimorphism,
> and I don't understand how an epimorphism is different than an
> isomorphism. The example he gives about how there are epimorphisms that
> *aren't* surjective doesn't seem to distinguish epimorphisms from
> monomorphisms. So I'm .
Try starting with the definition of a surjective function in set
theory, and then try categorifying it like I did above.
> Are there books I need to have read before reading this one? Is this
> the right group to ask a question like this?
I think it's okay to ask these questions here -- category theory is
pretty fundamental to formal semantics, and that's pretty fundamental
to functional programming.
A handy hint is to use wikipedia as a cheat sheet for definitions when
working through these things -- I know I easily lose track of what
each definition is, and so I find it helpful to be able to look them
up without flipping through a book.
--
Neel R. Krishnaswami
neelk@cs.cmu.edu
| |
| Thant Tessman 2007-06-11, 10:05 pm |
| Jose Juan Mendoza Rodriguez wrote:
> Hi,
>
>
> I said "elements", not "objects".
Yes, I wondered about that. I just thought it was an analogy I wasn't
catching.
> Sets are particular instances
> of objects. Functions are particular instances of morphisms.
> Elements are just constant functions, and so they are also morphisms.
So 'g' and 'h' are elements of (or particular instances of) the "object"
(in the category-theory sense) morphed by 'f'?
Or is "element" the name for a "constant function"? What is a constant
function if it is not just a specific function?
I guess what's confusing me is that a function (in the lambda calculus
sense?) is a kind of morphism. The arrows can be functions, but the
arrows are more abstract than that. They're merely an edge on a graph
from one node to another node. And the nodes are "objects," which can be
other functions (or rather, structure shared by all the functions that
instance that particular structure which is preserved by the arrow in
the case of a monomorphism) but are really more abstract than that.
Am I anywhere close to getting it?
>
> By the way, I made a mistake in my message
> <466d7b1d$0$90274$14726298@news.sunsite.dk>
>
>
> That sentence should be negative: if f : B -> C is a monomorphism,
> then f preserves the structure of the object B.
In other words, an arrow that is NOT a monomorphism would NOT preserve
the structure of the object B as it is morphed into the object C. Yes?
-thant
| |
| Chris Smith 2007-06-11, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
>
>
> Okay, so 'f' is the arrow and 'g' and 'h' are the objects?
No. f, g, and h are all arrows (also known as morphisms). The objects
are A, B, and C.
> And the objects can be functions,
That's confusing levels of terminology. One thing that might be
confusing here is that there are two very different worlds being
discussed. On the one hand, there are category-theoretic concepts of
objects and arrows. On the other hand, there are set-theoretic concepts
of sets, elements, and functions. The set stuff is only one example of
a category. So the correspondence is:
General Category Category Set
-------------------------------------
Objects = Sets
Arrows = Functions
NOTHING = Elements
So there are actually less things available in the general category.
Set is just *one* example of a category -- its objects are sets and its
arrows are functions; but that's just an example.
> but that I shouldn't let functional
> programming confuse me about what's really going on here?
Definitely don't think about functional programming yet.
> And when we're
> talking monomorphism, epimorphism, and isomorphism, we're really talking
> about the nature of 'f', not 'g' and 'h' as such?
Right. The definitions of monomorphism and epimorphism are universally
quanitifed over g and h: FOR ALL g and h, such and such is true about f.
So it's not saying anything about any particular g or h.
> And all this talk of injection and surjection is merely metaphor?
>
Monomorphisms and epimorphisms generalize the idea of injections and
surjections. So in the one particular category called Set (whose
objects are sets, and arrows are functions), the monomorphisms are
precisely the injective functions and the epimorphisms are surjective
functions. But that's only that one category.
Monomorphisms and epimorphisms are perfectly well defined for ANY
category, regardless of what its objects and arrows represent. Perhaps
the objects are pancakes and the arrows are dreams, as long as they obey
the category axioms. Some arrows (dreams, in this case) may be
monomorphisms, and some may be epimorphisms. It remains meaningless,
though, to talk about injective or surjective dreams.
--
Chris Smith
| |
| Marlene Miller 2007-06-12, 7:06 pm |
| Here are two other presentations...
Take a look at the comments about Carl Gunter's book.
http://lambda-the-ultimate.org/node/972
John Mitchell's Foundations of Programming Languages
Chapter 7 Categories and Recursive Types (89 pages, 36 exercises)
"only a brief overview of a few relevant topics"
| |
| Jose Juan Mendoza Rodriguez 2007-06-12, 7:06 pm |
| Hello,
> Am I anywhere close to getting it?
The problem is that you keep imagining things that you are not reading.
Try to adhere more strictly to the definitions. Category theory is just
an abstract language. You don't have to invent anything when reading
a book on category theory. Just get used to the mechanics.
Kind regards.
--
Jose Juan Mendoza Rodriguez
let me=josejuanmr in
let privacy=iespana in
let net=es in
me@privacy.net
| |
| Emil Skoeldberg 2007-06-12, 7:06 pm |
| Lots of relevant replies on how to approach category theory have
already been given, I just want to clarify a possible confusion
about sets and functions.
Thant Tessman <adm@standarddeviance.com> writes:
> Here is 'epimorpism':
>
> "An arrow f : A -> B is an epimorphism if, for any pair of arrows g :
> B -> C, and h : B -> C, the equality g o f = h o f implies g = h."
>
> He says that in set theory, this corresponds to surjective
> functions. a function is surjective if for each b element of B there
> is an a element of A for which f(a) = b. I understand this to mean
> that every element in the codomain can be produced by the function f
> given the right unique element in the domain.
I do not know if this really is a misunderstanding, but there is no
uniqueness required of a preimage of b.
>
> I don't understand how this follows from the definition of
> epimorphism, and I don't understand how an epimorphism is different
> than an isomorphism.
In the category of sets, if f: A -> B is a morphism (function) such
that each element of B has a _unique_ preimage in A, then indeed, f
is an isomorphism.
Emil
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Neelakantan Krishnaswami wrote:
[...]
> So when you have an arrow f : B -> C, you can't talk about applying f
> to anything, because you don't have any elements to apply f to. What
> you can do is *compose* f with another arrow, because a category
> always supports the composition of arrows.
Okay, this helps a lot.
[...]
> Let's start with a sleazy trick. Instead of talking about elements of
> A, let's talk about the functions from the unit set to A. The unit
> set is the one element set {*}, and a function from {*} to A will
> map * to a particular element of A. This means that every element
> of this set of functions can be written as:
>
> const[a] == (lambda x. a) : unit -> A
And for every element of A there is a corresponding const function? And
the only reason we are bothering with the const functions is so that we
can compose them instead of talking about elements, because categories
aren't concerned with elements?
And the interesting part is that there is a notion of injection that
survives as monomorphism when you generalize beyond the notion of set
elements? (Is this a fair rephrasing of Chris Smith's statement?)
> Try starting with the definition of a surjective function in set
> theory, and then try categorifying it like I did above.
Will do, thanks much,
-thant
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Neelakantan Krishnaswami wrote:
[...]
> So when you have an arrow f : B -> C, you can't talk about applying f
> to anything, because you don't have any elements to apply f to. What
> you can do is *compose* f with another arrow, because a category
> always supports the composition of arrows.
This implies that objects are *always* a collection of morphisms? If
not, what does composition mean?
-thant
| |
| Dirk Thierbach 2007-06-12, 7:06 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Neelakantan Krishnaswami wrote:
[color=darkred]
> This implies that objects are *always* a collection of morphisms?
No. Objects are just "opaque" things without any inner structure.
At least when seen as a category. Imagine them as "points".
> If not, what does composition mean?
Composition is one of the basic ingredients of a category. To have a
category, you just need to know what the objects are, what the arrows
are, and how to compose arrows. That's all (besides the laws that have
to be satisfied, of course). It's so simplistic that it's almost silly.
Of course, to show that some concrete thing is indeed a category,
you have to exactly say what these things look like. And in case
of the category of sets, arrow composition is just function
composition. But in other categories, it may be something completely
different.
I think it would really help if you go over a few other examples
for categories besides "SET", otherwise it's probably hard to see
the differences.
For example, here's the Category "REL" of relations:
- Objects are all sets (just like in "SET").
- An arrow A -> B is any subset of the cartesian product A x B.
- Composition of two arrows f : A -> B and g : B -> C is defined as
g . f = {(a,c) | \exists b \in B. (a,b) \in f & (b,c) \in g}.
Exercises: What are the identity arrows? Can you prove that the laws
are satisfied? How do monomorphisms and epimorphisms look like in this
category? What about isomorphisms?
- Dirk
| |
| Dirk Thierbach 2007-06-12, 7:06 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Neelakantan Krishnaswami wrote:
[color=darkred]
> And for every element of A there is a corresponding const function?
In the category of sets, yes.
> And the only reason we are bothering with the const functions is so
> that we can compose them instead of talking about elements, because
> categories aren't concerned with elements?
Yes.
> And the interesting part is that there is a notion of injection that
> survives as monomorphism when you generalize beyond the notion of set
> elements?
Yes. The whole point of Category Theory is to generalize beyond the
notion of sets and their elements: You express everything with arrows
and composition. And once you have expressed an interesting property
just with arrows, you can have a look what this does in other
categories.
It helps a lot if you have seen other categories than the category
of sets (have you so far?).
- Dirk
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Emil Skoeldberg wrote:
> Lots of relevant replies on how to approach category theory have
> already been given, I just want to clarify a possible confusion
> about sets and functions.
>
> Thant Tessman <adm@standarddeviance.com> writes:
>
> I do not know if this really is a misunderstanding, but there is no
> uniqueness required of a preimage of b.
In other words, it's perfectly okay for more than one 'a' to produce a
given 'b', but that there must be at least one 'a' that does produce 'b'
for every 'b' in B.
>
>
> In the category of sets, if f: A -> B is a morphism (function) such
> that each element of B has a _unique_ preimage in A, then indeed, f
> is an isomorphism.
In other words, in Category SET, if an arrow is both monomorphic and
epimorphic, it is isomorphic. But in general this is not necessarily true?
My brain hurts.
-thant
| |
| Neelakantan Krishnaswami 2007-06-12, 7:06 pm |
| In article <<f4m2bb$hfv$1@news.xmission.com>>,
Thant Tessman <adm@standarddeviance.com> wrote:
> Neelakantan Krishnaswami wrote:
>
> [...]
>
>
> This implies that objects are *always* a collection of morphisms? If
> not, what does composition mean?
Now, objects and morphisms are just different things.
The concept of "category" is like a module signature in a programming
language. Part of constructing a concrete category is giving
particular collections of objects and morphisms, and showing they
satisfy all of the properties that a category should satisfy.
So, here's a non-Set based example. Let's take a directed graph G, and
make a category C(G) out of it.
1. The objects of C(G) are the vertices of G.
2. The morphisms of C(G) are the *paths* through the graph, following
the edges.
So if there's an edge e1 from A to B and an edge e2 from
B to C, we have both edges as 1-element paths, as well as the path
[e1; e2] from A to C.
3. The domain of a morphism is the vertex the path starts at.
4. The co-domain of a morphism is the vertex the path finishes at.
5. The identity morphisms is the zero-step path that leaves you where
you started.
6. Composition of morphisms is just concatenating paths -- if you have
a path f : A -> B, and a path g : B -> C, we can make a path
(g o f) : A to C by concatenating g to the end of f.
Now we can check that composing the identity morphism with any other
morphism gives you that same morphism back, and that composition is
associative (ie, h o (g o f) == (h o g) o f), and then we've shown
that this is a category.
You can also see that the objects here are not collections of
morphisms, or vice versa.
--
Neel R. Krishnaswami
neelk@cs.cmu.edu
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Dirk Thierbach wrote:
[...]
> For example, here's the Category "REL" of relations:
>
> - Objects are all sets (just like in "SET").
> - An arrow A -> B is any subset of the cartesian product A x B.
So in this case, an arrow doesn't *produce* a subset of the cartesian
product of A and B. Rather, it is merely some collection of possible
pairings between the 'a's in A and the 'b's in B.
This arrow doesn't necessarily have a direction then, yes? It's just an
edge in a graph.
> - Composition of two arrows f : A -> B and g : B -> C is defined as
> g . f = {(a,c) | \exists b \in B. (a,b) \in f & (b,c) \in g}.
Not sure I follow the notation, but I'm guessing this just means that
for every pair (a,b) in f for which there is a corresponding pair (b,c)
in g, there exists a pair (a,c) in g o f : A -> C.
> Exercises: What are the identity arrows?
For a given object A, the identity arrow is the set of tuples (a,a) for
every a in A.
> Can you prove that the laws
> are satisfied?
You mean the 5 things that define what a Category is? You took care of
the first four, and I just hopefully specified the fifth.
I guess there's one more requirement in the #4 about composition being
associative. It clearly is in this case (assuming I understood your
definition), but I'm not up to proving it formally.
> How do monomorphisms and epimorphisms look like in this
> category? What about isomorphisms?
For an arrow f : B -> C to be monomorphic, it must have a pair (b,c) for
every b in B, because this would be the only way it could distinguish
every possible g : A -> B from a different h : A -> B.
For an arrow f : A -> B to be isomorphic, it must have a pair (a,b) for
every b in B, because this would be the only way it could distinguish
every possible g : B -> C from a different h : B -> C.
If an arrow f : A -> B is both monomorphic and epimorphic, it is also
isomorphic. It is also a complete cartesian product of A and B, not
merely a subset.
Eh?
-thant
| |
| Emil Skoeldberg 2007-06-12, 7:06 pm |
| Thant Tessman <adm@standarddeviance.com> writes:
>
> In other words, in Category SET, if an arrow is both monomorphic and
> epimorphic, it is isomorphic. But in general this is not necessarily
> true?
Exactly.
>
> My brain hurts.
Emil
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Thant Tessman wrote:
[...]
> For an arrow f : A -> B to be isomorphic, it must have a pair (a,b) for
> every b in B, because this would be the only way it could distinguish
> every possible g : B -> C from a different h : B -> C.
That of course should have been "epimorphic."
| |
| Chris Smith 2007-06-12, 7:06 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> So in this case, an arrow doesn't *produce* a subset of the cartesian
> product of A and B. Rather, it is merely some collection of possible
> pairings between the 'a's in A and the 'b's in B.
>
> This arrow doesn't necessarily have a direction then, yes? It's just an
> edge in a graph.
Arrows have a direction. In Dirk's example, this is because order
matters in cartesian products; in other words (a, b) is not the same as
(b, a).
In general, arrows do have direction in pretty much any category. The
only exceptions are categories whose only arrows are the identity
arrows; but those categories aren't particularly interesting.
--
Chris Smith
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Chris Smith wrote:
> Thant Tessman <adm@standarddeviance.com> wrote:
>
> Arrows have a direction. In Dirk's example, this is because order
> matters in cartesian products; in other words (a, b) is not the same as
> (b, a).
>
> In general, arrows do have direction in pretty much any category. The
> only exceptions are categories whose only arrows are the identity
> arrows; but those categories aren't particularly interesting.
Okay, the point (of the arrow, get it? he he) is only to distinguish one
end of an arrow from the other, not necessarily to imply that something
moves along the arrows.
Thanks everyone for all the replies.
-thant
| |
| Thant Tessman 2007-06-12, 7:06 pm |
| Neelakantan Krishnaswami wrote:
[...]
> You can also see that the objects here are not collections of
> morphisms, or vice versa.
So it's just that in the particular case that you want to think of
collections of functions as arrows in a category, you have to model the
things the functions operate on as other functions so you can satisfy
the requirement for a definition of composition. But that's really the
only reason you're doing it.
-thant
| |
| Pummelo 2007-06-12, 7:06 pm |
| "Thant Tessman" <adm@standarddeviance.com> wrote:
> Okay, the point (of the arrow, get it? he he) is only to distinguish one
> end of an arrow from the other, not necessarily to imply that something
> moves along the arrows.
That was the first step. You have learnt that a category is nothing more
than a directed graph with a non-standard equality on its paths.
In the next step you will learn that, in fact, every arrow is a kind of
function and every object is a kind of set :-) (due to the most fundamental
theorem of category theory)
I suggest you to read a good book on category theory (forget about Pierce's
book...). Perhaps the best introductory text is the following:
"Conceptual Mathematics: A First Introduction to Categories" by William
Lawvere
Cheers,
Pummelo
| |
| dbenson@eecs.wsu.edu 2007-06-12, 7:06 pm |
| > I suggest you to read a good book on category theory (forget about Pierce's
> book...). Perhaps the best introductory text is the following:
>
> "Conceptual Mathematics: A First Introduction to Categories" by William
> Lawvere
>
> Cheers,
> Pummelo
I fully agree. Pierce's book has no intuition. The full citation is
F. William Lawvere & Stephen H. Schanuel
Conceptual Mathematics: A first introduction to categories
Cambridge University Press
You then may wish to continue with
R.F.C. Walters
Categories and Computer Science
Cambridge University Press
with deeper applications in the graduate level
Michael Barr & Charles Wells
Category Theory for Computing Science: Third Edition
Centre de Recherches Mathematiques, Montreal
with the (needed) errata list available from either author.
| |
| Chris Smith 2007-06-12, 7:06 pm |
| Pummelo <pummelo@olemmup.com> wrote:
> I suggest you to read a good book on category theory (forget about Pierce's
> book...). Perhaps the best introductory text is the following:
>
> "Conceptual Mathematics: A First Introduction to Categories" by William
> Lawvere
I love that book (Lawvere's), but Thant, don't forget about Pierce's
book. Reading both would be ideal. Which order depends on your
temperament. I'd read Lawvere first, then Pierce -- in fact, I read the
first 15 pages of Pierce, then switched to Lawvere, then read all of
Pierce -- but I know plenty of people who'd never make it through
Lawvere without reading chapter 4 (???, or whatever the applications
shapter is; I think it's 4) of Pierce's book first, because Lawvere's
examples and motivation is further from computer science.
--
Chris Smith
| |
| Thant Tessman 2007-06-12, 10:05 pm |
| I have ordered Lawvere's book, and am continuing with Pierce's. I think
I'm in much better shape now. Thanks to all,
-thant
Chris Smith wrote:
> Pummelo <pummelo@olemmup.com> wrote:
>
> I love that book (Lawvere's), but Thant, don't forget about Pierce's
> book. Reading both would be ideal. Which order depends on your
> temperament. I'd read Lawvere first, then Pierce -- in fact, I read the
> first 15 pages of Pierce, then switched to Lawvere, then read all of
> Pierce -- but I know plenty of people who'd never make it through
> Lawvere without reading chapter 4 (???, or whatever the applications
> shapter is; I think it's 4) of Pierce's book first, because Lawvere's
> examples and motivation is further from computer science.
>
| |
| Dirk Thierbach 2007-06-13, 4:11 am |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Dirk Thierbach wrote:
[color=darkred]
> So in this case, an arrow doesn't *produce* a subset of the cartesian
> product of A and B. Rather, it is merely some collection of possible
> pairings between the 'a's in A and the 'b's in B.
Yes. Arrows are just an abstract concept, in general they don't
"produce" anything.
> This arrow doesn't necessarily have a direction then, yes? It's just an
> edge in a graph.
Arrows have always a direction. In this case, it has a direction,
because pairs are ordered, and composition is defined with respect to
that ordering.
However, one thing about categories is that you can turn arrows around
and get another category. This is called the "dual" or "opposite"
category. (You can also turn around arrows in various categorical
constructions, and the constructions you arrive at in this way are
usually prefixed with "co-". For example, you have products and
co-products, monads and co-monads, etc. In case you have already
heard of those).
As relations are highly symmetric, it turns out that the dual category
of REL is isomorphic to REL. In other words, REL is self-dual. Maybe
that's what was confusing you.
[color=darkred]
> Not sure I follow the notation, but I'm guessing this just means that
> for every pair (a,b) in f for which there is a corresponding pair (b,c)
> in g, there exists a pair (a,c) in g o f : A -> C.
More or less. A better description is that for (a,c) to be in g o f,
there must be a "chain" going through some b, such that (a,b) is in f, and
(b,c) in g.
>
> For a given object A, the identity arrow is the set of tuples (a,a) for
> every a in A.
Yes.
[color=darkred]
> You mean the 5 things that define what a Category is? You took care of
> the first four, and I just hopefully specified the fifth.
> I guess there's one more requirement in the #4 about composition being
> associative. It clearly is in this case (assuming I understood your
> definition), but I'm not up to proving it formally.
There's one more thing that is needed: The identity arrows must really
be the identity in arrow composition, but this is again easily seen.
[color=darkred]
> For an arrow f : B -> C to be monomorphic, it must have a pair (b,c) for
> every b in B, because this would be the only way it could distinguish
> every possible g : A -> B from a different h : A -> B.
No. Counterexample: Let B = {b1,b2}, C={c1,c2}, and f the all-relation
f = {(b1,c1),(b1,c2),(b2,c1),(b2,c2)}. You say that this would be a
monomorphism. Now choose A={a}, and consider g = {(a,b1)} and h = {(a,b2)}.
Then
f o g = {(a,c1),(a,c2)} and f o h = {(a,c1),(a,c2)}
(please verify this), so f o g = f o h, but h /= g. Oops.
(Hint: Use the trick with a one-element set A first, then think about the
general case).
> For an arrow f : A -> B to be [an epi], it must have a pair (a,b) for
> every b in B, because this would be the only way it could distinguish
> every possible g : B -> C from a different h : B -> C.
Some problem as above.
> If an arrow f : A -> B is both monomorphic and epimorphic, it is also
> isomorphic.
No, no, no. This is true for "SET", but not in any category, and "REL"
is actually a counterexample where it's not true (once you've
correctly identified mono's, epi's and iso's, that is :-)
- Dirk
| |
| Dirk Thierbach 2007-06-13, 4:11 am |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Emil Skoeldberg wrote:
> In other words, in Category SET, if an arrow is both monomorphic and
> epimorphic, it is isomorphic. But in general this is not necessarily
> true?
Yes. Please remember that :-)
OTOH, the reverse direction still holds: If f is an iso, than it
is also a mono and an epi. Proof (for mono):
Assume f o f' = f' o f = id. Now suppose f o g = f o h for some h, g.
Then also f' o f o g = f' o f o h, which means id o g = id o h,
from which follows g = h.
(Proof for epi left as exercise).
Described in different words, f is a mono if you can cancel it
from any composition where it's on the left side. If there is an
(left) inverse of f, that will always be true. But it might be even
true in situations where's no such inverse arrow (for example,
because they are very few arrows in the category to start with -- if
there are no arrows g and h we can compose f with, or if there's only
one such arrow, f is trivially a monomorphism).
> My brain hurts.
It tells you an important thing: You're lucky that it works in SET,
but in the general case you really need a concrete "inverse" arrow
to have an isomorphism. So that is the correct way to generalize this
notion, and to say "objects are structurally similar if I have an
arrow between them that is mono and epi" is wrong.
Categories strip away everything until you can see what is the correct
approach in the very general case, and what isn't. That's one thing
they are good for.
- Dirk
| |
| Thant Tessman 2007-06-13, 10:05 pm |
| Dirk Thierbach wrote:
> Thant Tessman <adm@standarddeviance.com> wrote:
[...]
>
> No. Counterexample: Let B = {b1,b2}, C={c1,c2}, and f the all-relation
> f = {(b1,c1),(b1,c2),(b2,c1),(b2,c2)}. You say that this would be a
> monomorphism. Now choose A={a}, and consider g = {(a,b1)} and h = {(a,b2)}.
> Then
>
> f o g = {(a,c1),(a,c2)} and f o h = {(a,c1),(a,c2)}
>
> (please verify this), so f o g = f o h, but h /= g. Oops.
>
> (Hint: Use the trick with a one-element set A first, then think about the
> general case).
So not only must f have a pair (b,c) for every b in B, but that it must
also be paired to a unique c (or set of c's) that no other b is linked
to. Yes, I should have thought of that.
f = {(b1,c1),(b2,c2)}
f o g = {(a,c1)}
f o h = {(a,c2)}
and indeed
h /= g
Don't see how making A have more than one element changes things, at
least in the monomorphism case.
>
>
> Some problem as above.
>
>
> No, no, no. This is true for "SET", but not in any category, and "REL"
> is actually a counterexample where it's not true (once you've
> correctly identified mono's, epi's and iso's, that is :-)
I'm grateful for your help, but I'm still not seeing this one. I can
imagine that there is *some* category with an f that is both mono, epi,
but not iso, but I don't see how "REL" is an example of just such a
category.
-thant
| |
| Emil Skoeldberg 2007-06-13, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> writes:
>
> I'm grateful for your help, but I'm still not seeing this one. I can
> imagine that there is *some* category with an f that is both mono,
> epi, but not iso, but I don't see how "REL" is an example of just such
> a category.
>
I'll leave REL to you to contemplate ;-), but for a simple (the simplest?)
example of a category with epi + mono != iso, look at the category
with two objects, say A and B, and 3 arrows:
id: A -> A
id: B -> B
f: A -> B
Since there is at most one morphism between any pair of objects, all
morphisms are automatically both monic and epic. However, f cannot be
an isomorphism since there is no morphism from B to A.
Emil
| |
| Dirk Thierbach 2007-06-13, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Dirk Thierbach wrote:
> So not only must f have a pair (b,c) for every b in B, but that it must
> also be paired to a unique c (or set of c's) that no other b is linked
> to.
Yes. It remains to "fix" your characterization of epi's (which is still
incomplete).
[color=darkred]
[color=darkred]
> I'm grateful for your help, but I'm still not seeing this one. I can
> imagine that there is *some* category with an f that is both mono, epi,
> but not iso, but I don't see how "REL" is an example of just such a
> category.
You're actually right, it's not a counterexample (I didn't think this
through to the end. Sorry, my fault). But one should still work out
what the iso's look like, just going from the definition.
Anyway, let's make another example for that:
- Objects: Natural numbers, without zero.
- Arrows: There's exactly one arrow from A to B if A divides B,
otherwise there's none.
What are the mono's, epi's, iso's? (It turns out that they are quite
boring...)
It's also interesting to find out what are the products and coproducts
in this category (once you've read this far in your book).
- Dirk
| |
| Paul Rubin 2007-06-13, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> writes:
> I have ordered Lawvere's book, and am continuing with Pierce's. I
> think I'm in much better shape now. Thanks to all,
Wikipedia's coverage is also pretty informative.
http://en.wikipedia.org/wiki/Category_theory
| |
| Thant Tessman 2007-06-14, 7:06 pm |
| Emil Skoeldberg wrote:
> [...] but for a simple (the simplest?)
> example of a category with epi + mono != iso, look at the category
> with two objects, say A and B, and 3 arrows:
>
> id: A -> A
> id: B -> B
> f: A -> B
>
> Since there is at most one morphism between any pair of objects, all
> morphisms are automatically both monic and epic. However, f cannot be
> an isomorphism since there is no morphism from B to A.
Ah, but see, you're not deriving a category from something else, you're
just stating it. Something tells me there's a difference.
But tell me this: does the Category SET have an infinite number of
objects corresponding to an infinite number of possible sets? Or when we
talk about Categories, are we always talking about something you pin
down and draw out?
-thant
| |
| Thant Tessman 2007-06-14, 7:06 pm |
| Dirk Thierbach wrote:
[...]
> Anyway, let's make another example for that:
>
> - Objects: Natural numbers, without zero.
I'm assuming each object is a single number.
> - Arrows: There's exactly one arrow from A to B if A divides B,
> otherwise there's none.
In other words, every number has an arrow from every number that it is
divisible by (including itself, which is the identity arrow).
>
> What are the mono's, epi's, iso's? (It turns out that they are quite
> boring...)
I had to think about this one a lot more than I expected to. I keep
thinking there's a trick to it.
Why aren't all arrows mono and epi simply because no matter what, for a
given A and B, there is always only zero or one arrow that connects
them? That is, *if* there's an arrow, it is always distinct. And if an
arrow connects A and B, and an arrow connects B and C, then they are
automatically composable to form an arrow A -> C (which already exists
anyway).
I suppose there's a more careful way to say this.
Will work on the products and co-products eventually...
-thant
| |
| Thant Tessman 2007-06-14, 7:06 pm |
| Thant Tessman wrote:
[...]
> Why aren't all arrows mono and epi simply because no matter what, for a
> given A and B, there is always only zero or one arrow that connects
> them? That is, *if* there's an arrow, it is always distinct. And if an
> arrow connects A and B, and an arrow connects B and C, then they are
> automatically composable to form an arrow A -> C (which already exists
> anyway).
But only the identity arrows are iso? Is that the point?
-thant
| |
| Chris Smith 2007-06-14, 7:06 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Emil Skoeldberg wrote:
>
>
> Ah, but see, you're not deriving a category from something else, you're
> just stating it. Something tells me there's a difference.
There's really not a difference. This category is different because
it's finite; but it's certainly not different in any sense of being non-
derived. Deriving categories from other mathematical concepts is useful
as a way of describing infinite categories easily; and also applying the
theorems from category theory to other places; but it doesn't change the
nature of the category at all.
> But tell me this: does the Category SET have an infinite number of
> objects corresponding to an infinite number of possible sets? Or when we
> talk about Categories, are we always talking about something you pin
> down and draw out?
Yes, the category Set does have an infinite number of objects and
arrows.
--
Chris Smith
| |
| Dirk Thierbach 2007-06-14, 7:06 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Thant Tessman wrote:
That's exactly the reason. So, all equations are trivially satisfied
(if all morphisms involved actually exist).
[color=darkred]
> But only the identity arrows are iso? Is that the point?
Yes. So indeed there are examples of arrows which are mono and epi,
but not iso.
BTW, you can generalize this construction to express any partial order
in a category.
- Dirk
| |
|
| On Jun 12, 5:03 pm, "Pummelo" <pumm...@olemmup.com> wrote:
> "Thant Tessman" <a...@standarddeviance.com> wrote:
>
> That was the first step. You have learnt that a category is nothing more
> than a directed graph with a non-standard equality on its paths.
>
> In the next step you will learn that, in fact, every arrow is a kind of
> function and every object is a kind of set :-) (due to the most fundamental
> theorem of category theory)
>
> I suggest you to read a good book on category theory (forget about Pierce's
> book...). Perhaps the best introductory text is the following:
>
> "Conceptual Mathematics: A First Introduction to Categories" by William
> Lawvere
>
> Cheers,
> Pummelo
I also agree "lose" Pierce's book .. very outdated and IMO a poor
presentation. Here:
1) "An Intro to Category Theory in four easy movements" =>
http://www.cs.man.ac.uk/~hsimmons/BOOKS/books.html .. very  ...
2) Both of Lawvere's books ...!
3) Awodey's notes => http://www.andrew.cmu.edu/course/80-413-713/notes/
Regards, Bill Halchin
| |
|
| On Jun 13, 9:59 am, Emil Skoeldberg <emil.skoldb...@nuigalway.ie>
wrote:
> Thant Tessman <a...@standarddeviance.com> writes:
>
>
> I'll leave REL to you to contemplate ;-), but for a simple (the simplest?)
> example of a category with epi + mono != iso, look at the category
> with two objects, say A and B, and 3 arrows:
>
> id: A -> A
> id: B -> B
> f: A -> B
>
> Since there is at most one morphism between any pair of objects, all
> morphisms are automatically both monic and epic. However, f cannot be
> an isomorphism since there is no morphism from B to A.
>
> Emil
Emil has provided a "preset" here ... see wikipedia for def. Posets
are also categories.
Bill Halchin
| |
|
| On Jun 13, 9:59 am, Emil Skoeldberg <emil.skoldb...@nuigalway.ie>
wrote:
> Thant Tessman <a...@standarddeviance.com> writes:
>
>
> I'll leave REL to you to contemplate ;-), but for a simple (the simplest?)
> example of a category with epi + mono != iso, look at the category
> with two objects, say A and B, and 3 arrows:
>
> id: A -> A
> id: B -> B
> f: A -> B
>
> Since there is at most one morphism between any pair of objects, all
> morphisms are automatically both monic and epic. However, f cannot be
> an isomorphism since there is no morphism from B to A.
>
> Emil
presets, posets, monoids, ... all are categories. See "An intro to
Category Theory in four easy movements" Simmons et. al. A great and
subtle intro!!
Bill halchin
| |
| Thant Tessman 2007-06-15, 10:07 pm |
|
Thanks again for the assistance and insights. I'm sure I'll have more
questions as I get farther along...
-thant
Dirk Thierbach wrote:
> Thant Tessman <adm@standarddeviance.com> wrote:
>
>
> That's exactly the reason. So, all equations are trivially satisfied
> (if all morphisms involved actually exist).
>
>
> Yes. So indeed there are examples of arrows which are mono and epi,
> but not iso.
>
> BTW, you can generalize this construction to express any partial order
> in a category.
>
> - Dirk
>
| |
| Thant Tessman 2007-06-16, 10:09 pm |
| Dirk Thierbach wrote:
[...]
> - Objects: Natural numbers, without zero.
> - Arrows: There's exactly one arrow from A to B if A divides B,
> otherwise there's none.
And in this example, the only initial object is 1 and there are no
terminal objects?
-thant
| |
| Dirk Thierbach 2007-06-17, 4:19 am |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Dirk Thierbach wrote:
>
> And in this example, the only initial object is 1 and there are no
> terminal objects?
Yes. What happens if you add zero to the objects (using the definition
"A divides B iff there is an integer X such that A*X = B")?
Another interesting quick exercise is to prove that all initial
objects must be isomorphic (and so must be all terminal objects).
- Dirk
| |
| Thant Tessman 2007-06-17, 8:04 am |
| Dirk Thierbach wrote:
> Thant Tessman <adm@standarddeviance.com> wrote:
>
>
> Yes. What happens if you add zero to the objects (using the definition
> "A divides B iff there is an integer X such that A*X = B")?
1 is still the only initial object:
1 * n = n
so there's one arrow from 1 to every n.
0 is the terminal object:
n * 0 = 0
so there's one arrow from every n to 0.
> Another interesting quick exercise is to prove that all initial
> objects must be isomorphic (and so must be all terminal objects).
Not sure I understand. I thought only arrows were isomorphic, not objects.
***
While I'm typing, Pierce's book says: "If a category C has a product AxB
for every pair of objects A and B, we say that C has all (binary)
products, or simply C has products."
Is this recursive? That is, if AxB is just another object, does that
mean that for every pair of product objects AxB and CxD, there is
another product object (AxB)x(CxD)?
***
Also, "Conceptual Mathematics" just arrived. Definitely a different
presentation.
The thing on page 19 with the "me" set helped. I think it corresponds to
Neel's const functions.
-thant
| |
| Dirk Thierbach 2007-06-17, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
[color=darkred]
> Not sure I understand. I thought only arrows were isomorphic, not
> objects.
Arrows can be *isomorphisms*. Two objects with an isomorphism between
them are called *isomorphic*. And the meaning is pretty much the same
as usual: If two objects are isomorphic, any construction carried out
for the one object can also be carried out for the other object. Hence,
structurally, they are considered equivalent.
So to show that all initial objects are isomorphic you have to prove
for any two initial objects that there's an isomorphism (i.e., an
arrow that has an "inverse" arrow, and composes to the identity both
ways) between them.
> While I'm typing, Pierce's book says: "If a category C has a product AxB
> for every pair of objects A and B, we say that C has all (binary)
> products, or simply C has products."
> Is this recursive? That is, if AxB is just another object, does that
> mean that for every pair of product objects AxB and CxD, there is
> another product object (AxB)x(CxD)?
Yes.
- Dirk
| |
| Thant Tessman 2007-06-17, 10:05 pm |
| Dirk Thierbach wrote:
[...]
> Arrows can be *isomorphisms*. Two objects with an isomorphism between
> them are called *isomorphic*. And the meaning is pretty much the same
> as usual: If two objects are isomorphic, any construction carried out
> for the one object can also be carried out for the other object. Hence,
> structurally, they are considered equivalent.
This actually makes some other things make sense. Thanks.
> So to show that all initial objects are isomorphic you have to prove
> for any two initial objects that there's an isomorphism (i.e., an
> arrow that has an "inverse" arrow, and composes to the identity both
> ways) between them.
Doesn't it fall out of the definition of an initial object? An initial
object is an object that has exactly one arrow to every other object.
This implies that every pair of initial objects have exactly one arrow
pointed at each other. (I mean, I hadn't thought of it that way until
now, but it seems obvious in hindsight anyway.)
Ditto final objects.
Interesting stuff, but I am beginning to wonder what the punchline of
all this is...
-thant
| |
| Dirk Thierbach 2007-06-18, 8:05 am |
| Thant Tessman <adm@standarddeviance.com> wrote:
[color=darkred]
> Doesn't it fall out of the definition of an initial object?
Why should it?
> An initial
> object is an object that has exactly one arrow to every other object.
> This implies that every pair of initial objects have exactly one arrow
> pointed at each other.
Yes. So if you've got a pair of initial objects, there's not much
choice about which arrows to look at if they are supposed to be iso's,
is there? :-)
All that remains to do is to show that they compose to the identity
each way...
> Interesting stuff, but I am beginning to wonder what the punchline of
> all this is...
At the moment, you're practicing to "say things with arrows", and to
actually prove a thing or two this way. And you're still at the very
early stage of that. Maybe it helps to think of those constructions as
"design patterns" in a very general and abstract context. Now the
"punchline" is whatever you want it to be: You take a construction
that is interesting to you (say, lambda calculus), and express it with
arrows. In this way you're forced on the one hand to get down to the
"bare bones", to the structure that is really important. OTOH, you can
now apply this structure to different categories, and see what this
construction turns out to be there. If you've looked at products
in the example category I gave (where the arrows express divisibility),
you've maybe had a mild aha-experience ("So that's what the products are.
I'd never thought there was a connection between those things...").
So you build yourself a mental toolset, a particular way to look at
things and spot similarities, and at the same time everything is so
much reduced to the bare necesseties that it often becomes obvious
what to do next. You may have noticed that in FP, when you've written
down the type of a function, for some general functions then the
code writes itself -- there's really no other choice to do it. In
categories, it's often very similar. (Actually, it's exactly the
same thing :-), as you'll maybe see later).
Hope that helps a bit as motivation. YMMV, of course.
- Dirk
| |
|
|
|
|
| Thant Tessman 2007-06-21, 8:05 am |
| I was gonna try to read a little farther before responding here again
(this category theory thing is definitely an extracurricular activity I
don't have the luxury of devoting a lot of time to, so my progress is
necessarily slow), but now it's bugging me...
Dirk Thierbach wrote:
> Thant Tessman <adm@standarddeviance.com> wrote:
>
>
> Why should it?
>
>
>
> Yes. So if you've got a pair of initial objects, there's not much
> choice about which arrows to look at if they are supposed to be iso's,
> is there? :-)
>
> All that remains to do is to show that they compose to the identity
> each way...
So your point is that all I've shown is that *if* two initial objects
are isomorphic, then the unique arrows they have pointing at each other
must be the ones that form the isomorphism, but I haven't yet proved
that they do in fact form an isomorphism.
Well, now my brain hurts again.
Given two initial objects A and B, we know there is only one arrow f : A
-> B and only one arrow g : B -> A. We know we can compose f o g to form
a new arrow h : A -> A. How do we know this is the identity arrow?
Given j : A -> X we know that idA o j = j because there's only one arrow
from A to X.
But given j : X -> A, how do we know that j o idA = j? There's nothing
that says there aren't many arrows to A, and that our candidate idA
doesn't change j to some other arrow.
?
>
> [...] If you've looked at products
> in the example category I gave (where the arrows express divisibility),
> you've maybe had a mild aha-experience ("So that's what the products are.
> I'd never thought there was a connection between those things...").
1
/|\
/ | \
4 2 6
/ | \
/ | \
4--2--2--3--6
Are you referring to the fact that in this case products really are
products?
>
> [...] You may have noticed that in FP, when you've written
> down the type of a function, for some general functions then the
> code writes itself -- there's really no other choice to do it. In
> categories, it's often very similar. (Actually, it's exactly the
> same thing :-), as you'll maybe see later).
Yes, this is indeed sort of related to what I was hoping to get out of
this eventually.
-thant
| |
| Thant Tessman 2007-06-21, 8:05 am |
| Thant Tessman wrote:
>
> 1
> /|\
> / | \
> 4 2 6
> / | \
> / | \
> 4--2--2--3--6
>
> Are you referring to the fact that in this case products really are
> products?
Sorry, I meant composition is multiplication. A product in this case is
a common factor. Right?
-thant
| |
| Thant Tessman 2007-06-21, 8:05 am |
| Thant Tessman wrote:
[...]
> Given j : A -> X we know that idA o j = j because there's only one arrow
> from A to X.
>
> But given j : X -> A, how do we know that j o idA = j? There's nothing
> that says there aren't many arrows to A, and that our candidate idA
> doesn't change j to some other arrow.
And I got those backwards. Ug. But you get the point.
-thant
| |
| Dirk Thierbach 2007-06-21, 8:05 am |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Given two initial objects A and B, we know there is only one arrow f : A
> -> B and only one arrow g : B -> A. We know we can compose f o g to form
> a new arrow h : A -> A. How do we know this is the identity arrow?
If A is initial, how many arrows A -> A are possible in the first place?
> 1
> /|\
> / | \
> 4 2 6
> / | \
> / | \
> 4--2--2--3--6
>
> Are you referring to the fact that in this case products really are
> products?
In your diagram, the categorical product of 4 and 6 is 2.
But clearly 4*6 /= 2, so it can't be the "numerical" product. So I'm
not sure what you mean. BTW, what's the coproduct of 4 and 6? Notice
anything? If not, maybe try the product and coproduct of 6 and 15.
- Dirk
| |
| Thant Tessman 2007-06-21, 8:05 am |
| Dirk Thierbach wrote:
> Thant Tessman <adm@standarddeviance.com> wrote:
>
> If A is initial, how many arrows A -> A are possible in the first place?
Oh! I get it! If the composition of f o g produces an arrow i : A -> A,
then i *has* to be the identity because if A is an initial object, it is
also an initial object for itself, which means there is only one arrow A
-> A. And if i didn't follow the rules of composition for identity, then
we're not talking about a catetory in the first place.
-thant
| |
| Dirk Thierbach 2007-06-21, 8:05 am |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Oh! I get it! If the composition of f o g produces an arrow i : A -> A,
> then i *has* to be the identity because if A is an initial object, it is
> also an initial object for itself, which means there is only one arrow A
> -> A.
Right. So there are two things to remember: First, initial and
terminal objects are only defined "up to isomorphism" -- you can have
several of them, but if you know one, you know how the rest looks
like. Second, if you have a construction like "for all objects X,
there's some condition on arrows to or from other objects A or B",
it's sometimes useful to take the objects A or B itself for X, and
see what happens.
Followup-exercise, if you're still interested: Show the same
for products. That is, if P is a product for A and B, and P' is also
a product for A and B, then P and P' must be isomorphic.
Another exercise is to show the reverse direction: If P is isomorphic
to P', and P is a product for A and B, then P' is also a product
for A and B.
If you can do those, you're starting to get an intuition how
the "diagram chasing" in categories works.
- Dirk
| |
| Thant Tessman 2007-06-23, 10:12 pm |
| Dirk Thierbach wrote:
[...]
> Followup-exercise, if you're still interested:
I'm not short on interest, just time and energy. I appreciate your
efforts. (And everyone's.)
> Show the same
> for products. That is, if P is a product for A and B, and P' is also
> a product for A and B, then P and P' must be isomorphic.
I'm having trouble with this one. Do the mediating arrows for P and P'
come from the same object? Or different ones? If the latter, I don't see
any connection at all between P and P' other than that they each have at
least one arrow to A and B. If the former, at least I know:
f = piA o <f,g> = piA' o <f,g>'
g = piB o <f,g> = piB' o <f,g>'
and these are unique:
<f,g> : C -> P
<f,g>' : C -> P'
But I have no idea where to take it from here.
Do I understand the problem correctly?
-thant
| |
| Dirk Thierbach 2007-06-24, 10:05 pm |
| Thant Tessman <adm@standarddeviance.com> wrote:
> Dirk Thierbach wrote:
[color=darkred]
> I'm having trouble with this one. Do the mediating arrows for P and P'
> come from the same object? Or different ones?
I am not sure if I understand the question correctly. Assuming you
mean by "mediating arrows" the isomorphisms between P and P', of
course one goes from P to P', and one from P' to P. In this sense,
they don't "come from the same object". But that's probably not what
you meant.
Anyway, if you've trouble to come up with an idea how to construct
these, have a look again at wrote I wrote before:
[color=darkred]
If P is a product for A and B, you know that for every X that has
a pair of arrows to A and B, there exists a unique arrow X -> P that
makes the whole diagram commute. Which is the obvious (and maybe
only) choice for X in the situation above? What do you get from that,
what is still missing?
- Dirk
| |
| Thant Tessman 2007-06-24, 10:05 pm |
| Dirk Thierbach wrote:
> [...] Assuming you
> mean by "mediating arrows" the isomorphisms between P and P', of
> course one goes from P to P', and one from P' to P.
Oh! That's different! I didn't understand that the 'isomorphism' was the
same as the mediating arrows. I assumed they were different arrows.
Okay, I'm back on the scent...
-thant
| |
| psidrinal@gmail.com 2007-06-27, 8:06 am |
| > My brain hurts.
>
> -thant
Just wait until you get to pullbacks. :-O
// Raphael
|
|
|
|
|