MathLabs

第4問

a,bを正の整数、A,Bを有限な整数集合とし、次を満たすとする。(i) AとBは互いに素。(ii) 整数iがAまたはBに属すなら、i+aはAに属すか、i-bはBに属す。|X|をXの要素数とするとき、a|A|=b|B|を証明せよ。
ステップ 2/5: 和集合の等号を導く
前のステップ次のステップ
A∪B⊆A∗∪B∗,∣A∗∪B∗∣≤∣A∗∣+∣B∗∣=∣A∣+∣B∣=∣A∪B∣.A\cup B\subseteq A^*\cup B^*,\quad |A^*\cup B^*|\le|A^*|+|B^*|=|A|+|B|=|A\cup B|.
詳しい解説

条件(ii)によりA∪Bの各元はAまたはBに入る。平行移動は濃度を保ち、A,Bは互いに素なので、表示した不等式列の両端は等しい。したがって全て等号である。