Псевдоконгруэнции
на
универсальных алгебрах

В.Н.Третьяков

Работа опубликована по решению редколлегии
журнала "Известия АН БССР.
Серия физико-математических наук"
как рукопись, депонированная в ВИНИТИ
(Москва, 1983).

I. Введение

I.1. Упорядоченная пара [M, T] называется толерантным пространством [2, 10], если T - отношение толерантности на М, т.е. рефлексивное и симметричное бинарное отношение. Алгебра {A, F} называется K-толерантной алгебраической структурой [4], если K - толерантность на А и для любой n-арной операции f € F и любых 2n элементов x_i, y_i € A, i = 1, 2, …, n, таких, что x_i K y_i, выполняется (x₁, …, x_n)f K (y₁, …, y_n)f. Множество L € M называется предклассом толерантности T в толерантном пространстве [M, T] [2], если для любых х, y € L выполняется xTy. Если К € М - максимальный предкласс, то он называется классом толерантности [2]. Граф G(A, T) называется толерантным графом [3], если А является его множеством вершин, а две вершины x и y из А соединены ребром тогда и только тогда, когда x T y.

I.2. При анализе этих и других математических понятий, связанных с множеством, можно заметить, что они строятся в предположении об абсолютной индивидуации (разрешимости) его элементов: для любых x и y всегда известно, x = y или x ? y. Другими словами, множество М отождествляется со своим фактор-множеством по равенству: М ? М_/= . Но равенство - это идеализированный случай отношения толерантности, имеющего произвольно высокую степень толерантного замыкания: x (=)ⁿ y влечет x = y для любого n € Z⁺. В силу неограниченности n свойство транзитивности является идеализацией: оно может лишь постулироваться, но принципиально непроверяемо. (Практическая невозможность проверки транзитивности связана также с тем, что перцептивное и экспериментальное "равенства" - тоже отношения толерантности). Отказ от этой идеализации означает замену отношения равенства на множестве отношением толерантности. Поскольку толерантностям, в отличие от эквивалентностей, не соответствуют правильные разбиения, то совокупности различимых по толерантности T (или T-различимых) элементов имеют не вполне определенный элементный состав.

Пусть M_T1, M_T2, …, M_Tk, … -- ряд совокупностей T_i-различимых элементов "реальной" совокупности М, где толерантности T_i можно связать, например, с разрешающей способностью приборов. Наше предположение (гипотеза врожденной толерантности) состоит в том, что точность индивидуации имеет пределом не абсолютную точность равенства, а неабсолютную точность некоторого отношения толерантности t (назовем ее врожденной), являющейся характеристикой совокупности М и определяющей (хотя и не вполне) ее элементный состав. Таким образом, любое пересечение толерантностей T_i включает t. В настоящей работе рассматриваются алгебраические системы, главными предикатами которых являются отношения толерантности, а носителями - совокупности t-различимых элементов.

I.3. Конкретизируем сказанное выше.
А. В духе идей П.К.Рашевского [1] можно предположить существование врожденной толерантности t₀ на числовой прямой, такой, что при достаточно больших N выполняется N t₀ (N + n), причем n возрастает с ростом N. Назовем ординальной совокупность N_t0⁺ t₀-различимых натуральных чисел, определяемую числом N₁:

N₁ t₀ (N₁ + 1) и неверно, что N₁ t₀ (N₁ - 1).

По определению, совокупность N _t0⁺ состоит из элементов 1, 2, …, N₁ - 1. Совокупность Q_t0 t₀-различимых вещественных чисел можно считать порожденной отношением толерантности t₀ на совокупности натуральных чисел (см. [1]).
Б. Если принять предположение о существовании фундаментальной длины L, характеризующей физическое пространство S, то S можно рассматривать как толерантное пространство [S, t_L], с пространственной толерантностью t_L, заданной в виде:

a t_L b -> неверно, что d (a, b) > L

(здесь d (a, b) - расстояние между точками a и b). При этом возникает дискретно-геометрический объект - совокупность t_L-различимых "точек" пространства.
Отметим, что определение t_L в духе классической толерантности (см. [13])

a t_L b -> d (a, b) < L

