순서론

순서론(順序論, 영어: order theory)은 이항 관계들 중에서 '순서'의 개념을 확장한 것으로 볼 수 있는 것들을 다루는 수학의 분야이다.

개론

수학 및 이에 관련된 컴퓨터 과학 등의 분야에서 순서의 개념은 널리 사용된다. 가장 기본적인 순서로는 자연수를 크기에 따라 순서대로 정렬하는 ≤가 있다. 또한, 사전에서 단어를 정렬할 때 쓰는 사전식 순서도 일반적으로 알려진 순서의 예이다.

위의 두 순서는 임의의 두 원소를 언제나 서로 비교할 수 있다는 공통점이 있다. 즉, 두 자연수 a와 b는 언제나 a≤b 혹은 b≤a이며, 두 단어가 있을 때는 어느 쪽이 사전에서 앞에 위치하는지를 결정할 수 있다. 하지만 이 조건이 성립하지 않는 중요한 경우도 있는데, 대표적인 예로 집합의 부분 집합 관계를 생각해 볼 수 있다. A와 B가 자연수 집합의 부분 집합일 때, A가 B의 모든 원소를 포함할 경우 "B는 A보다 작거나 같다"라고 말하기로 하자. 이때 A = {1,2,3}, B = {1,4}일 경우 어느 쪽도 상대방을 포함하지 않으므로 이 두 집합은 비교할 수 없다. 이를 두고 부분 집합 관계를 부분 순서라고 하고, 임의의 원소를 서로 비교할 수 있는 순서를 전순서라고 한다.

정의

이 부분에서는 집합론, 산술 및 이항관계의 기초적인 개념을 이용해 순서론의 기본 개념들을 정의한다.

부분 순서와 전순서

순서는 이항 관계의 일종이다. P가 집합이고 ≤가 그 위의 이항관계라 하자. 이때 ≤가 반대칭적이면서 추이적이고 동시에 반사적일 경우 이를 부분 순서라 한다. 만약 이 부분 순서가 완전성 조건까지 만족할 경우 이를 전순서라 한다. 부분 순서가 주어진 집합을 부분 순서 집합, 전순서가 주어진 집합을 전순서 집합이라 한다.

특수한 원소

부분 순서 집합에서 자신을 제외한 어떤 원소보다도 큰 원소를 최대 원소라 하고, 자신을 제외한 어떤 원소보다도 작은 원소를 최소 원소라 한다. 또한, 어떤 원소보다도 작지 않은 원소를 극대 원소라 하고, 어떤 원소보다도 크지 않은 원소를 극소 원소라 한다.

예를 들어, 집합 {2,3,4,5,6} 상의 약수 관계(원소 a가 원소 b를 나눌 경우 "a는 b보다 작거나 같다"로 정의하는 관계)를 생각해 보자.

모든 원소를 나누거나 모든 원소에 의해 나뉘는 원소가 없으므로 최대 및 최소 원소는 존재하지 않는다.
2,3,5는 자신을 제외한 원소에 의해 나뉘지 않으므로 극소 원소이다.
4,5,6은 자신을 제외한 원소를 나누지 않으므로 극대 원소이다.

극대 원소의 존재를 증명할 때에는 초른 보조정리가 중요하게 쓰인다.

부분 순서 집합의 부분 집합에 포함된 어떤 원소보다도 같거나 큰 원소를 그 부분집합의 상계라 하고, 어떤 원소보다도 작거나 같은 원소를 그 부분집합의 하계라 한다. 상계 중에 가장 작은 원소를 상한이라 하고, 하계 중에 가장 큰 원소를 하한이라 한다.

예를 들어, 정수의 집합에서 −5와 −3은 둘 다 자연수 집합의 하계이며, 이 경우 상계는 존재하지 않는다. 여기에서 1은 자연수 집합의 최대 하계인데, 이것이 동시에 자연수 집합의 원소이므로 이는 최소 원소와 일치한다. 일반적으로 최대 하계가 존재한다고 해도 이것이 부분 집합 자체에 포함되어 있어야 할 필요는 없다.

같이 보기