About One Groupoid Associated with the Composition of Multilayer Feedforward Neural Networks

1. Введение

В данной работе рассматриваются только многослойные нейронные сети с прямым распределением сигнала (далее, просто сети, нейросети или нейронные сети). Информацию о нейронных сетях и их структурах (архитектурах) можно найти в [1-4]. Работа направлена на построение группоидов, позволяющих моделировать композицию многослойных нейронных сетей.

В работах [5-6] изучались коммутативные (но в общем случае не ассоциативные) группоиды $\text{AGS}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$, элементы которых тесно связаны с подсетями нейронной сети $\mathcal{N}$. Изучались эндоморфизмы (см. теорема 2 из [5] и теорема 1 из [6]) этих группоидов и их подгруппоиды (см. теорема 1 из [5]). Определение 2.1, которое формализует понятие нейронной сети в данной работе, строится на основании определения нейронной сети из работ [5-6]. Нейронная сеть в смысле данного определения является математическим объектом: кортежем, элементы которого определяют структуру (по другому архитектуру или внутреннее устройство) нейронной сети.

Другим подходом к математической формализации понятия нейронной сети является понятие абстрактной нейронной сети, построенное в работе [7]. Такой подход имеет свои достоинства и близок к подходу, использующемуся в теории абстрактных автоматов ([8]). Представление нейронной сети в виде конкретного абстрактного автомата, который при этом не является конструкцией, построенной с помощью других абстрактных автоматов, не дает возможности изучать или принимать во внимание архитектуру нейронной сети. Данное обстоятельство является хорошо известным и отмечалось В. М. Глушковым в обзоре [8] для любых конкретных автоматов, представляемых в виде абстрактных автоматов.

 Основные результаты. В работе строится полный группоид композиции многослойных нейронных сетей (см. определение 2.2). Основным результатом работы является Теорема 5.1, которая показывает, что полный группоид композиции является свободным группоидом. Найдена система свободных образующих группоида построенного группоида (см. теорема 5.1, лемму 5.2 и предложение 5.3). Свойство группоида быть свободным достаточно полно характеризует его алгебраические свойства. В частности, можно считать известным моноид всех эндоморфизмов такого группоида.

Результаты работы будут полезны для разработки методов исследования нейронных сетей с помощью алгебраических объектов. Другим подходом исследований в этом направлении является моделирование композиции с помощью частичных группоидов (результаты авторов по этому направлению в настоящее время готовятся к отправке в журнал).

2. Основные определения и обозначения

Всюду далее $ℝ$ $–$ множество действительных чисел; $\mathbb{N}$ $–$ множество натуральных чисел и $F\mathrm{<mo\; stretchy="false">(</mo>}ℝ\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}Hom\mathrm{<mo\; stretchy="false">(</mo>}ℝ\mathrm{,}ℝ\mathrm{<mo\; stretchy="false">)</mo>}$ $–$ множество всех отображений множества $ℝ$ в множество $ℝ$. Сформулируем определение многослойной нейронной сети. Как обычно, мощность множества $X$ обозначим через $\mathrm{<mo>|</mo>}X\mathrm{<mo>|</mo>}$.

Определение 2.1. Пусть заданы следующие объекты:

1) кортеж $\mathrm{<mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{<mo\; stretchy="false">)</mo>}$ длины $n\ge 1$ конечных непустых множеств, где при $i\ne j$ справедливо условие $M_i\cap M_j\mathrm{<mo>=</mo>}\varnothing$;

2) множество $S\mathrm{<mo>:</mo><mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\times M_2\mathrm{<mo\; stretchy="false">)</mo>}\cup \mathrm{<mo\; stretchy="false">(</mo>}{M}_2\times M_3\mathrm{<mo\; stretchy="false">)</mo>}\cup \mathrm{...}\cup \mathrm{<mo\; stretchy="false">(</mo>}{M}_{n-1}\times M_n\mathrm{<mo\; stretchy="false">)</mo>}$;

3) отображение $f\mathrm{<mo>:</mo>}S\to ℝ$;

4) множество $A\mathrm{<mo>:</mo><mo>=</mo>}{M}_1\cup \mathrm{...}\cup M_n$;

5) отображение $g\mathrm{<mo>:</mo>}A\to F\mathrm{<mo\; stretchy="false">(</mo>}ℝ\mathrm{<mo\; stretchy="false">)</mo>}$;

6) отображение $l\mathrm{<mo>:</mo>}A\to ℝ$;

7) биективное отображение $i\mathrm{<mo>:</mo>}{M}_1\to \mathrm{<mo>\{</mo>1,2,...,<mo>|</mo>}{M}_1\mathrm{<mo>|</mo><mo>\}</mo>}$;

8) биективное отображение $o\mathrm{<mo>:</mo>}{M}_n\to \mathrm{<mo>\{</mo>1,2,...,<mo>|</mo>}{M}_n\mathrm{<mo>|</mo><mo>\}</mo>}$.

Тогда кортеж $\mathcal{N}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l\mathrm{<mo\; stretchy="false">)</mo>}$ будем называть многослойной нейронной сетью прямого распределения.

Отображение $f$ задает веса синаптических связей, отображение $g$ определяет функции активации у каждого нейрона, $l$ определяет пороговые значения нейронов (подробную информацию о перечисленных структурных единицах можно найти, например, в [5]). Совокупность нейронов $M_1$ будем называть входным слоем, а $M_n$ $–$ выходным слоем. Отображения $i$ и $o$ задают упорядочение входного и выходного слоя. Отображения $i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l$ будем называть структурными отображениями нейронной сети $\mathcal{N}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l\mathrm{<mo\; stretchy="false">)</mo>}$, поскольку они определяют структуру сети $\mathcal{N}$. Количество слоев в сети $\mathcal{N}$ будем обозначать через $n\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$.

