허용 관계

틀:위키데이터 속성 추적 보편 대수학과 격자 이론에서 허용 관계(틀:Llang)는 대수 구조의 연산과 호환되는 반사 대칭 관계이다. 즉, 합동 관계에서 추이성 조건을 없애 얻는 개념이다. 허용 관계에 대한 몫 대수는 합동 관계에 대한 몫 대수를 일반화한다. 합동 관계와 달리, 허용 관계에 대한 몫 대수는 존재하지 않을 수 있으며, 몫 대수는 (만약 존재한다면) 항등식들을 보존할 필요가 없다.

정의

대수 구조 위의 허용 관계는 통상적으로 모든 연산들과 호환되는 반사 대칭 관계로 정의되며, 특별한 조건을 만족시키는 덮개로 정의할 수도 있다. 이 두 정의는 서로 동치이다. 부호수 $F$의 대수 구조 $(A,F_A)$ 위의 허용 관계들은 포함 관계에 따라 대수적 격자 $\mathrm{Tolr}(A)$를 이룬다. 합동 관계 격자 $\mathrm{Cong}(A)$는 허용 관계 격자 $\mathrm{Tolr}(A)$의 부분 순서 집합이지만, 부분 격자일 필요는 없다.

이항 관계를 통한 정의

부호수 $F$의 대수 구조 $(A,F_A)$ 위의 허용 관계는 다음 조건을 만족시키는 $A$ 위의 이항 관계 $\sim$이다.

• (반사성) 임의의 $a\in A$에 대하여, $a\sim a$
• (대칭성) 임의의 $a,b\in A$에 대하여, 만약 $a\sim b$라면, $b\sim a$
• (연산과의 호환) $\{(a,b):a\sim b\}$는 두 $A$의 직접곱 $A^2$의 부분 대수이다. 즉, 임의의 $n$항 연산 $f\in F$ 및 $a_1,\dots ,a_n,b_1,\dots ,b_n\in A$에 대하여, 만약 임의의 $i=1,\dots ,n$에 대하여 $a_i\sim b_i$라면, $f_A(a_1,\dots ,a_n)\sim f_A(b_1,\dots ,b_n)$.

합동 관계는 추이적 허용 관계이다.

덮개를 통한 정의

부호수 $F$의 대수 구조 $(A,F_A)$ 위의 허용 관계는 다음 조건들을 만족시키는 $A$의 덮개 $𝒞\subseteq 𝒫(A)$이다.틀:Rp

• 임의의 $C\in 𝒞$ 및 $𝒮\subseteq 𝒞$에 대하여, 만약 $C\subseteq \bigcup 𝒮$라면, $\bigcap 𝒮\subseteq C$이다.
  • 특히, $𝒞$의 서로 다른 두 원소는 서로를 포함하지 않는다. (이 사실은 $𝒮=\{D\}$를 취하여 얻는다.)
• 임의의 $S\subseteq A$에 대하여, 만약 $S$가 $𝒞$의 원소의 부분 집합이 아니라면, $𝒞$의 원소의 부분 집합이 아닌 두 원소 집합 $\{s,t\}\subseteq S$가 존재한다.
• 임의의 $n$항 연산 $f\in F$ 및 $C_1,\dots ,C_n\in 𝒞$에 대하여, $f_A[C_1\times \cdots \times C_n]\subseteq f_{A/\sim }(C_1,\dots ,C_n)$인 $f_{A/\sim }(C_1,\dots ,C_n)\in 𝒞$가 존재한다. (이러한 $f_{A/\sim }(C_1,\dots ,C_n)$는 일반적으로 유일하지 않다.)

집합의 분할은 정의의 처음 두 조건을 만족시키지만, 그 역은 성립하지 않는다. 합동 관계는 집합의 분할을 이루는 허용 관계이다.

두 정의의 동치

이항 관계로서의 허용 관계와 덮개로서의 허용 관계의 정의는 서로 동치이다. 구체적으로, 부호수 $F$의 대수 구조 $(A,F_A)$ 위의 이항 관계 $\sim$가 허용 관계라고 하자. $A/\sim$이 다음 조건을 만족시키는 극대 부분 집합 $C\subseteq A$들의 집합이라고 하자.

