The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Toward a Formal, Machine-Parsable Definition of a Category
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 Messages 101 - 125 of 198 < Older  Newer >

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 5 2012, 12:13 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 09:13:44 -0800 (PST)
Local: Mon, Nov 5 2012 12:13 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 11:37 am, Rotwang <sg...@hotmail.co.uk> wrote:

Good point! Axiom 3 should be:

ALL(a):ALL(b):[a @ ob & b @ ob => ALL(f):[f @ hom(a,b)
<=> f @ mor & dom(f)=a & cod(f)=b]]

[snip]

Yes, I subsequently began to question whether or not this notation was
justified. My definition can be "rescued" if comp(g,f) is not The
Composition, but only a possible composition.

> Incidentally, if you're not allowed to assume from the axioms you gave
> earlier that comp is a partial function, then you probably shouldn't be
> assuming that cod and dom are partial functions either - you should add
> axioms that say so.

As I have defined them, dom and cod are full functions. dom and cod
are defined for EVERY element of the class of morphisms (mor). If x is
ANY morphism, than dom(x) is an element of ob. Likewise, if y is ANY
morphism, than cod(y) is also an element of ob.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 12:31 pm
Newsgroups: sci.logic, sci.math
From: Rotwang <sg...@hotmail.co.uk>
Date: Mon, 05 Nov 2012 17:30:55 +0000
Local: Mon, Nov 5 2012 12:30 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On 05/11/2012 17:13, Dan Christensen wrote:

Yes.

But in that case your axioms say nothing about the actual composition
that is part of the definition of a category, surely?

>> Incidentally, if you're not allowed to assume from the axioms you gave
>> earlier that comp is a partial function, then you probably shouldn't be
>> assuming that cod and dom are partial functions either - you should add
>> axioms that say so.

> As I have defined them, dom and cod are full functions. dom and cod
> are defined for EVERY element of the class of morphisms (mor). If x is
> ANY morphism, than dom(x) is an element of ob. Likewise, if y is ANY
> morphism, than cod(y) is also an element of ob.

That's exactly as it should be (though I don't see anywhere that says so
in the earlier material I quoted). But it's not clear from your reply
whether you accept that composition is supposed to be a partial
function. If your axioms don't require that it is then they are wrong.

--
I have made a thing that superficially resembles music:

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 12:33 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 09:33:15 -0800 (PST)
Local: Mon, Nov 5 2012 12:33 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 11:48 am, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:

[snip]

How can g o f can be the one and only composition of f followed by g
(assuming cod(f)=dom(g)) in a category with multiple distinct
morphisms from dom(f) to cod(g)? It seems to me that the only way that
'o' can be a function in such a case is for g o f to be simply one
possible composition. If so, then g o f should not be seen as The
Composition, but simply as one POSSIBLE composition. It could still be
a function.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 12:43 pm
Newsgroups: sci.logic, sci.math
From: Rotwang <sg...@hotmail.co.uk>
Date: Mon, 05 Nov 2012 17:43:11 +0000
Local: Mon, Nov 5 2012 12:43 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On 05/11/2012 17:33, Dan Christensen wrote:

You seem to be labouring under the misapprehension that the composition
in a category is defined in terms of the other properties. It isn't -
the composition is part of the definition of a category, and two
categories with the same objects, morphisms and dom and cod functions
may have different composition operators. Your question is akin to
saying that the group product in a group should not be seen as The
Product, but simply as one possible product. Different products give
rise to different groups, and a set of objects is not a group until a
product has been specified.

--
I have made a thing that superficially resembles music:

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 1:02 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 10:02:23 -0800 (PST)
Local: Mon, Nov 5 2012 1:02 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 12:31 pm, Rotwang <sg...@hotmail.co.uk> wrote:

[snip]

> >> Anyway, here's the answer: in the usual definition of a category,
> >> composition is a partial function - that is, if cod(f) = dom(g) then
> >> there is exactly one h such that h = comp(g, f). I had assumed that this
> >> was implicit in your axioms (since the notation comp(g, f) doesn't
> >> really make any sense if comp is not functional),

> > [snip]

> > Yes, I subsequently began to question whether or not this notation was
> > justified. My definition can be "rescued" if comp(g,f) is not The
> > Composition, but only a possible composition.