Приведенное определение построено на основе определения 1 из [5], в котором отсутствовали пункты 7) и 8). Последнее объясняется тем, что в работе [5] изучались подсети нейронной сети и не было необходимости рассматривать пункты 7) и 8), которые отвечают за упорядочение входного и выходного слоя нейронов. Последнее необходимо в контексте передачи выходного сигнала первой сети на вход второй сети. Кроме того, определение 1 разрешает однослойные нейронные сети (в отличии от определения 1 из [5]).

Для каждого целого $n\ge 0$ и непустого множества $P$ введем следующие обозначения:

                          $D_0\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}P\mathrm{,}{D}_n\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo><mo>\{</mo><mo\; stretchy="false">(</mo>}d\mathrm{,}i\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>|</mo>}d\in D_{n-1}\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo>,}i\in \mathrm{<mo>\{</mo>1,2<mo>\}</mo><mo>\}</mo>}\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo>></mo>0<mo\; stretchy="false">)</mo>.}$

В частности, выполняются равенства

                                                       $D_1\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo>\{</mo><mo\; stretchy="false">(</mo>}p\mathrm{,}i\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>|</mo>}p\in P\mathrm{,}i\in \mathrm{<mo>\{</mo>1,2<mo>\}</mo><mo>\}</mo>,}$

                         $D_n\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo>\{</mo><mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>...<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}p\mathrm{,}{i}_1\mathrm{<mo\; stretchy="false">)</mo>,}{i}_2\mathrm{<mo\; stretchy="false">)</mo>,...<mo\; stretchy="false">)</mo>,}{i}_{n-1}\mathrm{<mo\; stretchy="false">)</mo>,}{i}_n\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>|</mo>}p\in P\mathrm{<mo>;</mo>}{i}_1\mathrm{,}{i}_2\mathrm{,....,}{i}_n\in \mathrm{<mo>\{</mo>1,2<mo>\}</mo><mo>\}</mo>.}$

Определение 2.2. Для любого множества $Q\ne \varnothing$ через $\text{SN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}Q\mathrm{<mo\; stretchy="false">)</mo>}$ обозначим множество всевозможных нейронных сетей, таких что нейронная сеть из $\text{SN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}Q\mathrm{<mo\; stretchy="false">)</mo>}$ имеет ровно $k$ входов и ровно $k$ выходов, а ее нейроны являются элементами множества $Q$. Пусть $P\ne \varnothing$ $–$ множество свободное от специальных кортежей. Тогда введем множество нейронных сетей

                                                  $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}\text{SN}\left(k\mathrm{,}P\cup \left({\displaystyle \underset{s\in \mathbb{N}}{\cup }}{D}_s\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo>}\right)\right)\mathrm{,}$

где объединение берется по всем натуральным $s$.

Всюду далее $P$ $–$ это множество свободное от кортежей, содержащих компоненты, равные числам $1$ или $2$ (или просто множество, свободное от специальных кортежей). Обозначение $\text{SAN}$ возникает как аббревиатура Set of All Networks. В следующем разделе на множестве $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ будет введена бинарная алгебраическая операция (см. определение 4.1).

Две сети ${\mathcal{N}}_1\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l\mathrm{<mo\; stretchy="false">)</mo>}$ и ${\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{,...,}{M^{\prime }}_d\mathrm{,}{i}^{\prime }\mathrm{,}{o}^{\prime }\mathrm{,}{f}^{\prime }\mathrm{,}{g}^{\prime }\mathrm{,}{l}^{\prime }\mathrm{<mo\; stretchy="false">)</mo>}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ считаем равными, когда они равны как кортежи. Ясно, что ${\mathcal{N}}_1\mathrm{<mo>=</mo>}{\mathcal{N}}_2$ тогда и только тогда, когда выполняются равенства

             $n\mathrm{<mo>=</mo>}d\mathrm{,}{M}_1\mathrm{<mo>=</mo>}{M^{\prime }}_1\mathrm{,}{M}_2\mathrm{<mo>=</mo>}{M^{\prime }}_2\mathrm{,...,}{M}_n\mathrm{<mo>=</mo>}{M^{\prime }}_d\mathrm{,}i\mathrm{<mo>=</mo>}{i}^{\prime }\mathrm{,}o\mathrm{<mo>=</mo>}{o}^{\prime }\mathrm{,}f\mathrm{<mo>=</mo>}{f}^{\prime }\mathrm{,}g\mathrm{<mo>=</mo>}{g}^{\prime }\mathrm{,}l\mathrm{<mo>=</mo>}{l}^{\prime }\mathrm{,}$

где под равенством отображений понимается поточечное равенство.

3. Описание основных результатов

Каждой нейронной сети $\mathcal{N}\in \text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ будет соответствовать отображение $F_{\mathcal{N}}\mathrm{<mo>:</mo>}{ℝ}^k\to {ℝ}^k$, которое реализует действие нейронной сети $\mathcal{N}$ на входных сигналах $\overline{x}\mathrm{<mi>\; </mi>}\text{}\text{}\mathrm{<mo>=</mo><mi>\; </mi>}\text{}\text{}\mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{,...,}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}$ из ${ℝ}^k$. Отображение $F_{\mathcal{N}}$ определяется стандартным способом с помощью модели искусственного нейрона Мак-Каллока $–$ Питтса, (подробную информацию об этом можно найти, например, в [1] или [2]).

