Congruence relation

추상 대수(abstract algebra)에서, 합동 관계(congruence relation) (또는 단순히 합동)는 동등한 원소로 수행된 대수적 연산이 동등한 원소를 산출한다는 의미에서 구조와 호환되는 (그룹(group), 링(ring), 또는 벡터 공간(vector space)과 같은) 대수적 구조(algebraic structure)에 대한 동치 관계(equivalence relation)입니다.^[1] 모든 각 합동 관계는 해당하는 몫(quotient) 구조를 가지며, 그것의 원소는 관계에 대해 동치 클래스(equivalence class) (또는 합동 클래스)입니다.^[2]

Basic example

합동 관계의 원형적인 예제는 정수(integer)의 집합에 대한 합동 모듈로 $n$ ( congruence modulo $n$ )입니다. 주어진 양의 정수(positive integer) $n$ 에 대해, 두 정수 $a$ 와 $b$ 는 만약 $a-b$ 가 $n$ 에 의해 나뉠(divisible) 수 있으면 (또는 동등하게 만약 $a$ 와 $b$ 가 $n$ 에 의해 나뉠 때 같은 나머지(remainder)를 가지면), 합동 모듈로 $n$ 이라고 불리며, 다음처럼 쓰입니다:

a\equiv b{\pmod {n}}

.

예를 들어, $37$ 과 $57$ 은 합동 모듈로 $10$ 이며, 다음인데,

37\equiv 57{\pmod {10}}

왜냐하면 $37-57=-20$ 은 10의 배수이기 때문, 또는 동등하게 $37$ 와 $57$ 둘 다는 $10$ 으로 나눌 때 $7$ 의 나머지를 가지기 때문입니다.

합동 모듈로 $n$ (고정된 $n$ 에 대해)은 정수에 대한 덧셈(addition)과 곱셈(multiplication) 둘 다와 호환됩니다. 즉,

만약 다음이면

a_{1}\equiv a_{2}{\pmod {n}}

and

b_{1}\equiv b_{2}{\pmod {n}}

다음입니다:

a_{1}+b_{1}\equiv a_{2}+b_{2}{\pmod {n}}

and

a_{1}b_{1}\equiv a_{2}b_{2}{\pmod {n}}

동치 클래스의 해당하는 덧셈과 곱셈은 모듈로 산술(modular arithmetic)로 알려져 있습니다. 추상 대수의 관점으로부터, 합동 모듈로 $n$ 은 정수의 링(ring)에 대한 합동 관계이고, 산술 모듈로 $n$ 은 해당하는 몫 링(quotient ring)에서 발생합니다.

Definition

합동의 정의는 고려중인 대수적 구조(algebraic structure)의 유형에 의존합니다. 특정 합동의 정의는 그룹(groups), 링(rings), 벡터 공간(vector space), 모듈(modules), 반-그룹(semigroup), 격자(lattices), 등에 대해 만들어질 수 있습니다. 공통 주제는 합동이, 연산(operations)이 동치 클래스(equivalence classes)에서 잘-정의된(well-defined) 것임을 의미에서, 대수적 구조와 호환되는 대수적 대상에 대한 동치 관계(equivalence relation)라는 것입니다.

예를 들어, 그룹은, 특정 공리를 만족시키는, 단일 이항 연산(binary operation)과 함께 집합(set)으로 구성되는 대수적 대상입니다. 만약 $G$ 가 연산 $\ast$ 를 갖는 그룹이면, $G$ 에 대한 합동 관계는 모든 $g_{1}$ , $g_{2}$ , $h_{1}$ , $h_{2}\in G$ 에 대해 다음을 만족시키는 $G$ 의 원소에 대한 동치 관계 $\equiv$ 입니다:

g_{1}\equiv g_{2}\ \ \,

and

\ \ \,h_{1}\equiv h_{2}\implies g_{1}\ast h_{1}\equiv g_{2}\ast h_{2}

.

