홀 결혼 정리

조합적 집합론에서 홀 결혼 정리(Hall結婚定理, 영어: Hall marriage theorem)는 여러 유한 집합들의 집합족으로부터, 각 집합에서 서로 다른 원소를 고를 수 있는 필요충분조건에 대한 정리다.

정의

집합족 ${\mathcal {T}}$의 모든 원소가 유한 집합이라고 하자. 홀 결혼 정리에 따르면, 다음 두 조건이 서로 동치이다.^:289

• (결혼 조건 영어: marriage condition) 모든 ${\mathcal {U}}\subset {\mathcal {T}}$에 대하여, $\textstyle |{\mathcal {U}}|\leq \left|\bigcup {\mathcal {U}}\right|$
• (횡단의 존재) 다음 조건들을 만족시키는 순서쌍 $(S,f)$가 존재한다. 이러한 순서쌍을 횡단(橫斷, 영어: transversal) 또는 변별 대표원계(辨別代表元系, 영어: system of distinct representatives)라고 한다.
  • $S\subset \bigcup {\mathcal {T}}$는 집합이다.
  • $f\colon S\to T$는 전단사 함수이다.
  • 모든 $s\in S$에 대하여 $s\in f(s)$이다.

횡단의 존재가 결혼 조건을 함의한다는 것은 자명하므로, 홀 결혼 정리에서 실제로 증명할 것은 결혼 조건이 횡단의 존재를 함의한다는 것이다.

예

홀 결혼 정리는 무한 집합의 경우 성립하지 않는다. 예를 들어,

$T=\{\mathbb {N} \}\cup \{\{n\}\colon n\in \mathbb {N} \}\}$

이라고 하자. 이는 결혼 조건을 만족시키지만, 횡단이 존재하지 않는다.

역사와 어원

영국의 필립 홀(영어: Philip Hall)이 쾨니그의 정리와 동치인 홀 결혼 정리를 1935년에 증명하였다.

"결혼 조건"의 어원은 다음과 같다. $n$명의 미혼 이성애자 남성과 $n$명의 미혼 이성애자 여성이 있다고 하자. 이들이 배우자에 대하여 다음 조건들을 요구한다고 하자.

• 각 남성은 임의의 여성과 결혼할 수 있다.
• 각 여성 $i=1,\dots ,n$은 어떤 남성의 집합 $T_{i}\subset \{1,\dots ,n\}$의 원소만을 결혼하고자 한다.

복혼 없이 모든 사람들이 결혼하는 방법은 ${\mathcal {T}}=\{T_{i}\}_{i=1,\dots ,n}$의 횡단을 정의한다. 이 경우, 홀 결혼 정리는 모든 사람들이 결혼할 수 있는지 확인할 수 있는 필요충분조건을 제공한다.^:289

외부 링크

• “Combinatorial analysis”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Marriage theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

같이 보기

• 딜워스의 정리
• 쾨니그의 정리