부분순서·격자

모든 두 대상이 비교될 필요는 없다

부분순서 ≤는 반사성 a≤a, 반대칭성 a≤b와 b≤a이면 a=b, 추이성 a≤b≤c이면 a≤c를 만족합니다. 전순서는 추가로 모든 두 원소가 비교됩니다. 포함 관계 ⊆는 부분순서이지만 일반적으로 전순서가 아닙니다.

실습은 U={0,1,2}의 모든 부분집합 여덟 개를 원소로 하는 B₃입니다. A={0,1},B={0,2}는 어느 쪽도 다른 쪽에 포함되지 않아 비교 불가입니다. 이는 A=B도 아니고 어떤 모순도 아닙니다. 순서가 부분적으로만 지정되었다는 뜻입니다.

Hasse 그림의 읽는 방향

그림에서 위로 갈수록 포함 관계의 큰 집합입니다. 원소 하나를 추가하는 덮개 관계만 선으로 표시합니다. 자기 자신으로 가는 반사 간선과 여러 선을 따라 이미 알 수 있는 추이 간선은 생략합니다.

그러므로 A에서 B로 직접 선이 없어도 아래에서 위로 여러 선을 따라가면 A⊆B입니다. 모든 정점과 정점을 잇는 선이 들어 있는 관계 그래프와 Hasse 그림은 다릅니다. 가로 위치와 선 길이는 크기나 거리의 수치가 아닙니다. 높이는 이 특정 부분집합 예제에서 원소 개수에 따라 정했습니다.

공통 하한과 meet

A,B의 하한 X는 X⊆A이고 X⊆B인 집합입니다. 가장 큰 하한을 meet라 하며 A∧B로 씁니다. 여기서 “가장 큰”은 크기 수치가 아니라 부분순서 의미입니다.

A∩B는 양쪽에 포함되므로 하한입니다. 다른 모든 공통 하한 X는 A∩B에도 포함됩니다. 따라서

A={0,1},B={0,2}의 meet는 {0}입니다. 비교 불가인 원소 사이에도 meet가 존재할 수 있습니다. 극대 하한과 최대 하한을 구분하세요. 일반 부분순서에서는 비교 불가인 극대 하한이 여러 개일 수 있고, 이 경우 meet가 존재하지 않을 수 있습니다.

공통 상한과 join

상한 Y는 A⊆Y,B⊆Y를 만족합니다. 가장 작은 상한이 join이며 A∨B입니다. 합집합은 상한이고 다른 모든 상한에 포함되므로

기준 예제에서 join은 {0,1,2}입니다. 모든 원소쌍에 meet와 join이 존재하는 부분순서를 격자라고 합니다. 모든 부분순서가 격자는 아닙니다. 두 점이 서로 비교 불가이고 공통 상한이 없는 부분순서는 join이 없습니다.

경계·흡수·분배 법칙

부분집합 격자의 최소 원소는 ∅, 최대 원소는 U입니다. A∩(A∪B)=A와 A∪(A∩B)=A는 흡수 법칙입니다. 원소별 포함 여부로 증명할 수 있습니다.

이 격자는 분배적이며 여집합 U\A도 있습니다. 이런 구조는 Boolean 대수의 집합 모형입니다. 그러나 임의의 격자에 분배 법칙이나 여원 존재를 자동으로 가정할 수는 없습니다. 예를 들어 벡터 부분공간 격자의 join은 단순 집합 합집합이 아니라 선형 생성 공간입니다.

실습의 비트 연산

집합 마스크 3은 {0,1}, 5는 {0,2}입니다. 비트 AND는 교집합으로 3&5=1, 비트 OR는 합집합으로 3|5=7입니다. A⊆B는 (A&B)=A와 같습니다. 표에서 마스크와 실제 집합을 함께 확인하세요.

마스크 1,3을 선택하면 A⊆B여서 meet=A,join=B입니다. 마스크 0,7은 최소와 최대 원소입니다. 진리값 AND와 집합 meet는 서로 다른 대상에서 작동하지만 원소별 소속 지시값을 통해 연결됩니다.

AI 연결과 확인 문제

데이터 흐름 분석, 정보의 정밀도, 제약의 포함 관계에서 부분순서가 쓰입니다. 더 큰 집합이 “더 많은 정보”인지 “더 많은 가능한 상태라서 덜 정밀한 정보”인지는 해석에 따라 반대일 수 있습니다. 분석의 순서 방향을 먼저 정의하세요. 임의의 격자에서 고정점 알고리즘의 수렴을 주장하려면 단조성·완비성·유한 높이 등 해당 정리의 조건을 확인해야 합니다.

1. A⊆B일 때 meet,join은? A와 B입니다.
2. 비교 불가가 meet 부재를 뜻하나요? 아니요. 기준 예제가 반례입니다.
3. B₃에서 모든 쌍을 비교 가능하게 정렬하면 원래 포함 순서와 같나요? 아니요. 선형 확장은 새로운 비교를 추가합니다.

추가 읽기: MIT Mathematics for Computer Science. 본문은 유한 부분집합 격자의 직접 논증입니다.