Confused about C Embedding in Funct(Cop, Set)

In summary: Yoneda lemma is a vast generalization of Cayley's theorem. Given two categories C and D, the Yoneda lemma says that the set of natural transformations between C and D is isomorphic to the set of group actions between C and D. This is because the group action is a faithful embedding.
  • #1

Hurkyl

Staff Emeritus
Science Advisor
Gold Member
14,981
26
This thing still confuses me. And it seems every reference I look at states it entirely differently. :frown:

I guess I've heard it stated in words -- there is a full embedding of C in Funct(Cop, Set). I know what all of the words mean, but I'm not sure if that helps yet. :smile:

There's one particular application of it that interests me, and I can't really see how to use it: there's a proof that shows the existence of a natural transformation Hom(_, A) --> Hom(_, B).

From this, they then conclude (by the Yoneda lemma!) that this natural transformation must come from a uniquely determined map A --> B. (The existence of this map is what interests me)

How does that follow?
 
Physics news on Phys.org
  • #2
I agree Yoneda is quite confusing, at least I thought so (I think I may still think so).

I'm not sure I can adequately explain the lemma itself, but the corollary is easy.

Yoneda states that if F is a covariant function, and G a representable functor, say G=(X,?)=Hom(X,?), then the natural trans from G to F are in bijection with F(X).

So, given two representable functors (A,?) and (B,?) the natural transformations are in bijection with (A,B), ie a map A to B uniquely determines a natural transformation.

Actually you have the contravariant statement, but it doesn't matter.

The bijection Nat( (X,?), F) comes about from the fact that the universality properties say it is sufficient to consider what the image of Id in (X,X) is sent to in F(X) by the natural transformation, and that this assignment is sufficient to determine the transformation.

But I admit freely that I don't really *get* Yoneda. Perhaps this would be a good discussion topic? Anyone sufficiently well versed in Mac Lane to explain pages 59-61 without having to read pages 1-58?
 
  • #3
Well, a way to prove the lemma struck me to work today -- you can show that any natural transformation η: Hom(_, A) --> K is completely determined by its action on the identity morphism of A, ηHom(A, A)(1A). Since this object function takes values in K(A), we get the natural isomorphsim.

This isn't entirely enlightening, though. :smile:


Wikipedia describes the Yoneda lemma as a vast generalization of Cayley's theorem, so maybe understanding will come from looking at it from that perspective?

I'm using the convention that fg is in arrow order. That is, codom f = dom g. (Writing this, I'm beginning to feel like I should also write function application on the right too! Ah well)


If C is a category that is a group, then the content of the Yoneda lemma is:

K : C --> Set is simply a group representation of C. That is, C acts on the set K(1) through the group action described by K.

Hom(_, 1) amounts to the Cayley representation of a group. Hom(1, 1) is simply the elements of the group, and Hom(f, 1) is simply the set function that gives right multiplication by f.


So, the Yoneda lemma says that the set of natural transformations Hom(_, 1) --> K is isomorphic to the set K(1). A natural transformation, here, is simply a function from Hom(1, 1) --> K(1) that respects the group action. There is a clear 1-1 correspondence between the natural transformations and the set K(1): the identity can go anywhere, and the rest is determined by the group action.


Categories, Allegories (Freyd, Scedrov) describes a concept of category action, and a Cayley representation for categories.

A (right-)category action of C on a set S is just like a group action. There's a "target" function S --> C, and any morphism f is a partial operation f^ on S. The domain of f^ is precisely those elements of S whose target is f's source.

So, you can think of each element of S as being labelled with an object of C, and any morphism A --> B maps any object labelled as A to an object labelled with B.

The Cayley representation is a functor C --> Set given by:
Cayley(A) is the set of all morphisms whose target is A
Given f:A-->B, Cayley(f) is a set function Cayley(A) --> Cayley(B) which is defined by right multiplication. IOW, Cayley(f)(g) = gf

In other words, it's just the category acting on itself! (on the right)

This is a faithful embedding, BTW.


So now, let's consider a functor K : C --> Set. Let's assume the objects in the image of K are all disjoint. Then, K gives rise to a right C-set. (That is, a set with a right action by C)
The set is simply the union of all the objects in the image of K.
The target operation is simply the inverse of K. That is, the target of any element of K(A) is A.
The action is given by K. If the target of x is A, and f:A-->B, then xf := K(f)(x)

So, K is describing a category action on some set.


Hom(_, A) is also describing a category action... on the set of all morphisms whose target is A. Note that this is a subset of the Cayley representation!

