본문 바로가기
영문 위키피디아 번역

(번역) Equivalence relation

by 다움위키 2024. 2. 7.
Original article: w:Equivalence relation

 

수학(mathematics)에서, 동치 관계(equivalence relation)는 반사적(reflexive), 대칭적(symmetric)이고 전이적(transitive)인 이항 관계(binary relation)입니다. 관계 "과 같은 것임"은 동치 관계의 정식의 예제이며, 여기서 임의의 대상 a, b, 및 c에 대해:

  • a = a (반사적 속성),
  • 만약 a = b이면 b = a입니다 (대칭적 속성), 그리고
  • 만약 a = b이고 b = c이면, a = c입니다 (전이적 속성).

반서적, 대칭적, 전이적 속성의 결과로써, 임의의 동치 관계는 놓여있는 집합을 서로소 동치 클래스(equivalence classes)로의 분할(partition)을 제공합니다. 주어진 집합의 두 원소가 서로 동등한 것과 그것들이 같은 동치 클래스에 속하는 것은 필요충분 조건입니다.

Notation

다양한 표기법이 집합의 두 원소 a와 b가 동치 관계 R에 관해 동등하다는 것을 나타내기 위해 문헌에서 사용됩니다; 가장 공통적인 것은 "a ~ b" 및 "a ≡ b"이며, 이것은 R이 암시적일 때 사용되고, 명시적으로 R을 지정하기 위해 "\(a \sim_R b\)", "\(a \equiv_R b\)", 또는 "\({a\mathop{R}b}\)"의 변형을 사용합니다. 비-동치는 "a ≁ b" 또는 "\(a \not\equiv b\)"로 쓰일 수 있습니다.

Definition

집합 X에 대한 이항 관계(binary relation) ~가 동치 관계라고 말하는 것과 그것이 반사적, 대칭적 및 전이적인 것은 필요충분(iff) 조건입니다. 즉, X에서 모든 a, b 및 c에 대해:

관계 ~와 함께 X는 세토이드(setoid)라고 불립니다. \([a]\)로 표시되는, ~아래에서  \(a\)의 동치 클래스(equivalence class)는 \([a] = \{x\in X \mid x\sim a\}\)로 정의됩니다.

Examples

Simple example

집합 \(\{a, b, c\}\)가 동치 관계 \(\{(a, a), (b, b), (c, c), (b, c), (c, b)\}\)를 가진다고 놓습니다. 다음 집합은 이 관계의 동치 클래스(equivalence classes)입니다:

\(\quad [a] = \{a\}, ~~~~ [b] = [c] = \{b, c\}\).

이 관계에 대해 모든 동치 클래스의 집합은 \(\{\{a\}, \{b, c\}\}\)입니다. 이 집합은 집합 \(\{a, b, c\}\)의 분할(partition)입니다.

Equivalence relations

다음 관계는 모두 동치 관계입니다:

Relations that are not equivalences

  • 실수 사이에 관계 "≥"는 반사적이고 전이적이지만, 대칭적은 아닙니다. 예를 들어, 7 ≥ 5는 5 ≥ 7임을 의미하지는 않습니다. 그것은, 어쨌든, 전체 순서(total order)입니다.
  • 1보다 더 큰 자연수(natural numbers) 사이에 관계 "무엇과 1보다 더 큰 공통 인수(common factor)를 가짐"은 반사적이고 대칭적이지만, 전이적은 아닙니다. 예를 들어, 자연수 2와 6은 1보다 더 큰 공통 인수를 가지고 6과 3은 1보다 더 큰 공통 인수를 가지지만, 2와 3은 1보다 더 큰 공통 인수를 가지지 않습니다.
  • 비-빈(non-empty) 집합 X에 대한 (aRb가 결코 참이 되지 않도록 정의된) 빈 관계(empty relation) R은 공허하게(vacuously) 대칭적이고 전이적이지만, 반사적은 아닙니다. (만약 X가 역시 빈 것이면 R은 반사적입니다.)
  • 실수 사이에 관계 "무엇과 근사적으로 같음"은, 훨씬 더 정확하게 정의되면, 동치 관계가 아닌데, 왜냐하면 비록 반사적이고 대칭적일지라도, 그것은 전이적이 아닌데, 왜냐하면 여러 작은 변화가 큰 변화가 되기 위해 축적될 수 있기 때문입니다. 어쨌든, 만약 근사가 점근적으로 정의되면, 예를 들어 함수 f와 g가 일부 점 근처에서 대략적으로 같다고 말함으로써 만약 f − g의 극한이 해당 점에서 0이면, 이것은 동치 관계를 정의합니다.

