위키백과

쾨니그의 정리: 두 판 사이의 차이

입체적으로 역사 찾아보기
← 이전 편집다음 편집 →
내용 삭제됨 내용 추가됨
시각위키텍스트
편집 요약 없음
9번째 줄:
조합적 집합론에서는 쾨니그의 정리를 일반화하는 '''홀 결혼 정리'''({{llang|en|Hall’s theorem}})가 존재한다. 쾨니그의 정리와 홀의 정리는 서로 [[동치]]이며, 이들은 [[딜워스의 정리]]와도 동치이다.
 
어떤 [[집합]] S가 있고, 그 [[부분집합집합족]] <math>A_1, A_2, ..,\mathcal A_mT</math>의 이모든 이루는원소가 집합족 T가 있다고[[유한집합]]이라고 하자. 그러면 T에 대해 어떤 집합 s가 '''변별홀 대표원계결혼 정리'''(辨別代表元系에 따르면, {{llang|en|system of distinct representatives}})라는다음 것은두 다음과조건이 같이서로 정의된다동치이다.<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>
* S의 서로 다른 원소 <math>a_1, a_2, .., a_r</math> 이 <math>a_i \in A_i (i = 1, 2, .., r)</math> 일 때, T의 원소를 [[정의역]]으로 하고 S를 [[공역 (수학)|공역]]으로 하며 <math>s(A_i) = a_i</math> 를 만족하는 [[함수]] s를 T에 대한 변별 대표원계라 한다.
* (횡단의 존재) 다음 조건들을 만족시키는 순서쌍 <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>n</math>명의 미혼 [[이성애자]] 남성과 <math>n</math>명의 미혼 이성애자 여성이 있다고 하자. 이들이 배우자에 대하여 다음 조건들을 요구한다고 하자.
집합 S에서 얻을 수 있는 집합족 T는 변별 대표원계를 가질 수도, 가지지 않을 수도 있다. 또 변별 대표원계를 갖는 경우 유일하지 않을 수도 있다. 여기서 T가 변별 대표원계를 가지는 필요충분조건이 바로 이하의 정리로 주어지는 것이다.
* 각 남성은 임의의 여성과 결혼할 수 있다.
 
* 각 여성 <math>i=1,\dots,n</math>은 어떤 남성의 집합 <math>T_i\subset\{1,\dots,n\}</math>의 원소만을 결혼하고자 한다.
이 변별 대표원계의 개념에서 왜 이 정리가 결혼정리로 불리는지를 알 수 있다. r명의 남자(혹은 r명의 여자)가 결혼했으면 하는 여자(혹은 남자)의 표를 만들 때, 각 사람이 자기 표에 있는 이성과 결혼하는 것이 가능할 필요충분조건은 그 표가 변별 대표원계를 갖는 것이기 때문이다.<ref name="윤영진"/>{{rp|289}}
[[복혼]] 없이, 모든 사람들이 결혼할 는수 있는 방법은 <math>\mathcal T=\{T_i\}_{i=1,\dots,n}</math>의 횡단을 정의한다. 이 경우, 홀 결혼 정리는 모든 사람들이 결혼할 수 있는지 확인할 수 있는 [[필요충분조건]]을 제공한다.<ref name="윤영진"/>{{rp|289}}
 
이 꼴의 홀 결혼 정리는 다음과 같이 공식화할 수 있다.<ref name="윤영진"/>{{rp|289}} 일반적으로 이는 '홀의 정리'로 불린다.
 
* 앞에서와 같이 정의된 S, T에 대하여 T가 변별 대표원계를 가질 필요충분조건은 각각의 r≤m에 대해 r개 <math>A_i</math>의 [[합집합]]이 적어도 r개의 원소를 가지는 것이다.
 
여기서 →의 방향은 변별 대표원계의 정의에 따라 자명하므로, 홀 결혼 정리에서 실제로 증명할 것은 ←의 방향이다.
 
== 역사 ==
원본 주소 "https://ko.wikipedia.org/wiki/쾨니그의_정리"