• 임의의 $c,d\in C$에 대하여, $c\sim d$

그래프 이론의 용어를 사용하면, $A/\sim$은 그래프 $(A,\sim )$의 극대 클릭들의 집합이다. 합동 관계의 경우 이는 단순히 동치류들의 몫집합이다. 그렇다면, $A/\sim$는 $A$의 덮개이며, 덮개로서 허용 관계를 이룬다. (덮개 정의의 마지막 조건은 초른 보조정리를 사용하여 보일 수 있다.) 반대로, 허용 관계를 이루는 $(A,F_A)$의 덮개 $𝒞$가 주어졌을 때, 임의의 $a,b\in A$에 대하여

$a{\sim }_{𝒞}b⟺\mathrm{\exists }C\in 𝒞:a,b\in C$

라고 하자. 그렇다면, ${\sim }_{𝒞}$는 이항 관계로서 허용 관계를 이룬다. $\sim \mapsto A/\sim$과 $𝒞\mapsto {\sim }_{𝒞}$는 이항 관계로서의 허용 관계들과 덮개로서의 허용 관계들 사이의 일대일 대응이며, 서로 역함수이다. 따라서 두 정의는 서로 동치이다. 허용 관계가 이항 관계로서 동치 관계인 것은 덮개로서 집합의 분할인 것과 동치이다. 즉, 합동 관계의 두 가지 정의도 서로 일치한다.

허용 관계에 대한 몫 대수

부호수 $F$의 대수 구조 $(A,F_A)$ 위에 허용 관계 $\sim$이 주어졌다고 하자. 만약 임의의 $n$항 연산 $f\in F$ 및 $C_1,\dots ,C_n\in A/\sim$에 대하여,

$f_A[C_1\times \cdots \times C_n]\subseteq f_{A/\sim }(C_1,\dots ,C_n)$

인 $f_{A/\sim }(C_1,\dots ,C_n)$이 유일하게 존재한다면, 이는 자연스럽게 $(A,F_A)$의 $\sim$에 대한 몫 대수

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

를 정의한다. 합동 관계의 경우, 이러한 유일성 조건은 항상 만족되며, 정의된 몫 대수는 통상적인 몫 대수와 일치한다.

부호수 $F$의 대수 구조 다양체 $𝒱$가 다음 조건을 만족시키면, 허용 몫 가능 다양체(틀:Llang)라고 한다.

• 임의의 $(A,F_A)\in 𝒱$ 및 허용 관계 $\sim$ 및 $n$항 연산 $f\in F$ 및 $C_1,\dots ,C_n\in A/\sim$에 대하여, $f_A[C_1\times \cdots \times C_n]\subseteq f_{A/\sim }(C_1,\dots ,C_n)$인 유일한 $f_{A/\sim }(C_1,\dots ,C_n)$이 존재한다. (따라서, 몫 대수 $(A/\sim ,F_{A/\sim })$가 존재한다.)

부호수 $F$의 대수 구조 다양체 $𝒱$가 다음 두 조건을 만족시키면, 강하게 허용 몫 가능 다양체(틀:Llang)라고 한다.

• 허용 몫 가능 다양체이다.
• 임의의 $(A,F_A)\in 𝒱$ 및 허용 관계 $\sim$에 대하여, $(A/\sim ,F_{A/\sim })\in 𝒱$

모든 강하게 허용 몫 가능 다양체는 허용 몫 가능 다양체이지만, 그 역은 성립하지 않는다.

성질

만약 부호수 $F$의 대수 구조 $(A,F_A)$가 멱등 대수 구조라면 ($\mathrm{\forall }f\in F\mathrm{\forall }a\in A:f_A(a,\dots ,a)=a$), 임의의 허용 관계 $\sim$ 및 $C\in A/\sim$에 대하여, $C$는 $A$의 부분 대수이다.틀:Rp 틀:증명 임의의 $n$항 연산 $f\in F$ 및 $c_1,\dots ,c_n\in C$에 대하여, $f_A(c_1,\dots ,c_n)\in C$를 보이면 된다. 임의의 $c\in C$에 대하여, $c_i\sim c$($i=1,\dots ,n$)이므로,

