Complexity and subcomplexities, Part 2


Index



 

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

Leave a Reply

Your email address will not be published. Required fields are marked *