Отношение допуска

В универсальной алгебре и теории решеток отношение толерантности к алгебраической структуре — это рефлексивное симметричное отношение , совместимое со всеми операциями структуры. Таким образом, толерантность подобна конгруэнтности , за исключением того, что предположение о транзитивности отпадает. ^[1] На множестве , алгебраической структуре с пустым семейством операций, отношения толерантности являются просто рефлексивными симметричными отношениями. Множество, обладающее отношением допуска, можно описать как пространство допуска . ^[2] Отношения толерантности представляют собой удобный общий инструмент для изучения явлений неразличимости /неразличимости. Их важность для математики впервые осознала Пуанкаре . ^[3]

Определения [ править ]

Отношение толерантности к алгебраической структуре $(A,F)$ обычно определяется как рефлексивное симметричное отношение на $A$ который совместим с каждой операцией в $F$ . Отношения толерантности также можно рассматривать прикрытие как $A$ который удовлетворяет определенным условиям. Эти два определения эквивалентны, поскольку для фиксированной алгебраической структуры отношения толерантности в двух определениях находятся во взаимно однозначном соответствии . Отношения толерантности в алгебраической структуре $(A,F)$ образуют алгебраическую решетку $\operatorname {Tolr} (A)$ под включением. Поскольку каждое отношение конгруэнтности является отношением толерантности, решетка конгруэнтности $\operatorname {Cong} (A)$ является подмножеством решетки допусков $\operatorname {Tolr} (A)$ , но $\operatorname {Cong} (A)$ не обязательно является подрешеткой $\operatorname {Tolr} (A)$ . ^[4]

Как бинарные отношения [ править ]

Отношение толерантности к алгебраической структуре $(A,F)$ это бинарное отношение $\sim$ на $A$ который удовлетворяет следующим условиям.

( Рефлексивность ) $a\sim a$ для всех $a\in A$
( Симметрия ), если $a\sim b$ затем $b\sim a$ для всех $a,b\in A$
( Совместимость ) для каждого $n$ -арная операция $f\in F$ и $a_{1},\dots ,a_{n},b_{1},\dots ,b_{n}\in A$ , если $a_{i}\sim b_{i}$ для каждого $i=1,\dots ,n$ затем $f(a_{1},\dots ,a_{n})\sim f(b_{1},\dots ,b_{n})$ . То есть набор $\{(a,b)\colon a\sim b\}$ является подалгеброй прямого произведения $A^{2}$ из двух $A$ .

Отношение конгруэнтности — это отношение толерантности, которое также является транзитивным .

Как обложки [ править ]

Отношение толерантности к алгебраической структуре $(A,F)$ это обложка ${\mathcal {C}}$ из $A$ который удовлетворяет следующим трем условиям. ^[5]^{: 307, Теорема 3}

Для каждого $C\in {\mathcal {C}}$ $C\in {\mathcal {C}}$ и ${\mathcal {S}}\subseteq {\mathcal {C}}$ ${\mathcal {S}}\subseteq {\mathcal {C}}$ , если $\textstyle C\subseteq \bigcup {\mathcal {S}}$ $\textstyle C\subseteq \bigcup {\mathcal {S}}$ , затем $\textstyle \bigcap {\mathcal {S}}\subseteq C$ $\textstyle \bigcap {\mathcal {S}}\subseteq C$ .
- В частности, не существует двух различных элементов ${\mathcal {C}}$ сопоставимы. (Чтобы увидеть это, возьмите ${\mathcal {S}}=\{D\}$ .)
Для каждого $S\subseteq A$ , если $S$ не содержится ни в одном множестве ${\mathcal {C}}$ , то существует двухэлементное подмножество $\{s,t\}\subseteq S$ такой, что $\{s,t\}$ не содержится ни в одном множестве ${\mathcal {C}}$ .
Для каждого $n$ -и $f\in F$ и $C_{1},\dots ,C_{n}\in {\mathcal {C}}$ , есть $(f/{\sim })(C_{1},\dots ,C_{n})\in {\mathcal {C}}$ такой, что $\{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})$ . (Такой $(f/{\sim })(C_{1},\dots ,C_{n})$ не обязательно должен быть уникальным.)