> But in that case your axioms say nothing about the actual composition
> that is part of the definition of a category, surely?

I'm not sure what you are getting at.

Axiom 4 says the comp is a partial function mapping mor x mor to mor.

Axiom 5 says the domain and codomain of comp(g,f) are compatible with
those of f and g.

Axiom 6 says the comp is associative.

> >> Incidentally, if you're not allowed to assume from the axioms you gave
> >> earlier that comp is a partial function, then you probably shouldn't be
> >> assuming that cod and dom are partial functions either - you should add
> >> axioms that say so.

> > As I have defined them, dom and cod are full functions. dom and cod
> > are defined for EVERY element of the class of morphisms (mor). If x is
> > ANY morphism, than dom(x) is an element of ob. Likewise, if y is ANY
> > morphism, than cod(y) is also an element of ob.

> That's exactly as it should be (though I don't see anywhere that says so
> in the earlier material I quoted). But it's not clear from your reply
> whether you accept that composition is supposed to be a partial
> function.

That, in effect, is what Axiom 4 says. You don't agree?

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 1:31 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 10:31:10 -0800 (PST)
Local: Mon, Nov 5 2012 1:31 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 12:43 pm, Rotwang <sg...@hotmail.co.uk> wrote:

Suppose some category C includes 4 distinct morphisms f, g, h1 and h2
such that

1.  dom(f)=dom(h1)=dom(h1)

2.  cod(f)=dom(g)

3.  cod(g)=cod(h1)=cod(h2)

What is g o f? Is it h1 or h2 or both or possibly neither?

Dan

Different products give

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 1:43 pm
Newsgroups: sci.logic, sci.math
From: Aatu Koskensilta <aatu.koskensi...@uta.fi>
Date: Mon, 05 Nov 2012 20:43:19 +0200
Local: Mon, Nov 5 2012 1:43 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category

Dan Christensen <Dan_Christen...@sympatico.ca> writes:
> Suppose some category C includes 4 distinct morphisms f, g, h1 and h2
> such that

> 1.  dom(f)=dom(h1)=dom(h1)

> 2.  cod(f)=dom(g)

> 3.  cod(g)=cod(h1)=cod(h2)

> What is g o f? Is it h1 or h2 or both or possibly neither?

Possibly neither, if there are morphisms apart from h1 and h2 with
suitable domain and codomain. What is it that's bothering you here? The
objects and morphisms do not determine the composition operation;
rather, the composition operation is part of the data making up the
category, just as with the operation * for groups etc.

--
Aatu Koskensilta (aatu.koskensi...@uta.fi)

"Wovon man nicht sprechen kann, dar ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 1:59 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 10:59:15 -0800 (PST)
Local: Mon, Nov 5 2012 1:59 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 3, 12:02 am, Dan Christensen <Dan_Christen...@sympatico.ca>
wrote:

Should be:

ALL(a):ALL(b):[a @ ob & b @ ob => ALL(f):[f @ hom(a,b)
<=> f @ mor & dom(f)=a & cod(f)=b]]

Thanks to Rotwang.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 2:18 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 11:18:33 -0800 (PST)
Local: Mon, Nov 5 2012 2:18 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
Correction

On Nov 5, 1:43 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> Dan Christensen <Dan_Christen...@sympatico.ca> writes:
> > Suppose some category C includes 4 distinct morphisms f, g, h1 and h2
> > such that

> > 1.  dom(f)=dom(h1)=dom(h1)

> > 2.  cod(f)=dom(g)

> > 3.  cod(g)=cod(h1)=cod(h2)

> > What is g o f? Is it h1 or h2 or both or possibly neither?

>   Possibly neither, if there are morphisms apart from h1 and h2 with
> suitable domain and codomain.

So the choice is arbitrary? You just have to choose one? So, you COULD
have

g o f = h1

Then, of course, we would also have:

g o f =/= h2

even though, in a sense, h2 is also a composition of f followed by g.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 2:38 pm
Newsgroups: sci.logic, sci.math
From: "Jesse F. Hughes" <je...@phiwumbda.org>
Date: Mon, 05 Nov 2012 14:38:00 -0500
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category