$c=f_A(c,\dots ,c)\sim f_A(c_1,\dots ,c_n)$

이다. $C$의 극대성에 따라, $f_A(c_1,\dots ,c_n)\in C$이다. 틀:증명 끝

존재

부호수 $F$의 대수 구조 $(A,F_A)$가 다음 두 조건을 만족시킨다고 하자.

• $|A|\ge 3$
• $(A,F_A)$의 연산의 값이 될 수 없는 원소 $a\in A$가 존재한다.

그렇다면, $(A,F_A)$ 위에 합동 관계가 아닌 허용 관계가 존재한다.틀:Rp

합동 관계의 준동형 상

부호수 $F$의 대수 구조 $(A,F_A)$ 및 전사 준동형 $\varphi :(A,F_A)\to (B,F_B)$가 주어졌다고 하자. $A$ 위에 합동 관계 $R$가 주어졌을 때, $B$ 위에 다음 이항 관계 $\varphi (R)$를 정의하자.

$a{\sim }_{\varphi (R)}b⟺\mathrm{\exists }{a}^{\prime }\in {\varphi }^{-1}(a)\mathrm{\exists }{b}^{\prime }\in {\varphi }^{-1}(b):a^{\prime }{\sim }_R{b}^{\prime }(a,b\in B)$

그렇다면, $\varphi (R)$는 $B$ 위의 허용 관계이다.

강하게 허용 몫 가능 다양체 $𝒱$에서, 모든 허용 관계는 합동 관계의 준동형에 대한 상이다.

예

집합

집합은 $F=\varnothing$인 대수 구조이다. 집합 위의 허용 관계는 단순히 반사 대칭 관계가 된다. 따라서, 집합의 다양체는 자명하게 강하게 허용 몫 가능 다양체를 이룬다.

군

군 위에서, 모든 허용 관계는 합동 관계이다. 특히, 환, 벡터 공간, 가군, 불 대수 등의, 일부 연산을 잊었을 때 군을 이루는 대수 구조들 위에서도 마찬가지다.틀:Rp 따라서, 이들의 다양체가 강하게 허용 몫 가능 다양체를 이룬다는 사실 역시 자명하다.

격자

격자 $L$ 위에 허용 관계 $\sim$이 주어졌을 때, $L/\sim$의 모든 원소는 $L$의 볼록 부분 격자를 이룬다. 따라서, 임의의 $A\in L/\sim$에 대하여,

$A=\uparrow A\cap \downarrow A$

이다. 특히,

• $a\sim b$일 필요충분조건은 $a\vee b\sim a\wedge b$이다.
• 만약 $a\sim b$이며, $a\le c,d\le b$라면, $c\sim d$이다.

틀:증명 만약 $a\sim b$라면,

$a\vee b=(a\vee b)\wedge a\sim (a\vee a)\wedge b=a\wedge b$

이다. 반대로, 만약 $a\vee b\sim a\wedge b$라면,

$a=a\vee (a\wedge b)\sim a\vee (a\vee b)=a\vee b$

이며, 마찬가지로

$b\sim a\vee b$

이다. 따라서,

$a=a\wedge (a\vee b)\sim (a\vee b)\wedge b=b$

이다.

만약 $a\sim b$이며, $a\le c,d\le b$라면,

$c=b\wedge c\sim a\wedge c=a$

이며, 마찬가지로

$d\sim a$

이다. 따라서,

$c=a\vee c\sim d\vee a=d$

이다.

모든 격자는 멱등 대수 구조이므로, 임의의 $A\in L/\sim$은 $L$의 부분 격자이다. 이제, $a,b\in A$, $c\in L$이며, $a\le c\le b$라고 하자. $A$의 극대성에 따라, $c\in A$를 보이려면, 임의의 $d\in A$에 대하여 $c\sim d$임을 보이는 것으로 족하다.