Connections to other relations

Well-definedness under an equivalence relation

만약 ~가 X에 대한 동치 관계이고, P(x)가, x ~ y일 때마다, 만약 P(y)가 참이면, P(x)가 참을 만족하는 X의 원소의 속성이며, 그때에 속성 P는 관계 ~ 아래에서 잘-정의된(well-defined) 또는 클래스 불변이라고 말합니다.

빈번한 특별한 경우가 f가 X에서 또 다른 집합 Y로의 함수일 때 발생합니다; 만약 \(x_1 \sim x_2\)가 \(f(x_1) = f(x_2)\)를 의미하면, f는 ~에 대한 사상, ~ 아래에서 클래스 불변, 또는 간단히 ~ 아래에서 불변이라고 말합니다. 이것은, 예를 들어, 유한 그룹의 성격 이론에서 발생합니다. 함수 f를 갖는 후자의 경우는 교환적 삼각형에 의해 표현될 수 있습니다. 역시 불변(invariant)을 참조하십시오. 일부 저자는 "~ 아래에서 불변" 대신에 "~와 호환" 또는 "~에 관계"를 사용합니다.

보다 일반적으로, 함수는 (동치 관계 \(\sim_{\rm A}\) 아래에서) 동치 인수를 (동치 관계 \(\sim_{\rm B}\) 아래에서) 등가 값에 매핑할 수 있습니다. 그러한 함수는 \(\sim_{\rm A}\)에서 \(\sim_{\rm B}\)로의 사상으로 알려져 있습니다.

Equivalence class, quotient set, partition

\(a,b\in X\)라고 놓습니다. 일부 정의:

Equivalence class

a ~ b가 Y 안에 모든 a와 b에 대해 유지되고, Y 안에 a와 Y 밖의 b에 대해 결코 유지되지 않음을 만족하는 X의 부분집합 Y는 ~에 의한 X의 동치 클래스(equivalence class)라고 불립니다. \([a] := \{x \in X \mid a \sim x\}\)가 a가 속하는 동치 클래스를 나타내는 것으로 놓습니다. 서로 동등한 X의 모든 원소가 역시 같은 동치 클래스의 원소입니다.

Quotient set

\( X/\mathord{\sim} := \{[x] \mid x \in X\}\)로 표시되는, ~에 의한 X의 모든 동치 클래스의 집합은 ~에 의한 X의 몫 집합(quotient set)입니다. 만약 X가 토폴로지적 공간(topological space)이면, X/~를 토폴로지적 공간으로 변환하는 자연스러운 방법이 있습니다; 자세한 것에 대해 몫 공간(quotient space)을 참조하십시오.

Projection

~의 투영(projection)은 X의 원소를 ~에 의한 그들의 각각의 동치 클래스로의 매핑하는 \(\pi(x) = [x]\)에 의해 정의된 함수 \(\pi: X \to X/\mathord{\sim} \)입니다. 

  • 투영(projection)에 대한 정리: 함수 f: X → B를 a ~ b → f(a) = f(b)를 만족하는 것으로 놓습니다. 그런-다음 f = gπ를 만족하는, 고유한 함수 g : X/~ → B가 있습니다. 만약 f가 전사(surjection)이고 a ~ b ↔ f(a) = f(b)이면, g는 전단사(bijection)입니다.

Equivalence kernel

함수 f의 동치 커널(equivalence kernel)은 \(x\sim y \iff f(x) = f(y)\)에 의해 정의된 동치 관계 ~입니다. 단사(injection)의 동치 커널은 항등 관계(identity relation)입니다.

Partition

