# Complexity and subcomplexities, Part 2

## First three properties of complexity   $\mathit{rn}$

Every Ł-string features character $1$ at least one time. It follows that   $\mathit{rn}(n)\ge 1$   for every natural number   $n=1\ 2\ \ldots$. On the other hand, since Ł-string   $''1''$   represents   $1$,   it follows that   $\mathit{rn}(1) \le 1$,   hence:
$\mathit{rn}(1) = 1$

That’s the first of the three properties. Now let   $a\ b\in\mathbb N$   be two arbitrary natural numbers; and let Ł-strings   $''A''\ \ ''B''$   be such that:

• $\mathit{val}(''A'') = a$     and     $\mathit{val}(''B'') = b$;
• $\mathit{rn}(a) = \mathit{RN}(''A'')$     and     $\mathit{rn}(b) = \mathit{RN}(''B'')$

Then Ł-string   $''AB+''$   represents (has value)   $a\ b\ +$.   It follows that:
$\mathit{rn}(a\ b\ +)\ \ \le\ \ \mathit{RN}(”AB+”)\ \ =\ \ \mathit{RN}(”A”)\ \mathit{RN}(”B”)\ +$

$=\ \ \mathit{rn}(a)\ \mathit{rn}(b)\ +$

We see that

$\forall_{a\ b\ \in\ \mathbb N}\quad \mathit{rn}(a\ b\ +)\quad\le\quad \mathit{rn}(a)\ \mathit{rn}(b)\ +$

and this is the second property of complexity   $\mathit{rn}$.   A very similar proof justifies also the third property:

$\forall_{a\ b\ \in\ \mathbb N}\quad \mathit{rn}(a\ b\ \bullet)\quad\le\quad \mathit{rn}(a)\ \mathit{rn}(b)\ +$

## Subcomplexities

DEFINITION 0   A real positive function   $\gamma : \mathbb N \rightarrow (0;\infty)$   is called a subcomplexity   $\Leftarrow:\Rightarrow$   $\gamma$   satisfies the following three properties:

1. $\gamma(1)\le 1$
2. $\forall_{a\ b\ \in\ \mathbb N}\quad \gamma(a\ b\ +)\ \le\ \gamma(a)\ \gamma(b)\ +$
3. $\forall_{a\ b\ \in\ \mathbb N}\quad \gamma(a\ b\ \bullet)\ \le\ \gamma(a)\ \gamma(b)\ +$

We can see from the First three properties that the complexity function   $\mathit{rn}$   is a subcomplexity. Furthermore, a simple induction on natural numbers shows that   $\mathit{rn}$   is the greatest subcomplexity, meaning that for every subcomplexity   $\gamma$   the following inequality holds:

$\forall_{n\in\mathbb N}\ \ \gamma(n)\le\mathit{rn}(n)$

## Ceiling of a subcomplexity

We will see that the ceiling of a subcompolexity is a subcomplexity.

Let   $t\in\mathbb R$   be an arbitrary real number. Then the floor   $\lfloor t\rfloor$   and the ceiling   $\lceil t\rceil$   are defined as the integers which satisfy inequalities:
$t-1\ <\ \lfloor t\rfloor\ \le t$ $t\ \le\ \lceil t\rceil\ <\ t+1$ Such integers are unique for every real   $t$.   They have the following properties for every real   $t$   and integer   $n$:

• $t\ge n\qquad\Rightarrow\qquad \lfloor t\rfloor \ge n$
• $t \le n\qquad\Rightarrow\qquad \lceil t\rceil \le n$

We will apply the latter property. Let   $\gamma$   be an arbitrary subcomplexity. Let   $\delta :\mathbb N\rightarrow (0;\infty)$   be given by:

$\forall_{n\in\mathbb N}\quad \delta(n) := \lceil \gamma(n)\rceil$

(one could write   $\delta := \lceil\gamma\rceil$).   Then   $0 < \gamma(1)\le 1$   hence   $\delta(1) = 1$.   Thus   $\delta$   has the first property of subcomplexities.

Now let   $a\ b\in\mathbb N$   be two arbitrary natural numbers. Then

$\gamma(a\ b\ +)\ \ \le\ \ \gamma(a) \gamma(b)\ +\ \ \le\ \ \delta(a)\ \delta(b)\ +$

The $\delta$-expression on the right is an integer. Thus, by the definition of   $\delta$,   and by the general property of the operation ceiling (see above), we get:

$\delta(a\ b\ +)\ \ \le\ \ \delta(a)\ \delta(b)\ +$

Thus   $\delta$   has the second property of a su8bcomplexity. A proof of the third property:

$\delta(a\ b\ \bullet)\ \ \le\ \ \delta(a)\ \delta(b)\ +$