Now, any natural transformation Hom(_, A) --> K is simply a set function that respects the category action, and is again uniquely determined by its action on the identity morphism of A. So, we have the isomorphism Nat(Hom(_, A), K) ~ K(A). (It's K(A) because it has to respect the target operation!)

But the cool thing is that it's a natural isomorphism. (Right?) So we have this natural isomorphism Nat(Hom(_, ?), K) --> K(?). This is surely saying something important about the two representations of the category C! There's probably some really nice higher-dimensional picture that explains it all really nicely.

But for now, I think the key is understanding Nat(Hom(_, ?), K) --> K(?) as being natural in ?...
 
  • #4
here is an extract from my algebra book, which by the way is available in pdf format for the asking.

Our goal is the following converse assertion:
Theorem: Suppose the functors Hom(N,.) and Hom(M,.) are equivalent, via the isomorphisms ƒX:Hom(N,X)-->Hom(M,X), for all modules X. Then N and M are isomorphic via a unique map a:M¨N such that for all X, ƒX = a*.
proof: How do we prove something so abstract and complicated? As usual, just look for a natural map a:M-->N, and then try to show it has an inverse. Now the only entirely naturally given maps are the identities 1N:N-->N, and 1M:M-->M. But we have by hypothesis an isomorphism ƒN:Hom(N,N)-->Hom(M,N). This means we can transfer 1N over to a map a = ƒN(1N):M-->N. Since this is the only map obtainable from the assumptions, this must be it~ [Another way to guess the map a, is that if indeed ƒX = a*, then we can recover a as ƒN(1N) = a*(1N) = 1Noa = a. In particular this shows a is unique.]
The inverse map of course, should be (ƒM)^(-1)(1M):N-->M. To show these are indeed inverses, we must show their compositions are identities, using our hypotheses. The only hypotheses we have are those guaranteeing compatibility of ƒX and f*. That is, for each f:X-->Y, the two compositions: (f*oƒX):Hom(N,X)-->Hom(M,X)-->Hom(M,Y), and
(ƒYof*):Hom(N,X)-->Hom(N,Y)-->Hom(M,Y), are equal. Let's apply this to the case f = (ƒM)^(-1)(1M):N-->M. Then we have equality of the two compositions: (ƒM-1(1M)*0ƒN):Hom(N,N)¨Hom(M,N)¨Hom(M,M), and (ƒM)0(ƒM)^(-1)(1M)*):Hom(N,N)-->Hom(N,M)-->Hom(M,M). Applying the first of these compositions to the element 1N gives
(ƒM)^(-1)(1M)*oƒN)(1N) = (ƒM-1)(1M)o(ƒN(1N)). Applying the second composition gives (ƒM)0(ƒM-1)(1M)*)(1N) = ƒM(ƒM-1(1M)) = 1M. This proves that ƒM-1(1M) is left inverse to (ƒN(1N)). The proof it is also right inverse is similar.
To see that ƒN(1N)*(f) = ƒX(f) for all f in Hom(N,X), consider the two equal compositions: (ƒXof*):Hom(N,N)-->Hom(N,X)-->Hom(M,X), and
(f*oƒN):Hom(N,N)-->Hom(M,N)->Hom(M,X). Tracing 1N around both ways gives first (ƒXof*)(1N) = ƒX(1Nof) = ƒX(f), and then (f*oƒN)(1N) = f*(ƒN(1N)) = foƒN(1N) = (ƒN)(1N))*(f). QED.

actually i can't follow this myself as it is a flawed copy of my pdf file ina different font.

but the lemma is trivial.

as hurkyl guessed you just use the dientity map/


i.e. any map f:X--Y defines a map of functors from Hom(Y,.) to Hom(X,.) taking g to fog.

conversely any natural transformation from Hom(Y,.) to Hom(X,.) comes froma map f:X--<Y where f = the natural transformation applied to the identity map in Hom(Y,Y), yielding f in Hom(X,Y).

verifying this works is a trivial homework exercise in the definition of naturality, and it was a homework exercise in maurice auslanders class in first year aklgebra at brandeis in 1965.

I even got it right, which apparently is a great testimony to auslander's skill as a teacher. he made this incredibly abstract stuff look sooooo... easy.
 
Last edited:

1. What is C embedding?

C embedding refers to the process of incorporating code written in the C programming language into another programming language or environment. This allows for the use of C's powerful features and libraries within the context of a different language.

2. How do I embed C code in a function?

To embed C code in a function, you need to use a specific syntax depending on the language or environment you are working in. In general, you will need to use a special keyword, such as "extern" or "native", followed by the C code enclosed in curly braces. Make sure to also include any necessary header files and specify the return type and parameters of the function.

3. What is the purpose of C embedding in a function?

The purpose of C embedding in a function is to extend the functionality and capabilities of a programming language or environment by incorporating C code. This can be useful for tasks that require a high level of performance or for accessing C libraries that are not available in the current language or environment.

4. Can I call a C function from within another language?

Yes, it is possible to call a C function from within another language by using C embedding. This allows for the seamless integration of C code into a different language, making it possible to access C libraries and take advantage of its performance and functionality.

5. Are there any limitations to C embedding in a function?

There may be some limitations to C embedding in a function, as it depends on the specific language or environment you are working in. Some languages may have restrictions on the types of C code that can be embedded or may require additional steps for proper integration. It is important to research and understand the specific requirements and limitations for C embedding in your chosen language or environment.

Similar threads

  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Topology and Analysis
Replies
1
Views
995
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • General Math
Replies
8
Views
938
  • Special and General Relativity
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Special and General Relativity
Replies
14
Views
726
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
Replies
6
Views
784
Back
Top