How can a*b be 1 or c in a group with four elements?

The axioms of category theory require composition to be a partial
function.  A particular structure <Ob,Mor,dom,cod,id,comp> is a category
only if comp actually *is* a partial function.

The composition function is part of the specification of a category,
just like multiplication is part of the specification of a group. And
just as multiplication in groups must be functional, so must composition
in a category.

Example:

Consider the category with one object M and two arrows, f_0 and f_1,
where

dom(f_0) = dom(f_1) = cod(f_0) = cod(f_1) = M
id_M = f_1

f_1 o f_0 = f_0 o f_1 = f_0 o f_0 = f_0.
f_1 o f_1 = f_1.

There's a category for you.  It satisfies all of the axioms, including
the axiom that composition be functional, even though it has distinct
morphisms.

Here's another category.  It has one object M' and two arrows g_0 and
g_1 and its composition is given by

dom(g_0) = dom(g_1) = cod(g_0) = cod(g_1) = M'
id_M' = g_1

g_1 o g_0 = g_0 o g_1 = g_0.
g_1 o g_1 = g_0 o g_0 = g_1.

Distinct categories.  In the second category, for instance, every arrow
is an isomorphism, whereas this is not true in the first category.

I sincerely hope this clears up your misunderstanding.  Category theory
places certain restrictions on what counts as composition, but it
doesn't *determine* the composition function for each category.

--
"If you go to my blog you may notice that I have a link to a Princeton
graduate student who seems to think I'm a great 'mathematican', and I
do wonder why he has that word wrongly spelled."
-- James S. Harris has mathematic supporters

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 4:18 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 13:18:39 -0800 (PST)
Local: Mon, Nov 5 2012 4:18 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 2:38 pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:

That should be a PARTIAL function.

> in such a case is for g o f to be simply one
> > possible composition. If so, then g o f should not be seen as The
> > Composition, but simply as one POSSIBLE composition. It could still be
> > a function.

Again, a PARTIAL function.

> How can a*b be 1 or c in a group with four elements?

> The axioms of category theory require composition to be a partial
> function.

[snip]

Agreed. But leaving aside your own examples for now, in the example I
just posed to Rotwang and Aatu, you then agree that it doesn't matter
whether g o f = h1 or h2 -- I should just pick one. If I chose g o f =
h1, then, even though h2 is, in a sense, also a composition of f and
g, we would have g o f =/= h2. I can live with that. It just means
that, in some cases g o f is NOT the only composition of f and g.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 4:48 pm
Newsgroups: sci.logic, sci.math
From: "Jesse F. Hughes" <je...@phiwumbda.org>
Date: Mon, 05 Nov 2012 16:46:21 -0500
Local: Mon, Nov 5 2012 4:46 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category

No.  There is only one composite for f and g in a given category.  But,
in the situation you described, there are two distinct[1] categories
involving these arrows, depending on how composition is defined.

For any given category, composition must be functional.  But it may well
be that there is another category in which composition is defined
differently, although the objects, morphisms, domain, etc., are all the
same.

I'm not sure if that explains it to you, but the matter really is
analogous to group theory.  Given that the carrier of my group is
{1,a,b,c}, there are at least two obvious options for a * b.  It might
be 1, or it might be c.  The axioms of group theory doesn't tell me what
a * b is, but rather when I specify the group, I have to provide the
multiplication.

Similarly, categories come with a specified composition (partial)
function.

Footnotes:
[1]  Sort of.  Sounds to me like the two choices are equivalent
categories, so whether they should be distinct or not is a real question.

--
Jesse F. Hughes
"I will admit I can get giddy over these forays into ideas at the
extreme edge.  Being wrong can just add to the fun, oddly enough."
--James S. Harris just wants to have fun.

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 6:36 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 15:36:56 -0800 (PST)
Local: Mon, Nov 5 2012 6:36 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 4:48 pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:

[snip]

No, my example has 4 distinct morphisms, f, g, h1 and h2 within the
SAME category C. What do you do when there are multiple distinct
morphisms between dom(f) and cod(g)? Or is this not allowed in the
axioms of CT? If it is allowed, do you just select one and designate
it as The Composition and say that the others are simply NOT equal to
The Composition?