$a\wedge d\le c\wedge d\le c\vee d\le b\vee d$

이므로,

$a\wedge d\sim b\vee d$

를 보이면 족하다. $A$가 부분 격자이므로, $a\wedge d,b\vee d\in A$이며, 따라서 $a\wedge d\sim b\vee d$이다. 틀:증명 끝

격자의 다양체는 강하게 허용 몫 가능 다양체를 이룬다. 즉, 격자 $(L,{\vee }_L,{\wedge }_L)$ 위에 허용 관계 $\sim$이 주어졌을 때, 임의의 $A,B\in L/\sim$에 대하여,

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

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

인 유일한 $A{\vee }_{L/\sim }B,A{\wedge }_{L/\sim }B\in L/\sim$이 존재하며, 또한 몫 대수

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

는 다시 격자를 이룬다.틀:Rp 틀:증명 임의의 $A,B,C\in L/\sim$에 대하여 다음 네 명제를 보이는 것으로 족하다. (첫 번째와 두 번째, 세 번째와 네 번째 명제는 서로 쌍대이므로, 첫 번째와 세 번째만을 증명한다.)

• 만약 $\uparrow A=\uparrow B$라면, $A=B$이다.
• 만약 $\downarrow A=\downarrow B$라면, $A=B$이다.
• 만약 $\{a\vee b:a\in A,b\in B\}\subseteq C$라면, $\uparrow C=\uparrow A\cap \uparrow B$이다.
• 만약 $\{a\wedge b:a\in A,b\in B\}\subseteq C$라면, $\downarrow C=\downarrow A\cap \downarrow B$이다.

첫 번째 명제의 증명. $U=(\downarrow A{\vee }_{\mathrm{Ideal}(L)}\downarrow B)\cap \uparrow A=(\downarrow A{\vee }_{\mathrm{Ideal}(L)}\downarrow B)\cap \uparrow B$라고 하자 (${\vee }_{\mathrm{Ideal}(L)}$는 순서 아이디얼 격자에서의 상한). $A=\uparrow A\cap \downarrow A$, $B=\uparrow B\cap \downarrow B$이므로, $A\subseteq U$, $B\subseteq U$이다. $A$와 $B$의 극대성에 따라, 임의의 $u,u^{\prime }\in U$에 대하여 $u\sim u^{\prime }$임을 보이면 족하다. $u\le a\vee b$, $u^{\prime }\le a^{\prime }\vee b^{\prime }$, $a,a^{\prime }\in A$, $b,b^{\prime }\in B$이며, $x=u\wedge u^{\prime }\wedge a\wedge a^{\prime }\wedge b\wedge b^{\prime }$라고 하자. $x\le u,u^{\prime }\le a\vee a^{\prime }\vee b\vee b^{\prime }$이므로, $x\sim a\vee a^{\prime }\vee b\vee b^{\prime }$를 보이면 족하다. $x\le a,b$이므로 $x\in \downarrow A\cap \downarrow B$이다. 또한, $u,u^{\prime },a,a^{\prime }\in \uparrow A$, $u,u^{\prime },b,b^{\prime }\in \uparrow B$, $\uparrow A=\uparrow B$이므로 $x\in \uparrow A=\uparrow B$이다. 따라서, $x\in A\cap B$이다. $a\vee a^{\prime }\in A$, $b\vee b^{\prime }\in B$이므로 $x\sim a\vee a^{\prime }$, $x\sim b\vee b^{\prime }$이며, 따라서 $x\sim a\vee a^{\prime }\vee b\vee b^{\prime }$이다.