На множестве $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ вводится бинарная алгебраическая операция $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ (см. определение 4.1), которая любым двум сетям ${\mathcal{N}}_1$ и ${\mathcal{N}}_2$ ставит в соответствие нейронную сеть ${\mathcal{N}}_1\odot {\mathcal{N}}_2$, такую что на любом входном сигнале $\overline{x}\in {ℝ}^k$ имеет место равенство

                                                                $F_{{\mathcal{N}}_1\odot {\mathcal{N}}_2}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{{\mathcal{N}}_2}\mathrm{<mo\; stretchy="false">(</mo>}{F}_{{\mathcal{N}}_1}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$  (3.1)

 (см. утверждение 4.1). Поэтому нейронная сеть ${\mathcal{N}}_1\odot {\mathcal{N}}_2$ действует на множестве входных сигналов ${ℝ}^k$ как последовательное применение сетей ${\mathcal{N}}_1$ и потом ${\mathcal{N}}_2$. Такой подход, с точки зрения теории абстрактных автоматов, можно интерпретировать, как подачу выходных сигналов первого автомата на вход второго автомата (см., например, определение 25 [8, с. 54]). Операция $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ некоммутативна и неассоциативна (следует из теоремы 5.1).

Нейронная сеть $\mathcal{T}\mathrm{<mo>:</mo><mo>=</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2$ содержит в себе информацию о структуре нейронных сетей ${\mathcal{N}}_1$ и ${\mathcal{N}}_2$. Однако при этом сеть $\mathcal{T}$ не содержит нейронов, входящих в сети ${\mathcal{N}}_1$ и ${\mathcal{N}}_2$. Вместо них нейронами сети $\mathcal{T}$ выступают кортежи $\mathrm{<mo\; stretchy="false">(</mo>}{n}_1\mathrm{,1<mo\; stretchy="false">)</mo>}$ и $\mathrm{<mo\; stretchy="false">(</mo>}{n}_2\mathrm{,2<mo\; stretchy="false">)</mo>}$, где $n_1$ $–$ нейрон сети ${\mathcal{N}}_1$ и $n_2$ $–$ нейрон сети ${\mathcal{N}}_2$. Данный прием необходим для корректного определения сети $\mathcal{T}$ как математического объекта, введенного определением 2.1 (подробнее см. замечание 4.1). Группоид $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ строился так, чтобы для любых двух сетей ${\mathcal{N}}_1$ и ${\mathcal{N}}_2$, принадлежащих ему, выполнялось соотношение (3.1) (это позволяет использовать его для моделирования композиций сетей). Свойство группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ быть свободным не обеспечивалось специально.

4. Построение группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ 

В данном разделе строится группоид $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>,}\odot \mathrm{<mo\; stretchy="false">)</mo>}$, в котором ${\mathcal{N}}_1\odot {\mathcal{N}}_2$ будет являться сетью из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$, полученной в соответствие с принципом композиции нейронных сетей. Введем объекты, которые необходимы для формулировки группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Как правило, $X\times Y$ $–$ декартово произведение множеств. Для всякого множества $X$ и каждого $i\in \mathrm{<mo>\{</mo>1,2<mo>\}</mo>}$ определим множество $L_i\mathrm{<mo\; stretchy="false">(</mo>}X\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}X\times \mathrm{<mo>\{</mo>}i\mathrm{<mo>\}</mo>}$.

Каждой паре сетей

                      ${\mathcal{N}}_1\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}{i}_1\mathrm{,}{o}_1\mathrm{,}{f}_1\mathrm{,}{g}_1\mathrm{,}{l}_1\mathrm{<mo\; stretchy="false">)</mo>,}{\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{,...,}{M^{\prime }}_d\mathrm{,}{i}_2\mathrm{,}{o}_2\mathrm{,}{f}_2\mathrm{,}{g}_2\mathrm{,}{l}_2\mathrm{<mo\; stretchy="false">)</mo>}$

из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ сопоставим множества

                     $A\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}{\displaystyle \underset{i\mathrm{<mo>=</mo>2}}{\overset{n}{\cup }}}\mathrm{<mo\; stretchy="false">(</mo>}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_{i-1}\mathrm{<mo\; stretchy="false">)</mo>}\times L_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_i\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>;</mo>}B\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}{\displaystyle \underset{i\mathrm{<mo>=</mo>2}}{\overset{d}{\cup }}}\mathrm{<mo\; stretchy="false">(</mo>}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_{i-1}\mathrm{<mo\; stretchy="false">)</mo>}\times L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_i\mathrm{<mo\; stretchy="false">)</mo><mo>;</mo>}$

                                     $S\mathrm{<mo\; stretchy="false">[</mo>}{\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">]</mo><mo>:</mo><mo>=</mo>}A\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo>}\cup \left(L_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>}\times L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>}\right)\cup B\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo>.}$

Пусть $h_1\mathrm{<mo>:</mo>}{X}_1\to Y_1$ и $h_2\mathrm{<mo>:</mo>}{X}_2\to Y_2$ $–$ два отображения. Тогда через $\mathrm{<mo\; stretchy="false">[</mo>}{h}_1\mathrm{,}{h}_2\mathrm{<mo\; stretchy="false">]</mo>}$ будем обозначать отображение множества $L_1\mathrm{<mo\; stretchy="false">(</mo>}{X}_1\mathrm{<mo\; stretchy="false">)</mo>}\cup L_2\mathrm{<mo\; stretchy="false">(</mo>}{X}_2\mathrm{<mo\; stretchy="false">)</mo>}$ в множество $Y_1\cup Y_2$, которое для любого $x_1\in X_1$ и $x_2\in X_2$ действует по правилу:

                                        $\mathrm{<mo\; stretchy="false">[</mo>}{h}_1\mathrm{,}{h}_2\mathrm{<mo\; stretchy="false">]</mo><mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}{x}_1\mathrm{,1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}{h}_1\mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo><mo>;</mo>}\mathrm{<mo\; stretchy="false">[</mo>}{h}_1\mathrm{,}{h}_2\mathrm{<mo\; stretchy="false">]</mo><mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}{x}_2\mathrm{,2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}{h}_2\mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo>.}$

