유클리드 관계

Euclidean relation

수학에서 유클리드 관계는 유클리드 원소(Eucleid's Elements)에서 "Axiom 1"을 공식화하는 이진관계의 한 부류다: "동일하고 같은 크기의 크기는 서로 동등하다."

정의

우측 유클리드 특성: 고체 및 파선 화살표는 각각 선행 및 결과를 나타낸다.

세트 X의 이항 관계 R은 다음 사항을 만족하는 경우 유클리드(우측 유클리드라고도 함)이다: X의 모든 a, b, c에 대해, a가 b와 c에 관련되는 경우 b는 c와 관련된다.[1] 이것을 술어 논리로 쓰려면:

X의 모든 a, b, c에 대해 b가 a와 관련되고 c가 a와 관련되는 경우, b가 c:에 관련되는 경우, X의 관계 R은 유클리드 상태로 남는다.

특성.

속성 10에 따라 우측 유클리드 관계 도식화. 진한 색의 사각형은 R'의 등가 등급을 나타낸다. 옅은 색의 직사각형은 X\ran(R)에서 가능한 원소 관계를 나타낸다. 이러한 직사각형에서 관계는 유지될 수도 있고 유지되지 않을 수도 있다.
  1. 정의의 선행에서 ∧의 공통성 때문에, aRb a aRc는 R이 옳을 때 bRc c cRb를 내포하기도 한다. 마찬가지로 bRa ∧ cRa는 R이 유클리드에서 떠날 때 bRc ∧ cRb를 내포한다.
  2. 유클리드인이라는 속성은 과도함과 다르다. 예를 들어 ≤은 transitive이지만 right Euclidean은 아닌 반면,[2] 0 ≤ x + y + 1 2 2로 정의한 xRy는 transitive가 아니라,[3] 자연수에 대한 right Eucleidean이다.
  3. 대칭적 관계에 대해서는 transitability, right uklifeanness, left uklifeanness가 모두 일치한다. 그러나 비대칭적 관계도 transitive 및 right Euclidean, 예를 들어 y=0으로 정의된 xRy가 될 수 있다.
  4. 오른쪽 유클리드 및 반사적 관계도 대칭적이므로 동등성 관계가 된다.[1][4] 마찬가지로 각 좌뇌 유클리드 및 반사적 관계는 동등하다.
  5. 오른쪽 유클리드 관계의 범위는 항상 그 영역의 하위[5] 집합이다. 그 범위에 대한 우측 유클리드 관계의 제한은 항상 반사적이며,[6] 따라서 동등하다. 마찬가지로 왼쪽 유클리드 관계의 영역은 그 범위의 부분집합이며, 왼쪽 유클리드 관계의 영역과의 제한은 동등하다.
  6. R관계는 R의 영역과 범위 집합이 일치하는 경우에만 왼쪽과 오른쪽 유클리드 둘 다이며, R은 해당 집합의 동등성 관계다.[7]
  7. 오른쪽 유클리드 관계는 항상 Quasitrantic이고,[8] 왼쪽 유클리드 관계도 그렇다.[9]
  8. 연결된 우측 유클리드 관계는 항상 전이적이며,[10] 연결된 좌측 유클리드 관계도 마찬가지다.[11]
  9. X에 최소한 3개의 원소가 있는 경우 X에 연결된 우측 유클리드 관계 R은 대칭적일 수 없으며,[12] X에 연결된 좌측 유클리드 관계도 대칭적일 수 없다.[13] 2요소 집합에서 X = { 0, 1 }, 예를 들어 y=1에 의해 정의된 관계 xRy가 연결되고, 우측 유클리드 및 대칭성이 연결되며, x=1에 의해 정의된 xRy가 연결되고, 좌측 유클리드 및 대칭성이 없다.
  10. X의 관계 R은 제한 R' := R이 동등하고 X\ran(R)의 각 X에 대해 R에 의거하여 관련이 있는 모든 요소가 R에 의거하여 동등할 경우에만 오른쪽 유클리드인 것이다.[14] 마찬가지로 X의 R은 R' := R이 동등하고 X\dom(R)의 각 X에 대해 R 아래의 X와 관련된 모든 원소가 R'에 따라 동등할 경우에만 유클리드(Eucleidian)로 남는다.
  11. 왼쪽 유클리드 관계는 비대칭일 경우 좌익일 경우, 그리고 대칭일 경우에만 좌익일 수 있다. 마찬가지로 우유클리드 관계는 반대칭성일 경우에만 고유하다.
  12. 좌측 유클리드 및 좌측 고유 관계는 공허하게 전이되며, 우측 유클리드 및 우측 고유 관계도 그러하다.
  13. 왼쪽 유클리드 관계는 준반복적으로 남겨진다. 좌익의 관계에 대해서는 그 반대도 마찬가지다. 다달리 각각의 우위 유클리드 관계는 우측 준반반복적이며, 각 우위 고유하고 우측의 준반복적 관계는 우측 유클리드다.[15]

참조

  1. ^ a b Fagin, Ronald (2003), Reasoning About Knowledge, MIT Press, p. 60, ISBN 978-0-262-56200-3.
  2. ^ 예: 0 ≤ 2 및 0 ≤ 1, 2 ≤ 1은 아님
  3. ^ 예: 2R1 및 1R0, 2R0은 아님
  4. ^ xRy 및 xRx는 yRx를 의미한다.
  5. ^ 도메인과 범위의 동일성은 필요하지 않다: y=min{x,2}에 의해 정의된 xRy 관계는 자연수에 대한 유클리드인의 오른쪽이며, 그 범위인 {0,1,2}은 그 도메인 Ⅱ의 적절한 하위 집합이다.
  6. ^ y가 R 범위에 있으면 xRy ∧ xRy가 yRy를 의미하며, 일부 적합한 x에 대해서는 이것은 또한 y가 R의 영역에 있다는 것을 증명한다.
  7. ^ 단, 이전 단락에서 지시하는 경우에만 해당된다. — if 방향의 경우 aRb와 aRc, 즉 a,b,c가 R의 영역과 범위의 구성원이므로 대칭성과 transitability에 의한 bRc; R의 왼쪽 유클리드성은 이와 유사하게 따른다고 가정한다.
  8. ^ xRy ∧ ∧yRx ∧ yRz ∧ ∧zRy가 버틸 경우 y와 z 모두 R의 범위에 있다. R은 해당 집합에 대한 동등성이므로 yRz는 zRy를 암시한다. 따라서 준확정확정식의 선행은 충족될 수 없다.
  9. ^ x,y가 R의 영역에 있다는 것을 관찰하면서, 유사한 논거를 적용한다.
  10. ^ xRy ∧ yRz가 버티면 y와 z는 R의 범위에 있다. R이 연결되어 있기 때문에 xRz, zRx 또는 x=z가 유지된다. 1번 케이스의 경우, 아무것도 보여줄 것이 없다. 사례 2와 3에서는 x도 범위 내에 있다. 따라서 xRz는 그 범위에서 각각 R의 대칭성과 반사성을 따른다.
  11. ^ 유사하게, x를 사용하는 y는 R의 영역에 있다.
  12. ^ R이 연결되어 있기 때문에, 적어도 두 개의 구별되는 요소 x,y가 그 범위에 있고, xRy ∨ yRx는 유지된다. R은 그 범위에서 대칭이기 때문에, xRy r yRx도 지탱한다. 이것은 비대칭적 특성과 모순된다.
  13. ^ 유사한 인수에 의해, R의 도메인을 사용한다.
  14. ^ 오직: R'이 위와 같은 등가성인 경우에만 해당된다. 만약 xxX\ran(R)과 xR'y1, xR'y2, 그리고 yR12'y, 즉 yRy by ri1, 따라서2 yR'y. — 만약: xRy holds xRz가 버티면 y,zran(R. 또한 x∈ran(R)의 경우, xR'y ∧ xR'z도 유지하므로, R'의 대칭성과 transitability에 의한 yR'z, 즉 yRz x∈X\ran(R)의 경우, y와 z 요소는 가정에 의해 R'에 따라 동등해야 하므로 yRz도 동일해야 한다.
  15. ^ Jochen Burghardt (Nov 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036v2. 레마 44-46