X의 분할(partition)은, X의 모든 각 원소가 P의 단일 원소의 원소를 만족하는 X의 비-빈 부분집합의 집합 P입니다. P의 각 원소는 분할의 셀(cell)입니다. 게다가, P의 원소는 쌍별 서로소(pairwise disjoint)이고 그들의 합집합(union)은 X입니다.

Counting partitions

X를 n 원소를 갖는 유한 집합으로 놓습니다. X에 걸쳐 모든 각 동치 관계는 X의 분할에 해당하고, 그 반대도 마찬가지이므로, X에 대한 동치 관계의 숫자는 X의 구별되는 분할의 숫자이며, 이것은 n-번째 벨 숫자(Bell number) \(B_n\)입니다:

\(\quad\displaystyle B_n = \frac{1}{e}\sum_{k=0}^\infty \frac{k^n}{k!}\)       ([[Dobinski's formula|도비스키의 공식(Dobinski's formula)]]).

Fundamental theorem of equivalence relations

핵심 결과는 동치 관계와 분할을 연결합니다:

  • 집합 X에 대한 동치 관계는 X를 분할합니다.
  • 반대로, X의 임의의 분할에 해당하는, X에 대한 동치 관계 ~가 존재합니다.

둘 다 경우에서, X의 분할의 셀은 ~에 의한 동치 클래스입니다. X의 각 원소는 X의 임의의 분할의 고유한 셀에 속하므로, 그리고 그 분할의 각 셀은 ~에 의한 X의 동치 클래스(equivalence class)와 동일하므로, X의 각 원소는 ~에 의한 X의 고유한 동치 클래스에 속합니다. 따라서 X에 대한 모든 동치 관계의 집합과 X의 모든 분할의 집합 사이에 자연스러운 전단사(bijection)가 있습니다.

Comparing equivalence relations

만약 ~와 ≈가 같은 집합 S에 대한 동치 관계이고, 모든 a,b ∈ S에 대해 a~b가 a≈b를 의미하면, ≈가 ~보다 엉성한 관계라고 말해지고, ~는 ≈보다 섬세한 관계라고 말합니다. 동등하게,

  • ~는 만약 ~의 모든 각 동치 클래스가 ≈의 동치 클래스의 부분집합이면 ≈보다 섬세하고, 따라서 ≈의 모든 각 동치 클래스는 ~의 동치 클래스의 합집합입니다.
  • ~는 만약 ~에 의해 생성된 분할이 ≈에 의해 생성된 분할의 세분화이면 ≈보다 섬세합니다.

상등 동치 관계는 임의의 집합에 대한 가장-섬세한 동치 관계이지만, 모든 원소의 쌍을 관련시키는 보편적 관계는 가장 엉성합니다.

고정된 집합에 대한 모든 동치 관계의 모음에 대한 관계 "~이 ≈보다 더 섬세함"은 자체로 부분 순서 관계이며, 이것은 모음을 기하학적 격자(geometric lattice)로 만듭니다.

Generating equivalence relations

