완전순서

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

어떤 집합 X에 대한 완전순서(完全順序, total order, linear order, simple order), 선형순서반대칭적이고, 추이적이고, 완전성 성질이 있는 이항관계를 말한다. 즉, 집합 X와 이항관계 ≤가 있을 때, 임의의 원소 a, b, c에 대해서 항상 다음의 조건을 만족할 경우 ≤는 집합 X 위에서 완전순서를 만족한다고 한다.

  1. 반대칭성: a ≤ b이고 b ≤ a면 a = b
  2. 추이성: a ≤ b이고 b ≤ c이면 a ≤ c
  3. 완전성: 항상 a ≤ b거나 b ≤ a

부분순서는 완전순서에서 완전성 조건 대신 더 약한 조건인 반사성으로 대체한 경우로, 즉 어떤 서로 다른 두 원소에 대해 이항관계가 없을 수도 있는 경우를 포함한다. 즉, 완전순서는 항상 부분순서가 되며, 어떤 부분순서가 모든 원소에 대해 비교가 가능할 경우('완전'할 경우) 완전순서가 된다.

완전순서가 주어진 집합을 완전순서집합이라고 한다. 사슬(chain)이라는 용어도 사실상 같은 뜻이나, 이는 보통 부분순서집합에 포함된 완전순서 부분집합을 가리킬 때 쓴다.

순완전순서[편집]

순완전순서(strict total order)는 완전순서에서 등호 조건을 제거한 이항관계이다. 완전순서 ≤가 있을 때, 순완전순서 <는 다음과 같이 두 가지 방법으로 정의가 가능하다.

  • a < b는 a ≤ b, a ≠ b와 동치이다.
  • a < b는 b ≤ a가 아니라는 것과 동치이다.

반대로, 이미 정의된 순완전순서에 대해서 완전순서를 정의하는 것도 가능하다.