Ok, this helps a great deal.
That said, I am dismayed by the english language the authors use to
describe arrows. There's an important distinction which exists in the
mathematical framework they construct, and while they are careful
about distinguishing analogous ambiguities in other contexts they
never directly mentions the existence of what I feel is a significant
ambiguity involving the ways that arrows can be functions.
Here's an implementation of arrow, in J, which corresponds with their
initial construction of the theory in terms of a multigraph:
arrow=: 2 :0
assert. n -: y
u y
)
For example, a category with objects 0 and 1 could have arrows:
>: arrow 0
<: arrow 1
0: arrow 0
1: arrow 0
In other words, here an arrow is a constant function with a single
element domain. And, you can have different arrows that produce the
same result for a given domain.
Relevant operations on these kinds of arrows include:
source=: 1 :0
('';1;1;1) {:: 5!:1 <'u'
)
target=: 1 :0
u u source
)
idArrow=: 1 :0
(m"_) arrow m
)
isIdArrow=: 1 :0
-:/ u`(u source idArrow)
)
label=: 1 :0
({.('';1) {:: 5!:1 <'u')`:6
)
compose=: 2 :0
if. u isIdArrow do. v return. end.
if. v isIdArrow do. u return. end.
u@v arrow (v source)
)
Here are some examples of these operations:
(>: arrow 0) source
0
(>: arrow 0) target
1
(>: arrow 0) label
>:
Note that the parenthesis here are not necessary, I have only included
them for emphasis. Note that the function which defines the target in
terms of the source is the label for the arrow, and different arrows
can have the same label. (I want arrows to have labels so that I have
some way of distinguishing between different arrows that connect the
same nodes in the underlying multigraph.)
>: arrow 1 label
>:
>: arrow 2 label
>:
+&1 arrow 2 label
+&1
Note that arrows are functions:
(+&1 arrow 2) 2
3
but they have restricted domains
(+&1 arrow 2) 3
|assertion failure
Also, note that we can have an arbitrary number of arrows connecting a
node to itself, and exactly one of those arrows is defined as the
identity arrow:
The identity arrow for 0 is a constant function with the domain 0 and
the result 0:
0 idArrow 0
0
This arrow behaves the same as an arrow based on the constant function 0:
(0 idArrow -: 0: arrow 0) 0
1
(Note that, in the above sentence, the parenthesis are important
because of J's word formation rules.)
However, only one of these two arrows is the identity arrow:
(0 idArrow) isIdArrow
1
(0: arrow 0) isIdArrow
0
And, we can compose arrows:
(>: arrow 2) compose (>: arrow 1) target
3
(>: arrow 2) compose (>: arrow 1) source
1
Anyways, the above operations and examples roughly correspond with
what the authors describe as a "large category". The interesting
stuff starts happening when they deal with a "small category", which
is to say where the arrows and the objects are sets.
So, first off, let's consider an example of what we can do if the
objects are sets. I want to write a concrete implementation, so I
will restrict myself to representing sets as a sequence such that
~.@/:~ is an identity operation.
smallArrowCore=: 2 :0
'codomain domain'=. n
assert. *./ (u"_1 domain) e. codomain
codomain"_@:(u"1) arrow domain
)
smallArrow=: 2 :0
domain=. ~./:~ n
codomain=. ~./:~ m
smallArrowCore(codomain,&<domain)
)
smallDomain=: source
smallCodomain=: target
smallLabel=: 1 :0
({.('';1;0;1;1;1) {:: 5!:1 <'u')`:6
)
smallCompose=: 2 :0
assert. u source -: v target
(u label @ v label) (u target) smallArrow (u source)
)
smallIdArrow=: 1 :'(~./:~ m) idArrow'
isSmallIdArrow=: 1 :0
-:/ u`(u source smallIdArrow)
)
The difference here is that where before my function mapped directly
from the source to the target, here my function (my label) only
produces an image on the target, which means that I need to specify
the target explicitly.
>: 1 2 smallArrow 0 1 target
1 2
>: 1 2 smallArrow 0 1 smallLabel
>:
So now my objects are sets. But the authors specify that the arrows
be sets. What does this mean?
I *think* this means that when they say "an arrow" they no longer mean
a single arrow but they mean "a set of arrows". And, I think they
mean the set of arrows in a category which (if they were build by the
routines I have implemented here) have the same label.
But they might mean something else?
If this is what they mean then the composition of arrows is also a set
of arrows, an identity arrow is a set of arrows, and so on... And,
where individual arrows must always be constant functions, a set of
arrows is a relationship, instead, between sets of domains.
Anyways, if "an arrow" can be "an individual arrow" OR "a set of
arrows" then it is no longer the case that "an arrow" only connects a
single pair of objects.
In other words, if my current understanding is correct, in chapter 1
they went to great lengths to establish that an arrow was a unique,
single edge in a multigraph. And then, in chapter 2 they imply that
an arrow can be an entire subgraph of the multigraph.
If my understanding is correct, then I am bothered that they would
make this leap without stating it more clearly. If my understanding
is not correct then I am missing something big.
Thanks,
--
Raul
On Fri, Apr 13, 2012 at 7:04 AM, Robert Raschke <rtrli...@googlemail.com> wrote:
> May I recommend this introduction to Category Theory:
> http://www.ling.ohio-state.edu/~plummer/courses/winter09/ling681/barrwells.pdf
>
> The first ten pages should suffice to get a bit of clarity with the
> terminology. (Section 2.1.11 defines the "category of sets".)
>
> Robby
>
> On Thu, Apr 12, 2012 at 10:49 PM, Raul Miller <rauldmil...@gmail.com> wrote:
>
>> On Thu, Apr 12, 2012 at 3:46 PM, Jordan Tirrell
>> <jordantirr...@gmail.com> > We are using what we know about functions
>> on sets simply to define the
>> > category *Set* (where objects are all sets and arrows are all functions
>> on
>> > sets).
>>
>> That seems to be ambiguous, though, and I am trying to understand
>> what's really meant.
>>
>> The issues which are significant, to me, are:
>>
>> 1. The difference(s) between a "Function" and an "Arrow" which in some
>> way represents a function.
>>
>> 2. The difference between a member of a domain and the domain itself.
>>
>> 3. What exactly is being represented by the composition of arrows.
>>
>> > We then usually try to capture ideas about functions in categorical
>> > language in *Set*. Marshall gave a great example about how we can look at
>> > the category *Set* alone and identify which object corresponds to the
>> empty
>> > set, and which objects correspond to one-element sets. Specifically, the
>> > empty set is the object in our category which has a unique arrow to every
>> > object (in general this is called an initial object).
>>
>> And, this uniqueness works with a variety of different concepts for
>> how Arrows relate to Functions.
>>
>> > The dual notion of terminal object identifies the singleton sets.
>> > The power of category theory is right here: we have left behind
>> > our normal definitions of empty set and singleton set and discovered
>> > that they correspond to the categorical definitions of initial and
>> > terminal object (within this specific category *Set*).
>>
>> No.
>>
>> We have not yet left behind our normal definition of the -- that
>> definition was a part of the definition of this *Set*. We also
>> have not yet fully defined *Set*.
>>
>> > Now a set theorist can sit down with, say, a group theorist, and even if
>> > both are ignorant of each other's field, they can have a meaningful
>> > conversation: Does the category you study have an initial/terminal
>> object?
>> > One or many? Of course this is a toy example, but I think its a good
>> > glimpse into the usefulness of category theory as a unifying theme in
>> math.
>>
>> I have no problems believing that a notation can be useful.
>>
>> That is why I am interested in the first place.
>>
>> But before I can go there, there's a little matter of making sure
>> I understand what the notation means.
>>
>> >> First off, as a side note, let us consider "the set of all sets which
>> >> are not contained in any categories". Without further axioms we do
>> >> not know if this set is empty or non-empty. (Example axioms: "The
>> >> set of all sets which are not contained in any categories is a
>> >> non-empty set", or "The set of all sets which are not contained in any
>> >> categories is an empty set".) So right off, we know that involving
>> >> sets introduces all of the problems that sets have.
>> >
>> > As far as I know, set theory axioms would not allow a definition like
>> "the
>> > set of all sets which are not contained in any categories".
>>
>> All I need, to be able to do this, is to have a formal definition
>> of "category" in my system.
>>
>> > There are some very interesting issues with the use of sets
>> > vs collections when we discuss categories, which is why
>> > restricting to categories whose objects and arrows both form
>> > sets (called a small category) is common. *Set* is not small, so
>> > we do have to be careful. Let's not get into set theory though,
>> > since I will quickly be unable to offer good answers to questions,
>> > and it is another step removed from J programming.
>>
>> Yes... I wanted to work with a category where the objects represented
>> the domain of the values 0 and 1 and where arrows represented functions
>> on that domain. Another domain I liked was where objects represented
>> the domain of the values 0, 1, 2, 3 or 4.
>>
>> >> We could say that an arrow corresponds to a function and an object
>> >> corresponds to the domain of a function (and the object that an arrow
>> >> leads to corresponds to the image of the function). Here, identifying
>> >> an arrow uniquely identifies a function.
>> >
>> > This is a category, it is like *Set* but restricted to onto functions.
>>
>> Then I need a more complete definition of the category *Set*.
>>
>> But I think you are saying here that the function with the
>> domain {0, 1} and the image {0} with codomain {0} is a different
>> function from the function with the domain {0, 1} and the image
>> {0} with the codomain {0, 1}.
>>
>> And, while I can accept that these are different arrows, it
>> seems to me that these are the same function.
>>
>> --
>> Raul
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