\( X \)에 대한 임의의 이항 관계 \(A \subset X \times X\)가 주어지면, \(A\)에 의해 생성된 동치 관계는  \( A\)를 포함하는 \(X\)에 대한 동치 관계의 교집합입니다. (\(X \times X\)가 동치 관계이므로, 교집합은 비-자명한 것입니다.)

  • 임의의 집합 X가 주어지면, 모든 함수 X→X의 집합 [X → X]에 걸쳐 동치 관계입니다. 두 그러한 함수는 고정점(fixpoint)의 그들 각각의 집합이 같은 카디널리티(cardinality)를 가질 때 동등한 것으로 여겨지며, 순열(permutation)에서 길이 일의 순환에 해당합니다. 이 방식에서 동등한 함수는 [X → X]에 대한 동치 클래스, 및 이들 동치 클래스 분할 [X → X]을 형성합니다.
  • X에 대한 동치 관계 ~는 그것의 전사(surjective) 투영(projection) π : X → X/~의 동치 커널(equivalence kernel)입니다. 반대로, 집합 사이의 임의의 전사(surjection)는 그것의 도메인에 대한 분할, 코도메인(codomain)에서 한원소(singleton)의 이전-이미지(preimage)의 집합을 결정합니다. 따라서 X에 걸쳐 동치 관계, X의 분할, 그것의 도메인인 X인 투영은 같은 것을 지정하는 세 개의 동등한 방법입니다.
  • X에 걸쳐 동치 관계 (X × X의 부분집합(subset)으로 보이는 이항 관계)의 임의의 모음의 교집합은 역시 동치 관계입니다. 이것은 동치 관계를 생성하는 편리한 방법을 산출합니다: X에 대한 임의의 이항 관계 R이 주어지면 R에 의해 생성된 동치 관계는 R을 포함하는 가장-작은 동치 관계입니다. 구체적으로, R이 동치 관계 a ~ b를 생성하는 것과 \(a=x_1, b=x_n\), 및 \((x_i,x_{i+1}) \in R\) 또는 \((x_{i+1}, x_i) \in R\), i = 1, ..., n−1를 만족하는 X에서 원소 \(x_1,x_2,...,x_n\)가 존재하는 것은 필요충분(iff) 조건입니다.
    • 이 방식으로 생성된 동치 관계는 자명할 수 있음을 주목하십시오. 예를 들어, X에 대한 전체 순서(total order)에 의해 생성된 동치 관계 ~는 정확히 하나의 동치 클래스, X 자체를 가지는데, 왜냐하면 모든 x와 y에 대해 x ~ y이기 때문입니다. 또 다른 예제로써, X에 대한 항등 관계(identity relation)의 부분집합은 X의 한원소인 동치 클래스를 가집니다.
  • 동치 관계는 "대상을 함께 붙임"으로써 새로운 공간을 구성할 수 있습니다. X를 단위 데카르트 정사각형(Cartesian square) [0, 1] × [0, 1]으로 놓고, ~를 모든 a ∈ [0, 1]에 대해 (a, 0) ~ (a, 1)에 의해 및 모든 b ∈ [0, 1]에 대해 (0, b) ~ (1, b)에 의해 정의된 X에 대한 동치 관계로 놓습니다. 그런-다음 몫 공간(quotient space) X/~은 토러스(torus)로 자연스럽게 식별될 수 있습니다 (위상동형(homeomorphism)): 정사각형 종이를 가져다가, 위쪽과 아래쪽 가장자리를 구부리고 접착하여 원기둥을 형성하고, 그런-다음 결과 원기둥을 구부려서 그것의 열린 끝을 함께 붙이면, 토러스를 초래합니다.

Algebraic structure

수학의 대부분은 동치, 및 순서 관계(order relation)의 연구에 기초를 둡니다. 격자 이론(Lattice theory)은 순서 관계의 수학적 구조를 포착합니다. 비록 동치 관계가 수학에서 순서 관계만큼 어디에나 있을지라도, 동치의 대수적 구조는 순서의 구조만큼 잘 알려져 있지는 않습니다. 전자의 구조는 주로 그룹 이론(group theory)에 기반을 두고, 낮은 정도에서, 격자, 카테고리(categories), 및 그룹포이드(groupoid)의 이론에 기반을 둡니다.

Group theory

순서 관계(order relation)가 순서화된 집합(ordered sets), 쌍별 상한(supremum) 및 하한(infimum) 아래에서 닫힌 집합에 기초를 둔 것과 마찬가지로, 동치 관계는 분할 구조를 보존하는 전단사(bijection) 아래에서 닫힌 집합인 분할된 집합(partitioned sets)에 기초를 둡니다. 모든 그러한 전단사는 동치 클래스를 자체 위로 매핑하므로, 그러한 전단사는 역시 순열(permutation)로 알려져 있습니다. 따라서 순열 그룹(permutation group) (역시 변환 그룹(transformation groups)으로 알려져 있음)과 이와 관련된 궤도(orbit)의 개념은 동치 관계의 수학적 구조를 밝힙니다.

