Options

The opposite category and contravariant functors

edited February 7 in Drafts

Let's try to pin down the idea of the opposite category, which like "mirror image" of a catgory, obtained by systematically reversing "left" and "right" in the construction of a category. Where do left and right appear?

Consider a morphism \(f: A \rightarrow B\). We may view this as a relationship between \(A\) and \(B\), which object \(A\) on the left and object \(B\) on the right. In a mirror image category, we could have a twin morphism \(f'\), with the labelling reversed, so that the left object of \(f'\) is \(B\) and the right object is \(A\).

The standard names for 'left' and 'right' are 'domain' and 'codomain'.

The opposite of a category \(X\) has the same objects as \(X\), and its system of morphisms consists of all the twins \(f'\) for morphisms \(f\) in \(X\).

The reversal is stated by the following equations:

\[dom(f') = cod(f)\] \[cod(f') = dom(f)\]

Now suppose that \(f: A \rightarrow B\), \(g: B \rightarrow C\) in \(X\). This is a composable pair, and we may designate the composition by \(f \triangleright g\).

To distinguish composition in the opposite category \(X'\), let's use a different symbol for the composition operator.

For morphisms \(u, v\) in \(X'\), we'll write \(u \triangleleft v\) for their composition in \(X'\).

Having established notation, let's turn our attention back to our composable pair \(f \triangleright g\) in \(X\).

The question naturally arises: how can we form a composable pair from \(f'\) and \(g'\) in the opposite category \(X'\)?

First let's try \(f' \triangleleft g'\). For that to work, as always, in any category, we would require that \(cod(f') = dom(g')\).

But \(cod(f') = dom(f)\), which is not equal to \(dom(g') = cod(f)\). Bzzt.

The only other choice for the composable pair is \(g' \triangleleft f'\), and this works well. Indeed, we have that \(cod(g') = dom(f')\), which follows from that \(cod(f) = dom(g)\).

In a word:

\[g' \triangleleft f' = (f \triangleright g)'\]

These three equations define the transformation of a category \(X\) into its opposite category \(X'\).

Comments

  • 1.
    edited February 14

    Hi Jim, in light of your question, I revised my recommendation above. The main ideas are to clearly mark the starting and ending comments of the article, and to choose an identifier for referring to it.

    Comment Source:Hi Jim, in light of your question, I revised my recommendation above. The main ideas are to clearly mark the starting and ending comments of the article, and to choose an identifier for referring to it.
  • 2.
    edited February 14

    ARTICLE Tanzer.1 - The power set and its exponential notation

    For a set \(S\), the power set \(2^S\) refers to the collection of all subsets of \(S\).

    How big is \(2^S\)? Not surprisingly, if \(S\) has \(n\) elements, the power set has \(2^n\) elements:

    \[|2^S| = 2^{|S|}\]

    Comment Source:ARTICLE Tanzer.1 - The power set and its exponential notation For a set \\(S\\), the power set \\(2^S\\) refers to the collection of all subsets of \\(S\\). How big is \\(2^S\\)? Not surprisingly, if \\(S\\) has \\(n\\) elements, the power set has \\(2^n\\) elements: \\[|2^S| = 2^{|S|}\\]
  • 3.
    edited February 14

    There are a couple of ways to see why this holds.

    Suppose \(S\) has \(n\) elements \(x_1, \ldots, x_n\). Let \(A\) be a subset of \(S\). Then \(A\) can be represented by a vector of \(n\) bits, where the kth bit is 1 if \(x_k\) belongs to \(A\), or 0 otherwise.

    So each subset \(A\) is represented by a unique n-digit sequence in base 2.

    Since there are \(2^n\) such sequences, it follows that power set has size \(2^n\).

    Comment Source:There are a couple of ways to see why this holds. Suppose \\(S\\) has \\(n\\) elements \\(x_1, \ldots, x_n\\). Let \\(A\\) be a subset of \\(S\\). Then \\(A\\) can be represented by a vector of \\(n\\) bits, where the kth bit is 1 if \\(x_k\\) belongs to \\(A\\), or 0 otherwise. So each subset \\(A\\) is represented by a unique n-digit sequence in base 2. Since there are \\(2^n\\) such sequences, it follows that power set has size \\(2^n\\).
  • 4.
    edited February 14

    Another proof is by induction on n.

    The base case is for n = 0. That means S = {}. So what must be shown here is that:

    \[|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \]

    Well \(2^{\lbrace \rbrace}\) is the set of subsets of the empty set, which just contains one member -- the empty set. So the left hand side of this equation is 1.

    On the right hand side, since \(|\lbrace \rbrace|\) equals 0, we also get the value 1.

    Comment Source:Another proof is by induction on n. The base case is for n = 0. That means S = {}. So what must be shown here is that: \\[|2^{\lbrace \rbrace}| = 2^{|\lbrace \rbrace|} \\] Well \\(2^{\lbrace \rbrace\}\\) is the set of subsets of the empty set, which just contains one member -- the empty set. So the left hand side of this equation is 1. On the right hand side, since \\(|\lbrace \rbrace|\\) equals 0, we also get the value 1.
  • 5.
    edited February 14

    For the induction step, suppose the claim is true for all values of k less than n. That's the induction hypothesis.

    Let S be a set of size n. Now we'll show that the induction hypothesis implies that the claim is true for S as well.

    Write \(S = x_1, \ldots, x_n\).

    Now let \(T_1\) be all the subsets of \(S\) that contain \(x_n\), and \(T_0\) be all the subsets that don't contain \(x_n\).

    Together, \(T_0\) and \(T_1\) give a partition of \(2^S\).

    So the size of \(2^S\) will be obtained by summing the sizes of \(T_0\) and \(T_1\).

    Now, it's easy to see that \(T_0\) and \(T_1\) have the same size. That's because every subset \(A\) of \(S\) that contains \(x_n\) can uniquely paired with a subset \(A'\) of \(S\) that doesn't contain \(x_n\). To get from \(A\) to \(A'\), you just have to remove \(x_n\).

    Since they have equal size, the size of \(2^S\) is double the size of \(T_0\).

    Now let \(S' = S - \lbrace x_n \rbrace\) be the set obtained by removing \(x_n\) from \(S\).

    As we said, \(T_0\) is all subsets of \(S\) that don't contain \(x_n\).

    Which means that \(T_0\) is the same thing as the power set of \(S'\).

    By the induction hypothesis, the size of the power set of \(S'\) is \(2^{n-1}\).

    Putting this all together, we get:

    \[|S| = 2 * |T_0| = 2 * |2^{S'}| = 2 * 2^{n-1} = 2^n\]

    That completes the proof.

    Comment Source:For the induction step, suppose the claim is true for all values of k less than n. That's the induction hypothesis. Let S be a set of size n. Now we'll show that the induction hypothesis implies that the claim is true for S as well. Write \\(S = x_1, \ldots, x_n\\). Now let \\(T_1\\) be all the subsets of \\(S\\) that contain \\(x_n\\), and \\(T_0\\) be all the subsets that don't contain \\(x_n\\). Together, \\(T_0\\) and \\(T_1\\) give a partition of \\(2^S\\). So the size of \\(2^S\\) will be obtained by summing the sizes of \\(T_0\\) and \\(T_1\\). Now, it's easy to see that \\(T_0\\) and \\(T_1\\) have the same size. That's because every subset \\(A\\) of \\(S\\) that contains \\(x_n\\) can uniquely paired with a subset \\(A'\\) of \\(S\\) that doesn't contain \\(x_n\\). To get from \\(A\\) to \\(A'\\), you just have to remove \\(x_n\\). Since they have equal size, the size of \\(2^S\\) is double the size of \\(T_0\\). Now let \\(S' = S - \lbrace x_n \rbrace\\) be the set obtained by removing \\(x_n\\) from \\(S\\). As we said, \\(T_0\\) is all subsets of \\(S\\) that don't contain \\(x_n\\). Which means that \\(T_0\\) is the same thing as the power set of \\(S'\\). By the induction hypothesis, the size of the power set of \\(S'\\) is \\(2^{n-1}\\). Putting this all together, we get: \\[|S| = 2 * |T_0| = 2 * |2^{S'}| = 2 * 2^{n-1} = 2^n\\] That completes the proof.
  • 6.
    edited February 14

    The notation \(2^S\) is also consistent with the more general exponential notation \(B^A\) for sets \(A\), \(B\). The expression \(B^A\) denotes the set of all functions from A to B.

    So according to that, \(2^S\) would be these set of all functions from \(S\) into 2. Here, we'll take '2' to be a name for two-element set {0,1}.

    What's a function from \(S\) into {0,1}? It can be viewed as a predicate, which assigns true or false to every member of S.

    And that's equivalent to a subset of S -- the subset of all values in S that map to 1.

    So, as a set of functions, \(2^S\) is equivalent to \(2^S\) as a set of subsets.

    Comment Source:The notation \\(2^S\\) is also consistent with the more general exponential notation \\(B^A\\) for sets \\(A\\), \\(B\\). The expression \\(B^A\\) denotes the set of all functions from A to B. So according to that, \\(2^S\\) would be these set of all functions from \\(S\\) into 2. Here, we'll take '2' to be a name for two-element set {0,1}. What's a function from \\(S\\) into {0,1}? It can be viewed as a predicate, which assigns true or false to every member of S. And that's equivalent to a subset of S -- the subset of all values in S that map to 1. So, as a set of functions, \\(2^S\\) is equivalent to \\(2^S\\) as a set of subsets.
  • 7.
    edited February 14

    END-ARTICLE Tanzer.1

    Comment Source:END-ARTICLE Tanzer.1
Sign In or Register to comment.