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

- All Categories 2.3K
- Chat 500
- Study Groups 19
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 67
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 713

Options

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

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.

`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.`

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|}\]

`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|}\\]`

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\).

`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\\).`

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.

`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.`

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.

`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.`

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.

`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.`

END-ARTICLE Tanzer.1

`END-ARTICLE Tanzer.1`