그룹에 대한 합동에 대해, 항등 원소(identity element)를 포함하는 동치 클래스는 항상 정규 부분-그룹(normal subgroup)이고, 다른 동치 클래스는 이 부분그룹의 코셋(coset)입니다. 함께, 이들 동치 클래스는 몫 그룹(quotient group)의 원소입니다.

대수적 구조가 하나보다 많은 연산을 포함할 때, 합동 관계는 각 연산과 호환되는 것을 요구합니다. 예를 들어, 링은 덧셈과 곱셈 둘 다를 소유하고, 링의 합동 관계는 $r_{1}\equiv r_{2}{\text{ and }}s_{1}\equiv s_{2}$ 일 때마다 다음을 만족시켜야 합니다:

r_{1}+s_{1}\equiv r_{2}+s_{2}{\text{ and }}r_{1}s_{1}\equiv r_{2}s_{2}

링에 대한 합동에 대해, 0을 포함하는 동치 클래스는 항상 양-측 아이디얼(ideal)이고, 동치 클래스의 집합에 대한 두 연산은 대응하는 몫 링을 정의합니다.

합동 관계의 일반적인 개념은 보편 대수(universal algebra), 모든 대수적 구조(algebraic structures)에 공통적인 아이디어를 연구하는 분야의 문맥에서 형식적인 정의를 주어질 수 있습니다. 이 설정에서, 합동 관계는 $n$ -항 연산 $\mu$ 와 각 $i=1,...,n$ 에 대해 $a_{i}\equiv a_{i}'$ 를 만족하는 모든 원소 $a_{1}{\text{, }}\ldots {}{\text{, }}a_{n}{\text{, }}a_{1}'{\text{, }}\ldots {}{\text{, }}a_{n}'$ 에 대해 다음을 만족시키는 대수적 구조에 대한 동치 관계 $\equiv$ 입니다:

\mu \left(a_{1}{\text{, }}a_{2}{\text{, }}\ldots {}{\text{, }}a_{n}\right)\equiv \mu \left(a_{1}'{\text{, }}a_{2}'{\text{, }}\ldots {}{\text{, }}a_{n}'\right)

.

Relation with homomorphisms

만약 $f:A\,\rightarrow B$ 가 (그룹의 준동형(homomorphism of groups), 또는 벡터 공간(vector space) 사이의 선형 맵(linear map)과 같은) 두 대수적 구조 사이에 준동형)(homomorphism)이면, 다음에 의해 정의된 관계 $R$ 은 합동 관계입니다:

a_{1}\,R\,a_{2}

if and only if

f\left(a_{1}\right)=f\left(a_{2}\right)

.

첫 번째 동형 정리(first isomorphism theorem)에 의해, $f$ 아래의 A의 이미지(image)는 이 합동에 의해 A의 몫에 동형적인(isomorphic) B의 부분구조입니다.

Congruences of groups, and normal subgroups and ideals

그룹(groups)의 특정 경우에서, 합동 관계는 다음처럼 기초 항에서 설명될 수 있습니다: 만약 G가 (항등 원소(identity element) e와 연산 *를 갖는) 그룹이고 ~가 G 위에 이항 관계(binary relation)이면, ~는 다음일 때마다 합동입니다:

G의 임의의 원소가 주어지면(Given any), a ~ a (반사성(reflexivity));
G의 임의의 원소 a와 b가 주어지면, 만약(if) a ~ b이면, b ~ a입니다 (대칭(symmetry));
G의 임의의 원소 a, b, 및 c가 주어지면, 만약 a ~ b 및(and) b ~ c이면, a ~ c입니다 (전이성(transitivity));
G의 임의의 원소 a, a' , b, 및 b' 가 주어지면, 만약 a ~ a' 및 b ~ b' 이면, a * b ~ a' * b' 입니다;
G의 임의의 원소 a와 a' 가 주어지면, 만약 a ~ a' 이면, a⁻¹ ~ a' ⁻¹입니다 (이것은 다른 넷으로부터 실제로 입증될 수 있으므로, 엄격하게 중복된 것입니다).

조건 1, 2, 및 3은 ~가 동치 관계(equivalence relation)임을 말합니다.

