연결관계

타동사 이항 관계

	대칭	비대칭	연결된	근거가 충분한	조인 있음	Has meets	반사적	불변성	비대칭
			합계, 세미콘넥스					반(Anti-) 반사적인
등가관계	Y	✗	✗	✗	✗	✗	Y	✗	✗
프리오더(Qaasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
부분순서	✗	Y	✗	✗	✗	✗	Y	✗	✗
총예약자	✗	✗	Y	✗	✗	✗	Y	✗	✗
총순번	✗	Y	Y	✗	✗	✗	Y	✗	✗
프리웰오더링	✗	✗	Y	Y	✗	✗	Y	✗	✗
웰 준주문	✗	✗	✗	Y	✗	✗	Y	✗	✗
순서가 좋은	✗	Y	Y	Y	✗	✗	Y	✗	✗
격자	✗	Y	✗	✗	Y	Y	Y	✗	✗
조인-세밀라티스	✗	Y	✗	✗	Y	✗	Y	✗	✗
밋세밀라티스	✗	Y	✗	✗	✗	Y	Y	✗	✗
엄격한 부분 순서	✗	✗	✗	✗	✗	✗	✗	Y	Y
엄약질서	✗	✗	✗	✗	✗	✗	✗	Y	Y
엄격한 총계순서	✗	✗	Y	✗	✗	✗	✗	Y	Y
	대칭	비대칭	연결된	근거가 충분한	조인 있음	Has meets	반사적	불변성	비대칭
정의, $모든 a$ , b $a,b$ 및 $S\neq \varnothing :$ $S\neq \varnothing :$ $S\neq \varnothing :$ : $S\neq \varnothing :$	${\begin{aigned}&aRb\\\오른쪽 화살표 {}&bRa\end{aigned}}$	${\begin{aigned}aRb{\text{} 및 }}&bRa\\\\Rightarrow a={}&b\end}}}$	${\begin}a\neq {}&b\Rightarrow \\aRb{\text{} 또는 }&bRa\end{aigned}}}$	${\begin}\min S\\{\textists}\end{aligned}}$	${\regated}a\vee b\\\{\text}}\end{regated}}$	${\regated}a\b\\{\text}}\end{regated}}$	$(\displaystyle aRa}$	${\text{not}aRa$	${\begin{aigned}aRb\Rightarrow \\{\text{not}bRa\end{aigned}}$

는 행의 용어(맨 왼쪽)의 정의에 의해 열의 속성이 요구됨을 나타낸다.예를 들어, 동등성 관계의 정의는 대칭성을 요구한다.✗은 그 재산이 보유할 수도 있고 보유하지 않을 수도 있음을 나타낸다.

모든

정의는 암묵적으로 동종

관계

R

R

을(를) 타전적으로 요구하며

R

,

모든

aRc,

a

,

b

,

c

,

{\

displaystyle aRb}

및 b

aRb

R

c

bRc

이

a,b,c,

bRc

(가)

R

c , {\

displaystystystyle aRc}

에 해당될 수 있는 추가 속성이 있다.

수학에서 집합의 관계는 한 방향 또는 다른 방향으로 집합의 모든 구별되는 요소 쌍이 연관되어 있는 경우(또는 "동일체") 연결된 경우 전체 또는 전체라고 하는 반면, 모든 요소 쌍과 관련이 있는 경우 강하게 연결된다고 한다.아래 용어 섹션에서 설명한 바와 같이, 이러한 특성에 대한 용어는 균일하지 않다.이"전체"의 개념은 모든)∈ X{\displaystyle Xx\in}에 y∈ X{\displaystyle y\in X}(가)있다는 의미에서 전체 관계의 개념과 혼동해서는 안 된다(직렬 관계 참조).

연결성은 총 주문의 정의에서 두드러지게 나타난다. 총(또는 선형) 순서는 두 요소가 비교 가능한 부분 순서다. 즉, 주문 관계가 연결된다.마찬가지로, 연결된 엄격한 부분 순서는 엄격한 전체 순서다.관계는 부분적인 순서인 동시에 강하게 연결된 경우에만 총 주문이다.관계는 엄격한 부분적 명령이고 단지 연결되었을 경우에만 엄격한 전체 명령이다.엄격한 토털 오더는 절대 강하게 연결될 수 없다(빈 도메인 제외).

형식 정의

$집합$ $x,y\in X,$ $X}$ 의 $R$ 관계 R $R$ 은(는) $x,y\in X,$ x , y $x,y\in X,$ set X $x,y\in X,$ , ${\displaystyle x,y\in$ X,}에 대해 연결됨을 호출한다 $X$ .