Пусть $h\mathrm{<mo>:</mo>}X\to Y$ и $i\in \mathrm{<mo>\{</mo>1,2<mo>\}</mo>}$. Тогда через $\left[h_i\right]$ обозначим отображение множества $L_i\mathrm{<mo\; stretchy="false">(</mo>}X\mathrm{<mo\; stretchy="false">)</mo>}$ в множество $Y$, которое для любого $x\in X$ действует следующим образом: $\left[h_i\right]x\mathrm{,}ihx$.

Определение 4.1. Для любых нейронных сетей

                      ${\mathcal{N}}_1\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}{i}_1\mathrm{,}{o}_1\mathrm{,}{f}_1\mathrm{,}{g}_1\mathrm{,}{l}_1\mathrm{<mo\; stretchy="false">)</mo>,}{\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{,...,}{M^{\prime }}_d\mathrm{,}{i}_2\mathrm{,}{o}_2\mathrm{,}{f}_2\mathrm{,}{g}_2\mathrm{,}{l}_2\mathrm{<mo\; stretchy="false">)</mo>}$

из множества $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ определяем отображения

              $i_3:={\left[i_1\right]}_1\mathrm{,}{o}_3:={\left[o_2\right]}_2\mathrm{,}{g}_3:=\left[g_1\mathrm{,}{g}_2\right],l_3:=\left[l_1\mathrm{,}{l}_2\right]$

и отображение $f_3\mathrm{<mo>:</mo>}S\mathrm{<mo\; stretchy="false">[</mo>}{\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">]</mo>}\to ℝ$, которое однозначно определяется соотношениями:

                                      $f_3\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}a\mathrm{,1<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}b\mathrm{,1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}{f}_1\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}a\mathrm{,}b\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}a\mathrm{,1<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}b\mathrm{,1<mo\; stretchy="false">)</mo>}\in A\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>;</mo>}$

                                 $f_3\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}{a}^{\prime }\mathrm{,2<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}{b}^{\prime }\mathrm{,2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}{f}_2\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}{a}^{\prime }\mathrm{,}{b}^{\prime }\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}{a}^{\prime }\mathrm{,2<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}{b}^{\prime }\mathrm{,2<mo\; stretchy="false">)</mo>}\in B\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>;</mo>}$

                              $f_3\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}m\mathrm{,1<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}{m}^{\prime }\mathrm{,2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>1}\Leftarrow o_1\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{i}_2\mathrm{<mo\; stretchy="false">(</mo>}{m}^{\prime }\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo\; stretchy="false">(</mo>}m\in M_n\mathrm{,}{m}^{\prime }\in {M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo><mo>;</mo>}$

                              $f_3\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}m\mathrm{,1<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}{m}^{\prime }\mathrm{,2<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>0}\Leftarrow o_1\mathrm{<mo\; stretchy="false">(</mo>}m\mathrm{<mo\; stretchy="false">)</mo>}\ne i_2\mathrm{<mo\; stretchy="false">(</mo>}{m}^{\prime }\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo\; stretchy="false">(</mo>}m\in M_n\mathrm{,}{m}^{\prime }\in {M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>.}$

Операцию $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ определим равенством

                     ${\mathcal{N}}_1\odot {\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_1\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_d\mathrm{<mo\; stretchy="false">)</mo>,}{i}_3\mathrm{,}{o}_3\mathrm{,}{f}_3\mathrm{,}{g}_3\mathrm{,}{l}_3\mathrm{<mo\; stretchy="false">)</mo>.}$ (4.1)

Замечание 4.1. Отметим, что отображения $L_1$ и $L_2$ выполняют функцию покраски элементов множества в два различных цвета (первый цвет и второй цвет). Покраска является необходимым условием корректности определения 4.1. В самом деле, для покрашенных множеств выполняется равенство

                                 $\mathrm{<mo\; stretchy="false">(</mo>}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_1\mathrm{<mo\; stretchy="false">)</mo>}\cup \mathrm{...}\cup L_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}\cap \mathrm{<mo\; stretchy="false">(</mo>}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>}\cup \mathrm{...}\cup L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_d\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo>}\varnothing \mathrm{,}$

которое обеспечивает корректность введения структурных отображений $i_3\mathrm{,}{o}_3\mathrm{,}{f}_3\mathrm{,}{g}_3\mathrm{,}{l}_3$. При отсутствии покраски и наличия в двух сетях одинаковых нейронов данный способ задания структурных отображений результирующей сети приводил бы к тому, что на одном нейроне одно и то же отображение имеет различные значения. Последнее не корректно.