합동 ~는 항등 원소에 합동하는 G의 그들 원소의 집합 {a ∈ G : a ~ e}에 의해 전체적으로 결정되고, 이 집합은 정규 부분그룹(normal subgroup)입니다. 구체적으로 특별히, a ~ b인 것과 b⁻¹ * a ~ e인 것은 필요충분 조건입니다. 따라서 그룹 위에 합동에 대해 얘기하는 대신에, 사람들은 보통 그것들의 정규 부분그룹의 관점에서 말합니다; 사실, 모든 각 합동는 G의 어떤 정규 부분그룹에 고유하게 해당합니다.

Ideals of rings and the general case

유사한 트릭은 링 이론(ring theory)에서 커널을 합동 관계 대신에 아이디얼(ideals)로, 모듈 이론(module theory)에서 합동 관계 대신에 부분모듈(submodule)로 말하는 것을 허용합니다.

이 트릭이 가능한 보다 일반적인 상황은 오메가-그룹(Omega-group) (일반적인 의미에서 여러 애리티를 갖는 연산자를 허용함)을 사용하는 것입니다. 그러나 이것은, 예를 들어, 모노이드(monoid)로는 행할 수 없으므로, 합동 관계 연구는 모노이드 이론에서 더 중심적 역할을 합니다.

Universal algebra

아이디어는 보편 대수(universal algebra)로 일반화됩니다: 대수 A에 대한 합동 관계는 A에 대한 동치 관계(equivalence relation)이고 A × A의 부분대수(subalgebra) 둘 다인 직접 곱(direct product) A × A의 부분집합(subset)입니다.

준동형(homomorphism)의 커널(kernel)은 항상 합동입니다. 실제로, 모든 각 합동는 커널로 발생합니다. A에 대한 주어진 합동 ~에 대해, 동치 클래스(equivalence class)의 집합 A/~는 자연스러운 방식으로 대수, 몫 대수(quotient algebra)의 구조를 주어질 수 있습니다. A의 모든 각 원소를 그것의 동치 클래스에 매핑하는 함수는 준동형이고, 이 준동형의 커널은 ~입니다.

대수 A에 대한 모든 합동 관계의 격자(lattice) Con(A)는 대수적(algebraic)입니다.

존 매킨토시 하위(John M. Howie)는 반-그룹(semigroup) 이론이 보편 대수학에서 합동 관계를 어떻게 묘사하는지 설명했습니다:

그룹에서 합동는 만약 우리가 단일 합동 클래스를 알고 있으면, 특히 만약 우리가 항등원을 포함하는 클래스인 정규 부분-그룹을 알고 있으면 결정됩니다. 유사하게, 링에서 합동는 만약 우리가 영을 포함하는 합동 클래스인 아이디얼을 알고 있으면 결정됩니다. 반-그룹에서 그러한 운이 좋은 발생이 없고, 우리가 따라서 이를테면 합동를 연구해야 할 필요성에 직면합니다. 다른 무엇보다도 더, 그것이 반 집단 이론에 특징적인 풍미를 제공하는 이러한 필요성입니다. 반-그룹은 실제로 보편 대수의 방법이 적용되어야 하는 첫 번째이자 가장 단순한 유형의 대수입니다…^[3]

Notes

^ Hungerford, Thomas W.. Algebra. Springer-Verlag, 1974, p. 27
^ Hungerford, 1974, p. 26
^ J. M. Howie (1975) An Introduction to Semigroup Theory, page v, Academic Press

References

Horn and Johnson, Matrix Analysis, Cambridge University Press, 1985. ISBN 0-521-38632-2. (Section 4.5 discusses congruency of matrices.)
Rosen, Kenneth H (2012). Discrete Mathematics and Its Applications. McGraw-Hill Education. ISBN 978-0077418939.

[1] Hungerford, Thomas W.. Algebra. Springer-Verlag, 1974, p. 27

[2] Hungerford, 1974, p. 26

[3] J. M. Howie (1975) An Introduction to Semigroup Theory, page v, Academic Press

[1]

[2]

[3]