Каждый раздел $A$ удовлетворяет первым двум условиям, но не наоборот. Отношение конгруэнтности — это отношение допуска, которое также образует раздел множества.

Эквивалентность двух определений [ править ]

Позволять $\sim$ допуска быть бинарным отношением в алгебраической структуре $(A,F)$ . Позволять $A/{\sim }$ — семейство максимальных подмножеств $C\subseteq A$ такой, что $c\sim d$ для каждого $c,d\in C$ . Используя термины теории графов, $A/{\sim }$ множество всех максимальных клик графа — $(A,\sim )$ . Если $\sim$ это отношение конгруэнтности , $A/{\sim }$ это просто фактормножество классов эквивалентности . Затем $A/{\sim }$ это обложка $A$ и удовлетворяет всем трем условиям определения покрытия. (Последнее условие доказывается с помощью леммы Цорна .) Обратно, пусть ${\mathcal {C}}$ быть прикрытием $A$ и предположим, что ${\mathcal {C}}$ формирует толерантность к $A$ . Рассмотрим бинарное отношение $\sim _{\mathcal {C}}$ на $A$ для чего $a\sim _{\mathcal {C}}b$ тогда и только тогда, когда $a,b\in C$ для некоторых $C\in {\mathcal {C}}$ . Затем $\sim _{\mathcal {C}}$ это толерантность к $A$ как бинарное отношение . Карта ${\sim }\mapsto A/{\sim }$ представляет собой взаимно-однозначное соответствие между допусками как бинарными отношениями и покрытиями, обратными которым является ${\mathcal {C}}\mapsto {\sim _{\mathcal {C}}}$ . Следовательно, эти два определения эквивалентны. Допуск транзитивен как бинарное отношение тогда и только тогда, когда он является перегородкой в качестве покрытия . Таким образом, обе характеристики отношений конгруэнтности также согласуются.

Факторалгебры толерантности по отношениям

Позволять $(A,F)$ — алгебраическая структура и пусть $\sim$ быть толерантным отношением к $A$ . Предположим, что для каждого $n$ -арная операция $f\in F$ и $C_{1},\dots ,C_{n}\in A/{\sim }$ , есть уникальный $(f/{\sim })(C_{1},\dots ,C_{n})\in A/{\sim }$ такой, что

\{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})

Тогда это дает естественное определение факторалгебры

(A/{\sim },F/{\sim })

из $(A,F)$ над $\sim$ . В случае конгруэнтных отношений всегда выполняется условие единственности и определенная здесь факторалгебра совпадает с обычной.

Основное отличие от отношений конгруэнтности состоит в том, что для отношения толерантности условие единственности может не выполняться, и даже если это не так, факторалгебра не может наследовать тождества, определяющие многообразие , которое $(A,F)$ принадлежит многообразию, так что факторалгебра может снова не стать членом многообразия. Поэтому для разнообразия ${\mathcal {V}}$ алгебраических структур , мы можем рассмотреть следующие два условия. ^[4]

(Факторичность допуска) для любого $(A,F)\in {\mathcal {V}}$ и любые отношения толерантности $\sim$ на $(A,F)$ , условие единственности верно, так что фактор-алгебра $(A/{\sim },F/{\sim })$ определяется.
(Факторабельность с сильным допуском) для любого $(A,F)\in {\mathcal {V}}$ и любые отношения толерантности $\sim$ на $(A,F)$ , условие единственности истинно, и $(A/{\sim },F/{\sim })\in {\mathcal {V}}$ .

Каждый сорт, допускающий факторную устойчивость, является факторизуемым допуском, но не наоборот.

Примеры [ править ]

Наборы [ править ]

Множество , — это алгебраическая структура вообще не содержащая операций. В этом случае отношения толерантности представляют собой просто рефлексивные симметричные отношения , и тривиально то, что разнообразие множеств сильно факторизуется толерантностью.

Группы [ править ]

В группе каждое отношение толерантности является отношением конгруэнтности . В частности, это верно для всех алгебраических структур , которые являются группами, когда некоторые из их операций забыты, например кольца , векторные пространства , модули , булевы алгебры и т. д. ^[6]^{: 261–262} Следовательно, многообразия групп , колец , векторных пространств , модулей и булевых алгебр также тривиально факторизуемы с сильной толерантностью.