세 번째 명제의 증명. 우선, $\uparrow A\cap \uparrow B=\uparrow \{a\vee b:a\in A,b\in B\}\subseteq \uparrow C$이다. 이제, 임의의 $c\in C$에 대하여 $c\in \uparrow A\cap \uparrow B$임을 보이면 족하다. $c\in ̸\uparrow A$라고 가정하자. 임의의 $a\in A$와 $b\in B$를 취하자. 임의의 $x\in A$에 대하여, $x\vee a\vee b,c\in C$이므로 $x\vee a\vee b\sim c$이며, $x,a\in A$이므로 $x\vee a\sim x\wedge a$이다. 따라서, $x\vee a\sim x\wedge a\wedge c$이다. $x\vee a\ge x,a\wedge c\ge x\wedge a\wedge c$이므로, $x\sim a\wedge c$이다. $A$의 극대성에 따라, $a\wedge c\in A$이며, 따라서 $c\in \uparrow (a\wedge c)\subseteq \uparrow A$이다. 이는 모순이다. 틀:증명 끝 틀:증명 위 증명에 따라, 필터 격자와 순서 아이디얼 격자로 가는 자연스러운 단사 함수

$\uparrow :L/\sim \to \mathrm{Filter}(L)$

$\downarrow :L/\sim \to \mathrm{Ideal}(L)$

가 존재하며, 항상

$\uparrow (A{\vee }_{L/\sim }B)=\uparrow A\cap \uparrow B=\uparrow A{\wedge }_{\mathrm{Filter}(L)}\uparrow B$

$\downarrow (A{\wedge }_{L/\sim }B)=\downarrow A\cap \downarrow B=\downarrow A{\wedge }_{\mathrm{Ideal}(L)}\downarrow B$

가 성립한다. 따라서, $(L/\sim ,{\vee }_{L/\sim })$과 $(L/\sim ,{\wedge }_{L/\sim })$은 각각 가환 반군 $(\mathrm{Filter}(L),{\wedge }_{\mathrm{Filter}(L)})$ 및 $(\mathrm{Ideal}(L),{\wedge }_{\mathrm{Ideal}(L)})$의 부분 반군과 동형이다 (격자로서의 동형일 필요는 없다). 이제, 흡수 법칙을 보이는 일만 남았다. 쌍대성에 따라 두 흡수 법칙 가운데 하나

$A{\vee }_{L/\sim }(A{\wedge }_{L/\sim }B)=A$

만을 보여도 좋다. ${\wedge }_{L/\sim }$의 정의에 따라

$\uparrow (A{\wedge }_{L/\sim }B)\supseteq \uparrow \{a\wedge b:a\in A,b\in B\}=\uparrow A{\vee }_{\mathrm{Filter}(L)}\uparrow B\supseteq \uparrow A$

이므로,

$\uparrow (A{\vee }_{L/\sim }(A{\wedge }_{L/\sim }B))=\uparrow A\cap \uparrow (A{\wedge }_{L/\sim }B)=\uparrow A$

이다. 따라서 위 흡수 법칙은 참이다. 틀:증명 끝

특히, 분배 격자와 모듈러 격자는 임의의 허용 관계에 대하여 몫 격자를 취할 수 있다. 그러나, 이러한 몫 격자가 다시 분배 격자나 모듈러 격자가 될 필요는 없다. 즉, 분배 격자의 다양체와 모듈러 격자의 다양체는 허용 몫 가능 다양체이지만, 강하게 허용 몫 가능 다양체가 아니다.틀:Rp 사실, 격자 다양체의 모든 부분 다양체는 허용 몫 가능 다양체이지만, 격자 다양체의 강하게 허용 몫 가능 부분 다양체는 격자 다양체 전체와 자명한 (한 원소 격자로 구성된) 부분 다양체밖에 없다. 이는 모든 격자는 두 원소 격자들의 직접곱의 부분 격자의 허용 관계에 대한 몫 격자의 부분 격자와 동형이기 때문이다.틀:Rp

상대 여원 격자 위의 모든 허용 관계는 합동 관계이다.틀:Rp 반대로, 모든 허용 관계가 합동 관계인 분배 격자는 상대 여원 격자이다.틀:Rp

모든 크기 3 이상의 격자는, 합동 관계가 아닌 허용 관계가 존재하는 부분 격자를 갖는다.틀:Rp