허용 관계

보편 대수학과 격자 이론에서 **허용 관계**(tolerance relation)는 대수 구조의 연산과 호환되는 반사 대칭 관계이다. 즉, 합동 관계에서 추이성 조건을 없애 얻는 개념이다. 허용 관계에 대한 몫 대수는 합동 관계에 대한 몫 대수를 일반화한다. 합동 관계와 달리, 허용 관계에 대한 몫 대수는 존재하지 않을 수 있으며, 몫 대수는 (만약 존재한다면) 항등식들을 보존할 필요가 없다.
# 정의
대수 구조 위의 허용 관계는 통상적으로 모든 연산들과 호환되는 반사 대칭 관계로 정의되며, 특별한 조건을 만족시키는 덮개로 정의할 수도 있다. 이 두 정의는 서로 동치이다. 부호수 F의 대수 구조 (A,F_A) 위의 허용 관계들은 포함 관계에 따라 대수적 격자 \operatorname{Tolr}(A)를 이룬다. 합동 관계 격자 \operatorname{Cong}(A)는 허용 관계 격자 \operatorname{Tolr}(A)의 부분 순서 집합이지만, 부분 격자일 필요는 없다.s2cid=85560830
## 이항 관계를 통한 정의
부호수 F의 대수 구조 (A,F_A) 위의 **허용 관계**는 다음 조건을 만족시키는 A 위의 이항 관계 \sim이다. * (반사성) 임의의 a\in A에 대하여, a\sim a * (대칭성) 임의의 a,b\in A에 대하여, 만약 a\sim b라면, b\sim a * (연산과의 호환) \\{(a,b)\colon 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의 덮개 \mathcal C\subseteq\mathcal P(A)이다.12943307, Theorem 3 * 임의의 C\in\mathcal C 및 \mathcal S\subseteq\mathcal C에 대하여, 만약 \textstyle C\subseteq\bigcup\mathcal S라면, \textstyle\bigcap\mathcal S\subseteq C이다. ** 특히, \mathcal C의 서로 다른 두 원소는 서로를 포함하지 않는다. (이 사실은 \mathcal S=\\{D\\}를 취하여 얻는다.) * 임의의 S\subseteq A에 대하여, 만약 S가 \mathcal C의 원소의 부분 집합이 아니라면, \mathcal C의 원소의 부분 집합이 아닌 두 원소 집합 \\{s,t\\}\subseteq S가 존재한다. * 임의의 n항 연산 f\in F 및 C_1,\dots,C_n\in\mathcal C에 대하여, 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\mathcal C가 존재한다. (이러한 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)의 덮개 \mathcal C가 주어졌을 때, 임의의 a,b\in A에 대하여 :a\sim_{\mathcal C}b\iff\exist C\in\mathcal C\colon a,b\in C 라고 하자. 그렇다면, \sim_{\mathcal C}는 이항 관계로서 허용 관계를 이룬다. {\sim}\mapsto A/{\sim}과 \mathcal C\mapsto{\sim_{\mathcal C는 이항 관계로서의 허용 관계들과 덮개로서의 허용 관계들 사이의 일대일 대응이며, 서로 역함수이다. 따라서 두 정의는 서로 동치이다. 허용 관계가 이항 관계로서 동치 관계인 것은 덮개로서 집합의 분할인 것과 동치이다. 즉, 합동 관계의 두 가지 정의도 서로 일치한다.
## 허용 관계에 대한 몫 대수
부호수 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의 대수 구조 다양체 \mathcal V가 다음 조건을 만족시키면, **허용 몫 가능 다양체**(tolerance factorable variety)라고 한다. * 임의의 (A,F_A)\in\mathcal V 및 허용 관계 \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의 대수 구조 다양체 \mathcal V가 다음 두 조건을 만족시키면, **강하게 허용 몫 가능 다양체**(strongly tolerance factorable variety)라고 한다. * 허용 몫 가능 다양체이다. * 임의의 (A,F_A)\in\mathcal V 및 허용 관계 \sim에 대하여, (A/{\sim},F_{A/{\sim)\in\mathcal V 모든 강하게 허용 몫 가능 다양체는 허용 몫 가능 다양체이지만, 그 역은 성립하지 않는다.
# 성질
만약 부호수 F의 대수 구조 (A,F_A)가 멱등 대수 구조라면 (\forall f\in F\forall a\in A\colon f_A(a,\dots,a)=a), 임의의 허용 관계 \sim 및 C\in A/{\sim}에 대하여, C는 A의 부분 대수이다.308, Theorem 4 증명 임의의 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) 위에 합동 관계가 아닌 허용 관계가 존재한다.310, Theorem 8
## 합동 관계의 준동형 상
부호수 F의 대수 구조 (A,F_A) 및 전사 준동형 \phi\colon(A,F_A)\to(B,F_B)가 주어졌다고 하자. A 위에 합동 관계 R가 주어졌을 때, B 위에 다음 이항 관계 \phi(R)를 정의하자. :a\sim_{\phi(R)}b\iff\exist a'\in\phi^{-1}(a)\exist b'\in\phi^{-1}(b)\colon a'\sim_Rb'\qquad(a,b\in B) 그렇다면, \phi(R)는 B 위의 허용 관계이다. 강하게 허용 몫 가능 다양체 \mathcal V에서, 모든 허용 관계는 합동 관계의 준동형에 대한 상이다.arxiv=1207.1732
# 예

## 집합
집합은 F=\varnothing인 대수 구조이다. 집합 위의 허용 관계는 단순히 반사 대칭 관계가 된다. 따라서, 집합의 다양체는 자명하게 강하게 허용 몫 가능 다양체를 이룬다.
## 군
군 위에서, 모든 허용 관계는 합동 관계이다. 특히, 환, 벡터 공간, 가군, 불 대수 등의, 일부 연산을 잊었을 때 군을 이루는 대수 구조들 위에서도 마찬가지다.zbl=0615.20045261–262 따라서, 이들의 다양체가 강하게 허용 몫 가능 다양체를 이룬다는 사실 역시 자명하다.
## 격자
격자 L 위에 허용 관계 \sim이 주어졌을 때, 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\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_Lb\colon a\in A,\;b\in B\\}\subseteq A\vee_{L/{\simB :\\{a\wedge_Lb\colon a\in A,\;b\in B\\}\subseteq A\wedge_{L/{\simB 인 유일한 A\vee_{L/{\simB,A\wedge_{L/{\simB\in L/{\sim}이 존재하며, 또한 몫 대수 :(L/{\sim},\vee_{L/{\sim,\wedge_{L/{\sim) 는 다시 격자를 이룬다.zbl=0484.06010zbl=0727.06011lccn=201192125044, Theorem 22 부제=L/{\sim}은 대수 임의의 A,B,C\in L/{\sim}에 대하여 다음 네 명제를 보이는 것으로 족하다. (첫 번째와 두 번째, 세 번째와 네 번째 명제는 서로 쌍대이므로, 첫 번째와 세 번째만을 증명한다.) * 만약 \mathop\uparrow A=\mathop\uparrow B라면, A=B이다. * 만약 \mathop\downarrow A=\mathop\downarrow B라면, A=B이다. * 만약 \\{a\vee b\colon a\in A,\;b\in B\\}\subseteq C라면, \mathop\uparrow C=\mathop\uparrow A\cap\mathop\uparrow B이다. * 만약 \\{a\wedge b\colon a\in A,\;b\in B\\}\subseteq C라면, \mathop\downarrow C=\mathop\downarrow A\cap\mathop\downarrow B이다. 첫 번째 명제의 증명. U=(\mathop\downarrow A\vee_{\operatorname{Ideal}(L)}\mathop\downarrow B)\cap\mathop\uparrow A=(\mathop\downarrow A\vee_{\operatorname{Ideal}(L)}\mathop\downarrow B)\cap\mathop\uparrow B라고 하자 (\vee_{\operatorname{Ideal}(L)}는 순서 아이디얼 격자에서의 상한). A=\mathop\uparrow A\cap\mathop\downarrow A, B=\mathop\uparrow B\cap\mathop\downarrow B이므로, A\subseteq U, B\subseteq U이다. A와 B의 극대성에 따라, 임의의 u,u'\in U에 대하여 u\sim u'임을 보이면 족하다. u\le a\vee b, u'\le a'\vee b', a,a'\in A, b,b'\in B이며, x=u\wedge u'\wedge a\wedge a'\wedge b\wedge b'라고 하자. x\le u,u'\le a\vee a'\vee b\vee b'이므로, x\sim a\vee a'\vee b\vee b'를 보이면 족하다. x\le a,b이므로 x\in\mathop\downarrow A\cap\mathop\downarrow B이다. 또한, u,u',a,a'\in\mathop\uparrow A, u,u',b,b'\in\mathop\uparrow B, \mathop\uparrow A=\mathop\uparrow B이므로 x\in\mathop\uparrow A=\mathop\uparrow B이다. 따라서, x\in A\cap B이다. a\vee a'\in A, b\vee b'\in B이므로 x\sim a\vee a', x\sim b\vee b'이며, 따라서 x\sim a\vee a'\vee b\vee b'이다. 세 번째 명제의 증명. 우선, \mathop\uparrow A\cap\mathop\uparrow B=\mathop\uparrow\\{a\vee b\colon a\in A,\;b\in B\\}\subseteq\mathop\uparrow C이다. 이제, 임의의 c\in C에 대하여 c\in\mathop\uparrow A\cap\mathop\uparrow B임을 보이면 족하다. c\not\in\mathop\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\mathop\uparrow(a\wedge c)\subseteq\mathop\uparrow A이다. 이는 모순이다. 증명 끝 부제=L/{\sim}은 격자 위 증명에 따라, 필터 격자와 순서 아이디얼 격자로 가는 자연스러운 단사 함수 :\uparrow\colon L/{\sim}\to\operatorname{Filter}(L) :\downarrow\colon L/{\sim}\to\operatorname{Ideal}(L) 가 존재하며, 항상 :\mathop\uparrow(A\vee_{L/{\simB)=\mathop\uparrow A\cap\mathop\uparrow B=\mathop\uparrow A\wedge_{\operatorname{Filter}(L)}\mathop\uparrow B :\mathop\downarrow(A\wedge_{L/{\simB)=\mathop\downarrow A\cap\mathop\downarrow B=\mathop\downarrow A\wedge_{\operatorname{Ideal}(L)}\mathop\downarrow B 가 성립한다. 따라서, (L/{\sim},\vee_{L/{\sim)과 (L/{\sim},\wedge_{L/{\sim)은 각각 가환 반군 (\operatorname{Filter}(L),\wedge_{\operatorname{Filter}(L)}) 및 (\operatorname{Ideal}(L),\wedge_{\operatorname{Ideal}(L)})의 부분 반군과 동형이다 (격자로서의 동형일 필요는 없다). 이제, 흡수 법칙을 보이는 일만 남았다. 쌍대성에 따라 두 흡수 법칙 가운데 하나 :A\vee_{L/{\sim(A\wedge_{L/{\simB)=A 만을 보여도 좋다. \wedge_{L/{\sim의 정의에 따라 :\mathop\uparrow(A\wedge_{L/{\simB)\supseteq\mathop\uparrow\\{a\wedge b\colon a\in A,\;b\in B\\}=\mathop\uparrow A\vee_{\operatorname{Filter}(L)}\mathop\uparrow B\supseteq\mathop\uparrow A 이므로, :\mathop\uparrow(A\vee_{L/{\sim(A\wedge_{L/{\simB))=\mathop\uparrow A\cap\mathop\uparrow(A\wedge_{L/{\simB)=\mathop\uparrow A 이다. 따라서 위 흡수 법칙은 참이다. 증명 끝 특히, 분배 격자와 모듈러 격자는 임의의 허용 관계에 대하여 몫 격자를 취할 수 있다. 그러나, 이러한 몫 격자가 다시 분배 격자나 모듈러 격자가 될 필요는 없다. 즉, 분배 격자의 다양체와 모듈러 격자의 다양체는 허용 몫 가능 다양체이지만, 강하게 허용 몫 가능 다양체가 아니다.40 사실, 격자 다양체의 모든 부분 다양체는 허용 몫 가능 다양체이지만, 격자 다양체의 강하게 허용 몫 가능 부분 다양체는 격자 다양체 전체와 자명한 (한 원소 격자로 구성된) 부분 다양체밖에 없다. 이는 모든 격자는 두 원소 격자들의 직접곱의 부분 격자의 허용 관계에 대한 몫 격자의 부분 격자와 동형이기 때문이다.40, Theorem 3 상대 여원 격자 위의 모든 허용 관계는 합동 관계이다.308, Theorem 5 반대로, 모든 허용 관계가 합동 관계인 분배 격자는 상대 여원 격자이다.310, Corollary 2 모든 크기 3 이상의 격자는, 합동 관계가 아닌 허용 관계가 존재하는 부분 격자를 갖는다.308, Corollary 1