弱い形の定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/12 08:36 UTC 版)
「クネーザーの定理 (組み合わせ論)」の記事における「弱い形の定理」の解説
| A + B | ≥ | A | + | B | − | H | {\displaystyle |A+B|\geq |A|+|B|-|H|} となる G の非自明な部分群 H が存在することは比較的簡単に証明できる。 | B | {\displaystyle |B|} に関する数学的帰納法で証明する。 | B | = 1 {\displaystyle |B|=1} のとき、どのような部分群 H をとっても | A + B | = | A | = | A | + | B | − 1 ≥ | A | + | B | − | H | {\displaystyle |A+B|=|A|=|A|+|B|-1\geq |A|+|B|-|H|} である。 | B | > 1 {\displaystyle |B|>1} として、定理が | B ′ | < | B | {\displaystyle |B^{\prime }|<|B|} となるような空でない有限部分集合 A ′ , B ′ {\displaystyle A^{\prime },B^{\prime }} に対して成り立つとする。任意の a 1 ∈ A , b 1 , b 2 ∈ B {\displaystyle a_{1}\in A,b_{1},b_{2}\in B} に対して a 1 + b 2 − b 1 ∈ A {\displaystyle a_{1}+b_{2}-b_{1}\in A} が成り立つとする。このとき H をb2-b1 の形の元から生成される G の部分群とする。B の元 b0 を1つとれば H は b − b 0 ( b ∈ B ) {\displaystyle b-b_{0}(b\in B)} の形の要素をすべて含むから | B | ≤ | H | {\displaystyle |B|\leq |H|} かつ a 1 ∈ A , b 1 , 2 − b 1 , 1 + b 2 , 2 − b 2 , 1 + ⋯ + b k , 2 − b k , 1 ∈ H {\displaystyle a_{1}\in A,b_{1,2}-b_{1,1}+b_{2,2}-b_{2,1}+\cdots +b_{k,2}-b_{k,1}\in H} に対して a 1 + b 1 , 2 − b 1 , 1 + b 2 , 2 − b 2 , 1 + ⋯ + b k , 2 − b k , 1 = a 2 + b 2 , 2 − b 2 , 1 + ⋯ + b k , 2 − b k , 1 = ⋯ = a k ∈ A {\displaystyle a_{1}+b_{1,2}-b_{1,1}+b_{2,2}-b_{2,1}+\cdots +b_{k,2}-b_{k,1}=a_{2}+b_{2,2}-b_{2,1}+\cdots +b_{k,2}-b_{k,1}=\cdots =a_{k}\in A} となる a 2 , … , a k ∈ A {\displaystyle a_{2},\ldots ,a_{k}\in A} がとれる。また 0 = b − b ∈ H {\displaystyle 0=b-b\in H} より A + H = A であるが、 B が空でないことから | A | < | G | {\displaystyle |A|<|G|} よりA + H は G とは一致せず、特に H も G とは一致しない。よって H は G の非自明な部分群であり | A + B | ≥ | A | ≥ | A | + | B | − | H | {\displaystyle |A+B|\geq |A|\geq |A|+|B|-|H|} が成り立つ。 次に a 1 + b 2 − b 1 ∉ A {\displaystyle a_{1}+b_{2}-b_{1}\not \in A} が成り立つ a 1 ∈ A , b 1 , b 2 ∈ B {\displaystyle a_{1}\in A,b_{1},b_{2}\in B} がとれるとする。 e = b 1 − a 1 {\displaystyle e=b_{1}-a_{1}} とおく。 b 1 = a 1 − e ∈ A − e {\displaystyle b_{1}=a_{1}-e\in A-e} かつ b 2 = g − e ∉ A − e ( g ∉ A ) {\displaystyle b_{2}=g-e\not \in A-e(g\not \in A)} となる。そこで A ( e ) = A ∪ ( B + e ) , B ( e ) = B ∩ ( A − e ) {\displaystyle A(e)=A\cup (B+e),B(e)=B\cap (A-e)} とおく。 A ( e ) + B ( e ) ⊂ ( A + B ) ∪ ( ( B + e ) + ( A − e ) ) = A + B {\displaystyle A(e)+B(e)\subset (A+B)\cup ((B+e)+(A-e))=A+B} より | A + B | ≥ | A ( e ) + B ( e ) | {\displaystyle |A+B|\geq |A(e)+B(e)|} が成り立つ。また g ∈ B ∖ B ( e ) = B ∖ ( A − e ) {\displaystyle g\in B\backslash B(e)=B\backslash (A-e)} ならば g + e ∈ ( B + e ) ∖ A = A ( e ) ∖ A {\displaystyle g+e\in (B+e)\backslash A=A(e)\backslash A} となることから | B | − | B ( e ) | ≤ | A ( e ) | − | A | {\displaystyle |B|-|B(e)|\leq |A(e)|-|A|} つまり | A ( e ) | + | B ( e ) | ≥ | A | + | B | {\displaystyle |A(e)|+|B(e)|\geq |A|+|B|} が成り立つ。 ところで b 2 = g − e ∉ A − e ( g ∉ A ) {\displaystyle b_{2}=g-e\not \in A-e(g\not \in A)} より b 2 ∉ B ( e ) {\displaystyle b_{2}\not \in B(e)} だから | B ( e ) | < | B | {\displaystyle |B(e)|<|B|} である。よって帰納法の仮定より | A ( e ) + B ( e ) | ≥ | A ( e ) | + | B ( e ) | − | H | {\displaystyle |A(e)+B(e)|\geq |A(e)|+|B(e)|-|H|} となる G の非自明部分群 H がとれる。上記の不等式を使って | A + B | ≥ | A ( e ) + B ( e ) | ≥ | A ( e ) | + | B ( e ) | − | H | ≥ | A | + | B | − | H | {\displaystyle |A+B|\geq |A(e)+B(e)|\geq |A(e)|+|B(e)|-|H|\geq |A|+|B|-|H|} がいえる。よって帰納法により弱い形の定理が証明される。
※この「弱い形の定理」の解説は、「クネーザーの定理 (組み合わせ論)」の解説の一部です。
「弱い形の定理」を含む「クネーザーの定理 (組み合わせ論)」の記事については、「クネーザーの定理 (組み合わせ論)」の概要を参照ください。
- 弱い形の定理のページへのリンク