> Footnotes:
> [1]  Sort of.  Sounds to me like the two choices are equivalent
> categories, so whether they should be distinct or not is a real question.

Equivalence classes might work, but I have seen no mention of them
associated with a category -- not in the definitions of a category
anyway. Did you not say that there could be multiple, distinct
morphisms (arrows) from one object (node) to another?

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 7:03 pm
Newsgroups: sci.logic, sci.math
From: "Jesse F. Hughes" <je...@phiwumbda.org>
Date: Mon, 05 Nov 2012 18:58:22 -0500
Local: Mon, Nov 5 2012 6:58 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category

Look, there are two possible categories that satisfy your description.
We're ignoring the identity morphisms, of course, and assuming that
there are only four non-identity arrows:

f: A -> B
g: B -> C
h1:A -> C
h2:A -> C

Case 1: g o f = h1.

Case 2: g o f = h2.

These are (literally speaking) two distinct categories (though they are
indistinguishable as categories, and so we would treat them the same,
but this is a minor point that should not distract you much).

>> Footnotes:
>> [1]  Sort of.  Sounds to me like the two choices are equivalent
>> categories, so whether they should be distinct or not is a real question.

> Equivalence classes might work, but I have seen no mention of them
> associated with a category -- not in the definitions of a category
> anyway. Did you not say that there could be multiple, distinct
> morphisms (arrows) from one object (node) to another?

Of course you haven't learned what equivalence between categories is,
because you don't know what a functor is.

But, *YES*, there could be multiple, distinct morphisms from one object
to another.  I've told you this repeatedly, and nothing I've said here
should cast any doubt on that obvious fact.

--
"Reality has a fascinating ability to check us when we get a little too
big for our britches... Make no mistake.  There isn't a mathematician alive
today that I can't now touch, and not a mathematical career on the planet
that I can't now affect."  --James Harris, render of worlds

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 7:03 pm
Newsgroups: sci.logic, sci.math
From: Aatu Koskensilta <aatu.koskensi...@uta.fi>
Date: Tue, 06 Nov 2012 02:03:50 +0200
Local: Mon, Nov 5 2012 7:03 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category

Dan Christensen <Dan_Christen...@sympatico.ca> writes:
> Agreed. But leaving aside your own examples for now, in the example I
> just posed to Rotwang and Aatu, you then agree that it doesn't matter
> whether g o f = h1 or h2 -- I should just pick one. If I chose g o f =
> h1, then, even though h2 is, in a sense, also a composition of f and
> g, we would have g o f =/= h2.

In what sense is h2 also a composition of f and g? All you know is
that h2 has suitable domain and codomain. Whether it's the composition
of f and g depends on the f and g in question, and the relevant notion
of composition given by the category at issue.

> I can live with that. It just means that, in some cases g o f is NOT
> the only composition of f and g.

Whether h2 or h1 is the composition of f and g is determined by the
category. Again, do note the (partial binary) operation of composition
is part of the data that defines a category.

--
Aatu Koskensilta (aatu.koskensi...@uta.fi)

"Wovon man nicht sprechen kann, dar ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 7:07 pm
Newsgroups: sci.logic, sci.math
From: Aatu Koskensilta <aatu.koskensi...@uta.fi>
Date: Tue, 06 Nov 2012 02:07:35 +0200
Local: Mon, Nov 5 2012 7:07 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category

Dan Christensen <Dan_Christen...@sympatico.ca> writes:
> SAME category C. What do you do when there are multiple distinct
> morphisms between dom(f) and cod(g)?

The category tells you what to do -- when we are given a category we
are in particular given the relevant notion of composition for
morphisms.

--
Aatu Koskensilta (aatu.koskensi...@uta.fi)

"Wovon man nicht sprechen kann, dar ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 10:34 pm
Newsgroups: sci.logic
From: George Greene <gree...@email.unc.edu>
Date: Mon, 5 Nov 2012 19:34:51 -0800 (PST)
Local: Mon, Nov 5 2012 10:34 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 10:56 am, Dan Christensen <Dan_Christen...@sympatico.ca>
wrote:

> Or do we just accept that g o f may not be the only composition of f
> followed by g? That g o f is not THE composition, but only A
> composition?