Решетки [ править ]

За толерантное отношение $\sim$ на решетке $L$ , каждый набор в $L/{\sim }$ является выпуклой подрешеткой $L$ . Таким образом, для всех $A\in L/{\sim }$ , у нас есть

A=\mathop {\uparrow } A\cap \mathop {\downarrow } A

В частности, имеют место следующие результаты.

$a\sim b$ тогда и только тогда, когда $a\vee b\sim a\wedge b$ .
Если $a\sim b$ и $a\leq c,d\leq b$ , затем $c\sim d$ .

Разнообразие решеток сильно зависит от допуска. То есть для любой решетки $(L,\vee _{L},\wedge _{L})$ и любые отношения толерантности $\sim$ на $L$ , для каждого $A,B\in L/{\sim }$ существуют уникальные $A\vee _{L/{\sim }}B,A\wedge _{L/{\sim }}B\in L/{\sim }$ такой, что

\{a\vee _{L}b\colon a\in A,\;b\in B\}\subseteq A\vee _{L/{\sim }}B

\{a\wedge _{L}b\colon a\in A,\;b\in B\}\subseteq A\wedge _{L/{\sim }}B

и факторалгебра

(L/{\sim },\vee _{L/{\sim }},\wedge _{L/{\sim }})

решетка . снова ^[7]^[8]^[9]^{: 44, Теорема 22}

В частности, мы можем формировать фактор-решетки дистрибутивных решеток и модулярных решеток по отношениям толерантности. Однако, в отличие от отношений конгруэнтности , фактор-решетки не обязательно должны быть снова дистрибутивными или модулярными. Другими словами, разновидности дистрибутивных решеток и модульных решеток факторизуемы по допускам, но не сильно факторизуемы. ^[7]^: 40^[4] Действительно, каждое подмногообразие многообразия решеток толерантно факторизуемо, и единственным сильно толерантным подмногообразием, отличным от него самого, является тривиальное подмногообразие (состоящее из одноэлементных решеток). ^[7]^: 40 Это связано с тем, что каждая подрешетке факторрешетки решетка изоморфна по отношению толерантности подрешетки прямого произведения двухэлементных решеток. ^[7]^{: 40, Теорема 3}

См. также [ править ]

Отношение зависимости
Квазитранзитивное отношение - обобщение для формализации безразличия в теории социального выбора.
Грубый набор

Ссылки [ править ]

^ Кирнс, Кейт; Поцелуй, Эмиль В. (2013). Форма конгруэнтных решеток . Американское математическое соц. п. 20. ISBN 978-0-8218-8323-5 .
^ Сосинский, Алексей (1 февраля 1986 г.). «Теория пространства толерантности и некоторые приложения» . Acta Applicandae Mathematicae . 5 (2): 137–167. дои : 10.1007/BF00046585 . S2CID 119731847 .
^ Пуанкаре, Х. (1905). Наука и гипотеза (с предисловием под ред. Дж. Лармора). Нью-Йорк: 3 East 14th Street: The Walter Scott Publishing Co., Ltd., стр. 22–23 . {{cite book}}: CS1 maint: местоположение ( ссылка )
^ Jump up to: Перейти обратно: ^а ^б ^с Обвиняй, Иван; Раделечки, Шандор (2014). «Заметки о факторизуемых классах толерантности алгебр». Acta Scientiarum Mathematicarum 80 (3–4): 389–397. doi : 10.14232/actasm-012-861-x . ISSN 0001-6969 . МР 3307031 . S2CID 85560830 . Збл 1321.08002 .
^ Чайда, Иван; Нидерле, Йозеф; Зелинка, Богдан (1976). «Об условиях существования совместимых допусков» . Чехословацкий математический журнал . 26 (101): 304–311. дои : 10.21136/CMJ.1976.101403 . ISSN 0011-4642 . МР 0401561 . Збл 0333.08006 .
^ Шейн, Борис М. (1987). «Полугруппы отношений толерантности» . Дискретная математика . 64 : 253–262. дои : 10.1016/0012-365X(87)90194-4 . ISSN 0012-365X . МР 0887364 . Збл 0615.20045 .
^ Jump up to: Перейти обратно: ^а ^б ^с ^д Чедли, Габор (1982). «Факторные решетки по допускам». Журнал математических наук 44 : 35–42. ISSN 0001-6969 . МР 0660510 Збл 0484.06010 .
^ Гретцер, Джордж; Венцель, GH (1990). «Заметки о соотношениях допусков решеток». Acta Scientiarum Mathematicarum . 54 (3–4): 229–240. ISSN 0001-6969 . МР 1096802 . Збл 0727.06011 .
^ Гретцер, Джордж (2011). Теория решеток: Основание . Базель: Спрингер. дои : 10.1007/978-3-0348-0018-1 . ISBN 978-3-0348-0017-4 . LCCN 2011921250 . МР 2768581 . Збл 1233.06001 .

