Toleranzbeziehung

In der universellen Algebra und Verbandstheorie ist eine Toleranzrelation auf einer algebraischen Struktur eine reflexive symmetrische Relation , die mit allen Operationen der Struktur kompatibel ist. Eine Toleranz ist somit vergleichbar mit einer Kongruenz , allerdings ohne die Voraussetzung der Transitivität . ^{[ 1 ]} Auf einer Menge , einer algebraischen Struktur mit leerer Operationsfamilie, sind Toleranzrelationen einfach reflexive symmetrische Relationen. Eine Menge, die eine Toleranzrelation besitzt, kann als Toleranzraum beschrieben werden . ^{[ 2 ]} Toleranzrelationen bieten ein praktisches allgemeines Werkzeug zur Untersuchung von Ununterscheidbarkeitsphänomenen . Ihre Bedeutung für die Mathematik wurde erstmals von Poincaré erkannt . ^{[ 3 ]}

Eine Toleranzrelation auf einer algebraischen Struktur ist üblicherweise eine reflexive, symmetrische Relation , die mit jeder Operation in kompatibel ist . Eine Toleranzrelation kann auch als Überdeckung von aufgefasst werden , die bestimmte Bedingungen erfüllt. Die beiden Definitionen sind äquivalent, da für eine feste algebraische Struktur die Toleranzrelationen in beiden Definitionen bijektiv sind . Die Toleranzrelationen auf einer algebraischen Struktur bilden unter Inklusion einen algebraischen Verband . Da jede Kongruenzrelation eine Toleranzrelation ist, ist der Kongruenzverband eine Teilmenge des Toleranzverbandes , aber nicht notwendigerweise ein Unterverband von . ^{[ 4 ]}${\displaystyle (A,F)}$${\displaystyle A}$${\displaystyle F}$${\displaystyle A}$${\displaystyle (A,F)}$${\displaystyle \operatorname {Tolr} (A)}$${\displaystyle \operatorname {Cong} (A)}$${\displaystyle \operatorname {Tolr} (A)}$${\displaystyle \operatorname {Cong} (A)}$${\displaystyle \operatorname {Tolr} (A)}$

Eine Toleranzrelation auf einer algebraischen Struktur ist eine binäre Relation , die die folgenden Bedingungen erfüllt. ${\displaystyle (A,F)}$${\displaystyle \sim }$${\displaystyle A}$

• ( Reflexivität ) für alle${\displaystyle a\sim a}$${\displaystyle a\in A}$
• ( Symmetrie ) Wenn dann für alle${\displaystyle a\sim b}$${\displaystyle b\sim a}$${\displaystyle a,b\in A}$
• ( Kompatibilität ) für jede -äre Operation und , wenn für jedes dann . Das heißt, die Menge ist eine Unteralgebra des direkten Produkts zweier .${\displaystyle n}$${\displaystyle f\in F}$${\displaystyle a_{1},\dots ,a_{n},b_{1},\dots ,b_{n}\in A}$${\displaystyle a_{i}\sim b_{i}}$${\displaystyle i=1,\dots ,n}$${\displaystyle f(a_{1},\dots ,a_{n})\sim f(b_{1},\dots ,b_{n})}$${\displaystyle \{(a,b)\colon a\sim b\}}$${\displaystyle A^{2}}$${\displaystyle A}$

Eine Kongruenzrelation ist eine Toleranzrelation, die auch transitiv ist .

Eine Toleranzrelation auf einer algebraischen Struktur ist eine Überdeckung , die die folgenden drei Bedingungen erfüllt. ^{[ 5 ] : 307, Satz 3} ${\displaystyle (A,F)}$${\displaystyle {\mathcal {C}}}$${\displaystyle A}$

• Für jedes und , wenn , dann . ${\displaystyle C\in {\mathcal {C}}}$${\displaystyle {\mathcal {S}}\subseteq {\mathcal {C}}}$${\displaystyle \textstyle C\subseteq \bigcup {\mathcal {S}}}$${\displaystyle \textstyle \bigcap {\mathcal {S}}\subseteq C}$
  • Insbesondere sind keine zwei unterschiedlichen Elemente von vergleichbar. (Um dies zu sehen, betrachten Sie .)${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {S}}=\{D\}}$