было бы некорректным, поскольку оно входило бы в противоречие с принципиальной ненаблюдаемостью (неразличимостью) расстояний, меньших чем L.

II. Т-толерантные алгебры, или T_R-модели

II.1. Процедура выделения t-различимых элементов из "реальной" совокупности А принципиально неоднозначна: она порождает совокупности A_t⁽¹⁾, A_t⁽²⁾, …, элементы которых можно представить на склеенных листах многолистной поверхности, причем каждый лист соответствует какой-то одной возможности выделения. Обозначим через A_(t) объединение U_k A_t^(k), допускающее возможность "отклеивания" листов (объединение с "памятью"; ср. с [1]). При этом элементы A_(t) будут определяться "с точностью до толерантности t".

II.2. Определение. Будем называть T-моделью совокупность M_(t) с заданным на ней отношением толерантности T (обозначение: [M_(t), T]), таким, что x T y и y t z влечет x T z для x, y, z € M_(t).

II.3. Определение. Алгебраическая система {A_(t), R, T} на носителе M_(t) с совокупностями главных операций R ~ {r_k: k € I} и главных предикатов Т ~ {T_j: j € J} называется Т-толерантной алгеброй, или T_R-моделью, если
1) алгебра {A_(t), R} t-замкнута, т.е. для любой n_k-арной операции r_k € R и любых x₁, …, x_nk € A_(t) существует элемент y € A_(t) такой, что (x₁, …, x_nk)r_k t y (свойство t-замкнутости);
2) отношения T_j € T -- толерантности на любой A_t^(k);
3) операции r_k и толерантности T_j (k € I, j € J ) согласованы (или совместимы; см. [4]) на A_(t), т.е. для любых 2n_k элементов x₁, …, x_nk, y₁, …, y_nk € A_(t) таких, что x₁ T_j y₁, …, x_nk T_j y_nk, выполняется
(x₁, …, x_nk) r_k T_j (y₁, …, y_nk) r_k
(свойство согласованности Т с R).

Т-толерантную алгебру назовем t-локальной, если истинность любого утверждения Р относительрно этой алгебры не изменится при замене любого x € A_(t) на элемент y € A_(t) такой, что x t y, т.е.

P(… x …) - P(… y …)

(свойство t-локальности).

II.4. Теорема. Пусть {A_(t), R, T} -- t-локальная толерантная алгебра. Тогда:
а) {A_(t), R, T} -- t-несвязна (т.е. для любых x, y € A_(t) ни при каких n не выполняется x tⁿ y, если неверно x t y);
б) порядок {A_(t), R, T} дефинитно-конечен (т.е. |A_(t)| € N _t0⁺);
в) толерантное пространство [A_(t), T] образует T-модель;
г) толерантность t согласована с алгеброй {A_(t), R}.

Доказательство. Предположим противное, т.е. что для каких-то x, y € A_(t) выполняется x tⁿ y. Тогда, применяя к носителю A_(t) алгебры n - 1 раз свойство t-локальности, из последнего соотношения получим x t y, в противоречии с предположением, что x, y € A_(t).
Тем же способом докажем б). Предположим, что неверно |A_(t)| € N_t0⁺. Это означало бы, что для каких-то A_t⁽¹⁾, A_t⁽²⁾ € A_(t) выполняется |A_t⁽¹⁾| t₀ N и |A_t⁽²⁾| t₀ (N+1) (см. п. I.3а), т.е. что по крайней мере 2 элемента x, y € A_(t), t-различимые в A_t⁽²⁾, t -связны или t-неразличимы в A_t⁽¹⁾. Первая возможность противоречит свойству а), вторая - определению A_t.
Свойство в) следует непосредственно из t-локальности толерантной алгебры {A_(t), R, T} применительно к толерантному пространству [A_(t), T].
Свойство г) можно доказать, используя свойства t-замкнутости и t-локальности. Действительно, если x₁, …, x_nk, y₁, …, y_nk € A_(t) и x₁ t y₁, …, x_nk t y_nk, то, в силу t-замкнутости, (x₁, …, x_nk)r_k t z, (y₁, …, y_nk)r_k t z', а в силу t-локальности z t z' и (x₁, …, x_nk)r_k t (y₁, …, y_nk)r_k.

