수학에서 동치 관계(同値關係, 영어: equivalence relation)는 논리적 동치와 유사한 성질들을 만족시키는 이항 관계이다.
동치 관계[편집]
집합
위의 동치 관계는 다음 세 조건을 만족시키는,
위의 이항 관계
이다.
- (반사 관계) 임의의
에 대하여, ![{\displaystyle x\sim x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5792c97cd9f9f18929f0ebed6366bf472001813)
- (대칭 관계) 임의의
에 대하여, 만약
라면, ![{\displaystyle y\sim x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c54fe8e222fd770c44b4df39405b2616532a976)
- (추이적 관계) 임의의
에 대하여, 만약
이고
라면 ![{\displaystyle x\sim z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f11d95a4a86ec7546629417954a5252b82020049)
동치류와 몫집합[편집]
집합
위에 동치 관계
이 주어졌을 때, 원소
의,
에 대한 동치류(同値類, 영어: equivalence class)
는
와 동치인 원소들을 모은 집합이다.
![{\displaystyle [x]_{\sim }=\{y\in X\colon x\sim y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1584158d3dbf2a7a2c0b00d013e56f3e17b9a34)
집합
위에 동치 관계
이 주어졌을 때,
의
에 대한 몫집합(-集合, 영어: quotient set)
은 모든 동치류들을 모은 집합이다.
![{\displaystyle X/{\sim }=\{[x]_{\sim }\colon x\in X\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4748aa92fd76efdaadca7278f941fce027143a67)
모임의 경우[편집]
선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC)에서, 모임은 하나의 자유 변수를 가지는 논리식으로 여길 수 있다. 어떤 집합이 이 논리식을 만족시킬 때, 집합은 이 논리식에 대응하는 모임의 원소가 된다. 자유 변수에 논리식을 대입하는 것은 합법적이지 않으므로, 고유 모임은 모임의 원소가 될 수 없다.
모임 위에서도 동치 관계·동치류·몫집합의 개념을 정의할 수 있다. 동치 관계의 정의는 집합 위에서의 정의를 옮겨 오면 충분하다. 다만, 모임
위의 동치 관계는 곱모임
의 부분 모임으로서, 더 이상 집합이 아닐 수 있다. 모임의 원소의 동치류를 이 원소와 동치인 원소들의 모임으로 정의할 경우, 동치류들을 개별적으로 다루는 데에는 문제가 없으나, 동치류들이 고유 모임일 수 있으므로 동치류들의 모임을 합법적으로 정의할 수 없다. 즉,
을 정의하려면 동치류가 집합이 되도록 동치류의 정의에 수정을 가하여야 한다.
모임
위에 동치 관계
가 주어졌다고 하자. 원소
에 대하여, 다음과 같이 정의한다.[1]:65
![{\displaystyle [x]'_{\sim }=\{y\in X\colon x\sim y\land (\forall z\in X\colon x\sim z\implies \operatorname {rank} y\leq \operatorname {rank} z)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d21f9ce402fb5aafd8fe3fa9afee6891441b4b6e)
즉,
는
와 동치인 원소 가운데, (폰 노이만 전체에서의) 계수가 가장 낮은 것들의 모임이다. (이러한 최소 계수의 원소가 존재하는 것은 순서수의 모임이 정렬 전순서 모임이기 때문이다.) 이러한 최소의 계수를
라고 할 때,
는 집합
의 부분 모임이므로, 집합이다. 따라서, 모임
![{\displaystyle (X/{\sim })'=\{[x]'\colon x\in X\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/618a31521c7a3ff426286055408ad83bd5305da3)
을 정의할 수 있다.[1]:65
집합
위에 동치 관계
이 주어졌을 때, 다음과 같은 표준적인 전사 함수가 존재한다.
![{\displaystyle X\to X/{\sim }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26f8404062c6934c87cc150abca35f4ab8d23609)
![{\displaystyle x\mapsto [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a07b95c49afdb5a84f26120657148e94c94a69be)
즉, 이 함수는 모든 원소를 이 원소가 속하는 동치류로 대응시킨다.
집합의 분할과의 관계[편집]
집합
가 주어졌을 때,
위의 동치 관계들과
의 분할들 사이에 표준적인 일대일 대응이 존재하며, 이는 다음과 같다. 집합
위에 동치 관계
이 주어졌을 때, 몫집합
은 집합의 분할이다. 즉,
의 임의의 원소는 정확히 하나의 동치류에 속한다. 반대로, 집합
의 분할
가 주어졌다고 하자 (즉,
는
의 부분 집합들의 집합이며,
의 임의의 원소는 정확히 하나의
의 원소에 속한다).
위에 다음과 같은 이항 관계
를 정의하자.
![{\displaystyle x\sim _{\mathcal {P}}y\iff \exists A\in P\colon x,y\in A\qquad (x,y\in X)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4a701952a4270e00f35b592c643384bc37d80e9)
그렇다면
는
위의 동치 관계이다.
과
는 서로 역함수이다. 즉,
![{\displaystyle {\sim }_{X/{\sim }}={\sim }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3551c730d91d6fd74f370d6abc380be379203b82)
![{\displaystyle X/{\sim }_{\mathcal {P}}={\mathcal {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a106660747c01c33fd1ab621c703314cd11c58a)
이다. 따라서, 동치 관계와 집합의 분할의 개념은 동치이다.
순서론적 성질[편집]
집합
가 주어졌다고 하자. 임의의 이항 관계
에 대하여,
를 포함하는 최소의 동치 관계
가 존재한다. 구체적으로, 다음 두 조건이 서로 동치이다.
![{\displaystyle x\sim _{R}y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/78a4ab4ac128c887fea33ca5d8839a7fe8657182)
- 다음 조건을 만족시키는 열
가 존재한다.
![{\displaystyle x_{0}=x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14745b8f7723f2031eb388152d53b1b39b43bb66)
![{\displaystyle x_{n}=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e04ca9c091f77536a76c196199de9df858fc41e4)
에 대하여,
이거나 ![{\displaystyle (x_{i},x_{i-1})\in R}](https://wikimedia.org/api/rest_v1/media/math/render/svg/08f32d7cf5c0e58ea414562a2e9c60ddeea54977)
집합
위의 동치 관계들의 (포함 관계에 의한) 부분 순서 집합
는 완비 격자이다.
의 최소 원소는 (
로 국한된) 등호
이며, 최대 원소는 전체 관계
이다. 동치 관계들의 집합
의 만남
는 교집합
![{\displaystyle (x,y)\in \bigwedge _{i\in I}{\sim }_{i}\iff \forall i\in I\colon x\sim _{i}y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a67b8e34c091523b430cabae1d8175a2893c21d1)
이다.
의 이음
은 합집합
을 포함하는 최소의 동치 관계
![{\displaystyle (x,y)\in \bigvee _{i\in I}\sim _{i}\iff \exists n\in \mathbb {N} \exists x_{0},\dots ,x_{n}\in X\exists i_{1},\dots ,i_{n}\in I\colon x=x_{0}\sim _{i_{1}}x_{1}\sim _{i_{2}}\cdots \sim _{i_{n}}x_{n}=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c597a95120b4d04c542ee9f90d9589b77f5a641)
이다.
동치 관계 격자
는 항상 대수적 격자(영어: algebraic lattice)이자 반모듈러 격자(영어: semimodular lattice)이다. 유한 집합
의 경우,
는 단순 격자(영어: simple lattice, 합동 관계가 자명한 격자)이다.
임의의 집합
위에서, 등호
는 동치 관계를 이룬다.
평면 (또는 입체) 도형들의 집합 위에서, 닮음 관계는 동치 관계이다.
임의의 함수
에 대하여, 같은 함숫값을 갖는 관계
![{\displaystyle x\sim _{f}y\iff f(x)=f(y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f60958531debb28c9c5c6de0b359aa4c265a9bd)
는 정의역
위의 동치 관계이다. 이를테면,
가 어떤 사람들의 집합이며,
가 사람의 생일을 찾는 함수라면,
는 같은 생일의 사람들을 한데 묶는 동치 관계로 생각할 수 있다.
반사 관계가 아닌 대칭 추이적 관계[편집]
임의의 집합
위에서, 공관계
![{\displaystyle \varnothing \subseteq X^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afaafbd8977261e597311b769fbf6fa6c1496172)
는 항상 대칭 관계이자 추이적 관계이다. 그러나, 만약
이라면 이는 반사 관계가 아니다. 반사 관계가 아닌 대칭 추이적 관계는 이러한 형태밖에 없다.
대칭 관계가 아닌 반사 추이적 관계[편집]
정수의 집합
위의 표준적인 순서
![{\displaystyle x\leq y\iff \exists z\in \mathbb {Z} _{\geq 0}\colon y=x+z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/005648d9f1240d9a58d3fed0bd3e4be278341d1a)
를 생각하자. 이는 전순서이며, 특히 반사 관계이자 추이적 관계이지만, 대칭 관계가 아니다. 예를 들어,
이지만,
이다.
추이적 관계가 아닌 반사 대칭 관계[편집]
정수 집합
위의 이항 관계
![{\displaystyle (x,y)\in R\iff y=x+1\lor y=x-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f705f0d5791ff00a77104ff10e132a13ebdc4b8)
는 반사 관계이자 대칭 관계이지만, 추이적 관계가 아니다.
같이 보기[편집]
외부 링크[편집]