• Für jedes , wenn nicht in irgendeiner Menge in enthalten ist , dann gibt es eine zweielementige Teilmenge , so dass nicht in irgendeiner Menge in enthalten ist .${\displaystyle S\subseteq A}$${\displaystyle S}$${\displaystyle {\mathcal {C}}}$${\displaystyle \{s,t\}\subseteq S}$${\displaystyle \{s,t\}}$${\displaystyle {\mathcal {C}}}$
• Für jedes -äre und gibt es ein solches, dass . (Ein solches muss nicht eindeutig sein.)${\displaystyle n}$${\displaystyle f\in F}$${\displaystyle C_{1},\dots ,C_{n}\in {\mathcal {C}}}$${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})\in {\mathcal {C}}}$${\displaystyle \{f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_{n})}$${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})}$

Jede Partition erfüllt die ersten beiden Bedingungen, aber nicht umgekehrt. Eine Kongruenzrelation ist eine Toleranzrelation, die auch eine Mengenpartition bildet. ${\displaystyle A}$

Sei eine Toleranz -Binärrelation auf einer algebraischen Struktur . Sei die Familie der maximalen Teilmengen , sodass für jedes gilt. Graphentheoretisch ausgedrückt ist die Menge aller maximalen Cliquen des Graphen . Ist eine Kongruenzrelation , so ist die Quotientenmenge der Äquivalenzklassen . Dann ist eine Überdeckung von und erfüllt alle drei Bedingungen der Überdeckungsdefinition. (Die letzte Bedingung wird mithilfe des Lemmas von Zorn gezeigt .) Umgekehrt sei eine Überdeckung von und sei eine Toleranz auf . Betrachten wir eine Binärrelation auf , für die genau dann gilt, wenn für ein gilt . Dann ist eine Toleranz auf als Binärrelation . Die Abbildung ist eine Bijektion zwischen den Toleranzen als Binärrelationen und als Überdeckungen , deren Inverse ist . Daher sind die beiden Definitionen äquivalent. Eine Toleranz ist genau dann transitiv als Binärrelation , wenn sie als Überdeckung eine Partition ist . Somit stimmen auch die beiden Charakterisierungen von Kongruenzrelationen überein. ${\displaystyle \sim }$${\displaystyle (A,F)}$${\displaystyle A/{\sim }}$${\displaystyle C\subseteq A}$${\displaystyle c\sim d}$${\displaystyle c,d\in C}$${\displaystyle A/{\sim }}$${\displaystyle (A,\sim )}$${\displaystyle \sim }$${\displaystyle A/{\sim }}$${\displaystyle A/{\sim }}$${\displaystyle A}$${\displaystyle {\mathcal {C}}}$${\displaystyle A}$${\displaystyle {\mathcal {C}}}$${\displaystyle A}$${\displaystyle \sim _{\mathcal {C}}}$${\displaystyle A}$${\displaystyle a\sim _{\mathcal {C}}b}$${\displaystyle a,b\in C}$${\displaystyle C\in {\mathcal {C}}}$${\displaystyle \sim _{\mathcal {C}}}$${\displaystyle A}$${\displaystyle {\sim }\mapsto A/{\sim }}$${\displaystyle {\mathcal {C}}\mapsto {\sim _{\mathcal {C}}}}$

Sei eine algebraische Struktur und sei eine Toleranzrelation auf . Angenommen, für jede -äre Operation und existiert ein eindeutiges , sodass ${\displaystyle (A,F)}$${\displaystyle \sim }$${\displaystyle A}$${\displaystyle n}$${\displaystyle f\in F}$${\displaystyle C_{1},\dots ,C_{n}\in A/{\sim }}$${\displaystyle (f/{\sim })(C_{1},\dots ,C_{n})\in A/{\sim }}$

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

Dies liefert dann eine natürliche Definition der Quotientenalgebra.

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

von über . Im Falle von Kongruenzrelationen ist die Eindeutigkeitsbedingung stets erfüllt, und die hier definierte Quotientenalgebra stimmt mit der üblichen überein. ${\displaystyle (A,F)}$${\displaystyle \sim }$

Ein wesentlicher Unterschied zu Kongruenzrelationen besteht darin, dass die Eindeutigkeitsbedingung für eine Toleranzrelation verletzt sein kann. Selbst wenn sie nicht verletzt wird, erbt die Quotientenalgebra möglicherweise nicht die Identitäten der Varietät , zu der sie gehört, sodass die Quotientenalgebra unter Umständen nicht mehr Element dieser Varietät ist. Daher können wir für eine Varietät algebraischer Strukturen die folgenden zwei Bedingungen betrachten. ^{[ 4 ]}${\displaystyle (A,F)}$${\displaystyle {\mathcal {V}}}$

