Options

# Exercise 11 - Chapter 3

edited June 2018

Let’s make some definitions, based on the pattern in the previous exercise:

1) What is the category 1? That is, what are its objects and morphisms?

2) What is the category 0?

3) What is the formula for the number of morphisms in n for arbitrary $$n \in \mathbb{N}$$ ?

• Options
1.
edited May 2018

The Category $$\mathbf{1}$$ has one object 0, and one arrow $$id_0)$$.

Comment Source: The Category \$$\mathbf{1}\$$ has one object 0, and one arrow \$$id_0)\$$. 
• Options
2.
edited May 2018

2) 0 is the category with no objects or morphisms (i.e., both sets are $$\emptyset$$.

3) Claim: There are $$\frac{n(n+1)}{2}$$ morphisms in n for all $$n\in\mathbb{N}$$. Proof: For every two objects, say $$p>q$$, in n there is exactly one one morphism, that obtained from the compositions $$f_{p-1}\circ f_{p-2}\circ\cdots\circ f_{q+1}\circ f_q$$. By definition of n, these constitute all of the non-identity morphisms in n. So, there are $$\binom{n}{2}=\frac{n(n-1)}{2}$$ non-identity morphisms and $$n$$ identity morphisms, for a total of $$\frac{n(n+1)}{2}$$ morphisms.

Comment Source:2) **0** is the category with no objects or morphisms (i.e., both sets are \$$\emptyset\$$. 3) Claim: There are \$$\frac{n(n+1)}{2}\$$ morphisms in **n** for all \$$n\in\mathbb{N}\$$. Proof: For every two objects, say \$$p>q\$$, in **n** there is exactly one one morphism, that obtained from the compositions \$$f_{p-1}\circ f_{p-2}\circ\cdots\circ f_{q+1}\circ f_q\$$. By definition of **n**, these constitute all of the non-identity morphisms in **n**. So, there are \$$\binom{n}{2}=\frac{n(n-1)}{2}\$$ non-identity morphisms and \$$n\$$ identity morphisms, for a total of \$$\frac{n(n+1)}{2}\$$ morphisms.
• Options
3.
edited May 2018

3) The recursive function is $$f(n)= \begin{cases} 0, & \text{if x \le 0}.\\\\ f(n-1) + n, & \text{otherwise}. \end{cases}$$ The new element has a morphism to each of its predecessors $$n - 1$$ and one to itself. Which is equivalent to $$f(n) = \frac{n(n+1)}{2} = \frac{[n-1]([n-1]+1)}{2} + n$$

Comment Source:3) The recursive function is $f(n)= \begin{cases} 0, & \text{if x \le 0}.\\\\ f(n-1) + n, & \text{otherwise}. \end{cases}$ The new element has a morphism to each of its predecessors \$$n - 1\$$ and one to itself. Which is [equivalent to](https://forum.azimuthproject.org/discussion/comment/18665/#Comment_18665) $f(n) = \frac{n(n+1)}{2} = \frac{[n-1]([n-1]+1)}{2} + n$