이 단원 목차
묶기와 순서 비교는 다른 질문이다
‘같은 종류’, ‘선수 관계’, ‘비용이 이하’는 서로 다른 관계입니다. 모든 관계를 동치로 보거나 모든 비교를 전순서로 만들면 데이터 처리와 연구 주장에 중요한 실패를 숨깁니다.
D 위의 이항관계는 의 부분집합입니다. 순서쌍이 포함되면 xRy라고 씁니다. 함수는 각 입력에 출력 하나를 대응하는 특수 관계이고 일반 관계에는 그런 유일성이 필요하지 않습니다.
양화사를 명시한 네 조건
| 성질 | D의 해당 모든 원소에 대한 조건 |
|---|---|
| 반사성 | xRx |
| 대칭성 | xRy이면 yRx |
| 반대칭성 | xRy이고 yRx이면 x=y |
| 추이성 | xRy이고 yRz이면 xRz |
반대칭은 ‘대칭이 아니다’가 아닙니다. 등호는 대칭이고 반대칭입니다. 비대칭은 xRy이면 yRx가 아님을 요구하여 자기 관계도 금지합니다. 단어 하나의 차이가 정리를 바꿀 수 있습니다.
동치관계와 동치류
동치는 반사·대칭·추이입니다. k에 대한 합동, 즉 k가 x−y를 나누는 관계가 예입니다. D={1,2,3,4}, k=2에서 동치류는 {1,3}, {2,4}입니다.
0은 k의 배수라 반사적입니다. 차이의 부호를 바꿔도 나누어져 대칭입니다. x−y=ka, y−z=kb이면 x−z=k(a+b)이므로 추이적입니다. 유한 표의 크기에 의존하지 않는 모든 정수의 논증입니다.
동치류는 영역을 분할합니다. 두 류가 z에서 겹치면 대칭·추이를 써 어느 쪽의 모든 원소도 다른 류에 속함을 보여 두 류가 같습니다. 아니면 서로소입니다. 분할은 종류 소속이며 류 사이의 순위가 아닙니다.
부분순서는 비교 불가를 허용한다
비엄격 부분순서는 반사·반대칭·추이입니다. 양의 정수의 약수 관계가 예입니다. 서로 나누면 양수 조건으로 두 수가 같고, 두 번 나누어지는 것은 정수 인수를 곱하여 추이성을 보입니다.
{1,2,3,4}의 2와 3은 서로 나누지 않아 비교 불가입니다. 그래도 부분순서입니다. 모든 쌍이 비교되어야 전순서입니다. 수의 ≤는 전순서이지만 여기의 약수 관계는 아닙니다.
양수 조건이 중요합니다. 부호 있는 정수에서는 2와 −2가 서로 나누지만 같지 않아 반대칭이 실패합니다. 영역을 바꾸면 성질도 달라집니다.
엄격한 순서의 다른 규약
<는 반사적이지 않아 위 비엄격 정의의 부분순서가 아닙니다. 비반사적이고 추이적인 엄격한 순서입니다. 비엄격 부분순서에서 서로 다른 원소만 남기거나, 엄격 순서에 등호를 추가하여 대응할 수 있습니다.
규약을 번역하면 관계가 연결되지만 증명 중에 섞으면 안 됩니다. 실험 검사는 항상 위 표의 정의를 사용합니다.
실제 실패 증인 찾기
반사 실패는 xRx가 아닌 x, 대칭 실패는 xRy이지만 yRx가 아닌 쌍, 반대칭 실패는 다른 x,y의 양방향 쌍입니다. 추이 실패에는 세 원소가 필요합니다.
실험은 실패한 성질별로 증인을 표시합니다. 2에 대한 합동은 1과 3에서 반대칭이 실패합니다. <는 모든 원소에서 반사성이, 증가하는 쌍에서 대칭성이 실패합니다. 두 원소의 실패가 자동으로 추이 반례가 되는 것은 아닙니다.
유한 검사는 해당 영역의 모든 쌍·세쌍을 확인합니다. 그 유한 관계의 성질을 결정하지만 모든 양의 정수의 주장에는 앞의 일반 논증이 필요합니다.
AI의 유사도와 순위
‘임베딩 거리가 ε 이하’는 보통 반사·대칭이지만 추이적이지 않습니다. 0, 0.75ε, 1.5ε의 세 점은 짧은 두 연결과 멀어진 양 끝을 만듭니다. 유사도 임계값을 자동으로 동치라고 부르면 안 됩니다. 추이 폐포를 취하면 관계가 달라지고 긴 사슬이 한 집단으로 합쳐질 수 있습니다.
여러 목적의 Pareto 비교에는 비교 불가가 생깁니다. 단일 순위를 강제하면 추가 선호를 넣는 것입니다. 선수 그래프도 비순환성·추이 해석을 확인해야 합니다. ‘동등한 모형’, ‘더 좋은 방법’이라는 표현은 어떤 관계인지 명시하세요.
실험 읽기
행·열은 1부터 N까지 원소입니다. T/F는 확률이 아닌 정확한 관계입니다. 세 예제는 합동·약수·엄격 순서를 비교하며 별도 코드로 ≤도 선택합니다. 법 k는 합동에만 영향을 주므로 다른 관계에서 바꿔도 관계는 그대로입니다.
연습과 근거
- 등호는 대칭인가요, 반대칭인가요? 답: 둘 다입니다.
- 약수 관계의 최소·극대 원소는? 답: 1은 최소이며 3과 4는 극대입니다.
- 거리 임계값으로 대칭이지만 추이적이지 않은 관계를 만드세요.
- 다목적 실험에서 순위 규칙은 데이터 자체가 아니라 설계의 일부인 이유는?
보충은 MIT Mathematics for Computer Science 읽기 자료를 참고하세요. 실험은 명시한 유한 영역과 실제 계산한 증인을 사용합니다.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.