「結婚定理」置いときますね
どうやら「関東地方議員有志の会」なる団体が「未婚者ゼロ社会の早期実現」を目指しているらしいので、参考までに定理置いときますね。つ「結婚定理」
- 定理（Hall's Marriage Theorem, 1935）
- ある有限集合Xの部分集合A1、A2、・・・が与えられているとする。このとき、「全てのAiたちからそれぞれ一つずつ要素を選んできて、選んだ要素が全て異なるようにできる」ための必要充分条件は、「Aiたちをk個持ってきたら、それらの和集合はk個以上の要素を含んでいる」が常に（どんなkについても）成り立つことである。
- 系*1
- ある男女の（有限の）集団について、お互いに「この相手となら結婚してもよい」と思っている男女のペアを線で結ぶものとする。このとき、線で結ばれていないカップルを作ることなく全員をカップルにすることができるための必要充分条件は、男女の人数が同数であり、かつ「男性*2をk人選ぶと、その少なくとも一人と線で結ばれている女性はk人以上いる」が常に成り立つことである。
というわけで、独身者が一人もいない状態を達成するためには、少なくとも男女の人数が同じでないといけない*3のですが、その状況をどうやって達成/維持するつもりなのでしょうか・・・と思ったのですが、よく見ると目指しているのは「未婚者」ゼロ社会であって「独身者」ゼロ社会ではないんですね。なぁんだ。
（追記）
証明を書き忘れたので追記しておきます。
定理の証明
必要性
定理の前半部のような要素の選び方があったら、Aiたちをk個持ってきたとき、その和集合は「Aiから選んだ要素」全て、合計k個を含む。（必要性の証明終わり）
充分性
定理の後半の条件が成り立っているとする。
もし、「Aiたちをk個持ってきたら、それらの和集合はk+1個以上の要素を含んでいる」・・・（＊）が1以上Xの要素数未満の全てのkで成り立っているとしたら、A1から要素xを持ってきて*4、それを「A1から選ぶ要素」にする。一方、Xからxを除いた集合と、部分集合A2、A3、・・・を考えると、（＊）によりそれらは定理後半の条件を満たす*5ので、定理前半の条件を満たす要素の選び方がある*6。それらをあわせれば求める要素の選び方が得られる。
また、ある1以上Xの要素数未満のkについて、（＊）が成り立たないようなk個の部分集合たち（それらk個の集合の集合をBとおく）があるとき、「Bに属する集合たちの和集合」をYとおくと、条件からYはちょうどk個の要素を含んでいる。このとき、「集合Ｙと、Bに属する部分集合たち」も定理後半の条件を満たすので、全体集合の要素数に関する数学的帰納法により、Bに属する部分集合たちについては、定理前半の条件を満たす（Yに属する）要素の選び方がある。
一方、Xの中でY以外の部分をZとおき、Bに属していない部分集合Aiたちをm個持ってくる。もし「これらのAiたちの和集合とZの共通部分」（これをWとおく）がm個未満の要素しか含まないとしたら、これらm個のAiたちと、Bに属する部分集合たち、計k+m個の部分集合の和集合（これはYとWの和集合）はk+m個未満の要素しか含まないことになり、定理後半の条件と矛盾する。従ってWはm個以上の要素を含むので、「集合Zと、Bに属していないAiとZとの共通部分たち」も定理後半の条件を満たし、全体集合の要素数に関する数学的帰納法により、Bに属していない部分集合たちについては、定理前半の条件を満たす（Zに属する）要素の選び方がある。
これら二つをあわせれば、定理前半の条件を満たす要素の選び方が得られる。（充分性の証明終わり）
*1:こちらを「結婚定理」と呼ぶ場合もあります
*2:男性と女性の立場を入れ替えても差し支えありません
*3:同性同士の結婚や重婚を合法化するという荒技もあるにはありますが
*4:前提からA1は空でない
*5:満たさないと仮定して、k個のAiたち（ただしiは2以上）についてそれらの和集合がx以外の要素をk個未満しか含まない（この時点でk=0ではありえない）としたら、この和集合は要素をk+1個未満しか含まず、条件（＊）を満たさない。ということは、場合分けの条件からkはXの要素数以上となるが、このとき「今持ってきたAiたちと、A1」というk+1個の部分集合の和集合はXの部分集合なのでk個以下の要素しか含まない。これは定理の後半の条件に反するので、元々の仮定が誤りだったことになる