II.5. Теорема. Совокупность Г t-локальных толерантных алгебр вкладывается в совокупность D толерантных алгебраических структур из [4].

Доказательство. Пусть {A_(t), R, T} € Г - одна из t-локальных толерантных алгебр порядка |A_(t)|. Определим взаимно-однозначное отображение Ф следующим образом:

Ф: {A_(t), r_k, T_j, t, ¬t) > {B, f_k, K_j, =, не=}, т.е.

A_(t) > (x₁Ф, …, x_nkФ)f_k, x T_j y > xФ K_j yФ; x t y > xФ = yФ; x ¬t y -> xФ не= yФ (k € I, j € J).
Тогда алгебры
{A_(t), R, T} и {B, (f_k: k € I), (K_j: j € J)} изоморфны. Пусть { Ф } - совокупность всевозможных изоморфизмов таких алгебр. Очевидно, что { Ф } осуществляет вложение Г в ?, поскольку из-за ограничения |B| € N_t0⁺ не всякая толерантная алгебраическая структура из ? имеет изоморфный аналог в классе Г.

Замечание. Теоремы о толерантностях, согласованных (совместимых) со структурами пролугруппы, группы, кольца и решетки, а также теоремы об абстрактных алгебраических структурах, доказанные в [4-9], могут быть с соответствующими изменениями сформулированы и доказаны для t-локальных толерантных алгебр.

II.6. Предложение. Пусть [A_(t), T] - T-модель, а {A(t), R} -- алгебра, у которой любая операция r_k € R осуществляет отображение A_(t) в предкласс B_(t) толерантности T. Тогда {A_(t), R, T} -- T-толерантная алгебра.

Доказательство. По предположению, r_k: A_(t)^nk > B_(t), где B_(t) € A_(t) -- предкласс толерантности T. Так как [A_(t), T] - T-модель, то это означает, что для любых x_i, y_i € A_(t) и любой r_k € R выполняется (x₁, …, x_nk)r_k T (y₁, …, y_nk)r_k.
В частности, имеем:
x₁ T y₁,…, x_nk T y_nk > (x₁, …, x_nk)r_k (y₁, …, y_nk)r_k.

II.7. Определение (ср. с [10] и [12]). Отображение

F: [A_(t), T]ⁿ > (B_(t), т)

называется толерантным отображением, если оно является отображением из A_(t) в B_(t) (т.е. для любых x₁, …, x_n € A_(t) существует b € B_(t), что (x₁, …, x_n)f t b) и для любых x_i, y_i € A_(t), таких, что x₁ T y₁, …, x_n T y_n, выполняется (x₁, …, x_n)f т (y₁, …, y_n)f.

II.8. Предложение (обобщает утверждение II.6). Пусть

Ф_k: [A_(t), T] ^nk > B_(t)^(k), т_k], k € I, --

толерантные отображения модели [A_(t), T] в модели [B_(t)^(k), т_k], k € I. Если B_(t)^(k) € A_(t) и на любом B_(t)^(k), k € I, T € т_k, то алгебраическая система {A_(t), (Ф_k: k € I), T} образует T-толерантную алгебру.

Доказательство. В силу определения II.6 x₁ T y₁, …, x_nk T y_nk > (x₁, …, x_nk)Ф_k т_k (y₁, …, y_nk)Ф_k, где x₁, …, x_nk, y₁, …, y_nk € A_(t). Поскольку т_k € T на B_(t) (k), то (x₁, …, x_nk)Ф_k т_k (y₁, …, y_nk)Ф_k > (x₁, …, x_nk)Ф_k T (y₁, …, y_nk)Ф_k, и согласованность T с т_k доказана. Другие свойства толерантной алгебры (см. II.3) очевидны.

III. Свойства псевдоконгруэнции

III.1. Другое название отношения толерантности - псевдоэквивалентность [11]. Поэтому согласованное с алгеброй V ? {A_(t), R} отношение толерантности естественно назвать псевдоконгруэнцией.

III.2. Для t-локальных толерантных алгебр (так же как и для K_j-толерантных алгебраических структур [4]) полное отношение толерантности U является псевдоконгруэнцией. Однако условие t-локальности может быть заменено более слабым.