NO, it's THE composition, within any ONE category.
The composition FUNCTION is being defined WITHIN the category.
It's an associative binary operator on arrows/morphisms.
It takes two arrows as arguments and returns an arrow as a result.
IF the operands are compatible.
g o f  satisfies  cod(f)=dom(g) --> (dom(f)=dom(gof) /\
cod(g)=cod(gof)).

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 10:46 pm
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 19:46:47 -0800 (PST)
Local: Mon, Nov 5 2012 10:46 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 7:03 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:

> Dan Christensen <Dan_Christen...@sympatico.ca> writes:
> > Agreed. But leaving aside your own examples for now, in the example I
> > just posed to Rotwang and Aatu, you then agree that it doesn't matter
> > whether g o f = h1 or h2 -- I should just pick one. If I chose g o f =
> > h1, then, even though h2 is, in a sense, also a composition of f and
> > g, we would have g o f =/= h2.

>   In what sense is h2 also a composition of f and g?

In the sense that dom(h2)=dom(f) and cod(h2)=cod(g).

> All you know is
> that h2 has suitable domain and codomain.

That should be enough.

"For each ordered triple of objects A, B, C in category [curly] C,
there is a law of composition: If f:A->B and g:B->C, then the
composite of f and g is a morphism gf:A->C."

Source: "Category Theory," WikiBooks, http://en.wikibooks.org/wiki/Category_Theory/Categories#Definition

Doesn't that suggest that ANY morphism mapping A to C (in the
defintion here) would do for the composite of f and g? Did WikiBooks
get it wrong?

> Whether it's the composition
> of f and g depends on the f and g in question, and the relevant notion
> of composition given by the category at issue.

I'm just going by the above definition, and it suggests that the
domain and codomain are the ONLY relevant criteria. A problem arises,
of course, when there are multiple, distinct morphisms from A to C --
which one to pick? It's beginning to look to me like the choice is
completely arbitrary.

Can you cite any authoritative source to contrary? Online would be
nice.

> > I can live with that. It just means that, in some cases g o f is NOT
> > the only composition of f and g.

>   Whether h2 or h1 is the composition of f and g is determined by the
> category.

Again, the definition above suggests that the only determining
criteria are the domain and codomain.

> Again, do note the (partial binary) operation of composition
> is part of the data that defines a category.

It seems to me that would it work perfectly fine to arbitrary select
as the composite any morphism with the required domain and codoemain.
This would at least be consistent with all the definitions we have
looked at.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 10:51 pm
Newsgroups: sci.logic
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 19:51:08 -0800 (PST)
Local: Mon, Nov 5 2012 10:51 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 10:34 pm, George Greene <gree...@email.unc.edu> wrote:

> On Nov 5, 10:56 am, Dan Christensen <Dan_Christen...@sympatico.ca>
> wrote:

> > Or do we just accept that g o f may not be the only composition of f
> > followed by g? That g o f is not THE composition, but only A
> > composition?

> NO, it's THE composition, within any ONE category.

See my reply to Aatu K. just now.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 10:56 pm
Newsgroups: sci.logic
From: George Greene <gree...@email.unc.edu>
Date: Mon, 5 Nov 2012 19:56:14 -0800 (PST)
Local: Mon, Nov 5 2012 10:56 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 10:03 am, Dan Christensen <Dan_Christen...@sympatico.ca>
wrote:

> It is true in categories for which there is at most one distinct
> morphism from one object to another, but how do we handle composition
> if there are multiple distinct morphisms from one object to another?

BOTH OF THE EXAMPLES YOU WERE JUST GIVEN *ARE* examples where there
are multiple distinct morphisms from one object to another (or to THE
SAME object,
just for simplicity).  If 4x4 was too big for you, let's dial both
examples down to order 3.
In both examples, we have 1 object.
Example 1: the group (of order 6) of permutations of 3 objects.
The identity-arrow and the only object here is the permutation that
leaves all 3 objects in their original order ..  ( 1 2 3 ).
The other 5 arrows/morphisms are ( 1 3 2 )  ( 2 1 3 )   (2 3 1 )  ( 3
1 2 )  ( 3 2 1 ).
Each of these morphisms/permutations composes with any/all of the
others (pairwise) to yield ONE UNIQUE
result.  There are *six*, NOT *one*, arrows between the object (1 2 3)
and itself, here.

