#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

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'$$.

• Options
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.
• Options
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|}\$ 
• Options
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\$$. 
• Options
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. 
• Options
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. 
• Options
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. 
• Options
7.
edited February 14

END-ARTICLE Tanzer.1

Comment Source:END-ARTICLE Tanzer.1