5장
관계
1. 관계와 이항관계
• 일상생활에서의 관계
• 주로 인간과 인간의 관계로 가족 관계, 친구 관계, 직장 동료 관계, 교수-학생 관계 등을 말함
• 컴퓨터 시스템에서의 관계
• 하드웨어를 구성하는 각 파트의 관계, 데이터와 데이터 간의 관계 등을 말함
• 데이터와 데이터 간의 관계 예
• 아래에 있는 교수정보 테이블과 학생 정보 테이블은 각각 교 수 및 학생에 대한 정보를 갖고 있고, 이 두 테이블에 속한 데 이터들이 일정한 관계를 맺으면서 새로운 관계인 수강신청 정 보라는 테이블을 생성함
관계
교수 정보
학번 학생명 학과
학생 정보
학번 학생명 학과 과목코드 과목명 교수명
수강 신청 정보
교번 교수명 학과
1. 관계와 이항관계
• 관계(relation)의 정의
• 서로 다른 두 집합이 A, B가 있을 때, A에서 B로의 관계 R은 그 두 집합의 원소 a와 b의 순서쌍들의 모임으로 정의함
• 예 : A={철수, 영희, 기훈, 미정, 소희}, B={남자, 여자}일 때 관 계 R을 사람과 성별의 관계로 정의한다면 R={(철수,남자), (영희, 여자), (기훈,남자), (미정,여자), (소희,여자)}임
• 일반적으로 관계라고 하면 이항(2항)관계(binary relation)라고 보면 됨
• 이항이 넘는 경우에는 3항(3-ary)관계, n항(n-ary)관계로 명확히 명시해야 함
• 이항관계는 두 집합의 원소 a, b가 관계 있을 때 aRb로 쓰고, 관계가 없다면 a℟b로 표기함
• aRb⇔(a,b)∈R, a℟b⇔(a,b)∉R
• 이항관계를 표현하는 순서쌍에서 먼저 나오는 것을 정의역 (domain), 뒤에 나오는 것을 치역(range)이라고 말함
• 정의역 : Dom(R)={a｜(a,b)∈R}⊆A
1. 관계와 이항관계
• 이항관계 예
• 예 1
• 두 집합 A, B에서 A={0, 1, 2}이고, B={1, 2, 3}이라고 하 자. 집합 A의 원소 x, 집합 B의 원소 y에 대해 x가 y보다 작은 관계의 집합을 구하라.
• 0<1이므로 0R1
• 0<2이므로 0R2
• 0<3이므로 0R3
• 1≮1이므로 1℟1
• 1<2이므로 1R2
• 1<3이므로 1R3
• 2≮1이므로 2℟1
• 2≮2이므로 2℟2
• 2<3이므로 2R3
• 따라서 집합 A와 B의 곱집합의 원소 9개 중에서 주어진 관 계를 만족하는 집합 R={(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}임
1. 관계와 이항관계
• 예 2
• 두 집합 A={1, 2}, B={1, 2, 3}이라고 할 때, 이항관계 R이 (a,b)∈AⅹB, (a,b)∈R⇔‘a-b는 짝수’라고 하자.
• AⅹB의 순서쌍과 관계 R의 순서쌍을 구하라.
• AⅹB의 순서쌍은 {(1,1), (1,2), (1,3), (2,1), (2,2), 2,3)}
• 관계 R의 순서쌍은 {(1,1), (1,3), (2,2)}
• 1R3, 2R3, 2R2가 성립하는가?
• 1-3은 짝수이므로 1R3
• 2-3은 홀수이므로 2℟3
• 2-2는 짝수이므로 2R2
• Dom(R)과 Ran(R)을 구하라.
• Dom(R)={1, 2}
• Ran(R)={1, 2, 3}
• 이항관계에서의 주의사항
• 이항관계에서의 순서쌍은 순서가 있기 때문에 xRy≠yRx임을 유
1. 관계와 이항관계
• 3항관계의 예
• 세 집합 A, B, C에서 A={1, 2}이고, B={x, y, z}, C={3, 4}라고 하자. 집합 A, B, C의 곱집합 AⅹBⅹC를 구하라.
• {(1,x,3), (1,x,4), (1,y,3), (1,y,4), (1,z,3), (1,z,4), (2,x,3), (2,x,4), (2,y,3), (2,y,4), (2,z,3), (2,z,4)}
• 교과목의 학점 집합 A, 교과목 집합 B, 학생의 이름 집합 C에서 A={1, 2, 3}, B={이산수학, C언어프로그래밍}, C={홍길동, 이순 신, 김유신}라고 하자. 집합 A, B, C의 곱집합 AⅹBⅹC를 구하라.
• 역관계(inverse relation)
• 집합 A에서 집합 B로의 관계 R에 대한 역관계 R-1은 집합 B에서 집합 A로의 관계를 나타내며 관계 R의 순서쌍 내의 순서를 바꾸 는 것으로 손쉽게 표현할 수 있음
• 예
• 두 집합 A, B에서 A={1, 2, 3}, B={3, 4}일 때 관계
R={(1,3), (2,3), (2,4), (3,4)}이라고 하자. 관계 R의 역관계 R-1을 구하라.
• R-1={(3,1), (3,2), (4,2), (4,3)}
2. 관계의 표현
• 화살표 도표(arrow diagram)
• 집합 A의 원소 a와 집합 B의 원소 b가 관계가 있을 때, a에서 b로 화살표를 연결함으로써 관계를 표현하는 기법
• 집합 A={1, 2, 3, 4}, 집합 B={a, b, c}일 때, 그들 사이에 다음과 같은 관계 R={(1,a), (1,c), (2,b), (3,a), (3,c), (4,b)}이 형성되어 있 다면 화살표 도표로는 다음과 같이 표현할 수 있음
관계를 나타내는 다양한 표현
1
2
3
a
b
c
2. 관계의 표현
• 좌표 도표(coordinate diagram)
• 집합 A의 원소 a와 집합 B의 원소 b가 관계가 있을 때, a를 x 좌표 로, b를 y 좌표로 지정하여 x, y 좌표가 만나는 곳에 점으로 표현하 는 기법
• 집합 A={1, 2, 3, 4, 5}, 집합 B={2, 3, 4}일 때, 그들 사이에 다음 과 같은 관계 R={(1,2), (1,4), (2,3), (4,2), (4,4), (5,2), (5,3)}이 형 성되어 있다면 좌표 도표로는 다음과 같이 표현할 수 있음
B
O 1 2 3 4 5 A
1 2 3 4
2. 관계의 표현
• 방향 그래프(directed graph)
• 관계 R이 두 집합 A, B에서 발생한 것이 아니라 자신(즉, A와 A 또 는 B와 B)과의 관계일 때 주로 사용하는 표기법으로, 집합 A의 각 원소를 정점(vertex), (a,b)∈R인 경우 a에서 b를 연결하는 간선 (edge)으로 표현하는 기법
• 집합 A={a, b, c, d}이고 관계 R={(a,b), (b,a), (a,d), (d,c), (c,c), (c,a)}이라면 방향 그래프로는 다음과 같이 표현할 수 있음
a b
d c
2. 관계의 표현
• 관계 행렬(relation matrix)
• 관계를 나타내는 정보를 행렬을 이용하여 표현하는 방법으로 두 집합 A, B에서 A의 원소는 행(row), B의 원소는 열(column)에 표기 하고, 원소 간에 관계가 있으면 행렬의 값을 1, 관계가 없으면 0으 로 표현하는 기법
• M[i,j] ╔ 1 if (ai,bj)∈R ╘ 0 if (ai,bj) ∉R 단, i=1,2,…,n, j=1,2,…,m
• 집합 A={1, 2, 3}, B={2, 4, 6}이고 관계 R={(1,2), (1,4), (2,2), (3,4), (3,6)}이라면 관계 행렬로는 다음과 같이 표현할 수 있음
1 1 0 1 0 0 0 1 1
1 2 3
2 4 6
2. 관계의 표현
• 관계를 표현하는 예
• 집합 A={1, 2, 3, 4}, B={x, y, z}일 때, 이 둘의 관계 R={(1,y), (1,z), (3,y), (4,x), (4,z)}라 하자.
• 관계 R을 화살표 도표, 좌표 도표, 관계 행렬로 표현하라.
1
2
3
4
x
y
z
B
O 1 2 3 4 A
x y z
0 1 1 0 0 0 0 1 0 1 0 1
1 2 3
x y z
4
화살표 도표 좌표 도표 관계 행렬
3. 합성 관계
• 합성 관계(composite relation)
• 세 집합 A, B, C에서 R1을 집합 A에서 집합 B로의 관계, R2를 집 합 B에서 집합 C로의 관계라고 한다면 집합 A에서 집합 C로의 관 계를 합성 관계라고 하고, R1·R2 또는 R1R2로 표기함
• R1·R2={(a,c)｜a∈A, c∈C, (a,b)∈R1이고, (b,c)∈R2}
• 예를 들어, 세 집합 A, B, C는 A={1, 2, 3, 4}, B={a, b, c}, C={x, y, z}이고, 집합 A에서 집합 B로의 관계 R, 집합 B에서 집합 C로의 관계 S가 다음과 같을 때 R·S를 구하라.
• R={(1,a), (1,b), (2,b), (3,a), (4,b), (4,c)}
• S={(a,x), (b,y), (c,x), (c,z)}
합성 관계
1 2 3 4
a b c
x y z
1 2 3 4
x y z
관계 R 관계 S 관계 R·S
집합 A 집합 B 집합 C 집합 A 집합 C
3. 합성 관계
• 합성 관계의 관계 행렬 표현 예
• 세 집합 A, B, C는 A={1, 2, 3, 4}, B={a, b, c}, C={x, y, z}
이고, 집합 A에서 집합 B로의 관계 R, 집합 B에서 집합 C로의 관계 S가 다음과 같을 때 R·S를 구하라.
• R={(1,a), (1,b), (2,b), (3,a), (4,b), (4,c)}
• S={(a,x), (b,y), (c,x), (c,z)}
1 1 0 0 1 0 1 0 0 0 1 1
1 2 3
a b c
4
1 0 0 0 1 0 1 0 1
a b c
x y z
1 1 0 0 1 0 1 0 0 0 1 1
1 2 3
x y z
4
관계 R 관계 S 관계 R·S
3. 합성 관계
• 합성 관계의 화살표 도표 표현 예
• 세 집합 A, B, C는 A={1, 2, 3, 4}, B={a, b, c, d}, C={x, y, z}
이고, 집합 A에서 집합 B로의 관계 R, 집합 B에서 집합 C로의 관계 S가 다음과 같을 때 R·S를 구하라.
• R={(1,a), (2,d), (3,a), (3,b), 3,d)}
• S={(b,x), (b,z), (c,y), (d,z)}
1 2 3 4
a b c d
x y z
1 2 3 4
x y z
관계 R 관계 S 관계 R·S
집합 A 집합 B 집합 C 집합 A 집합 C
3. 합성 관계
• 항등 관계(identity relation)
• 다음 조건을 만족하는 경우 IA를 집합 A에 대한 항등 관계라고 말함
• IA={(a,a)｜a∈A}
• 곱셈의 항등원(1), 덧셈의 항등원(0)이 연산 결과에 영향을 주지 않듯이 항등 관계와 어떤 관계를 합성하든 결과 값에는 변화가 없 음
• IA R=RIB=R
• 예
• 집합 A={1, 2, 3, 4}, 집합 B={1, 2, 3}, 집합 A에서 집합 B 로의 관계 R={(1,2), (1,3), (2,2), (3,1), (4,2)}라고 하자.
• IA ={(1,1), (2,2), (3,3), (4,4)}
• IB ={(1,1), (2,2), (3,3)}
• IA R={(1,2), (1,3), (2,2), (3,1), (4,2)}
• IB R={(1,2), (1,3), (2,2), (3,1), (4,2)}
• RI ={(1,2), (1,3), (2,2), (3,1), (4,2)}
4. 관계의 성질
• 반사 관계(reflexive relation)
• 집합 A의 모든 원소 x에 대하여 xRx이면, 즉 (x,x)∈R일 때 관계 R을 반사 관계라고 말함. 예를 들어, 집합 A={1, 2, 3, 4}일 때, 다 음 관계는 모두 반사 관계임
• R1={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,4)}
• R2={(1,1), (2,2), (3,3), (4,4)}
• R3={(3,2), (3,3), (4,4), (4,1), (2,3), (1,1), (2,2), (1,3)}
• 비반사 관계(irreflexive relation)
• 집합 A의 모든 원소 x에 대하여 (x,x)∉R인 경우에 비반사 관계라 고 말함. 예를 들어, 집합 A={1, 2, 3, 4}일 때, 다음 관계는 비반 사 관계임
• R4={(1,2), (1,3), (2,1), (2,3), (3,2), (3,4), (4,2)}
• 예를 들어, 집합 A={1, 2, 3, 4}일 때, R5={(1,1), (1,2), (1,3), (2,1), (2,3), (3,2), (3,4), (4,2)}라면 R5는 반사 관계도 아니고, 비반사 관계도 아님
관계에 대한 여러 가지 성질
4. 관계의 성질
• 대칭 관계(symmetric relation)
• 집합 A의 임의의 원소 x, y에 대하여 (x,y)∈R일 때 (y,x)∈R이면 관계 R을 대칭 관계라고 말함. 예를 들어, 집합 A={1, 2, 3, 4}일 때, 다음 관계 R1은 대칭 관계임
• R1={(1,1), (1,2), (2,1), (3,3), (3,4), (4,3)}
• 대칭 관계 예
• x, y가 자연수의 집합 N의 원소일 때 다음 관계가 대칭 관계 인지 구분해보자.
• R2={(x,y)｜x∈N, y∈N, x+y=20} : x와 y의 합이 늘 20 이어야 하므로 대칭 관계이다.
• R3={(x,y)｜x∈N, y∈N, x≢y} : x=1, y=2일 때는 성립 하지만, x=2, y=1일 때는 성립하지 않으므로 대칭 관계 가 아니다.
• 반대칭 관계(anti symmetric relation)
• 집합 A의 모든 원소 x, y에 대하여 (x,y)∈R이고, (y,x)∈R일 때 x=y이면 관계 R을 반대칭 관계라고 말함
4. 관계의 성질
• 추이 관계(transitive relation)
• 집합 A의 원소 x, y, z에 대하여 (x,y)∈R이고, (y,z)∈R이면 (x,z)∈R인 관계 R을 추이 관계라고 말함. 예를 들어, 집합 A={1, 2, 3}일 때, 다음 관계 R은 추이 관계가 아니고, S는 추이 관계임
• R={(1,1), (1,2), (2,2), (2,3)} : (1,2)와 (2,3)은 R의 원소이 지만 (1,3)은 R의 원소가 아니기 때문임
• S={(1,1), (1,2), (2,1), (2,2), (3,3)}
• 추이 관계의 예
• 집합 A={a, b, c, d}일 때 다음 관계가 추이 관계인지 판별 하시오.
• R1={(a,a), (a,d), (b,c), (c,c), (c,a), (d,b), (d,d)} : (a,d) 와 (d,b)는 R1의 원소지만, (a,b)는 R1의 원소가 아니기 때문 에 추이 관계가 아님
• R2={(a,a), (b,b), (c,c), (d,b), (d,d)} : 추이 관계임
• R3={(a,a), (d,d)} : 추이 관계임
• R4={(a,d), (b,c), (d,a), (d,b)} : (a,d)와 (d,a)는 R4의 원소 지만 (a,a)는 R4의 원소가 아니기 때문에 추이 관계가 아님
4. 관계의 성질
• 방향 그래프로 표현된 추이 관계 성립 예
a
b c
1 4
R1
R2
• (a,a)와 (a,b) 모두 R1의 원소이고, (a,b)도 R1의 원소임
• (a,a)와 (a,c) 모두 R1의 원소이고, (a,c)도 R1의 원소임
• (a,b)와 (b,b) 모두 R1의 원소이고, (a,b)도 R1의 원소임
• (a,b)와 (b,c) 모두 R1의 원소이고, (a,c)도 R1의 원소임
• 따라서, 추이 관계임
• (1,3)과 (3,4) 모두 R2의 원소이고, (1,4)도 R2의 원소임
• (2,1)과 (1,4) 모두 R2의 원소이지만, (2,4)는 R2의 원소 가 아님
• 따라서, 추이 관계가 아님
4. 관계의 성질
• 폐포(closure)
• 집합 A에 대한 관계 R이 있고, 관계 R이 가질 수 있는 성질을 P 라고 할 때, 집합 A에 대한 관계 S가 관계 R을 포함하면서 성질 P 를 갖는다면 관계 S를 관계 R에 대한 P의 폐포라고 함. 산술 연산 에서는 통상 ‘닫혀있다’라고 함
• 반사 폐포(reflexive closure)
• 집합 A에 대해 관계 R을 포함하면서 반사 관계를 갖는 S 즉, S=R∪{(a,a)｜a∈A}
• 즉, R을 그대로 갖고 있으면서 반사 관계도 성립해야 함
• 반사 폐포의 예
• 집합 A={1, 2, 3}이고, 관계 R={(1,1), (1,3), (2,1), (3,2)}
라면 S={(1,1), (1,3), (2,1), (2,2), (3,2), (3,3)}은 반사 폐포 임
• 대각선의 원소의 값을 모두 1로 만들어주면 손쉽게 반사 폐 포를 만들 수 있음
관계의 폐포
4. 관계의 성질
• 대칭 폐포(symmetric closure)
• 집합 A에 대해 관계 R을 포함하면서 반사 관계를 갖는 S 즉, S=R∪{(b,a)∈AⅹA｜(a,b)∈R}=R∪R-1
• 즉, R을 그대로 갖고 있으면서 대칭 관계도 성립해야 함
• 대칭 폐포의 예
• 집합 A={1, 2, 3}이고, 관계 R={(1,1), (1,3), (2,1), (3,2)}라 면 S={(1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2)}임
• 대칭이 되는 원소의 값을 모두 1로 만들어주면 손쉽게 대칭 폐포를 만들 수 있음
a
b c
d a
b c
d a
b c
d
4. 관계의 성질
• 추이 폐포(transitive closure)
• 집합 A에 대해 관계 R을 포함하면서 추이 관계를 갖는 S 즉, S=R∪{(a,c)∈AⅹA｜(a,b)∈R∧(b,c)∈R}
• 추이 폐포의 예
• 집합 A={a, b, c, d}이고, 관계 R={(a,b), (b,b), (b,c), (c,a)}일 때 관계 R의 추이 폐포 S를 구하라.
• (a,b)∈R이고, (b,b)∈R인데 (a,b)∈R이므로 OK!
• (a,b)∈R이고, (b,c)∈R인데 (a,c)∉R이므로 (a,c) 추가!
• (b,b)∈R이고, (b,c)∈R인데 (b,c)∈R이므로 OK!
• (b,c)∈R이고, (c,a)∈R인데 (b,a)∉R이므로 (b,a) 추가!
• (c,a)∈R이고, (a,b)∈R인데 (c,b)∉R이므로 (c,b) 추가!
• 기존의 R={(a,b), (b,b), (b,c), (c,a)}에 (a,c), (b,a), (c,b) 를 추가함
• 새로 추가된 (a,c), (b,a), (c,b)에 대해서도 추이 폐포가 성 립되어야 하므로 2차로 (a,a), (c,c)를 추가해서 최종적으로 S={(a,b), (b,b), (b,c), (c,a), (a,c), (b,a), (c,b), (a,a),
(c,c)}가 됨
5. 동치 관계와 분할
• 동치 관계(equivalence relation)
• 관계 R이 반사 관계, 대칭 관계, 추이 관계일 때 R을 동치 관계라 고 말함
• 동치 관계의 예
• 집합 A={1, 2, 3, 4}이고, 관계 R={(1,1), (1,3), (2,2), (2,4), (3,1), (3,3), (4,2), (4,4)}가 있을 때 동치 관계임을 확인하라.
• (1,1)∈R, (2,2)∈R, (3,3)∈R, (4,4)∈R이므로 반사 관계 성 립
• (1,3)∈R, (3,1)∈R이므로 대칭 관계 성립
• (1,1)∈R이고, (1,3)∈R인데 (1,3)∈R이고,
• (1,3)∈R이고, (3,1)∈R인데 (1,1)∈R이고,
• (1,3)∈R이고, (3,3)∈R인데 (1,3)∈R이고,
• (2,2)∈R이고, (2,4)∈R인데 (2,4)∈R이고,
• (2,4)∈R이고, (4,2)∈R인데 (2,2)∈R이고, 그 외 모든 x,y 동치 관계와 분할
5. 동치 관계와 분할
• 동치류 또는 동치 클래스(equivalence class)
• 집합 A에 대한 동치 관계를 R이라 할 때, A의 각 원소 x에 대하 여 [x]를 R에 대한 x의 동치류라고 하고, [x]={y｜(x,y)∈R}로 표 기함
• 몫집합(quotient set)
• 집합 A에 대한 동치 관계를 R이라 할 때, A의 각 원소 x에 대하 여 [x]를 R에 대한 x의 동치류라고 하면, 집합 A의 동치류의 모임 을 A의 몫집합이라 하고, ={[x]｜x∈A}로 표기함
• 분할(partition)
• 공집합이 아닌 집합 A의 분할은 다음 조건을 만족하는 A의 부분 집합의 모임 S={A1, A2, …, An}을 말함
• Ai≠ Ø, 1≢i≢n
• S=
∪
Ai• Ai∩Aj=Ø, i≠j
A
━ R
i=1 n
5. 동치 관계와 분할
• 동치류와 분할의 예
• 집합 A={1, 2, 3, 4}에 대한 동치 관계 R={(1,1), (1,2), (2,1), (2,2), (3,3), (3,4), (4,3), (4,4)}이라 할 때, 각 원소에 대한 동치 류를 구하라.
• [1]=[2]={1, 2}
• [3]=[4]={3, 4}
• 위와 같은 상황에서 이 동치류의 집합이 분할임을 보여라.
• 동치류의 집합 {1, 2}를 A1, {3, 4}를 A2라고 하자. A1과A2 모두 공집합이 아니므로 분할이 되기 위한 첫 번째 조건이 성 립한다. A1∪A2={1, 2, 3, 4}이므로 분할이 되기 위한 두 번 째 조건도 성립한다. A1∩A2=Ø이므로 분할이 되기 위한 세 번째 조건도 성립한다. 따라서, 두 동치류 {1, 2}와 {3, 4}는 집합 A의 분할이다.
• 합동(congruence)
• x≡y(mod m)와 같은 mod 합동이란 x와 y를 각각 m으로 나눴을 때 나머지가 같은 집합을 말하고, 예를 들어, 5일, 12일, 19일, 26
6. 부분 순서 관계
• 부분 순서 관계(partially ordered relation)
• 집합 A에 대한 관계 R이 반사 관계, 반대칭 관계, 추이 관계일 때 R을 부분 순서 관계라고 말함
• 부분 순서 관계의 예
• 자연수의 집합 N이 관계 ≢에 대해 부분 순서 관계임을 확인 하라.
• 임의의 자연수 x에 대해 x≢x이므로 반사 관계이다.
• x,y∈N일 때, x≢y이고 y≢x이면 x=y이므로 반대칭 관계이다.
• x,y,z∈N일 때, x≢y이고 y≢z이면 x≢z이므로 추이 관계이 다.
• 따라서, 관계 ≢은 부분 순서 관계라고 말할 수 있다.
• 부분 순서 관계는 통상 ‘≲’로 표기함. 즉, 집합 A의 두 원소 x,y에 대하여 x,y∈R을 x≲y로 표기하고, ‘x가 y를 선행한다’고 읽음
• 관계 R이 집합 A에 대한 부분 순서 관계이면 순서쌍 (A,R)을 부 분 순서 집합(partially ordered set : POSET)이라고 말함
부분 순서 관계
6. 부분 순서 관계
• 비교 가능(comparable)과 비교 불가능(non comparable)
• 부분 순서 집합 A의 두 원소 x,y가 x≲y 또는 y≲x이면 x와 y를 비 교 가능하다고 말함
• 부분 순서 집합 A의 두 원소 x,y가 x≴y 또는 y≴x이면 x와 y를 비 교 불가능하다고 말함
• 비교 가능과 비교 불가능의 예
• 자연수의 집합 N에 대해 관계 R={(a,b)∈NⅹN｜a｜b}(단, a｜b는 b가 a로 나누어 떨어지는 관계)라고 했을 때, a=2, b=4라면 2와 4는 비교 가능, a=2, b=5 라면 2와 5는 비교 불 가능임
• 집합 A의 모든 두 원소가 비교 가능하면 집합 A를 선형 순서 집 합(linearly ordered set)이라고 말함
• 선형 순서(linear order)
• 관계 R이 부분 순서이고, a∈A, b∈A라면 aRb, bRa 또는 a=b 중 하나가 성립한다.
• 이럴 경우 관계 ≲를 선형 순서 또는 선형 순서 관계(linearly
6. 부분 순서 관계
• 하세 도표(Hasse diagram)
• 부분 순서 집합 (A,≲)를 그림으로 표현하고자 할 때 주로 쓰는 방 식
• 다음과 같은 몇 가지 조건을 충족시키는 방향 그래프의 일종
• 방향 그래프지만 방향성은 제거함
• 모든 연결선은 트리와 같이 아래 방향으로 향하도록 그림
• 순환은 표시하지 않고 집합 A의 원소 x, y, z에서 x≲y이고 y≲z 을 만족하는 y가 존재하지 않을 경우에만 x에서 z로의 연결을 그림
1 3
2 4
4
2 3
1
반사 관계 제거 추이 관계가 있는 경우
화살표 제거
방향성 제거