• (Toleranzfaktorisierbarkeit) für jedes und jede Toleranzrelation auf , ist die Eindeutigkeitsbedingung wahr, sodass die Quotientenalgebra definiert ist.${\displaystyle (A,F)\in {\mathcal {V}}}$${\displaystyle \sim }$${\displaystyle (A,F)}$${\displaystyle (A/{\sim },F/{\sim })}$
• (Starke Toleranzfaktorisierbarkeit) für jedes und jede Toleranzrelation auf , die Eindeutigkeitsbedingung ist wahr, und .${\displaystyle (A,F)\in {\mathcal {V}}}$${\displaystyle \sim }$${\displaystyle (A,F)}$${\displaystyle (A/{\sim },F/{\sim })\in {\mathcal {V}}}$

Jede stark toleranzfaktorisierbare Sorte ist toleranzfaktorisierbar, aber nicht umgekehrt.

Eine Menge ist eine algebraische Struktur ohne jegliche Operationen. In diesem Fall sind Toleranzrelationen einfach reflexive symmetrische Relationen , und es ist trivial, dass die Varietät der Mengen stark toleranzfaktorisierbar ist.

Auf einer Gruppe ist jede Toleranzrelation eine Kongruenzrelation . Dies gilt insbesondere für alle algebraischen Strukturen , die Gruppen sind, wenn einige ihrer Operationen weggelassen werden, z. B. Ringe , Vektorräume , Moduln , Boolesche Algebren usw. ^{[ 6 ] : 261–262.} Daher sind auch die Varietäten von Gruppen , Ringen , Vektorräumen , Moduln und Booleschen Algebren trivial stark toleranzfaktorisierbar.

Für eine Toleranzrelation auf einem Verband ist jede Menge in ein konvexer Unterverband von . Somit gilt für alle : ${\displaystyle \sim }$${\displaystyle L}$${\displaystyle L/{\sim }}$${\displaystyle L}$${\displaystyle A\in L/{\sim }}$

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

Insbesondere gelten die folgenden Ergebnisse.

• ${\displaystyle a\sim b}$nur dann, wenn .${\displaystyle a\vee b\sim a\wedge b}$
• Wenn und , dann .${\displaystyle a\sim b}$${\displaystyle a\leq c,d\leq b}$${\displaystyle c\sim d}$

Die Varietät der Verbände ist stark toleranzfaktorisierbar. Das heißt, zu jedem Verband und jeder Toleranzrelation auf gibt es für jedes eindeutige , sodass ${\displaystyle (L,\vee _{L},\wedge _{L})}$${\displaystyle \sim }$${\displaystyle L}$${\displaystyle A,B\in L/{\sim }}$${\displaystyle A\vee _{L/{\sim }}B,A\wedge _{L/{\sim }}B\in L/{\sim }}$

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

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

und die Quotientenalgebra

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

ist wieder ein Gitter . ^{[ 7 ] [ 8 ] [ 9 ] : 44, Satz 22}

Insbesondere können wir Quotientenverbände von distributiven Verbänden und modularen Verbänden über Toleranzrelationen bilden. Anders als im Fall von Kongruenzrelationen müssen die Quotientenverbände jedoch nicht wieder distributiv oder modular sein. Mit anderen Worten: Die Varietäten der distributiven und modularen Verbände sind toleranzfaktorisierbar, aber nicht stark toleranzfaktorisierbar. ^{[ 7 ] : 40 [ 4 ]} Tatsächlich ist jede Untervarietät der Verbandsvarietät toleranzfaktorisierbar, und die einzige stark toleranzfaktorisierbare Untervarietät neben der Varietät selbst ist die triviale Untervarietät (bestehend aus einelementigen Verbänden). ^{[ 7 ] : 40} Dies liegt daran, dass jeder Verband isomorph zu einem Unterverband des Quotientenverbandes über einer Toleranzrelation eines Unterverbandes eines direkten Produkts zweielementiger Verbände ist . ^{[ 7 ] : 40, Satz 3}

• Annäherung
• Abhängigkeitsbeziehung
• Quasitransitive Relation – eine Verallgemeinerung zur Formalisierung von Indifferenz in der Theorie der sozialen Wahl
• Grobes Set

• Gerasin, S. N., Shlyakhov, V. V. und Yakovlev, S. V. 2008. Mengenüberdeckungen und Toleranzrelationen. Cybernetics and Sys. Anal. 44, 3 (Mai 2008), 333–340. doi : 10.1007/s10559-008-9007-y
• Hryniewiecki, K. 1991, Toleranzverhältnisse , FORMALIZED MATHEMATICS, Vol. 2, Nr. 1, Januar–Februar 1991.