is very similar.

## Maximum of two subcomplexities. A truncated subcomplexity.

Let   $\alpha\ \beta : \mathbb N\rightarrow (0;\infty)$   be two arbitrary subcomplexities. Define their maximum   $\gamma : \mathbb N\rightarrow (0;\infty)$   in the usual way:
$\forall_{n\in\mathbb N}\quad \gamma(n)\ \ :=\ \ \max(\alpha(n)\ \ \beta(n))$

Then, as it is easy to prove,   $\gamma$   is a subcomplexity too.

Let   $\gamma:\mathbb N\rightarrow (0;\infty)$   be an arbitrary subcomplexity. Let   $M\in (0;\infty)$   be an arbitrary positive real number. Define the truncated function   $\gamma_M$   as follows:

$\forall_{n\in\mathbb N}\quad \gamma_M(n)\ \ :=\ \ \min(\gamma(n)\ \ M)$

It is easy to prove that the truncated function   $\gamma_M$   is a subcomplexity–call it the truncated subcomplexity.

POTENTIAL APPLICATION   Let   $\gamma$   be a subcomplexity, and let   $M\in\mathbb N$   be such that   $\gamma(k) = \mathit{rn}(k)$   for every   $k=1\ldots M$.   Then define   $\delta:\mathbb N\rightarrow (0;\infty)$   as follows:

• $\forall_{k\in\mathbb N\setminus\{M\}}\quad \delta(k)\ :=\ \gamma(k)$
• $\delta(M)\ :=\ \mathit{zn}(M)$

Then   $\delta$   is a subcomplexity too–call it an improved subcomplexity.

## Subcomplexity   $m_5$

Let’s define function   $m_5:\mathbb N\rightarrow (0;\infty)$   as follows:

$\forall_{k\in\mathbb N}\quad m_5(k)\ \ :=\ \ \min(k\ \ 5)$

First of all   $m_5(1)=1$   which means that function   $m_5$   has the first subcomplexity property.

Now let   $a\ b\in\mathbb N$   be two arbitrary natural numbers. Then

• $\max(a\ b)\le 5\qquad\Rightarrow\qquad m_5(a\ b\ +)\ \ \le\ \ a\ b\ +\ \ =\ \ m_5(a)\ m_5(b)\ +$
• $\max(a\ b)\ge 5\qquad\Rightarrow\qquad m_5(a\ b\ +)\ \ \le\ \ 5\ \ \le\ \ m_5(a)\ m_5(b)\ +$

which show that   $m_5$   has the second property of a subcomplexity:

$\forall_{a\ b\in \mathbb N}\quad m_5(a\ b\ +)\ \ \le\ \ m_5(a)\ m_5(b)\ +$

Furthermore, if   $\min(a\ b) = 1$   then   $a\ b\ \bullet\ =\ \max(a\ b)$   and   $\{1\ \max(a\ b)\}\ =\ \{a\ b\}$,   hence

$\min(a\ b) = 1\quad\Rightarrow\quad m_5(a\ b\ \bullet)\ =\ \ m_5(\max(a\ b))$
$<\ \ \ 1\ \ m_5(\max(a\ b))\ \ +\ \ \ =\ \ \ m_5(a)\ m_5(b)\ +$ -- i.e. the third subcomplexity property holds when   $\min(a\ b) = 1$.   Next, if     $\min(a\ b) = \max(a\ b) = 2$   (so that   $a=b=2$)   then
$m_5(a\ b\ \bullet)\ =\ 4\ \ =\ \ m_5(a)\ m_5(b)\ +$

Finally, let the remaining possibility hold:   $\min(a\ b)\ \ge 2$   and   $\max(a\ b) \ge 3$.   Then   $m_5(\min(a\ b))\ \ge\ 2$   and   $m_5(\max(a\ b))\ \ge\ 3$   hence

$m_5(a\ b\ \bullet)\ \ \ \le\ \ \ 5\ \ \ \le\ \ \ m_5(\min(a\ b))\ \ m_5(\max(a\ b))\ \ +$

$=\ \ \ m_5(a)\ m_5(b)\ +$

We see that the third subcomplexity property holds in every case, i.e.

$\forall_{a\ b\in \mathbb N}\quad m_5(a\ b\ \bullet)\ \ \le\ \ m_5(a)\ m_5(b)\ +$

We have proven that function   $m_5$   is a subcomplexity.

THEOREM 0   $\mathit{rn}(k)=k$   for every   $k=1\ldots 5$.

PROOF   Indeed,

$k\ =\ m_5(k)\ \le\ \mathit{rn}(k)\ \le\ k$

for every   $k=1\ldots 5$.   END of PROOF