## Index

- First three properties of complexity
- Subcomplexities
- Ceiling of a subcomplexity
- Maximum of two subcomplexities. A truncated subcomplexity.
- Subcomplexity

## First three properties of complexity

Every Ł-string features character at least one time. It follows that for every natural number . On the other hand, since Ł-string represents , it follows that , hence:

\[ \mathit{rn}(1) = 1\]

That’s the **first** of the three properties. Now let be two arbitrary natural numbers; and let Ł-strings be such that:

- and ;
- and

Then Ł-string represents (has value) . 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 . 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 is called a subcomplexity satisfies the following three properties:

We can see from the First three properties that the complexity function is a subcomplexity. Furthermore, a simple induction on natural numbers shows that is the greatest subcomplexity, meaning that for every subcomplexity 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 be an arbitrary real number. Then the floor and the ceiling 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 . They have the following properties for every real and integer :

We will apply the latter property. Let be an arbitrary subcomplexity. Let be given by:

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

(one could write ). Then hence . Thus has the first property of subcomplexities.

Now let be two arbitrary natural numbers. Then

\[\gamma(a\ b\ +)\ \ \le\ \ \gamma(a) \gamma(b)\ +\ \ \le\ \ \delta(a)\ \delta(b)\ + \]

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

\[ \delta(a\ b\ +)\ \ \le\ \ \delta(a)\ \delta(b)\ + \]

Thus 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 be two arbitrary subcomplexities. Define their maximum in the usual way:

\[ \forall_{n\in\mathbb N}\quad \gamma(n)\ \ :=\ \ \max(\alpha(n)\ \ \beta(n)) \]

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

Let be an arbitrary subcomplexity. Let be an arbitrary positive real number. Define the truncated function as follows:

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

It is easy to prove that the truncated function is a subcomplexity–call it the *truncated subcomplexity*.

**POTENTIAL APPLICATION** Let be a subcomplexity, and let be such that for every . Then define as follows:

Then is a subcomplexity too–call it an *improved subcomplexity*.

## Subcomplexity

Let’s define function as follows:

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

First of all which means that function has the first subcomplexity property.

Now let be two arbitrary natural numbers. Then

which show that 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 then and , 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 . Next, if (so that ) then

\[ m_5(a\ b\ \bullet)\ =\ 4\ \ =\ \ m_5(a)\ m_5(b)\ + \]

Finally, let the remaining possibility hold: and . Then and 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 ** ** is a subcomplexity**.

**THEOREM 0** for every .

**PROOF** Indeed,

\[ k\ =\ m_5(k)\ \le\ \mathit{rn}(k)\ \le\ k \]

for every . **END of PROOF**