Предложение. Пусть [A_(t), U] - U-модель, где U - полное отношение. Тогда U - псевдоконгруэнция (являющаяся конгруэнцией) на любой алгебре [A_(t), R}.

Доказательство аналогично доказательству предложения II.6.

III.3. Теорема. Пусть T - псевдоконгруэнция на t-локальной алгебре V. Тогда:
а) кратная к T толерантность Tⁿ - псевдоконгруэнция на V;
б) транзитивное замыкание Z толерантности T на V - псевдоконгруэнция на V (являюшаяся конгруэнцией).

Доказательство. А) Пусть V ? {A_(t), R}, R ? (r_k: k € I)}, -- алгебра, с которой согласована толерантность T. Поскольку x_i Tⁿ y_i означает, что существуют z₁⁽ⁱ⁾, …, z_n-1⁽ⁱ⁾ € A_(t) такие, что

x₁T z₁⁽ⁱ⁾& z₁⁽ⁱ⁾ T z₂⁽ⁱ⁾ &…& z₂ ⁽ⁱ⁾ T y_i,

то, полагая x₁ Tⁿ y₁ & y₁ Tⁿ y₂ & … & x_nk T_n y_nk и меняя порядок членов конъюнкции, получим (с учетом t-локальности):

(x₁, …, x_nk) T (z₁ T⁽¹⁾,…, z₁ ^(nk))r_k & (z₁ ⁽¹⁾,…, z₁ (nk))r_k T (z₂ (i),…, z₂ (nk))r_k &…&(z_n-1(i),…, z_n-1 (nk))r_k T (y₁, …, y_nk)r_k,

т.е. для любых x₁, …, x_nk, y₁, …, y_nk € A_(t) таких, что x₁ T _n y₁&…& x_nk Tⁿ y_nk, выполняется (x₁, …, x_nk)r_k Tⁿ (y₁, …, y_nk)r_k.
б). Поскольку алгебра V t-локальна, то ее порядок, а значит, и минимальная степень m транзитивного замыкания Z толерантности T конечны: |A_t|, m € N_t0⁺, т.е. для .x, y € A(t) xty равносильно xT^my. По доказанному в п. А), t - псевдоконгруэнция, являющаяся конгруэнцией в силу III.2.

III.4. Определения. Пусть A_(t) - носитель t-локальной толерантной алгебы {A_(t), R, T}, R ~ (r_k: k€ I). Толерантным графом G_T (A_(t)) T-модели [A_(t), T] естественно считать такой неориентированный псевдограф, в котором любые две вершины соединены ребром тогда и только тогда, когда они связан отношением толерантности T, и петлей, когда они t-неразличимы. Пусть T_(n), t_(n) - отношения толерантности, индуцируемые толерантностями T и t на декартовых степенях n совокупности A_(t) (ср. с [13]). Кортеж (x₁, …, x_n) € A_(t)ⁿ будем называть T-маршрутом, если x₁ T x₂, x₂ T x₃, …, x_n-1 T x_n, замкнутым T-маршрутом, если к тому же x₁ t x_n, и удлиненным T-маршрутом (по отношению к (x₁, …, x_m), x_m+1 t x_m, …, x_n t x_m. (Здесь и далее мы используем для t-неразличимых элементов один и тот же буквенный символ). Под r-композицией T-маршрутов максимальной длины n (т.е. среди них могут быть удлиненные) будем понимать операцию r над соответствующими элементами кортежей.

III.5. Лемма. Пусть T - псевдоконгруэнция t-локальной алгебры { A_(t), R, T}, а G_T (A_(t)) - толерантный граф ее T-модели. Тогда любая r_k-композиция T-маршрутов (замкнутых T-маршрутов) максимальной длины n порождает T-маршрут (замкнутых T-маршрут) максимальной длины n.

Доказательство первой части утверждения производится непосредственно при использовании условия согласованности T с {A_(t), R}. Для доказательства замкнутости r_k-композиций на замкнутых T-маршрутах дополнительно используется условие согласованности t с алгеброй {A_(t), R}.

III.6. Теорема. Пусть выполнены условия леммы. Если к тому же совокупность R_n T-маршрутов максимальной длины n дефинитно-конечна, то
а) T_(n) - псевдоконгруэнция на алгебрах {R_n, C(R)} и {R*n,C*(R)}, где C(R) и C*(R) -- r_k-композиции T-маршрутов из R_n и замкнутых T-маршрутов из R*_n максимальной длины n;
б) толерантные алгебры {R_n, C(R),T_(n)} t-локальны.

