홀 결혼 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합적 집합론]]에서 '''홀 결혼 정리'''(Hall結婚定理, {{llang|en|Hall marriage theorem}})는 여러 [[유한 집합]]들의 집합족으로부터, 각 집합에서 서로 다른 원소를 고를 수 있는 [[필요충분조건]]에 대한 정리다.

== 정의 ==
[[집합족]] <math>\mathcal T</math>의 모든 원소가 [[유한 집합]]이라고 하자. '''홀 결혼 정리'''에 따르면, 다음 두 조건이 서로 동치이다.<ref name="윤영진"/>{{rp|289}}
* (결혼 조건 {{llang|en|marriage condition}}) 모든 <math>\mathcal U\subset\mathcal T</math>에 대하여, <math>\textstyle|\mathcal U|\le\left|\bigcup\mathcal U\right|</math>
* (횡단의 존재) 다음 조건들을 만족시키는 순서쌍 <math>(S,f)</math>가 존재한다. 이러한 순서쌍을 '''횡단'''(橫斷, {{llang|en|transversal}}) 또는 '''변별 대표원계'''(辨別代表元系, {{llang|en|system of distinct representatives}})라고 한다.
** <math>S\subset\bigcup\mathcal T</math>는 [[집합]]이다.
** <math>f\colon S\to T</math>는 [[전단사 함수]]이다.
** 모든 <math>s\in S</math>에 대하여 <math>s\in f(s)</math>이다.
횡단의 존재가 결혼 조건을 함의한다는 것은 자명하므로, 홀 결혼 정리에서 실제로 증명할 것은 결혼 조건이 횡단의 존재를 함의한다는 것이다.

== 예==
홀 결혼 정리는 [[무한 집합]]의 경우 성립하지 않는다. 예를 들어,
:<math>T=\{\mathbb N\}\cup\{\{n\}\colon n\in\mathbb N\}\}</math>
이라고 하자. 이는 결혼 조건을 만족시키지만, 횡단이 존재하지 않는다.

== 역사와 어원 ==
[[영국]]의 [[필립 홀]]({{llang|en|Philip Hall}})이 쾨니그의 정리와 [[동치]]인 홀 결혼 정리를 1935년에 증명하였다.<ref>{{저널 인용 | last=Hall | first=Philip | title=On representatives of subsets  | doi=10.1112/jlms/s1-10.37.26  | 날짜=1935 | journal=Journal of the London Mathematical Society | volume=10 | issue=1 | pages=26–30 | zbl = 0010.34503 | jfm = 61.0067.01 |언어=en}}</ref>

"결혼 조건"의 어원은 다음과 같다. <math>n</math>명의 미혼 [[이성애자]] 남성과 <math>n</math>명의 미혼 이성애자 여성이 있다고 하자. 이들이 배우자에 대하여 다음 조건들을 요구한다고 하자.
* 각 남성은 임의의 여성과 결혼할 수 있다.
* 각 여성 <math>i=1,\dots,n</math>은 어떤 남성의 집합 <math>T_i\subset\{1,\dots,n\}</math>의 원소만을 결혼하고자 한다.
[[복혼]] 없이 모든 사람들이 결혼하는 방법은 <math>\mathcal T=\{T_i\}_{i=1,\dots,n}</math>의 횡단을 정의한다. 이 경우, 홀 결혼 정리는 모든 사람들이 결혼할 수 있는지 확인할 수 있는 [[필요충분조건]]을 제공한다.<ref name="윤영진">{{서적 인용|저자=윤영진|제목=새로운 조합수학|출판사=교우사|날짜=2007|isbn=978-89-8172-379-8|url=http://www.kyowoo.co.kr/02_sub/view.php?p_idx=334|언어=ko}}</ref>{{rp|289}}

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Combinatorial analysis}}
* {{매스월드|id=MarriageTheorem|title=Marriage theorem}}

== 같이 보기 ==
* [[딜워스의 정리]]
* [[쾨니그의 정리]]

[[분류:조합적 집합론]]
[[분류:그래프 이론 정리]]
[[분류:조합론 정리]]