クネーザーの定理 (組み合わせ論)
が成り立つとする。このとき 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)}