Дальнейшее чтение [ править ]

Герасин С.Н., Шляхов В.В., Яковлев С.В. 2008. Накрытия множеств и отношения толерантности. Кибернетика и сис. Анальный. 44, 3 (май 2008 г.), 333–340. дои : 10.1007/s10559-008-9007-y
Гриневецкий, К. 1991, Отношения толерантности , ФОРМАЛИЗОВАННАЯ МАТЕМАТИКА, Том. 2, № 1, январь – февраль 1991 г.

[1] Кирнс, Кейт; Поцелуй, Эмиль В. (2013). Форма конгруэнтных решеток . Американское математическое соц. п. 20. ISBN 978-0-8218-8323-5 .

[2] Сосинский, Алексей (1 февраля 1986 г.). «Теория пространства толерантности и некоторые приложения» . Acta Applicandae Mathematicae . 5 (2): 137–167. дои : 10.1007/BF00046585 . S2CID 119731847 .

[3] Пуанкаре, Х. (1905). Наука и гипотеза (с предисловием под ред. Дж. Лармора). Нью-Йорк: 3 East 14th Street: The Walter Scott Publishing Co., Ltd., стр. 22–23 . {{cite book}}: CS1 maint: местоположение ( ссылка )

[ChajdaRadeleczki-4] Jump up to: Перейти обратно: ^а ^б ^с Обвиняй, Иван; Раделечки, Шандор (2014). «Заметки о факторизуемых классах толерантности алгебр». Acta Scientiarum Mathematicarum 80 (3–4): 389–397. doi : 10.14232/actasm-012-861-x . ISSN 0001-6969 . МР 3307031 . S2CID 85560830 . Збл 1321.08002 .

[ChajdaNiederle-5] Чайда, Иван; Нидерле, Йозеф; Зелинка, Богдан (1976). «Об условиях существования совместимых допусков» . Чехословацкий математический журнал . 26 (101): 304–311. дои : 10.21136/CMJ.1976.101403 . ISSN 0011-4642 . МР 0401561 . Збл 0333.08006 .

[Schein-6] Шейн, Борис М. (1987). «Полугруппы отношений толерантности» . Дискретная математика . 64 : 253–262. дои : 10.1016/0012-365X(87)90194-4 . ISSN 0012-365X . МР 0887364 . Збл 0615.20045 .

[Czédli-7] Jump up to: Перейти обратно: ^а ^б ^с ^д Чедли, Габор (1982). «Факторные решетки по допускам». Журнал математических наук 44 : 35–42. ISSN 0001-6969 . МР 0660510 Збл 0484.06010 .

[GrätzerWenzel-8] Гретцер, Джордж; Венцель, GH (1990). «Заметки о соотношениях допусков решеток». Acta Scientiarum Mathematicarum . 54 (3–4): 229–240. ISSN 0001-6969 . МР 1096802 . Збл 0727.06011 .

[Grätzer-9] Гретцер, Джордж (2011). Теория решеток: Основание . Базель: Спрингер. дои : 10.1007/978-3-0348-0018-1 . ISBN 978-3-0348-0017-4 . LCCN 2011921250 . МР 2768581 . Збл 1233.06001 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]