Структурные отображения $i_3\mathrm{,}{o}_3\mathrm{,}{f}_3\mathrm{,}{g}_3\mathrm{,}{l}_3$ из определения 4.1 подобраны так, чтобы сеть ${\mathcal{N}}_1\odot {\mathcal{N}}_2$ действовала на любом входном сигнале, как последовательное применение сетей ${\mathcal{N}}_1$ и ${\mathcal{N}}_2$.

 Группоид $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo><mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>,}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ назовем полным группоидом композиции многослойных нейронных сетей.

 Работа сети. Работу нейронной сети $\mathcal{N}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_d\mathrm{,}i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l\mathrm{<mo\; stretchy="false">)</mo>}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ как вычислительной схемы будет реализовывать функция $F_{\mathcal{N}}\mathrm{<mo>:</mo>}{ℝ}^k\to {ℝ}^k$. Действие этой функции опишем помощью модели искусственного нейрона Мак-Каллока $–$ Питтса ([1]). Пусть $n$ $–$ нейрон слоя $M_j$ при $j\mathrm{<mo>></mo>1}$. Нейрон $n$ получает сигнал (в виде числа) от каждого нейрона предыдущего слоя. Обозначим эти нейроны символами $n_1\mathrm{,...,}{n}_{\mathrm{<mo>|</mo>}{M}_{j-1}\mathrm{<mo>|</mo>}}$, а сигналы (числа), которые они посылают, обозначим символами $a_1\mathrm{,...,}{a}_{\mathrm{<mo>|</mo>}{M}_{j-1}\mathrm{<mo>|</mo>}}$. Тогда $n$ генерирует свой сигнал $G_n$ по правилу

                                                      $G_n\mathrm{<mo>=</mo>}{y}_n\left({\displaystyle \sum _{s\mathrm{<mo>=</mo>1}}^{\mathrm{<mo>|</mo>}{M}_{j-1}\mathrm{<mo>|</mo>}}}f\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}{n}_s\mathrm{,}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}\cdot a_s+l\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}\right)\mathrm{,}$

где $y_n\mathrm{<mo>:</mo><mo>=</mo>}g\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ $–$ функция активации нейрона $n$ (для каждого нейрона $n$ функцию активации определяет структурное отображение $g$; здесь $g\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$ $–$ значение отображения $g$ на нейроне $n$ ). Дальше сигнал передается через соответствующие синаптические связи.

Действие функции $F_{\mathcal{N}}$ состоит в том, что сигнал $\mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{,...,}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}\in {ℝ}^k$ передается на входной слой $M_1$ так, что нейрон $n\in M_1$ получает сигнал $x_s$, когда $i\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}s$. Нейроны входного слоя передают свои сигналы $y_n\mathrm{<mo\; stretchy="false">(</mo>}{x}_s+l\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$ ( $y_n\mathrm{<mo>=</mo>}g\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo>}$, $i\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}s$ ) по синаптическим связям на второй слой. Далее сигнал распространяется по сети в соответствии с моделью искусственного нейрона, описанной выше. Выходной слой $M_d$ генерирует вектор $\mathrm{<mo\; stretchy="false">(</mo>}{u}_1\mathrm{,...,}{u}_k\mathrm{<mo\; stretchy="false">)</mo>}$, где число $u_s$ сгенерировано нейроном $n\in M_d$ таким, что $o\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}s$.

 Для любых двух сетей ${\mathcal{N}}_1$ и ${\mathcal{N}}_2$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ и всякого сигнала $\overline{x}\in {ℝ}^k$ выполняется равенство $F_{{\mathcal{N}}_1\odot {\mathcal{N}}_2}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{F}_{{\mathcal{N}}_2}\mathrm{<mo\; stretchy="false">(</mo>}{F}_{{\mathcal{N}}_1}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>.}$ 

Доказательство. Рассмотрим сети

                      ${\mathcal{N}}_1\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}{i}_1\mathrm{,}{o}_1\mathrm{,}{f}_1\mathrm{,}{g}_1\mathrm{,}{l}_1\mathrm{<mo\; stretchy="false">)</mo>,}{\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{,...,}{M^{\prime }}_d\mathrm{,}{i}_2\mathrm{,}{o}_2\mathrm{,}{f}_2\mathrm{,}{g}_2\mathrm{,}{l}_2\mathrm{<mo\; stretchy="false">)</mo>}$

из множества $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$.

