集合の一致を利用した証明？

質問

大学受験をするにあたって受験勉強をしているのですが、どうしても自分では解決できない問題にぶち当たってしまいました。
数学Aの集合と論理の範囲での問題で、いわゆるチャート式のようなタイプの問題集のものなのですが、この問題ばかりは解説を読んでもどうしても理解できません。

0以上の整数xに対して、C(x)でxの下２桁をあらわすことにする。例えば、C(12578)＝78、C(6)＝6である。nを2でも5でも割り切れない正の整数とする。
(1)x,yが0以上の整数のとき、C(nx)＝C(ny)ならばC(x)=C(y)であることを示せ。
(2)C(nx)=1となる0以上の整数xが存在することを示せ

解答(2)
A={C(nk)|k=0,1,2…,99}
B={k|k=0,1,2,…,99}
とする。C(nk)は二桁以下の正の整数ゆえ、A⊂Bが成り立つ。
さて、i,jを0以上99以下の整数でi≠jなるものとする。
C(i)＝i、C(j)＝jであるから、C(i)≠C(j)
すると、(1)の対偶より、C(ni)≠C(nj)
よって、Aの要素はどの二つをとっても異なる。
これより、n(A)=n(B)=100となり、A=Bが成り立つ。
したがって、0≦x≦99なる整数xで、C(nx)＝1なるものが存在する。

(2)の解答の意図が全くつかめないのですが、集合を一致させるまでの過程と、集合が一致すればなぜ証明されたのかというところが全くつかめません。

よろしければご教授ください。

回答No.3

banakona

＞集合を一致させるまでの過程と

Ｂはいいですよね？　０から９９まで「漏れなくダブリなく」整数を並べたものですから。

Ａなんですが、これはＣによる像なので、その元は０から９９までのいずれかになるのは明らかなのですが「ダブリ」があるかもしれません。

例えばＣ（ｎ・３）＝Ｃ（ｎ・２９）のように像が同じになるものがあるということです。このダブリがないことを示しているのが、「さて、i,jを0以上99以下の・・・よって、Aの要素はどの二つをとっても異なる。」の部分です。

ＡはＢの像とも言えるので、これによりＡ＝Ｂだと言えます。

＞集合が一致すればなぜ証明されたのか

これは簡単で、C(nx)=1となるｘが存在する、つまりＡの中に１があることを証明すればいい。Ａ＝Ｂなので、Ｂの中に１があれば必ずＡの中にも１がある。Ｂの中に１はありますよね。だからＡの中にも１がある。

回答No.2

kt1965

回答しておきます。

途中で「対偶」を用いています。「対偶」とは、ご存知の通り、「証明命題Ａ」とすれば、「証明命題Ａの全否定」です。もしも、「証明命題Ａの全否定」が成り立たないとすれば、その「対偶」である「証明命題Ａ」が証明されたことになります。

その事を用いた証明なのです。
なお、証明命題の仮定を部分否定して証明命題を証明するやり方を「背理法（間接法）」と言います。

では。

回答No.1

naozou

個人的にはA=Bは言わなくてもいい気がします。

証明はこんなことを言っています。
Aの要素は0,1,2,...,99のうちのいずれかである。（A⊂B)
Aの要素はすべて異なる。C(ni)≠C(nj)
Aの要素は100個ある。n(A)=n(B)=100
ならば、Aの要素には必ず1がある。