Example 2: the matrix-algebra on 3x3 matrices.
The identity arrow and the only object here is the 3x3 identity-
matrix,
1 0 0
0 1 0
0 0 1

ANY AND EVERY 3x3 matrix in the world (integers, rationals, reals,
complex numbers, for all 9 "elements")
IS AN ARROW from this matrix BACK TO this matrix.  To compose two 3x3
matrices, you just take their
matrix product.  There is some non-determinism here about whether
"applying" the morphism means multiplying
on the left or on the right but every matrix has a transpose so there
is a sense in which that almost doesn't matter.
I guess this category has some very special property AS A RESULT of
every matrix having a transpose, but I
don't know what it's called.

In any case, the point is, OF COURSE there are multiple arrows between
the same two objects -- THAT'S
WHY WE CALL THEM HOM-SETS -- and OF COURSE this fact does NOT make
composition multi-valued
or non-functional.  FOR EVERY pair of arrows that chain, the
composition function INSIDE THAT category
ALWAYS PRODUCES A UNIQUE result!

You are thinking that there could be different "possible" results
because you are imagining DIFFERENT
categories with DIFFERENT arrows and a DIFFERENT locally-defined
composition over "the same" objects.
The point here is simply that every category is different and comes
with ITS OWN VERSION OF composition.

There is, for example, more than 1 group of order 4.
Represented as a category, every group of order 4
has 1 identity arrow and 3 other arrows, but there are TWO DIFFERENT
WAYS OF DEFINING COMPOSITION
on those 4 arrows that make it associative and functional and that
make sure every arrow has an inverse (those
are the things it takes to make the arrows a group).
These are NOT two different forms or kinds of composition; they are
just two different ways of defining the
category.   The "structure of" the category is ALL in the
"composition" function, really.  Different categories
just chain the arrows (via composition) differently.

One group of order 4, where the only object/identity is 0 and you can
define composition
0 1 2 3.
An isomorphic  group of order 4, where the only object/identity is 1
and you define composition by complex multiplication, is
1 i -1 -i .   Categorically speaking, these are the SAME group and the
SAME category, just with different labels on the arrows.
Adding 1 in the top group is like multiplying by i in the bottom one.

In the other group of order 4, every element is its own inverse and
the composition of any two
non-identity elements is the third one.

All 3 of these groups are abelian.

They have "different" composition operators but all of their
composition operators satisfy the categorical axioms for composition,
and withIN each category, each composition operator provides a UNIQUE
composition for any two morphisms.

Trying to compare between categories is arguably impossible anyway
since (despite the occurrence of "1" in both
of the cyclic group categories as-presented-here) the objects really
are different and disjoint.
Or otherwise totally the same (isomorphic)  and just being labeled
differently.

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 11:03 pm
Newsgroups: sci.logic
From: George Greene <gree...@email.unc.edu>
Date: Mon, 5 Nov 2012 20:03:09 -0800 (PST)
Local: Mon, Nov 5 2012 11:03 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 10:46 pm, Dan Christensen <Dan_Christen...@sympatico.ca>
wrote:

> It seems to me that would it work perfectly fine to arbitrary select
> as the composite any morphism with the required domain and codoemain.
> This would at least be consistent with all the definitions we have
> looked at.

ANYthing that satisfies the axioms COUNTS.
It is NOT like you have some arrows PREdefined just lying around!
YOU HAVE TO ASSERT *which* arrow the composition is going to be!

In the matrix-multiplication case, there are a lot of other operations
besides
matrix multiplication that you could use to define composition of 2
matrices,
that would still produce a category.  A different, lamer, category,
but still a category.

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 11:28 pm
Newsgroups: sci.logic
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 20:28:20 -0800 (PST)
Local: Mon, Nov 5 2012 11:28 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 10:56 pm, George Greene <gree...@email.unc.edu> wrote:

> On Nov 5, 10:03 am, Dan Christensen <Dan_Christen...@sympatico.ca>
> wrote:

