Options

A proof with labelled statements

The original version of the following proof can be found here

Puzzle 90. What's a \(\mathbf{Cost}^{\text{op}}\)-category, and what if anything are they good for?

The story doesn't look very good for them :(

Theorem. If \(\mathcal{X}\) is a \(\mathbf{Cost}^{\text{op}}\)-enriched category, then:

$$ \tag{a} \forall a,b. \mathcal{X}(a,b) = 0 \text{ or } \mathcal{X}(a,b) = \infty $$ Proof.

If every element \(\mathcal{X}(a,b) = 0\), we are done.

Next assume to the contrary. We must show that for an arbitrary \(a\) and \(b\) that \(\mathcal{X}(a,b) = \infty\).

So observe there must be some \(\hat{a}\) and \(\hat{b}\) such that \(\mathcal{X}(\hat{a},\hat{b}) > 0\).

It must be \(\mathcal{X}(\hat{a},\hat{b}) = \infty\). To see this, we know from the laws of enriched categories (part (b)) that:

$$ \tag{b} \begin{align} \mathcal{X}(\hat{a},\hat{b}) + \mathcal{X}(\hat{b},\hat{a}) & \leq \mathcal{X}(\hat{a},\hat{a}) \\ \implies \mathcal{X}(\hat{a},\hat{b}) & \leq \mathcal{X}(\hat{a},\hat{a}) \end{align} $$ However, then we have

$$ \tag{c} \begin{align} \mathcal{X}(\hat{a},\hat{b}) + \mathcal{X}(\hat{a},\hat{a}) & \leq \mathcal{X}(\hat{a},\hat{b}) \\ \implies 2 \mathcal{X}(\hat{a},\hat{b}) & \leq \mathcal{X}(\hat{a},\hat{b}) \end{align} $$ This can only happen if \(\mathcal{X}(\hat{a},\hat{b}) = \infty\) or \(\mathcal{X}(\hat{a},\hat{b}) = 0\). But we know \(\mathcal{X}(\hat{a},\hat{b}) > 0\) so it must be \(\mathcal{X}(\hat{a},\hat{b}) = \infty\) .

Next observe from the enriched category theory law (b) that:

$$ \tag{d} \mathcal{X}(a,\hat{a}) + \mathcal{X}(\hat{a},\hat{b}) \leq \mathcal{X}(a,\hat{b}) $$ So it must be that \(\mathcal{X}(a,\hat{b}) = \infty\). But then

$$ \tag{e} \mathcal{X}(a,\hat{b}) + \mathcal{X}(\hat{b},b) \leq \mathcal{X}(a,b) $$ Hence \(\mathcal{X}(a,b) = \infty\). \(\qquad \square \)

[Edit: Updated following Christopher's suggestion. Thanks Chris!]

Comments

  • 1.
    edited May 2018

    This example has some nice features.

    • The math statements are clearly centered and tagged with names.
    • Justification for the next for statement is provided with appropriate embedded math statements.
    • It uses the QED box
    • It provides an edit note indicating that it was updated based on a subsequent comment, there is a link provided to that comment.
    • It starts with a restatement of the problem
    • It indicates how to 'quote' someone else.

    Links to comments can be obtained via the 'gear' icon in the upper right corner of the comment.

    Comment Source:This example has some nice features. - The math statements are clearly centered and tagged with names. - Justification for the next for statement is provided with appropriate embedded math statements. - It uses the QED box - It provides an edit note indicating that it was updated based on a subsequent comment, there is a link provided to that comment. - It starts with a restatement of the problem - It indicates how to 'quote' someone else. Links to comments can be obtained via the 'gear' icon in the upper right corner of the comment.
Sign In or Register to comment.