'~'가, 전체집합(universe) 또는 놓여-있는 집합이라고 불리는, 어떤 비-빈 집합 A에 걸쳐 동치 관계를 표시한다고 놓습니다. G는 A: ∀x ∈ A ∀g ∈ G (g(x) ∈ [x])의 분할 구조를 보존하는 A에 걸쳐 전단사 함수의 집합을 표시한다고 놓습니다. 그런-다음 다음 셋의 연결된 정리를 유지됩니다:

  • ~는 A를 동치 클래스로 분할합니다. (이것은 위에 언급된 Fundamental Theorem of Equivalence Relations입니다);
  • A의 분할이 주어지면, G는 합성 아래에서 변환 그룹 아래에서 변환이며, 그것의 궤도는 분할의 셀(cells)입니다;
  • A에 걸쳐 변환 그룹 G가 주어지면, A에 걸쳐 동치 관계 ~가 존재하며, 그것의 동치 클래스는 G의 궤도입니다.

합에서, A에 걸쳐 동치 관계 ~가 주어지면, A에 걸쳐 변환 그룹(transformation group) G가 존재하며 그것의 궤도는 ~ 아래에서 A의 동치 클래스입니다.

동치 관계의 이 변환 그룹 특성화는 격자(lattices)가 순서 관계를 특성화하는 방법과 근본적으로 다릅니다. 격자 이론 연산 미트(meet)와 조인(join)의 인수는 일부 전체집합 A의 원소입니다. 한편, 변환 그룹 연산 합성(composition) 및 역(inverse)의 인수는 전단사(bijections), A → A의 집합의 원소입니다.

일반적으로 그룹으로 이동하면, H를 일부 그룹(group) G의 부분그룹(subgroup)이라고 놓습니다. ~를 \(a \sim b \leftrightarrow (ab^{-1} \in H)\)를 만족하는 G에 대한 동치 관계로 놓습니다. ~의 동치 클래스는–역시 G에 대한 H의 동작(action)의 궤도라고 불림–G에서 H의 오른쪽 코셋(coset)입니다. a와 b를 교환하면 왼쪽 코셋을 산출합니다.

관련된 생각은 Rosen (2008: chpt. 10)에서 찾을 수 있습니다.

Categories and groupoids

G를 집합으로 놓고 "~"는 G에 걸쳐 동치 관계를 나타내는 것으로 놓습니다. 그런-다음 우리는 다음처럼 이 동치 관계를 나타내는 그룹포이드(groupoid)를 형성할 수 있습니다. 대상은 G의 원소이고, G의 임의의 두 원소 x와 y에 대해, x에서 y로의 고유한 사상이 존재하는 것과 x~y인 것은 필요충분(iff) 조건입니다.

동치 관계를 그룹포이드의 특별한 경우로 여기는 것의 이점은 다음을 포함합니다:

  • "자유 동치 관계"의 개념은 존재하지 않는 반면에, 방향화된 그래프(directed graph) 위에 자유 그룹포이드(free groupoid)의 개념은 존재합니다. 따라서 "동치 관계의 표현", 즉 해당하는 그룹의 표현을 말하는 것이 의미가 있습니다.
  • 그룹의 번들, 그룹 동작(group action), 집합, 및 동치 관계는 그룹포이드의 개념의 특별한 경우, 여러 아날로그를 제시하는 관점으로 여겨질 수 있습니다.
  • 많은 문맥에서, "인용"과 따라서 종종 합동(congruences)라고 불리는 적절한 동치 관계가 중요합니다. 이것은 카테고리(category)의 내부 그룹포이드의 개념으로 이어집니다.

Lattices

임의의 집합 X에 대한 동치 관계는, 집합 포함(set inclusion)에 의해 순서화될 때, 관례에 의해 Con X라고 불리는 complete lattice완전 격자(complete lattice)]]를 형성합니다. 정식의 맵(map) ker: X^X → Con X는 X와 Con X 위의 모든 함수(function)의 모노이드(monoid) X^X를 관련시킵니다. ker는 전사(surjective)이지만 단사(injective)는 아닙니다. 덜 공식적으로, X 위의 동치 관계 ker는 각 함수 f: X→X를 그것의 커널(kernel) ker f로 취합니다. 마찬가지로, ker(ker)는 X^X 위의 동치 관계입니다.