> > It is true in categories for which there is at most one distinct
> > morphism from one object to another, but how do we handle composition
> > if there are multiple distinct morphisms from one object to another?

> BOTH OF THE EXAMPLES YOU WERE JUST GIVEN *ARE* examples where there
> are multiple distinct morphisms from one object to another (or to THE
> SAME object,
> just for simplicity).

That was the point -- what to do when there are multiple, distinct
morphisms from which to choose the composition?

> If 4x4 was too big for you, let's dial both
> examples down to order 3.

[snip]

Thanks for the lengthy and thoughtful response, George. But I just
don't have time to wade through your list of examples. Maybe you can
just tell us what your bottom line is? What aspects of CT do your
examples illustrate?

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 11:42 pm
Newsgroups: sci.logic
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 20:42:14 -0800 (PST)
Local: Mon, Nov 5 2012 11:42 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 11:03 pm, George Greene <gree...@email.unc.edu> wrote:

> On Nov 5, 10:46 pm, Dan Christensen <Dan_Christen...@sympatico.ca>
> wrote:

> > It seems to me that would it work perfectly fine to arbitrarily select
> > as the composite any morphism with the required domain and codoemain.
> > This would at least be consistent with all the definitions we have
> > looked at.

> ANYthing that satisfies the axioms COUNTS.
> It is NOT like you have some arrows PREdefined just lying around!
> YOU HAVE TO ASSERT *which* arrow the composition is going to be!

But what do to if several, distinct arrows (morphisms) have the
required domain and codomain for a composition? It seems to me that
any one of them would do as The Composition. Of course, if all your
arrows (morphisms) are functions, this is not a consideration as there
is a unique composition of any pair of functions with compatible
domains and codomains.

> In the matrix-multiplication case, there are a lot of other operations
> besides
> matrix multiplication that you could use to define composition of 2
> matrices,
> that would still produce a category.  A different, lamer, category,
> but still a category.

It is not clear to me what aspect of CT this illustrates.

Dan

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 5 2012, 11:57 pm
Newsgroups: sci.logic, sci.math
From: Rotwang <sg...@hotmail.co.uk>
Date: Tue, 06 Nov 2012 04:57:08 +0000
Local: Mon, Nov 5 2012 11:57 pm
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On 06/11/2012 03:46, Dan Christensen wrote:

> On Nov 5, 7:03 pm, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
>> Dan Christensen <Dan_Christen...@sympatico.ca> writes:
>>> Agreed. But leaving aside your own examples for now, in the example I
>>> just posed to Rotwang and Aatu, you then agree that it doesn't matter
>>> whether g o f = h1 or h2 -- I should just pick one. If I chose g o f =
>>> h1, then, even though h2 is, in a sense, also a composition of f and
>>> g, we would have g o f =/= h2.

>>    In what sense is h2 also a composition of f and g?

> In the sense that dom(h2)=dom(f) and cod(h2)=cod(g).

But that isn't what "composition of f and g" means.

>> All you know is
>> that h2 has suitable domain and codomain.

> That should be enough.

> "For each ordered triple of objects A, B, C in category [curly] C,
> there is a law of composition: If f:A->B and g:B->C, then the
> composite of f and g is a morphism gf:A->C."

> Source: "Category Theory," WikiBooks, http://en.wikibooks.org/wiki/Category_Theory/Categories#Definition

> Doesn't that suggest that ANY morphism mapping A to C (in the
> defintion here) would do for the composite of f and g?

No, it doesn't.

> Did WikiBooks get it wrong?

No, you just don't understand what you're reading. Look, here's a quote
from http://en.wikipedia.org/wiki/Group_%28mathematics%29:

The following properties of integer addition serve as a model for the
abstract group axioms given in the definition below.

For any two integers a and b, the sum a + b is also an integer.

Do you take that last sentence to mean that ANY integer would do for the
sum of a and b? Of course not. When defining a group, such as the
additive group of integers, one specifies the group product as part of
the definition. There is more than one way to define a group product on
the set of integers; different definitions of the group product give
rise to different groups, albeit ones with the same underlying set.

There's a good reason why people keep using group theory as an analogy -
in fact it's more than an analogy. Groups are really a special case of
categories. That WikiBooks page even says so:

