이항관계 : 두 집합 A,B에 대하여 A에서 B로의 이항관계binaryrelation는 A∗B의 부분집합이다.
정의역 / 치역 : 관계 R의 순서쌍에서 모든 첫 번째 원소의 집합을 정의역domain이라고 하고 모든 두 번째 원소의 집합을 치역range이라고 하며, 각각 dom(R),ran(R)로 나타낸다.
집합 A1,A2,…,An에 대한 n항 관계n−ary relation는 A1∗A2∗…∗An의 부분집합이다.
역관계 : 집합 A에서 집합 B로 관계 R에 대한 역관계inverse relation는 R−1로 나타내며, 다음과 같이 정의한다.
관계의 표현
화살도표 : 두 집합 A,B가 있을 때 집합 A의 원소 a와 집합 B의 원소 b 사이에 관계가 성립하는 경우 그 관계를 화살표로 그려서 나타내는 방법
좌표도표 : 두 집합 A,B가 있을 때 집합 A의 원소 a를 x축 위의 점으로 표시하고, 집합 B의 원소 b를 y축 위의 점으로 표시하여 두 점이 좌표 상에서 만나는 점을 나타내는 방법
관계행렬 : 두 집합 A,B에 대한 관계를 행렬로 표현한 방법. A의 원소들을 행에 배치하고 B의 원소들을 열에 배치한 후 A의 원소와 B의 원소 사이에 관계가 있으면 1로, 관계가 없으면 0으로 행렬의 원소를 나타낸다.
방향그래프 : 하나의 집합에 대한 관계를 나타내며, 집합의 원소들을 나타내는 정점vertex를 그리고, 원소 (a,b)가 관계에 속하면 a에서 b로 화살표 모양의 에지edge를 그린다.
집합 A에 대한 관계 R은 다음과 같이 분류한다.
집합 A에 대한 관계 R은 다음과 같이 분류한다.
관계의 연산
집합 A에서 B로의 관계를 R이라 하고, 집합 B에서 C로의 관계를 S라고 하자. R과 S의 합성관계composition relation는 a∈A고 c∈C일 때 aRb고 bSc인 b∈B가 존재하는 순서쌍 (a,c)로 구성되는 단계며 S∘R로 나타낸다.
집합 A에 대한 관계 R에 대하여 n=1,2,3,…일 때 거듭제곱 Rn은 다음과 같다.
집합 A에 대한 관계 R이 추이관계일 때 모든 양의 정수 n에 대하여 Rn⊆R이다.
관계의 폐포
집합 A에 대한 관계를 R이라고 하고 그 관계가 갖는 성질들을 P라고 할 때 집합 A에 대한 관계 S가 R을 포함하면서 성질 P를 갖는 모든 관계의 부분집합이면 S를 P에 관한 R의 폐포(closure, 닫힘)라고 한다. 또한 관계 S는 성질 P가 반사적이냐 대칭적이냐 추이적이냐에 따라 각각 R의 반사폐포, 대칭폐포, 추이폐포가 된다.
동치관계
동치관계 : 반사관계, 대칭관계, 추이관계가 모두 성립하는 관계 R을 동치관계라고 한다.
동치류 : 집합 A에 대한 관계 R이 동치관계일 때 집합 A의 각 원소 a에 대하여 [a]를 R에 대한 a의 동치류라고 하며, 다음과 같이 정의한다.
부분순서관계
부분순서관계 / 부분순서집합 : 집합 A에 대한 관계 R이 반사관계, 반대칭관계, 추이관계가 성립하면 관계 R을 부분순서관계라고 한다. 그리고 이때 A를 부분순서집합 이라고 하며, (A,R)로 나타낸다.
완전순서관계 / 완전순서집합 : 집합 A에 대한 관계 R이 부분순서관계고 a,b∈A일 때 a⪯b또는 b⪯a면 a와 b는 비교가능하다고 하고, a⪯̸b또는 b⪯̸a면 a와 b는 비교불가능하다고 한다. 이대 집합 A에 속하는 원소들의 모든 쌍이 비교가능하면 R을 완전순서관계 또는 선형순서관계라고 하며, 집합 A를 완선순서집합 또는 선형순서집합이라고 한다.
사전식순서 : 두 부분순서집합 (A,⪯1)과 (B,⪯2)가 있을 때 곱집합 A∗B에 대한 사전식 순서 (a1,b1)⪯(a2,b2)는 a1≺a2인 경우 또는 a1=a2고 b1≺b2인 경우에 정해진다.
극대원소 / 극소원소 : 부분순서집합 (A,⪯)가 있을 때 A의 원소 a에 대하여 a≺b인 원소 b가 A에 존재하지 않으면 원소 a를 극대원소라고 하며, b≺a인 원소 b가 A에 존재하지 않으면 원소 a를 극소원소라고 한다.
최대원소 / 최소원소 : 부분순서집합 A의 모든 원소 b에 대하여 b⪯a인 A의 원소 a를 최대원소라고 하며, a⪯b인 A의 원소 a를 최소원소라고 한다.
위상정렬 : ⪯1과 ⪯2가 집합 A에 대한 부분순서관계라고 하자. 이때 A의 모든 원소 a와 b에 대하여 a⪯1b면 a⪯2b를 만족할 때 ⪯2는 ⪯1과 양립한다고 한다. 그리고 ⪯2가 ⪯1과 양립할 수 있는 완전순서관계면 ⪯2는 ⪯1에 대한 위상정렬이라고 한다.