Equivalence relations and mathematical logic

동치 관계는 예제 또는 반대-예제의 준비된 원천입니다. 예를 들어, 정확하게 두 무한 동치 클래스를 갖는 동치 관계는 ω-카테고리적(categorical)이지만, 임의의 더 큰 세는 숫자(cardinal number)에 대해 카테고리적이 아닌 것인 이론의 쉬운 예제입니다.

모델 이론(model theory)의 의미는 관계를 정의하는 속성이 서로 독립적으로 입증될 수 있는 것 (및 따라서 정의의 필요한 부분)과, 각 속성에 대해, 예제가 모든 다른 속성을 만족시키는 동안 주어진 속성을 만족시키지 않는 관계의 것으로 찾아질 수 있는 것은 필요충분 조건이라는 것입니다. 따라서 동치 관계의 속성을 정의하는 세 가지는 다음 세 가지 예제에 의해 서로 독립적으로 입증될 수 있습니다:

동치 관계가 소유할 수도 있고 소유하지 않을 수도 있는 일-차 논리(first-order logic)에서 정의할 수 있는 속성은 다음을 포함합니다:

Euclidean relations

유클리드(Euclid)의 원론(The Elements)은 다음 "공통 개념 1"을 포함합니다:

  • 같은 것과 같은 어떤 것은 역시 서로 같습니다.

요즘, 공통 개념 1에 의해 설명된 속성은 유클리드(Euclidean) ("같은"을 "무엇과 관계에 있음"으로 대체)라고 불립니다. "관계"에 의해 설명된 것은 이항 관계(binary relation)를 의미하며, 이것에서 aRb는 일반적으로 bRa와 구별됩니다. 유클리드 관계는 따라서 두 형식에서 나타납니다:

  • (aRc ∧ bRc) → aRb (왼쪽-유클리드 관계)
  • (cRa ∧ cRb) → aRb (오른쪽-유클리드 관계)

다음 정리는 유클리드 관계(Euclidean relation)와 동치 관계를 연결합니다:

 

정리

  • 만약 관계가 (왼쪽 또는 오른쪽) 유클리드이고 [[reflexive relation|반사적(reflexive)]]이면, 그것은 역시 대칭적이고 전이적입니다.

왼쪽-유클리드 관계에 대해 증명:

  • (aRc ∧ bRc) → aRb [a/c] = (aRa ∧ bRa) → aRb [반사적; 지움 T∧] = bRa → aRb. 따라서 R은 대칭적(symmetric)입니다.
  • (aRc ∧ bRc) → aRb [대칭] = (aRc ∧ cRb) → aRb. 따라서 R은 전이적(transitive)입니다. ◻

오른쪽-유클리드 관계에 대한 유사한 증명을 가집니다. 따라서 동치 관계는 유클리드이고 반사적인 관계입니다. 원론은 대칭성도 반사성도 언급하지 않았고, 유클리드는 명백한 언급을 정당화하기에는 상등의 반사성이 너무 분명하다고 생각했을 것입니다.

References

  • Brown, Ronald, 2006. Topology and Groupoids. Booksurge LLC. ISBN 1-4196-2722-8.
  • Castellani, E., 2003, "Symmetry and equivalence" in Brading, Katherine, and E. Castellani, eds., Symmetries in Physics: Philosophical Reflections. Cambridge Univ. Press: 422-433.
  • Robert Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice Hall. Chpt. 12 discusses how equivalence relations arise in lattice theory.
  • Higgins, P.J., 1971. Categories and groupoids. Van Nostrand. Downloadable since 2005 as a TAC Reprint.
  • John Randolph Lucas, 1973. A Treatise on Time and Space. London: Methuen. Section 31.
  • Rosen, Joseph (2008) Symmetry Rules: How Science and Nature are Founded on Symmetry. Springer-Verlag. Mostly chapters. 9,10.
  • Raymond Wilder (1965) Introduction to the Foundations of Mathematics 2nd edition, Chapter 2-8: Axioms defining equivalence, pp 48–50, John Wiley & Sons.

External links

 

 

 

 
 

 

 

관련글

티스토리툴바