Из построения сети ${\mathcal{N}}_1\odot {\mathcal{N}}_2$ видно, что сигнал $\overline{x}$ распространяется по слоям $L_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_1\mathrm{<mo\; stretchy="false">)</mo>,}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_2\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>}$ так же, как он распространялся бы по сети ${\mathcal{N}}_1$ (действительно, это гарантируется способом задания структурных отображений сети ${\mathcal{N}}_1\odot {\mathcal{N}}_2$ ). Поэтому слой $L_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>}$ сгенерирует сигнал $F_{{\mathcal{N}}_1}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo>}$. Нейрон $\mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{,1<mo\; stretchy="false">)</mo>}$ из $L_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>}$ будет соединяться с нейроном $\mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{,2<mo\; stretchy="false">)</mo>}\in L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>}$ синаптической связью, имеющей вес 1, тогда и только тогда, когда $o_1\mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{i}_2\mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$. С другими нейронами слоя $L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>}$ нейрон $a$ соединяется синаптическими связями, имеющими вес 0. Следовательно, слой $L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>}$ получает сигнал $F_{{\mathcal{N}}_1}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo>}$, который распространяется по слоям $L_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_2\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_d\mathrm{<mo\; stretchy="false">)</mo>}$ так же, как он распространялся бы по сети ${\mathcal{N}}_2$. Поэтому сеть ${\mathcal{N}}_1\odot {\mathcal{N}}_2$ возвращает сигнал $F_{{\mathcal{N}}_2}\mathrm{<mo\; stretchy="false">(</mo>}{F}_{{\mathcal{N}}_1}\mathrm{<mo\; stretchy="false">(</mo>}\overline{x}\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$, когда на ее вход подается сигнал $\overline{x}$. Утверждение доказано.

5. Структура группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$

Главным результатом данного раздела будет являться теорема 5.1, которая показывает, что группоид $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ является свободным группоидом. Вспомогательные утверждения дадут арифметические свойства данного группоида в терминах нейронных сетей.

Если элемент группоида нельзя разложить в произведение двух элементов данного группоида, то будем называть такой элемент простым элементом. Для каждой сети $\mathcal{N}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ определим множество

                        $\Theta \mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo><mo>\{</mo><mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo>}\in \text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}\times \text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>|</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2\mathrm{<mo>=</mo>}\mathcal{N}\mathrm{<mo>\}</mo>.}$

Будем использовать обозначение

                                                                 $K\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}P\cup \mathrm{<mo\; stretchy="false">(</mo>}{\displaystyle \underset{s\in N}{\cup }}{D}_s\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>.}$

Ясно, что $K\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo>}$ $–$ это множество всех возможных нейронов, из которых формируются нейронные сети группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$.

Определение 5.1. Для каждой нейронной сети $\mathcal{N}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ введем натуральное число ${\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$ такое, что выполняются условия:

1) если сеть $\mathcal{N}$ имеет вид

                              $\mathcal{N}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_1\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M}_{n+1}\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M}_d\mathrm{<mo\; stretchy="false">)</mo>,}i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l\mathrm{<mo\; stretchy="false">)</mo>}$

для подходящих подмножеств $M_1\mathrm{,...,}{M}_n\mathrm{,}{M}_{n+1}\mathrm{,...,}{M}_d$ множества $K\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo>}$ и выполняются неравенства $n\ge 1$, $d\ge n+1$, то полагаем по определению ${\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>}n$;

2) если не существует натурального числа $n$ такого, что выполняются условия первого пункта, то ${\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>:</mo><mo>=</mo>0}$.

Число ${\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$ назовем разделителем первого типа сети $\mathcal{N}$.

Из определения 4.1 операции $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ вытекает

Предложение 5.1. Если ${\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>0}$, то $\mathcal{N}$ $–$ простой элемент группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$.

Если разделитель первого типа сети $\mathcal{N}$ равен $n\mathrm{<mo>=</mo>0}$, то это означает, что основной кортеж нейронов сети $\mathcal{N}$ имеет структуру непригодную для того, чтобы представить данную сеть в виде произведения некоторых двух сетей из группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ (см. равенство (4.1)).

При $n\ne 0$ выполняется необходимое (но не достаточное) условие того, что нейронную сеть $\mathcal{N}$ можно представить в виде произведения $\mathcal{N}\mathrm{<mo>=</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2$, где $n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}n$.

Не сложно увидеть, что все однослойные нейронные сети из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ являются простыми элементами группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ (обратное не верно). Последнее вытекает из того, что группоид для любого $\mathcal{N}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ выполняется неравенство $n\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\ge 1$ и равенство $n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo>}+n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo>}$.

Далее введем объект, который позволит сформулировать необходимое и достаточное условие того, что нейронную сеть можно представить в виде композиции двух сетей (см. ниже предложение 5.2 пункт 3).

Определение 5.2. Пусть нейронная сеть $\mathcal{N}$ принадлежит $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Тогда определим множество ${\text{Del}}_2\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$, состоящее из всевозможных натуральных чисел $n$ (и только из них), таких что одновременно выполняются условия:

1) сеть $\mathcal{N}$ имеет вид $\mathcal{N}\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}{M}_{n+1}\mathrm{,...,}{M}_d\mathrm{,}i\mathrm{,}o\mathrm{,}f\mathrm{,}g\mathrm{,}l\mathrm{<mo\; stretchy="false">)</mo>}$;

2) выполняются равенства $\mathrm{<mo>|</mo>}{M}_n\mathrm{<mo>|</mo><mo>=</mo><mo>|</mo>}{M}_{n+1}\mathrm{<mo>|</mo><mo>=</mo>}k$;

3) выполняются неравенства $n\ge 1$ и $d\ge n+1$;

4) в каждый нейрон $u$, входящий в $M_{n+1}$, входит только одна синаптическая связь с весом $1$, а все остальные синаптические связи, входящие в нейрон $u$, имеют нулевой вес;

5) из каждого нейрона $v$, принадлежащего $M_n$, выходит только одна синаптическая связь с весом $1$, а все остальные синаптические связи, выходящие из нейрона $v$, имеют нулевой вес.

Множество ${\text{Del}}_2\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$ будем называть разделителем второго типа сети $\mathcal{N}$.

Рассмотрим условия на число $n$ из определения 5.2. Условие 2) продиктовано тем, что в множество $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ входят только нейронные сети, у которых во входном слое $k$ нейронов и в выходном слое $k$ нейронов. Условие 3) продиктовано тем, что в множество $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ входят нейронные сети, у которых число слоев строго больше 1. Условия 4) и 5) объясняются определением структурного отображения $f_3$ результирующей сети из определения 4.1.

