데코수학/ 관계, 동치관계

개념

  • 수식은 연산과 관계로 표현 됨.
    • a + b = c 에서 ‘+’는 연산 ‘=’ 은 관계
  • 관계와 함수는 순서쌍의 집합
  • 관계 R, 집합 A, B에 대하여 관계식은 아래와 같이 쓴다.
    • R : A → B
      • A = { a1, a2, a3 }, B = { b1, b2, b3 }
    • R = { {a1, b2), {a3, b1), (a3, b3) }
      • 두 집합 A, B가 있고 어떤 A에서 B로 가는 어떤 관계 조건을 만족하는 순서쌍의 집합을 R이라고 이해하면 된다.
      • 위 상황에서는 그 조건에 만족하는 순서쌍이 (a1, b2), (a3, b1), (a3, b3) 이라는 것.
  • 관계를 R로 표시하고 아래와 같은 집합에서 철수와 영희가 배우자 관계일 때 다음과 같이 한다.
    • 집합 A = { 철수, 영희, 진수 }
    • R배우자 = { (철수, 영희), (영희, 철수) }
      • 위의 관계는 특히 대칭인 관계인데, (철수, 영희), (영희, 철수)가 존재하기 때문
      • 일반적인 관계 R에서 aRbbRa가 성립하면 대칭인 관계라고 한다.
  • 역관계
    • 어떤 관계 R에 대하여 순서쌍을 거꾸로 쓴 집합. 역함수와 같다. R-1
    • R에 대하여 R-1 := { (y, x) | (x, y) ∈ R }
  • 정의역 (Domain)
    • Dom(R) = { a | (a, b) ∈ R }
  • 치역 (Image)
    • Im(R) = { b | (a, b) ∈ R }
  • 다음과 같은 상황에서 정의역과 치역은 다음과 같다.
    • R : A → B
      • A = { a1, a2, a3 }, B = { b1, b2, b3 }
      • R = { (a1, b2), (a3, b1), (a3, b3) }
      • Domain(R) = { a1, a3 }
      • Im(R) = { b1, b2, b3 }
  • 동치관계
    • 아래 조건을 모두 만족하는 관계를 동치관계라 부른다.
    • ε : X → X
      • ∀x ∈ X, x ε x (반사율)
      • x ε  y ⇒ y ε x (대칭율)
      • x ε y ∧ y ε z ⇒ x ε z (추이율)
    • 닮음도 동치관계
  • 동치류, 상집합(Quotient Set)
    • ε : X → X, x ε X 일 때
      • x/ε = { a | a ε x } 인 것을 동치류라고 한다.
      • X/ε = { x/ε | x ∈ X} 인 것을 상집합이라고 한다. (동치류를 모아 놓은 집합)
    • 다음과 같은 조건이 있다고 할 때
      • X = { a, b, c, d, e, f }
        • a, b, f는 11살
        • c는 12살
        • d, e 는 13살
      • ε : X → X, a ε b := a와 b는 동갑이다.
    • 동치류는 다음과 같다.
      • a/ε = { a, b, f }
      • b/ε = { a, b, f }
      • c/ε = { c }
      • d/ε = { d, e }
      • e/ε = { d, e }
      • f/ε = { a, b, f }
    • 상집합은 다음과 같다.
      • X/ε = { { a, b, f }, { c }, { d, e } }

관계식

  • Dom(R-1) = Im(R)
    • 역관계의 정의역은 원래 관계의 치역과 같다.
  • Im(R-1) = Dom(R)
    • 역관계의 치역은 원래 관계의 정의역과 같다.
  • x/ε ≠ ∅, x/ε ⊆ X
    • (반사율) 자기 자신이 동치이기 때문에, 동치인 집합이 공집합일 수는 없다.
  • x ε y ⇔ x/ε ∩ y/ε ≠ ∅
    • x, y가 동치관계일 때 x의 동치류와 y의 동치류의 교집합은 공집합이 아니다.
  • x ε y ⇔ x/ε = y/ε
    • x, y가 동치관계일 때 x의 동치류와 y의 동치류는 같다.
[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.