Toleransförhållande

I universell algebra och gitterteori är en toleransrelation på en algebraisk struktur en reflexiv symmetrisk relation som är kompatibel med strukturens alla funktioner. Således är en tolerans som en kongruens , förutom att antagandet om transitivitet slopas. På en uppsättning , en algebraisk struktur med tom familj av operationer, är toleransrelationer helt enkelt reflexiva symmetriska relationer. En mängd som har en toleransrelation kan beskrivas som ett toleransutrymme . Toleransrelationer är ett praktiskt allmänt verktyg för att studera fenomen som inte kan urskiljas . Vikten av dem för matematik hade först erkänts av Poincaré .

Definitioner

En toleransrelation på en algebraisk struktur $(A,F)$ definieras vanligtvis som en reflexiv symmetrisk relation på $A$ som är kompatibel med varje operation i $F$ . En toleransrelation kan också ses som en täckning av $A$ som uppfyller vissa villkor. De två definitionerna är likvärdiga, eftersom för en fast algebraisk struktur är toleransförhållandena i de två definitionerna i en-till-en-överensstämmelse . Toleransrelationerna på en algebraisk struktur $(A,F)$ bildar ett algebraiskt gitter $\operatorname {Tolr} (A)$ under inkludering. Eftersom varje kongruensrelation är en toleransrelation, är kongruensgittret $\operatorname {Cong} (A)}$$\operatorname {Tolr} ( A)$ en delmängd av toleransgittret , men $\operatorname {Cong} (A)$ är inte nödvändigtvis ett subgitter till $\operatorname {Tolr} (A)$ .

Som binära relationer

En toleransrelation på en algebraisk struktur $(A,F)$ är en binär relation $\sim$ på $A$ som uppfyller följande villkor.

• ( Reflexivitet ) a $\displaystyle a\sim a}$ för alla $a\in A$
• ( Symmetri ) om $a\sim b$ så $b\sim a$ för alla $a,b\in A$
• ( Kompatibilitet ) för varje $n$ -är operation $f\in F$ och ${\displaystyle a_{1} ,\dots ,a_{n},b_{1},\dots ,b_{n}\in A} ,$ om $a_{i}\sim b_{i}$ för varje $i=1,\dots ,n$ sedan $f(a_{1},\ prickar ,a_{n})\sim f(b_{1},\dots ,b_{n})$ . Det vill säga mängden $\{(a,b)\colon a\sim b\}$ är en subalgebra till den direkta produkten $A^{ 2}$ av två $A$ .

En kongruensrelation är en toleransrelation som också är transitiv .

Som omslag

En toleransrelation på en algebraisk struktur $(A,F)$ är en cover ${\mathcal {C}}$ av $A$ som uppfyller följande tre villkor.

• För varje $C\in {\mathcal {C}}$ och ${\displaystyle {\mathcal {S}}\subseteq {\mathcal {C}}} ,$ om ${ \displaystyle \textstyle C\subseteq \bigcup {\mathcal {S}}}$ , sedan $\textstyle \bigcap {\mathcal {S}}\subseteq C$ .
  • I synnerhet är inga två distinkta element i ${\mathcal {C}}$ jämförbara. (För att se detta, ta ${\displaystyle {\mathcal {S}}=\{D\}} .$ )
• För varje $S\subseteq A$ , om $S$ inte ingår i någon uppsättning i ${\mathcal {C}}$ , så finns det en tvåelementsdelmängd $\{s,t\}\subseteq S$ så att $\{s,t\}$ inte ingår i någon uppsättning i ${ \mathcal {C}}$ .
• För varje $n$ -ary $f\in F$ och $C_{1},\dots ,C_{n}\in {\ mathcal {C}}$ , det finns en $(f/{\sim })(C_{1},\dots ,C_{n} )\in {\mathcal {C}}$ så att $\ {f(c_{1},\dots ,c_{n})\colon c_{i}\in C_{i}\}\subseteq (f/{\sim })(C_{1},\dots ,C_ {n})$ . (En sådan $(f/{\sim })(C_{1},\dots ,C_{n})$ behöver inte vara unik.)

Varje partition av $A$ uppfyller de två första villkoren, men inte omvänt. En kongruensrelation är en toleransrelation som också bildar en uppsättningspartition.

Likvärdighet mellan de två definitionerna

Låt $\sim$ vara en tolerans binär relation på en algebraisk struktur $(A,F)$ . Låt $A/{\sim }$ vara familjen av maximala delmängder $C\subseteq A$ så att $c\sim d$ för varje $c,d\in C$ . Med grafteoretiska termer $A/{\sim }$ mängden av alla maximala klick i grafen $(A,\sim )$ . Om $\sim$ är en kongruensrelation , är $A/{\sim }$ bara kvotuppsättningen av ekvivalensklasser . Då $A/{\sim }$ en omslag till $A$ och uppfyller alla tre villkoren i omslagsdefinitionen. (Det sista villkoret visas med Zorns lemma .) Omvänt, låt ${\mathcal {C}}$ vara en omslag till $A$ och anta att ${\mathcal {C}}$ bildar en tolerans på $A$ . Betrakta en binär relation $\sim _{\mathcal {C}}$ på $A$ för vilken $a\sim _{\mathcal {C}}b$ om och endast om $a,b\in C$ för vissa $C\in {\mathcal {C}}$ . Då $\sim _{\mathcal {C}}$ en tolerans på $A$ som en binär relation . Kartan ${\sim }\mapsto A/{\sim }$ är en en-till-en-överensstämmelse mellan toleranserna som binära relationer och som omslag vars invers är ${\mathcal {C}}\mapsto {\sim _{\mathcal {C}}}$ . Därför är de två definitionerna likvärdiga. En tolerans är transitiv som en binär relation om och endast om den är en partition som ett omslag . Således överensstämmer också de två karaktäriseringarna av kongruensrelationer .