Вхождение некоторого натурального числа $n$ в разделитель второго типа сети $\mathcal{N}$ является необходимым условием для того, чтобы нейронную сеть $\mathcal{N}$ можно было разбить в произведение $\mathcal{N}\mathrm{<mo>=</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2$, где $n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}n$. Из определений 4.1, 5.1 и 5.2 вытекает

Предложение 5.2. Выполняются следующие утверждения:

1) Если ${\text{Del}}_2\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varnothing$, то $\mathcal{N}$ $–$ простой элемент группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$.

2) Если ${\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\notin {\text{Del}}_2\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$, то $\mathcal{N}$ $–$ простой элемент группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$.

3) Сеть $\mathcal{N}$ не является простым элементом группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ тогда и только тогда, когда разделитель первого типа является элементом разделителя второго типа.

 Пусть $\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$ $–$ множество всех простых элементов группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Тогда из пункта 3) предложения 5.2 вытекает

Предложение 5.3. Справедливо равенство

                              $\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>=</mo><mo>\{</mo>}\mathcal{N}\in \text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}\mathrm{<mo>|</mo>}{\text{Del}}_1\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\notin {\text{Del}}_2\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>\}</mo>.}$

Лемма 5.1. Для каждого элемента $\mathcal{N}$ группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ выполняется условие $\mathrm{<mo>|</mo>}\Theta \mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\le 1$.

Доказательство. Если $\mathcal{N}$ $–$ простой элемент группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$, то $\mathrm{<mo>|</mo>}\Theta \mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo>0}$. В этом случае неравенство из утверждения выполняется.

Пусть $\mathrm{<mo>|</mo>}\Theta \mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>></mo>0}$. Тогда существуют сети

                      ${\mathcal{N}}_1\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}{i}_1\mathrm{,}{o}_1\mathrm{,}{f}_1\mathrm{,}{g}_1\mathrm{,}{l}_1\mathrm{<mo\; stretchy="false">)</mo>,}{\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{,...,}{M^{\prime }}_d\mathrm{,}{i}_2\mathrm{,}{o}_2\mathrm{,}{f}_2\mathrm{,}{g}_2\mathrm{,}{l}_2\mathrm{<mo\; stretchy="false">)</mo>}$

из множества $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ такие, что $\mathcal{N}\mathrm{<mo>=</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2$. Предположим, что существуют сети $\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_1$ и $\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_2$ такие, что $\mathcal{N}\mathrm{<mo>=</mo>}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_1\odot \mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_2$ и $\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo>}\ne \mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_1\mathrm{,}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_2\mathrm{<mo\; stretchy="false">)</mo>}$ В этом случае выполняются равенства

  $\mathcal{N}\mathrm{<mo>=</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_1\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_1\mathrm{<mo\; stretchy="false">(</mo>}{M}_n\mathrm{<mo\; stretchy="false">)</mo>,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>,...,}{L}_2\mathrm{<mo\; stretchy="false">(</mo>}{M^{\prime }}_d\mathrm{<mo\; stretchy="false">)</mo>,}{i}_3\mathrm{,}{o}_3\mathrm{,}{f}_3\mathrm{,}{g}_3\mathrm{,}{l}_3\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_1\odot \mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_2\mathrm{,}$

которые вместе с определением опреации $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ показывают, что

                     $\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_1\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M}_1\mathrm{,...,}{M}_n\mathrm{,}{i^{\prime }}_1\mathrm{,}{o^{\prime }}_1\mathrm{,}{f^{\prime }}_1\mathrm{,}{g^{\prime }}_1\mathrm{,}{l^{\prime }}_1\mathrm{<mo\; stretchy="false">)</mo>,}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_2\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{M^{\prime }}_1\mathrm{,...,}{M^{\prime }}_d\mathrm{,}{i^{\prime }}_2\mathrm{,}{o^{\prime }}_2\mathrm{,}{f^{\prime }}_2\mathrm{,}{g^{\prime }}_2\mathrm{,}{l^{\prime }}_2\mathrm{<mo\; stretchy="false">)</mo>.}$

