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

- All Categories 2.4K
- Chat 502
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 73
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

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`