議論と例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/14 20:57 UTC 版)
例 1: S = {S1, S2, S3} があり、それぞれは以下の通り。 S1 = {1, 2, 3} S2 = {1, 4, 5} S3 = {3, 5} 妥当なSDRは {1, 4, 5} である（ただし、これは唯一のSDRではない。例えば {2, 1, 3} でもよい）。 例 2: S = {S1, S2, S3, S4} があり、それぞれは以下の通り。 S1 = {2, 3, 4, 5} S2 = {4, 5} S3 = {5} S4 = {4} 妥当なSDRは存在しない。また、部分集合 {S2, S3, S4} について結婚条件が成り立たない。 結婚定理の一般的応用例は、n人の男性とn人の女性という2つのグループを想定する。それぞれの女性は男性の部分集合のいずれかと結婚できれば幸せである（結婚してもよいと思う男性が何人かいる）。また、それぞれの男性は自分と結婚したい（してもよい）と思っている女性と結婚できれば幸せである。ここで、全員が幸せになるような組合せ（結婚）は可能か、という問題である（男女を入れ替えた設定でもよい）。 ここで Si を i番目の女性が結婚して幸せになれる男性の集合とする。結婚定理によれば、それぞれの女性が男性と幸せな結婚をできることと、集合の集まり {S1, S2, ...} が結婚条件を満たすことは同値である。 なお、この場合の結婚条件とは、女性の任意の部分集合 I {\displaystyle I} について、結婚したら幸せだという女性が少なくとも1人以上いる男性の数 | ⋃ i ∈ I S i | {\displaystyle |\bigcup _{i\in I}S_{i}|} がその部分集合に含まれる女性の人数 | I | {\displaystyle |I|} 以上でなければならない。これが成り立たないと結婚対象となる男性の人数が（ I {\displaystyle I} に属する女性の人数に対して）足りないことを意味するので、この条件が必要条件であることは明らかである。興味深いことに、これは同時に十分条件でもある。 この定理は結婚以外にもいろいろな場面に応用できる。例えば、52枚のトランプを4枚ずつ13の山に分けるとする。結婚定理をこれに適用すると、それぞれの山から1枚ずつカードを選んで、エースからキングまでの13枚を必ず揃えることができるといえる（スートは考慮しない）。 より抽象的な例としては、ある群 G があり、H を G の有限な部分群とする。これに結婚定理を適用すると、G における H の左剰余類の集合と右剰余類の集合のSDRであるような集合 X が必ず存在するといえる。 より一般的問題として、集合の集まりがあったときにそれぞれの集合から（別個とは限らない）元を選ぶことができるには、選択公理が成り立たなければならない。
※この「議論と例」の解説は、「ホールの定理」の解説の一部です。
「議論と例」を含む「ホールの定理」の記事については、「ホールの定理」の概要を参照ください。
- 議論と例のページへのリンク
