The Unapologetic Mathematician

Mathematics for the interested outsider

Arrow Categories

One very useful example of a category is the category of arrows of a given category \mathcal{C}.

We start with any category \mathcal{C} with objects {\rm Ob}(\mathcal{C}) and morphisms {\rm Mor}(\mathcal{C}). From this we build a new category called \mathcal{C}^\mathbf{2}, for reasons that I’ll explain later. The objects of \mathcal{C}^\mathbf{2} are just the morphisms of \mathcal{C}. The morphisms of this new category are where things start getting interesting.

Let’s take two objects of \mathcal{C}^\mathbf{2} — that is, two morphisms of \mathcal{C} — and lay them side-by-side:
\begin{matrix}A&&C\\\downarrow^f&&\downarrow^g\\B&&D\end{matrix}
Now we want something that transforms one into the other. What we’ll do is connect each of the objects on the left to the corresponding object on the right by an arrow:
\begin{matrix}A&\rightarrow^h&C\\\downarrow^f&&\downarrow^g\\B&\rightarrow^k&D\end{matrix}
and require that the resulting square commute: g\circ h=k\circ f as morphisms in \mathcal{C}. This is a morphism from f to g. Sometimes we’ll write (h,k):f\rightarrow g, and sometimes we’ll name the square and write \alpha:f\rightarrow g.

If we have three morphisms f, g, and h in \mathcal{C}, and commuting squares (k_1,k_2):f\rightarrow g and (k_3,k_4):g\rightarrow h then we can get a commuting square (k_3\circ k_1,k_4\circ k_2):f\rightarrow h. We check that this square commutes: h\circ k_3\circ k_1=k_4\circ g\circ k_1=k_4\circ k_2\circ f. This gives a composition of commuting squares. It’s easily checked that this is associative.

Given any morphism f:A\rightarrow B in \mathcal{C} we can just apply the identity arrows to each of A and B to get a commuting square (1_A,1_B) between f and itself. It is clear that this square serves as the identity arrow on the object f in \mathcal{C}^\mathbf{2}, completing our proof that arrows and commuting squares in \mathcal{C} do form a category.

May 23, 2007 Posted by | Category theory | 5 Comments

ARML Scrimmage Power Question

As expected, the only really interesting part of the scrimmage was the “power question”. This is basically a proof-based problem the whole team of 15 (or so) works on for an hour. This was always what I was best at, and tonight’s was no exception. I’ll post the question here for you to chew on. I’m restating it somewhat for this forum. You can ask for clarifications in the comments, but I’d rather you not post solutions since I intend to come back to it in a week to give my own (cleaned-up) solutions.

I didn’t write them all the answers out myself, but I could have done within the hour if I didn’t have to write them out longhand. I also give credit to more fastidious members of the team reviewing some of my answers and writing them out in the actual competition.

This problem is concerned with “arrangements” of “bits”. A bit is just a symbol in one of two states: {}0 or 1. A configuration is a string of bits, considered to loop around from one end to the other. Actually the problem is written in terms of bits arranged around a circle, but I’ll just write them as strings to avoid having to draw circular configurations here.

We’re interested in the following transformation on arrangements: a string a_1a_2...a_n becomes the string b_1b_2...b_n, where b_i=1 if a_i\neq a_{i+1} and b_i=0 if a_i=a_{i+1}. Since we’re considering the strings to loop around, we have b_n=1 if a_n\neq a_1 and b_n=0 if a_n=a_0. As an example, the string 1000 becomes the string 1001.

Part I
1. What arrangements are created by starting with 1001 and transforming it one, two, three, and four times?
2. Show the first 4 transformations of 100.
3. Justify why 100 will never become all zeroes no matter how many transformations are applied.

Part II
4. Show that any arrangement of two bits becomes all zeroes within two transformations.
5. Let a_ia_{i+1}a_{i+2} be any three consecutive bits in an arrangement, which may have any number of other bits (these three may also wrap from the end of a string to the beginning). Show that transforming the arrangements twice gives a {}0 or 1 at position i depending on whether a_i and a_{i+2} are the same or different.
6. Use problem 5 to prove the following statement: if an arrangement with an even number of bits is transformed twice, then the result is the same if every other bit was treated as an arrangement and transformed once. That is: a_1a_2a_3a_4a_5a_6a_7a_8 going to b_1b_2b_3b_4b_5b_6b_7b_8 in two transformations is equivalent to a_1a_3a_5a_7 and a_2a_4a_6a_8 going to b_1b_3b_5b_7 and b_2b_4b_6b_8 in one transformation each, and similarly for other even-length arrangements.
7. Extend the idea of problems 5 and 6 by proving the following. Let a_1...a_{2^n} be an arrangement of length 2^n. Prove that after 2^k transformations, the value in position 1 depends only on whether a_1 and a_{2^k+1} were the same or different in the original arrangement for all k<n.
8. Prove that, for any positive integer k, any arrangement of 2^k bits becomes all zeros after 2^k transformations.
Part III
9. Justify why arrangements that are either all zeros or all ones are the only arrangements that give all zeros after one transformation.
10. Prove that one transformation on any arrangement of bits results in arrangement with an even number of ones.
11. Combine Problems 9 and 10 and prove that if an arrangement has an odd number of bits and is not all zeros and not all ones, then no number of transformations will result in all zeros.
12. Prove that if an arrangement has an even number of bits that is not a power of two, and exactly one bit is 1, then no number of transformations will result in an arrangement of all zeros.

[UPDATE] Somehow the post got clipped.. I’ve replaced the old material as close to my original wording as I remember

May 23, 2007 Posted by | Uncategorized | 2 Comments