Hyunjung Im

관계

  • 두 집합 X와 Y에 대하여 곱집합 X×YX \times Y의 부분집합 R을 X에서 Y로의 관계라고 한다.
    • 만약 x와 y가 각각 X와 Y의 원소이고 (x,y)R(x, y) \in R이면 xRyxRy로 표기하며, x는 y와 R의 관계가 있다고 한다.
    • 만약 (x,y)R(x, y) \notin R이면 x̸ ⁣Ryx \not\! R y 로 표기하며, x는 y와 R의 관계가 없다고 한다.
  • 예제) 집합 A={2,3,4,5},B={1,2}A = \{2, 3, 4, 5\}, B = \{1, 2\}일 때, A에서 B로 가는 관계 R은 다음과 같을 때 물음에 답하라.
    • R={(a,b)a+b=4}R = \{(a,b)|a+b = 4\}
    • 관계 R을 순서쌍으로 나타내시오
      • R={(2,2),(3,1)}R = \{(2,2), (3,1)\}
    • 4R1은 성립하는가?
      • 성립하지 않음

관계의 표현

화살표 도표

집합 A={2,3,4,5},B={0,1,2,3}A = \{2, 3, 4, 5\}, B = \{0, 1, 2, 3\}

  1. (a,b)R(a,b) \in R이기 위한 필요충분조건은 aba \leq b 화살표도표

부울행렬

  • 관계를 행렬로 나타냈을 때 이점: 대수연산자를 이용하여 관계에 관련된 문제를 편리하게 계산 가능 X={1,2,3,4}X = \{1, 2, 3, 4\} 에서의 관계 R이 다음과 같이 정의되었을 때 R을 부울행렬로 나타내시오
  • R={(x,y)y=x+1,xX,yX}R = \{(x,y)|y = x + 1, x \in X, y \in X\}
    • MR=[0100001000010000]M_R = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}

관계의 성질

반사적(reflexive)

  • 집합 A에서의 관계 R에 대해 모든 aAa \in A에 대해 (a,a)R(a,a) \in R이면 R은 반사적이라고 한다.
  • 집합 A에서의 관계 R이 반사적이 되려면 A의 모든 원소가 자기 자신과 관계를 가져야 한다.
    • 예를 들어, 집합 A={1,2,3}A = \{1, 2, 3\}에서의 관계 R이 반사적이려면 (1, 1), (2, 2), (3, 3)이 모두 R에 포함되어야 한다.

대칭적(symmetric)

  • 집합 A에서의 관계 R에 대해 모든 a,bAa, b \in A에 대해 (a,b)R(a,b) \in R일 때 (b,a)R(b, a) \in R이면 R은 대칭적이라고 한다.
  • 집합 A에서의 관계 R이 대칭적이 되려면, R에 포함된 모든 원소가 대칭되는 관계를 가져야 한다.
    • 예를 들어, 집합 A={1,2,3}A = \{1, 2, 3\}에서의 관계 R이 대칭적이려면 (1, 2)가 R에 포함되어 있다면 (2, 1)도 R에 포함되어야 한다.

추이적(transitive)

  • 집합 A에서의 관계 R에 대해 모든 a,b,cAa, b, c \in A에 대해 (a,b)R(a, b) \in R이고 (b,c)R(b, c) \in R일 때, (a,c)R(a, c) \in R이면 R은 추이적이라고 한다.
  • 집합 A에서의 관계 R이 추이적이 되려면, R에 포함된 모든 원소들에 대해서 (a,b)R(a, b) \in R이고, (b,c)R(b, c) \in R이면 (a,c)R(a, c) \in R이어야 한다.

화살표도표2

  • R 관계
    • (1,1), (2,2), (3,3)모두 R에 포함되어 있으므로 반사적이다.
    • (1,2)일 때 (2,1)은 포함되어 있지 않으므로 대칭적이지 않다.
    • (1,3)이 관계에 포함되어 있고, (3,2)가 포함되어 있지만, (1,2)는 포함되어 있지 않으므로 추이적이지 않다.
  • S 관계
    • 반사적이다.
    • (1,3)이 관계에 포함되어 있을 때 (3,1)도 포함되어 있으므로 대칭적이다.
    • 추이적 조건에도 만족하지 못함
  • T 관계
    • (2,2)와 (3,3) 은 관계에 포함하지 않으므로 반사적이지 않다.
    • (2,1)이 관계에 포함되어 있을 때 (1,2)는 포함되어 있지 않으므로 대칭적이지 않다.
    • (2,1)과 (1,3)이 관계에 포함되어 있고, (2,3)도 포함되어 있으므로 추이적이다.
      • 추이적 관계의 필요조건을 만족시키는 원소들이 존재하므로 추이적이다.

관계의 종류

주어진 관계를 이용하여 새로운 관계를 만들어 낼 수 있다.

역관계(inverse relation)

  • 집합 X에서 집합 Y로의 관계 R이 있을 때, 관계를 구성하는 각 순서쌍의 원소 순서를 바꾸면 Y에서 X로의 관계가 되며, 이를 역관계라고 한다.
  • R1R^{-1}라고 표기함
  • R1={(y,x)(x,y)R}R^{-1} = \{(y, x)|(x, y) \in R\}

합성관계(composition relation)

  • 집합 A에서 집합 B로의 관계 R이 있고, 집합 B에서 집합 C로의 관계 S가 있을 때, SRS \cdot R은 집합 A에서 집합 C로의 관계를 나타낸다.
  • SR={(a,c)A×CaA,bB,cC,(a,b)R,(b,c)S}S \cdot R = \{(a, c) \in A \times C|a \in A, b \in B, c \in C, (a, b) \in R, (b, c) \in S\}

화살표도표2

  • 집합 A에서 집합 B로의 관계가 R이고, 집합 B에서 C로의 관계가 S일 때, A에서 C로의 관계는 RSR \cdot S로 표기하는 것이 아니라 SRS \cdot R로 표기한다. 주의할 것

동치관계(equivalence relation)

  • 집합 A에서의 관계 R이 반사적이고, 대칭적이고, 추이적이면 R은 동치관계라고 한다.
  • 나머지함수: 하나의 식을 다른 값으로 나눈 뒤 나머지를 구하는 함수
    • 8 mod 5 = 3이고 13 mod 5 = 3이다. 두 정수 m, n에 대해 양의 정수 d로 나머지 연산을 하였을 때 같은 값이 나오는 경우가 있는데 이때의 m과 n은 d에 관한 모듈로 합동이라 하고 mn(modd) m \equiv n(\mod d)로 표기한다.