Доказательство. а) Свойство согласованности T_(n) с r_k-композициями следует непосредственно из определения С(R) при учете леммы и согласованности T с {A_(t), R}. Оно не зависит от выполнимости условий замкнутости T-маршрутов, и потому справедливо для замкнутых маршрутов тоже.
б). Свойство t-локальной толерантной алгебры - дефинитная конечность совокупности R_n (т.е. и совокупности R*_n) - выполняется по условию теоремы. Согласованность t_(n) с С(r_k) может быть доказана аналогично доказательству п. а). Положение, что толерантные пространства [R_n, T_(n)] и [R*_n, T_(n)] являются T_(n) -моделями, следует из того, что [A_(t), T_(n)] -- T-модель.

III.7. Следствия. 1. Для псевдоконгруэнций T_(n) верны все свойства псевдоконгруэнций t-локальной толерантной алгебры.
2. Для T-маршрутов максимальной длины 0 алгебра {A_(t), C(R), T_(n)} вырождается в алгебру {A_(n), R, T}.
3. Алгебры {R*_n, C*(R), T_(n)} и {R_n-p, C(R), T_(n)}, p < n, являются подалгебрами алгебры {R_n, C(R), T_(n)}.

Автор признателен акад. АН БССР Д.А.Супруненко и участникам руководимого им алгебраического семинара, особенно И.Б.Воличенко и Н.М.Корниенко, за критические замечания и ценные советы. (Прим. 1983 г.)

Литература

1. Рашевский П.К. О догмате натурального ряда. - УМН, 1973, т. 28 (4), с. 243-246.
2. Шнейдер Ю.А. Равенство, сходство, порядок. - М.: Наука, 1971. - 254 с.
3. Zelinka B. Tolerance graphs. - Comm. Math. Univ. Carol., 1968, vol. 9 (1), p. 121-131.
4. Zelinka B. Tolerance in algebraic structures. - Czech. Math. J., 1970, vol. 20 (2), p. 179-183.
5. Zelinka B. Tolerance in algebraic structures-II. - L.c., 1975, vol. 25 (2)< 175-178.
6. Chajda I., Zelinka B. Tolerance relation on lattices. - Cas. Pest. Mat., 1974, sv. 99 (4), 394-399.
7. Chajda I., Zelinka B. Compatible relations on algebras. L.c., 1975, sv. 100 (4), 355-360.
8. Chajda I. A construction of tolerances on modular lattices. - Cas. Pest. Mat., 1976, sv. 101 (2), 195-198.
9. Chajda I., Zelinka B. Weakly associative lattices and tolerance relation. -- Czech. Math. J., 1976, vol. 26 (2), p. 259-269.
10. Зиман Э., Бьюнеман О. Толерантные пространства и мозг. - В кн.: На пути к теоретической биологии. - М., Мир, 1970, с. 134-144.
11. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. -- 392 с.
12. Drbohlav K. Remarks on tolerance algebras. Acta Univ. Carol., Math. & Phys., 1981, vol. 22 (1), p. 11-16.
13. Chajda I. Systems… -- Czech. Math. J., 1975, vol. 25 (2), 302-308.

Аннотация статьи помещена в журнале "Весцi АН БССР. Серыя фiзiка-матэматычная", 1983, № 3; полный текст : Москва: ВИНИТИ,1983, ДЕП № 1357-83. Автор благодарен проф. В.Н.Маслову, инициировавшему размещение этой работы на сайте. (Прим. 7.07.2005).

P.S. 1.06.2007. Запоздалая благодарность -- ему же -- за предложение установить связь между принципом толерантности и механизмом старения "по Маслову"

 

 

(C) Copyright «ИнтелТех»—В.Н.Третьяков. Настоящая информация является интеллектуальной собственностью автора сайта, которому было бы интересно знать о любом использовании его материалов. Vlad-Tretyakov@yandex.ru