Since you apparently believe what that page says about category theory
(quite why you believe that page but don't believe what anybody here is
telling you - including Jesse, who did a PhD in category theory - is a
mystery), why not consider how the things you're saying apply groups,
when those groups are viewed as categories? In such categories, the
morphisms are simply the elements of a group, and the composition of
morphisms is simply their product. So when you write, for example,

How can g o f can be the one and only composition of f followed by g
(assuming cod(f)=dom(g)) in a category with multiple distinct
morphisms from dom(f) to cod(g)? It seems to me that the only way that
'o' can be a function in such a case is for g o f to be simply one
possible composition. If so, then g o f should not be seen as The
Composition, but simply as one POSSIBLE composition.

this becomes (denoting a group product by *)

How can a*b can be the one and only product of b and a in a group
with multiple distinct elements? It seems to me that the only way that
'*' can be a function in such a case is for a*b to be simply one
possible product. If so, then a*b should not be seen as The Product,
but simply as one POSSIBLE product.

Similarly, when you write

Then, of course, we would also have:

g o f =/= h2

even though, in a sense, h2 is also a composition of f followed by g.

this becomes

Then, of course, we would also have

a*b =/= c2

even though, in a sense, c2 is also a product of b and a.

And when you write

It just means that, in some cases g o f is NOT the only composition
of f and g.

this becomes

It just means that, in some cases a*b is NOT the only product of b
and a.

You see how nonsensical these statements about group theory are, right?
But those are /your/ statements, applied to the special case of category
theory in which categories have a single object and every morphism is an
isomorphism (i.e. groups).

>> Whether it's the composition
>> of f and g depends on the f and g in question, and the relevant notion
>> of composition given by the category at issue.

> I'm just going by the above definition, and it suggests that the
> domain and codomain are the ONLY relevant criteria. A problem arises,
> of course, when there are multiple, distinct morphisms from A to C --
> which one to pick? It's beginning to look to me like the choice is
> completely arbitrary.

> Can you cite any authoritative source to contrary? Online would be
> nice.

the sentence that says "We take as composition the group
multiplication." Notice how it doesn't say "We take as the composition
anything at all, since the choice is completely arbitrary."

> [...]

> It seems to me that would it work perfectly fine to arbitrary select
> as the composite any morphism with the required domain and codoemain.
> This would at least be consistent with all the definitions we have
> looked at.

No it wouldn't, since many such arbitrary choices would fail to satisfy
associativity.

--
I have made a thing that superficially resembles music:

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 6 2012, 12:27 am
Newsgroups: sci.logic, sci.math
From: Dan Christensen <Dan_Christen...@sympatico.ca>
Date: Mon, 5 Nov 2012 21:27:33 -0800 (PST)
Local: Tues, Nov 6 2012 12:27 am
Subject: Re: Toward a Formal, Machine-Parsable Definition of a Category
On Nov 5, 11:57 pm, Rotwang <sg...@hotmail.co.uk> wrote:

That's all it means in CT -- in effect, just putting 2 arrows head-to-
tail.

[snip]

I disagree.

> So when you write, for example,

>    How can g o f can be the one and only composition of f followed by g
>    (assuming cod(f)=dom(g)) in a category with multiple distinct
>    morphisms from dom(f) to cod(g)? It seems to me that the only way that
>    'o' can be a function in such a case is for g o f to be simply one
>    possible composition. If so, then g o f should not be seen as The
>    Composition, but simply as one POSSIBLE composition.

> this becomes (denoting a group product by *)

>    How can a*b can be the one and only product of b and a in a group
>    with multiple distinct elements?

[snip]

As I have said elsewhere, if all your morphisms are functions (as in
your group examples), their composition is always uniquely defined.
But morphisms are not always functions in other categories.

This is only a particular case -- the category of groups where all
morphisms are functions. Our definitions must also cover the case
where morphisms are not functions.

> > It seems to me that would it work perfectly fine to arbitrary select
> > as the composite any morphism with the required domain and codoemain.
> > This would at least be consistent with all the definitions we have
> > looked at.

> No it wouldn't, since many such arbitrary choices would fail to satisfy
> associativity.

How so?

Dan