Из определения операции $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ следует, что структурные отображения сети $\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_i$ совпадают со структурными отображениями сети ${\mathcal{N}}_i$ при $i\mathrm{<mo>=</mo>1,2}$. Поэтому $\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}$ $\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_1\mathrm{,}\mathcal{N}{\mathrm{<mo>\text{'}</mo>}}_2\mathrm{<mo\; stretchy="false">)</mo>}$, следовательно, имеем противоречие, которое дает условие $\mathrm{<mo>|</mo>}\Theta \mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo>1}$. Лемма доказана.

 Далее под символом $\mathrm{<mo\; stretchy="false">(</mo>}\backslash \mathrm{<mo\; stretchy="false">)</mo>}$ будем понимать разность двух множеств.

Лемма 5.2. Группоид $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ порождается своим множеством простых элементов.

Доказательство. Истинность этого утверждения вытекает из существования процедуры, которая за конечное число шагов позволяет представить любую сеть из группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ в виде алгебраического выражения, записанного с помощью скобок, операции $\mathrm{<mo\; stretchy="false">(</mo>}\odot \mathrm{<mo\; stretchy="false">)</mo>}$ и простых элементов группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ (далее это алгебраическое выражение будем называть разложением через простые элементы). Опишем указанную процедуру.

Этап 1. Пусть $\mathcal{N}$ $–$ произвольная сеть из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Если $\mathcal{N}$ $–$ простой элемент группоида, то оставляем его без изменений. Если $\mathcal{N}$ $–$ сеть из множества $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}\backslash \Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$, то данная сеть раскладывается в произведение $\mathcal{N}\mathrm{<mo>=</mo>}{\mathcal{N}}_1\odot {\mathcal{N}}_2$, где ${\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2$ $–$ подходящие сети (единственные в силу леммы 5.1) такие, что выполняются неравенства $n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_1\mathrm{<mo\; stretchy="false">)</mo><mo><</mo>}n\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$ и $n\mathrm{<mo\; stretchy="false">(</mo>}{\mathcal{N}}_2\mathrm{<mo\; stretchy="false">)</mo><mo><</mo>}n\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}$.

Этап 2. Если обе сети ${\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2$ являются простыми элементами группоида, то фиксируем это (т. е. записываем полученное выражение). В этом случае мы получили, что сеть $\mathcal{N}$ принадлежит $\mathrm{<mo><</mo>}\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>></mo>}$, следовательно, получим разложение этой сети через простые элементы.

Этап 3. Если одна или обе из сетей ${\mathcal{N}}_1\mathrm{,}{\mathcal{N}}_2$ окажутся не простыми элементами группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$, то будем раскладывать их в произведения подходящих сетей (применяем к этим сетям первый этап процедуры). Данный процесс продолжаем, пока не получим разложение сети $\mathcal{N}$ через простые элементы.

Построенный процесс обязательно приведет к получению разложения сети $\mathcal{N}$ через простые элементы. Каждый раз, когда мы раскладываем некоторую сеть $\mathcal{A}$ в произведение подходящих сетей $\mathcal{A}{\mathrm{<mo>\text{'}</mo>}}_1\mathrm{,}\mathcal{A}{{\text{'}}^{\prime }}_2$, то число слоев в сетях $\mathcal{A}{\mathrm{<mo>\text{'}</mo>}}_1\mathrm{,}\mathcal{A}{{\text{'}}^{\prime }}_2$ будет строго меньше, чем число слоев в сети $\mathcal{A}$. Поскольку для каждой сети $\mathcal{A}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ число слоев $n\mathrm{<mo\; stretchy="false">(</mo>}A\mathrm{<mo\; stretchy="false">)</mo>}$ $–$ конечное число и все сети $\mathcal{T}$ из $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ с условием $n\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{T}\mathrm{<mo\; stretchy="false">)</mo>}\le 1$ являются простыми элементами, то за конечное число шагов можно получить разложение любой сети через простые элементы. Лемма доказана.

 Свободный группоид слов в заданном алфавите. Будем говорить, что $G$ $–$ свободный группоид слов со свободной системой образующих $X$, если элементами группоида $G$ являются слова в алфавите $X$, где под словом понимают любую конечную упорядоченную систему элементов из $X$ с любыми повторениями, причем в этой системе задано распределение скобок (каждый символ считается взятым в скобки, а затем скобки расставлены так, что каждый раз перемножаются только две скобки).

В свободном группоиде слов любая пара различных слов дает пару различных элементов, а множество свободных образующих является множеством всех простых элементов данного свободного группоида. Например, если $X\mathrm{<mo>=</mo><mo>\{</mo>}a\mathrm{,}b\mathrm{<mo>\}</mo>}$ $–$ система свободных образующих, то слова $a\mathrm{<mo>*</mo>}b\mathrm{<mo>*</mo>}a\mathrm{,}b\mathrm{<mo>*</mo>}b\mathrm{<mo>*</mo>}b$ не являются элементами свободного группоида (т. к. нет корректной расстановки скобок), а слова $\mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>*</mo><mo\; stretchy="false">(</mo>}b\mathrm{<mo>*</mo>}a\mathrm{<mo\; stretchy="false">)</mo>,<mo\; stretchy="false">(</mo>}a\mathrm{<mo>*</mo>}b\mathrm{<mo\; stretchy="false">)</mo><mo>*</mo><mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}$ являются элементами свободного группоида (кроме того, данные слова различны).

Всякий группоид $G$, который изоморфен свободному группоиду слов, будем называть свободным группоидом. Если группоид $G$ порождается множеством всех своих простых элементов и каждый непростой элемент этого группоида можно только одним способом представить в виде произведения двух элементов этого группоида, то $G$ $–$ свободный группоид (в этом случае любое отображение множества простых элементов группоида $G$ в группоид $G$ продолжается до эндоморфизма группоида $G$ ).

Теорема 5.1. Группоид $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ является свободным группоидом со свободной системой образующих $\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$.

Доказательство. В силу леммы 5.2 мы можем считать, что $\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$ $–$ система образующих группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Лемма 5.1 показывает, что всякий элемент группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$ либо простой элемент, либо единственным образом раскладывается в произведение элементов этого группоида. Следовательно, два различных слова в алфавите $\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$ являются различными элементами в группоиде $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Поэтому множество $\Pi \mathrm{<mo\; stretchy="false">(</mo>}\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$ является свободной системой образующих группоида $\text{SAN}\mathrm{<mo\; stretchy="false">(</mo>}k\mathrm{,}P\mathrm{<mo\; stretchy="false">)</mo>}$. Теорема доказана.

Благодарности. Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки России (Соглашение 075-02-2024-1429).