Quotientalgebror över toleransrelationer

Låt $(A,F)$ vara en algebraisk struktur och låt $\sim$ vara en toleransrelation på $A$ . Antag att för varje $n$ -är operation $f\in F$ och $C_{1},\dots ,C_{ n}\i A/{\sim }$ , det finns en unik $(f/{\sim })(C_{1} ,\dots ,C_{n})\in A/{\sim }$ så att

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

Då ger detta en naturlig definition av kvotalgebra

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

av $(A,F)$ över $\sim$ . När det gäller kongruensrelationer gäller alltid unikhetsvillkoret och den här definierade kvotalgebran sammanfaller med den vanliga.

En huvudskillnad från kongruensrelationer är att för en toleransrelation kan unikhetsvillkoret misslyckas, och även om det inte gör det, kanske kvotalgebra inte ärver de identiteter som definierar varieteten som ( A , $(A,F) }$ tillhör, så att kvotalgebra kan misslyckas med att vara medlem av sorten igen. Därför, för en mängd ${\mathcal {V}}$ av algebraiska strukturer , kan vi överväga följande två villkor.

• (Toleransfaktorerbarhet) för alla $(A,F)\in {\mathcal {V}}$ och alla toleransrelationer $\sim$ på ${\ displaystyle (A,F)}$ , unikhetsvillkoret är sant, så att kvotalgebra $(A/{\sim },F/{\sim })$ definieras.
• (Stark toleransfaktorabilitet) för alla $(A,F)\in {\mathcal {V}}$ och alla toleransrelationer $\sim$ på ${ \displaystyle (A,F)}$ , unikhetsvillkoret är sant, och $(A/{\sim },F/{\sim })\i {\mathcal {V}}$ .

Varje starkt toleransfaktorbar sort är toleransfaktorbar, men inte vice versa.

Exempel

Uppsättningar

En uppsättning är en algebraisk struktur utan några operationer alls. I det här fallet är toleransrelationer helt enkelt reflexiva symmetriska relationer och det är trivialt att variationen av mängder är starkt toleransfaktorerbar.

Grupper

På en grupp är varje toleransrelation en kongruensrelation . I synnerhet gäller detta för alla algebraiska strukturer som är grupper när några av deras operationer glöms bort, t.ex. ringar , vektorrum , moduler , booleska algebror etc. Därför är variationerna av grupper , ringar , vektorrum , moduler och booleska algebror är också starkt toleransfaktorerbara trivialt.

Galler

För en toleransrelation $\sim$ på ett gitter ${\displaystyle L} är$ varje uppsättning i $L/{\sim }$ ett konvext subgitter av $L$ . För alla $A\in L/{\sim }$ har vi alltså

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

I synnerhet gäller följande resultat.

• $a\sim b$ om och bara om $a\vee b\sim a\wedge b$ .
• Om $a\sim b$ och $a\leq c,d\leq b$ , då $c\sim d$ .

Variationen av gitter är starkt toleransfaktorerbar. Det vill säga givet valfritt gitter $(L,\vee _{L},\wedge _{L})$ och eventuella toleransrelationer $\sim$ på ${ \displaystyle L}$ , för varje $A,B\in L/{\sim }$ finns det unika ${ \displaystyle A\vee _{L/{\sim }}B,A\wedge _{L/{\sim }}B\in L/{\sim }} så$ att

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

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

och kvotalgebra

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

är ett galler igen.

I synnerhet kan vi bilda kvotgitter av distributiva gitter och modulära gitter över toleransrelationer. Men till skillnad från fallet med kongruensrelationer behöver kvotgittren inte vara distributiva eller modulära igen. Med andra ord är varianterna av distributiva gitter och modulära gitter toleransfaktorerbara, men inte starkt toleransfaktorerbara. I själva verket är varje subvarietet av variationen av gitter toleransfaktorerbar, och den enda starkt toleransfaktorerbara subvarianten förutom sig själv är den triviala subvarieten (bestående av ettelementsgitter). Detta beror på att varje gitter är isomorft till ett subgitter av kvotgittret över ett toleransförhållande för ett subgitter av en direkt produkt av tvåelementsgitter.

Se även

• Beroenderelation
• Kvasitransitiv relation — en generalisering för att formalisera likgiltighet i teori om sociala val
• Grovt set

Vidare läsning

• Gerasin, SN, Shlyakhov, VV och Yakovlev, SV 2008. Ställbeklädnader och toleransförhållanden. Cybernetik och sys. Anal. 44, 3 (maj 2008), 333–340. doi : 10.1007/s10559-008-9007-y
• Hryniewiecki, K. 1991, Relations of Tolerance , FORMALIZED MATHEMATICS, Vol. 2, nr 1, januari–februari 1991.