코넥스 관계

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

수학에서, 집합 X 에 대한 어떤 이항관계 R이 X 에서 뽑은 가능한 모든 요소 쌍 사이를 (어떤 방식으로든) 연관짓는 경우 이를 코넥스 관계(Connex relation)라고 한다. 형식적으로, R

한편, 모든 같지 않은 두 요소의 쌍 사이를 연관짓는 경우는 준-코넥스 관계라고 한다. 코넥스 속성은 순서 이론에서 유래된 개념으로, 순서 이론에서는 전체 순서를 부분 순서가 코넥스 관계를 따르는 특수한 경우로 취급한다. 이에 고전적으로는 코넥스 성질을 전체 성질이라고도 일컫기도 하지만, 이 용어는 Right-totality (전사 함수)와 같은 전체(total)라는 용어가 사용되는 다른 무관한 개념들과 혼동을 줄 수 있는 단점이 있다. 일부 문헌에서는 코넥스 관계를 어떤 관계의 완전성으로 부르기도 한다. [출처 필요]

약식 설명[편집]

어떤 집합 X과 어떤 관계 R이 있을 때, 이 집합에서 어떤 두 개의 요소 x, y를 뽑아내든 x가 y에 대해 R하든지, 혹은 반대로 y가 x에 대해 R하다고 말할 수 있다면, 이 때 관계 R을 집합 X에 대한 코넥스 관계라고 한다. 대표적인 코넥스 관계의 예시는 다음과 같다.

  • (정수 집합 Z에 대해) 부등호 관계 ≤
  • (공무원의 직급, 즉 1~9급에 대해) 직급의 서열

형식 정의[편집]

어떤 집합 X에 대해 코넥스 관계 R은, 집합 내 임의의 두 요소 x, y로 만들어 진 모든 (x, y) 쌍에 대해, 적어도 xR혹은 yRx 둘 중 하나가 적법한 균일 이항관계이다. 보편적 관계 X × X에 대해서는 다음과 같이 표현할 수 있다. 

RTR의 역관계.

한편 임의의 관계 R x≠y인 두 요소 x, y에 대해, 가 곧  의미한다면, 관계 R는 준-코넥스이다. 단위 관계 I를 이용하면 준-코넥스 관계를 다음과 같이 서술할 수도 있다.

I 위의 가로줄은 여집합을 표시.

몇몇 문헌에서는 특별히 준-코넥스 특성을 따로 정의하지 않고, 후자의 특성을 바로 코넥스 특성이라고 이르기도 한다.[1][2][3]

참조 문헌[편집]

  1. Bram van Heuveln. “Sets, Relations, Functions” (PDF). Troy, NY. 2018년 5월 28일에 확인함.  Page 4.
  2. Carl Pollard. “Relations and Functions” (PDF). Ohio State University. 2018년 5월 28일에 확인함.  Page 7.
  3. Felix Brandt; Markus Brill; Paul Harrenstein (2016). 〈Tournament Solutions〉. F. Brandt; V. Conitzer; U. Endriss; J. Lang; A. Procaccia. 《Handbook of Computational Social Choice》. Cambridge University Press.  Page 3, footnote 1.