순서론

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
Lattice of the divisibility of 60.svg

순서론(順序論, 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은 자연수 집합의 최대하계인데, 이것이 동시에 자연수 집합의 원소이므로 이는 최소원소와 일치한다. 일반적으로 최대하계가 존재한다고 해도 이것이 부분집합 자체에 포함되어 있어야 할 이유는 없다.

함께 보기[편집]