{\text{}x\neq y{\text{}{}x\mathrel {R} y\quad {\text{or}}\quad y\mathrel {R}x,

또는

x,y\in X,

하게

x,y\in X,

모든 x ,

x,y\in X,

X

x,y\in X,

, {\

displaystyle x,y\in

X

,}

x\mathrel {R}y\quad {\text{or}\quad y\cultrel {R}x\quad{or}\quad x=y.

모든 $x,y\in X,$ , $x,y\in X,$ $x,y\in X,$ $x,y\in X,$ , ${\displaystyle x,y\in$ X $,}$ 에 대한 속성과의 관계

x\mathrel {R} y\quad {\text{or}\quad y\mathrel {R}x

강하게 연결된다고 한다.^[1]^[2]^[3]

용어.

연결 관계의 개념의 주요 용도는 총 또는 선형 순서를 정의하는 데 사용되는 주문의 맥락에 있다.이러한 맥락에서, 그 속성은 종종 구체적으로 명명되지 않는다.오히려 전체 순서는 어떤 두 요소가 비교 가능한 부분 순서로 정의된다.^[4]^[5]따라서, 총액은 연결되거나 강하게 연결된 관계에 더 일반적으로 사용된다.^[6]그러나, 이러한 「전체 관계」의 개념은, 연속성이라는 성질과는 구별되어야 하는데, 이것을 합계라고도 한다.마찬가지로, 연결된 관계도 때로는 완전한 관계라고 부르기도 하지만, 이것 역시 혼란을 초래할 수 있다.^[7]보편적 관계는 완전 관계라고도 하며,^[8] "완전"은 순서 이론에서 몇 가지 다른 의미를 갖는다.연결된 관계를 connex라고^[9]^[10] 부르거나 $x\mathrel {R} y,y\mathrel {R} x,x=y$ 절개술을 만족한다고 말하기도 한다(삼차 절개술의 보다 일반적인 정의는 $x\mathrel {R} y,y\mathrel {R} x,x=y$ 세 가지 $x\mathrel {R} y,y\mathrel {R} x,x=y$ x R $x\mathrel {R} y,y\mathrel {R} x,x=y$ $x\mathrel {R} y,y\mathrel {R} x,x=y$ $x\mathrel {R} y,y\mathrel {R} x,x=y$ = $x\mathrel {R} y,y\mathrel {R} x,x=y$ x $\mathrel {R} y, y\mathrel {R} x,x=y}$ 가 보유해야 $x\mathrel {R} y,y\mathrel {R} x,x=y$ 한다는 점에서 더 강하다).

고려된 관계가 질서가 아닐 때, 연결되고 강하게 연결되는 것은 중요한 서로 다른 성질이다.그런 다음 두 가지 모두를 정의하는 선원은 위에서 정의한 연결 및 연결의 개념에 대한 대체 명칭으로 각각 약하게 ^[12]완전하고 강력하게 완전하며 ^[13]완전하고 완전하며 완전하고 완전하며 ^[6]완전하며 완전하고 완전하며 세미코넥스와 코넥스 또는 ^[14]엄격히 연결된다.^[15]

특성화

$R$ $R$ 을(를) 균일한 관계가 되도록 $R$ 한다.다음은 이에 해당한다.^[14]

$R$ $R$ 이 $R$ (가) 강하게 연결됨;
$U\subseteq R\cup R^{\top }$ $U\subseteq R\cup R^{\top }$ R $U\subseteq R\cup R^{\top }$ $U\subseteq R\cup R^{\top }$ $U\subseteq R\cup R^{\top }$ ${\$ R $^{\top }$ ;
${\overline {R}}\subseteq R^{\top }$ ${\overline {R}}\subseteq R^{\top }$ ${\overline {R}}\subseteq R^{\top }$ ${\overline {R}}\subseteq R^{\top }$ ${\$ R $^{\top$ ${\overline {R}}\subseteq R^{\top }$
$'{\$ 은 ${\overline {R}}$ (는) 비대칭이며,

여기서 $U$ $U$ 은 $U$ (는) 범용 관계이고 $R^{\top }$ $R^{\top }$ ${\$ 은 $R^{\top }$ (는) $R .$ ${\displaystyle$ R $.}$ 의 역관계다.

다음은 이에 해당한다.^[14]

$R$ $R$ 이 $R$ (가) 연결됨;
${\overline {I}}\subseteq R\cup R^{\top }$ s ${\overline {I}}\subseteq R\cup R^{\top }$ ${\overline {I}}\subseteq R\cup R^{\top }$ ${\overline {I}}\subseteq R\cup R^{\top }$ ${\$ R $\cup$ R $^{\top$
${\overline {R}}\subseteq R^{\top }\cup I$ ${\overline {R}}\subseteq R^{\top }\cup I$ ${\overline {R}}\subseteq R^{\top }\cup I$ ${\overline {R}}\subseteq R^{\top }\cup I$ ${\overline {R}}\subseteq R^{\top }\cup I$ ${\overline {R}}\subseteq R^{\top }\cup I$ ${\displaystyle {\overline{R$ }\ $subseteq$ R $^{\top }\cup$ I ${\overline {R}}\subseteq R^{\top }\cup I$
$'{\$ 은 ${\overline {R}}$ (는) 대칭성이며

여기서 $}$ {\ $displaystyle {I}$ 은(는) ID $관계$ I $I$ 의 보완적 관계이고 $\overline {I}$ $I$ $R^{\top }$ $R^{\top }$ ${\$ R $^{\top }$ 은(는 $R^{\top }$ ) $R .$ {\ $displaystyle$ R $.}$ 의 역관계다.

진행 과정을 소개하면서 러셀은 연결의 공리를 호출했다.

어떤 시리즈가 원래 전이적 비대칭 관계에 의해 주어질 때마다, 우리는 우리의 시리즈 중 어떤 두 용어라도 생성 관계를 갖는다는 조건으로 연결을 표현할 수 있다.
— Bertrand Russell, The Principles of Mathematics page 239

특성.

토너먼트 그래프 $G$ $G$ 의 $E$ 에지 관계^{[note 1]} $E$ $E$ 은(는) 항상 $G$ $G$ 의 $G$ 정점 집합에서 연결된 관계다 $G$ .
강하게 연결된 관계가 대칭이면 그것은 보편적 관계다.
관계는 연결되고 반사적일 때에만 강하게 연결된다.^{[proof 1]}
$X$ $X$ 에 최소한 $X$ 4개의 요소가 있는 경우 집합 $X$ ${\$ displaystyle $X}$ 에 연결된 관계는 반독점적일 수 없다 $X$ .^[16]예를 들어 $\{a,b,c\},$ 3-element set $\{a,b,c\},$ { $\{a,b,c\},$ $\{a,b,c\},$ $\{a,b,c\},$ {\ $displaystyle$ \{ $a,$ ${\displaystyle$ 관계에는 두 가지 속성이 모두 있다 $\{(a,b),(b,c),(c,a)\}$ .
$R$ ${\displaystyle$ $R$ $}$ 이(가) $X$ , ${\displaystyle$ X $,}$ 에 $X,$ 연결된 관계인 $R$ 경우, $X$ {\ $displaystyle$ $X$ $}$ 의 모든 요소가 $R .$ ${\displaystyle$ R $.}$ 과 $R.$ ^{[proof 2]}(와) 유사하게, $X$ ${\displaystystyle$ X $}$ 의 요소가 R $}$ 의 도메인에 있다 $X$ $X$ .

메모들

^ 그래프 에지가 꼭지점 $v$ $v$ 에서 $꼭지점$ w $w$ 까지 $v$ 이어지는 경우 $vEw$ $v$ $E$ w $vEw$ 에 의해 공식적으로 정의됨

교정쇄

^ 두 속성 모두 사소한 방향으로만 따르게 된다.— For the if direction: when $x\neq y,$ then $x\mathrel {R} y\lor y\mathrel {R} x$ follows from connectedness; when $x=y,$ $x\mathrel {R} y$ follows from reflexivity.
^ If $x,y\in X\setminus \operatorname {ran} (R),$ then $x\mathrel {R} y$ and $y\mathrel {R} x$ are impossible, so $x=y$ follows from connectedness.

참조

^ Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12.
^ Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8.
^ Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN 0-86720-463-X., 페이지 135
^ Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. 여기: 14장.할모스는 반사성, 반대칭성, 전이성의 이름을 주지만 연결성의 이름은 주지 않는다.
^ Patrick Cousot (1990). "Methods and Logics for Proving Programs". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 841–993. ISBN 0-444-88074-7. 여기: 6장 3절, p.878
^ ^a ^b Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer. ISBN 978-3-540-32696-0., 페이지 6
^ Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN 978-1-4471-2500-6., 페이지 50
^ Whitehead, Alfred North; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Cambridge University Press.{{cite book}}: CS1 maint: 날짜 및 연도(링크)
^ Wall, Robert E. (1974). Introduction to Mathematical Linguistics. Prentice-Hall. 114쪽
^ Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. 7페이지.
^ Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN 978-1-904987-14-7. 24 페이지
^ Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.
^ Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN 978-0-521-10243-8. 29페이지
^ ^a ^b ^c Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1.
^ Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media. ISBN 978-3-642-59830-2. 86 페이지
^ Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. 보조정리 8.2, 페이지 8.

[16] 그래프 에지가 꼭지점 $v$ $v$ 에서 $꼭지점$ w $w$ 까지 $v$ 이어지는 경우 $vEw$ $v$ $E$ w $vEw$ 에 의해 공식적으로 정의됨

[17] 두 속성 모두 사소한 방향으로만 따르게 된다.— For the if direction: when $x\neq y,$ then $x\mathrel {R} y\lor y\mathrel {R} x$ follows from connectedness; when $x=y,$ $x\mathrel {R} y$ follows from reflexivity.

[19] If $x,y\in X\setminus \operatorname {ran} (R),$ then $x\mathrel {R} y$ and $y\mathrel {R} x$ are impossible, so $x=y$ follows from connectedness.

[1] Clapham, Christopher; Nicholson, James (2014-09-18). "connected". The Concise Oxford Dictionary of Mathematics. Oxford University Press. ISBN 978-0-19-967959-1. Retrieved 2021-04-12.

[2] Nievergelt, Yves (2015-10-13). Logic, Mathematics, and Computer Science: Modern Foundations with Practical Applications. Springer. p. 182. ISBN 978-1-4939-3223-8.

[3] Causey, Robert L. (1994). Logic, Sets, and Recursion. Jones & Bartlett Learning. ISBN 0-86720-463-X., 페이지 135

[4] Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. 여기: 14장.할모스는 반사성, 반대칭성, 전이성의 이름을 주지만 연결성의 이름은 주지 않는다.

[5] Patrick Cousot (1990). "Methods and Logics for Proving Programs". In Jan van Leeuwen (ed.). Formal Models and Semantics. Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 841–993. ISBN 0-444-88074-7. 여기: 6장 3절, p.878

[Aliprantis-6] Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Infinite Dimensional Analysis: A Hitchhiker's Guide. Springer. ISBN 978-3-540-32696-0., 페이지 6

[7] Makinson, David (2012-02-27). Sets, Logic and Maths for Computing. Springer. ISBN 978-1-4471-2500-6., 페이지 50

[8] Whitehead, Alfred North; Russell, Bertrand (1910). Principia Mathematica. Cambridge: Cambridge University Press.{{cite book}}: CS1 maint: 날짜 및 연도(링크)

[9] Wall, Robert E. (1974). Introduction to Mathematical Linguistics. Prentice-Hall. 114쪽

[10] Carl Pollard. "Relations and Functions" (PDF). Ohio State University. Retrieved 2018-05-28. 7페이지.

[11] Kunen, Kenneth (2009). The Foundations of Mathematics. College Publications. ISBN 978-1-904987-14-7. 24 페이지

[12] Fishburn, Peter C. (2015-03-08). The Theory of Social Choice. Princeton University Press. p. 72. ISBN 978-1-4008-6833-9.

[13] Roberts, Fred S. (2009-03-12). Measurement Theory: Volume 7: With Applications to Decisionmaking, Utility, and the Social Sciences. Cambridge University Press. ISBN 978-0-521-10243-8. 29페이지

[Schmidt-14] Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer. ISBN 978-3-642-77970-1.

[15] Ganter, Bernhard; Wille, Rudolf (2012-12-06). Formal Concept Analysis: Mathematical Foundations. Springer Science & Business Media. ISBN 978-3-642-59830-2. 86 페이지

[18] Jochen Burghardt (Jun 2018). Simple Laws about Nonprominent Properties of Binary Relations (Technical Report). arXiv:1806.05036. Bibcode:2018arXiv180605036B. 보조정리 8.2, 페이지 8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[note 1]

[proof 1]

[16]

[proof 2]

Search

연결관계

네임스페이스

더

목차

형식 정의

용어.

특성화

특성.

메모들

참조