수학 에서 이항 관계 (二項關係, 영어 : binary relation )는 “…는 …보다 크다” 또는 “…와 …는 같다”와 같이, 두 대상에 대하여 정의되는 성질을 집합론 적으로 실현한 개념이다. 이항 관계는 순서쌍 들로 구성된 집합 이다. 어떤 순서쌍이 이항 관계의 원소라면, 순서쌍의 두 성분 사이에 관계가 성립한다고 해석한다.
예를 들어, “…는 …의 약수 ”라는 조건은 두 정수 사이의 이항 관계 ∣ {\displaystyle \mid } m {\displaystyle m} n {\displaystyle n} 순서쌍 ( m , n ) {\displaystyle (m,n)} ( 5 , 20 ) {\displaystyle (5,20)} ( 6 , 13 ) {\displaystyle (6,13)} ( 5 , 20 ) ∈ ∣ {\displaystyle (5,20)\in {\mid }} ( 6 , 13 ) ∉ ∣ {\displaystyle (6,13)\not \in {\mid }}
5 ∣ 20 {\displaystyle 5\mid 20} 6 ∤ 13 {\displaystyle 6\nmid 13} 와 같이 적는다.
이항 관계의 개념은 모임 위로 확장할 수 있다. 모임 위의 이항 관계는 모임이며, 고유 모임 일 수 있다. 고유 모임은 모임의 원소가 될 수 없으므로, 주어진 두 모임 사이의 이항 관계들의 모임을 정의할 수 없다. 반면, 주어진 집합 위의 이항 관계들의 모임을 정의할 수 있으며, 이는 항상 집합이다.
이항 관계는 관계 의 항수가 2인 경우이다. 이항 관계의 이론은 다른 항수의 관계보다 풍부하다. 일부 문헌에서는 이항 관계를 단순히 관계 라고 부른다. 혹자는 이항 관계를 대응 (對應, correspondence)이라고 일컫는다.
이항 관계 는 다음 조건을 만족시키는 집합 R {\displaystyle R}
모든 원소는 순서쌍 이다. 즉, 임의의 r ∈ R {\displaystyle r\in R} r = ( x , y ) {\displaystyle r=(x,y)} x {\displaystyle x} y {\displaystyle y} 만약 ( x , y ) ∈ R {\displaystyle (x,y)\in R} x {\displaystyle x} y {\displaystyle y} R {\displaystyle R} x R y {\displaystyle xRy} ( x , y ) ∈ R {\displaystyle (x,y)\in R} x R̸ y {\displaystyle x\not Ry} ( x , y ) ∉ R {\displaystyle (x,y)\not \in R} x R y S z {\displaystyle xRySz} ( x , y ) ∈ R {\displaystyle (x,y)\in R} ( y , z ) ∈ S {\displaystyle (y,z)\in S}
집합 X {\displaystyle X} Y {\displaystyle Y} R ⊆ X × Y {\displaystyle R\subseteq X\times Y} X {\displaystyle X} X {\displaystyle X} X {\displaystyle X} R ⊆ X × X {\displaystyle R\subseteq X\times X} R {\displaystyle R} X = ⋃ ⋃ R {\displaystyle X=\bigcup \bigcup R}
이항 관계 R {\displaystyle R} S {\displaystyle S} 합성 S ∘ R {\displaystyle S\circ R}
S ∘ R = { ( x , z ) | ∃ y : ( x , y ) ∈ R ∧ ( y , z ) ∈ S } {\displaystyle S\circ R=\{(x,z)|\exists y\colon (x,y)\in R\land (y,z)\in S\}} 이항 관계의 합성은 결합 법칙 을 만족시킨다.
( T ∘ S ) ∘ R = T ∘ ( S ∘ R ) {\displaystyle (T\circ S)\circ R=T\circ (S\circ R)} 이에 따라, 집합과 이항 관계의 범주 Rel {\displaystyle \operatorname {Rel} }
대상은 집합 이다.
두 집합 사이의 사상 f : X → Y {\displaystyle f\colon X\to Y} f ⊆ X × Y {\displaystyle f\subseteq X\times Y}
사상의 합성은 이항 관계의 합성이다.
집합 X {\displaystyle X} id X = { ( x , x ) : x ∈ X } ⊆ X × X {\displaystyle \operatorname {id} _{X}=\{(x,x)\colon x\in X\}\subseteq X\times X} 범주 Rel {\displaystyle \operatorname {Rel} } 곱 과 쌍대곱 을 가지며, 둘 모두 분리합집합 으로 주어진다. 또한, 동등자 를 가지지 않지만, 모든 작은 약한 동등자 (영어 : weak equalizer )를 갖는다.
이항 관계 R {\displaystyle R} 역관계 R − 1 {\displaystyle R^{-1}} R {\displaystyle R}
R − 1 = { ( y , x ) | ( x , y ) ∈ R } {\displaystyle R^{-1}=\{(y,x)|(x,y)\in R\}} 역관계는 자명하게 멱등 연산이다.
( R − 1 ) − 1 = R {\displaystyle (R^{-1})^{-1}=R} 역관계와 합성은 다음과 같이 호환된다.
( S ∘ R ) − 1 = R − 1 ∘ S − 1 {\displaystyle (S\circ R)^{-1}=R^{-1}\circ S^{-1}} 정의역과 치역
편집
이항 관계 R {\displaystyle R}
집합 또는 모임 A {\displaystyle A} 상 은 A {\displaystyle A} R ( A ) = { y | ∃ x ∈ A : ( x , y ) ∈ R } {\displaystyle R(A)=\{y|\exists x\in A\colon (x,y)\in R\}} 집합 또는 모임 B {\displaystyle B} 원상 은 역관계에 대한 상이다.
R − 1 ( B ) = { x | ∃ y ∈ B : ( x , y ) ∈ R } {\displaystyle R^{-1}(B)=\{x|\exists y\in B\colon (x,y)\in R\}} R {\displaystyle R} 정의역 dom R {\displaystyle \operatorname {dom} R} 고유 모임 의 원상이다. (이는 범주 Rel {\displaystyle \operatorname {Rel} } dom R = R − 1 ( V ) = { x | ∃ y : ( x , y ) ∈ R } {\displaystyle \operatorname {dom} R=R^{-1}(V)=\{x|\exists y\colon (x,y)\in R\}} R {\displaystyle R} 치역 ran R {\displaystyle \operatorname {ran} R} 고유 모임 의 상이다.
ran R = R ( V ) = { y | ∃ x : ( x , y ) ∈ R } {\displaystyle \operatorname {ran} R=R(V)=\{y|\exists x\colon (x,y)\in R\}} 만약 ( x , y ) = { { x } , { x , y } } ∈ R {\displaystyle (x,y)=\{\{x\},\{x,y\}\}\in R} { x } , { x , y } ∈ ⋃ R {\displaystyle \{x\},\{x,y\}\in \bigcup R} x , y ∈ ⋃ ⋃ R {\displaystyle x,y\in \bigcup \bigcup R} [1] :27, Definition I.6.6, Justification
임의의 이항 관계 R {\displaystyle R}
dom R − 1 = ran R {\displaystyle \operatorname {dom} R^{-1}=\operatorname {ran} R} ran R − 1 = dom R {\displaystyle \operatorname {ran} R^{-1}=\operatorname {dom} R} dom R ∪ ran R = ⋃ ⋃ R {\displaystyle \operatorname {dom} R\cup \operatorname {ran} R=\bigcup \bigcup R}
함수 F ⊆ X × Y {\displaystyle F\subseteq X\times Y} F : X → Y {\displaystyle F\colon X\to Y} ∀ x ∈ X ∃ y ∈ Y : x F y {\displaystyle \forall x\in X\exists y\in Y\colon xFy} ∀ x ∈ X ∀ y , z ∈ Y : x F y ∧ x F z ⟹ y = z {\displaystyle \forall x\in X\forall y,z\in Y\colon xFy\land xFz\implies y=z} 이항관계는 일반적으로 함수가 아니다. 예를 들어 약수 관계에서, 5로 나누어지는 정수는 유일하지 않다.
반사관계 R ⊆ X 2 {\displaystyle R\subseteq X^{2}} ∀ x ∈ X : x R x {\displaystyle \forall x\in X\colon xRx} 대칭관계 R ⊆ X 2 {\displaystyle R\subseteq X^{2}} ∀ x , y ∈ X : x R y ⟹ y R x {\displaystyle \forall x,y\in X\colon xRy\implies yRx} 반대칭관계 R ⊆ X 2 {\displaystyle R\subseteq X^{2}} ∀ x , y ∈ X : x R y ∧ y R x ⟹ x = y {\displaystyle \forall x,y\in X\colon xRy\land yRx\implies x=y} 추이관계 R ⊆ X 2 {\displaystyle R\subseteq X^{2}} ∀ x , y , z ∈ X : x R y ∧ y R z ⟹ x R z {\displaystyle \forall x,y,z\in X\colon xRy\land yRz\implies xRz} 완전관계 R ⊆ X 2 {\displaystyle R\subseteq X^{2}} ∀ x , y ∈ X : x R y ∨ y R x {\displaystyle \forall x,y\in X\colon xRy\lor yRx} 참고 문헌
편집
외부 링크
편집
