第４回 分配法則とド・モルガンの法則 [集合論入門]
第４回 分配法則とド・モルガンの法則
定理８ A、B、Cを任意の集合とするとき、次の関係が成立する。
【証明】
（１） まず、
を証明する。
x∈A∩(B∪C）であるとする。すると、定義より、x∈Aでかつ(x∈B またはx∈C）になる。
で、x∈Aかつx∈B、つまり、x∈A∩Bのとき、
同様に、x∈Aかつx∈C、つまり、x∈A∩Cのとき、
になる。
よって、x∈Bであろうがx∈Cであろうが、
次に、
を証明する。
同様に
よって、
①と②より
（２）
（証明終）
（２）の証明では、次の吸収法則を使っている。
吸収法則が成り立つことは、前回の定理４の（３）と定理６の（３）より明らか。
なぜならば、
A⊂A∪Bだから、定理６の（３）より、A∩（A∪B）=A
A∩C⊂Aだから、定理４の（３）より、A∪（A∩C）=A
であるからである。
定理９（ド・モルガンの法則）
A、B、Cを任意の集合とするとき、次の関係が成り立つ。
【証明】
（証明終）
A、Bが普遍集合Uの部分集合である場合には、次の形のド・モルガンの法則が成り立つ。
定理１０ （ド・モルガンの法則）
問１ 次のことを示せ。ただし、Uは普遍集合とする。
【解】
（１） ド・モルガンの法則より
したがって、
（２） ド・モルガンの法則より
したがって、
（解答終）
問２ AとBが普遍集合Uの部分集合であるとき、Aに関するBの補集合A−Bは
になる。
このことと定理１０を用いて、定理９が成り立つことを示せ。
【解】
（解答終）
第３回 集合の和と交わり [集合論入門]
第３回 集合の和と交わり
§１ 和集合
AとBを集合とする。
AとBの要素を全て寄せ集めてできる集合をAとBの和集合、または、単に和といい、
A∪B
であらわす。
すなわち、
である。
例 A=｛1, 2, 3｝、B=｛2 , 4 , 6｝であるとき、
定理４
【証明】
（１） A∪Bは、AとBの要素を全部寄せ集めたもの。よって、x∈Aならば、x∈A∪B。
よって、A⊂A∪B。B⊂A∪Bも同様。
（２） x∈A∪Bとすれば、x∈Aまたはx∈Bである。
仮定より、A⊂CかつB⊂Cであるから、いずれにせよx∈C。ゆえに、A∪B⊂C
（３） （１）よりA∪B⊃Aであるから、A∪B⊂Aであることをいえばよい。
A⊂A、B⊂Aであるから、（２）によってA∪B=A。
（４） A∪B=AだからA∪B⊂A。（１）より、A⊂A∪B。ゆえに、第１回の定理２よりB⊂A。
（証明終）
（３）、（４）は、B⊂Aであるための必要十分条件がA∪B=Aであることを示している。
定理５
【証明】
（１） A∪B、B∪AともにAの要素とBの要素をすべて寄せ集めたもの。したがって、A∪B=B∪A。
（２） (A∪B)∪Cは、A∪Bの要素とCの要素をすべて寄せ集めたもの。A∪BはAとBの要素をすべて寄せ集めたもの。ゆえに、（A∪B）∪Cは、AとB、Cのすべての要素を集めたものにほかならない。
同様に、A∪（B∪C）も、AとB、Cのすべての要素を集めたものである。
したがって、(A∪B)∪C=A∪(B∪C)である。
（証明終）
（２）の結合法則より、
と括弧を取り外して計算してよいことが保証される。
問１ A∪A=Aであることを示せ。
【解】
定理２の（１）より、A∪A⊃A。
また、A⊂A、A⊂Aだから、定理２の（２）より、A∪A⊂A。
したがって、
A∪A=A
（解答終）
問２ A∪∅=Aであることを示せ。
【解】
A∪∅⊃A
また、A⊂A、∅⊂Aだから、A∪∅⊂A。
したがって、
A∪∅=A
（証明終）
問３ A∪B=(A−B)∪Bであることを示せ。
【解】
A−B⊂A⊂A∪B、B⊂A∪Bだから、
（A−B）∪B⊂A∪B
つぎに、x∈A∪Bとすれば、x∈Aまたはx∈B。
x∈Bならば、x∈(A−B)∪B。
x∉Bならばx∈Aだから、x∈A−Bで、x∈(A−B)∪B。
いずれにせよ、
x∈（A−B）∪B。
したがって、
A∪B=(A−B)∪B
（解答終）
問４ （A−B）∪B=Aであるための必要十分条件はA⊃Bであることを示せ。
【解】
問３より、（A−B）∪B=A∪B。
問の条件より（A−B）∪B=Aだから、
A∪B=A
定理５の（３）、（４）より、A∪B=Aであるための必要十分条件はA⊃B。
したがって、
（A−B）∪B=Aであるための必要十分条件はA⊃Bである
（解答終）
§２ 共通部分
２つの集合A、Bに共通する要素の全体からなる集合を、AとBの共通部分、あるいは、交わりといい、
A∩B
であらわす。
すなわち、
である。
AとBに共通する要素が１つもないとき、すなわち、
A∩B=∅
のとき、AとBは互いに素であるという。
例 A=｛1, 2, 3｝、B=｛2, 4, 6｝のとき、
定理６
【証明】
（１） x∈A∩Bだから、x∈Aかつx∈B。ゆえに、x∈A∩Bならばx∈A。よって、A∩B⊂Aである。
A∩B⊂Bも同様。
（２） x∈Cならば、C⊂A、C⊂Bより、x∈Aかつx∈B。ゆえに、x∈A∩B。よって、C⊂A∩Bである。
（３） （１）より、A∩B⊂B。よって、B⊂A∩Bであることを示せばよい。
B⊂A、B⊂Aであるから、（２）によってB⊂A∩B。
よって、B⊂AならばA∩B=Bである。
（４） 仮定より、B=A∩Bである。
したがって、（１）より
B=A∩B⊂A
（証明終）
定理７
定理７は明らかなので、証明略。
問１ 定理４を用いて、A∩A=Aであることを示せ。
【解】
A⊂Aだから、定理４の（３）より、
A∩A=A
（解答終）
問２ A∩∅=∅であることを示せ。
【解】
∅⊂Aだから、定理４の（３）より、
A∩∅=∅
（解答終）
問３ A−B=Aとなる必要十分条件は、AとBが互いに素であることを示せ。
【解】
x∈A−Bとすると、x∈Aかつx∉B。
したがって、
（A−B）∩B=∅
である。
仮定より、A−B=Aだから、
逆に、AとBが互いに素であるとき、
A−B=A
よって、
A−B=Aとなる必要十分条件は、AとBが互いに素である。
（解答終）
第２回 集合の差、補集合 [集合論入門]
第２回 集合の差、補集合
§１ 集合の差
A、Bを集合とする。
x∈Aであるがx∈Bでないではないx全体からなる集合、すなわち、
をAとBとの差集合または差といい、記号
または
などであらわす。
差集合の定義から明らかであるが、
【略証】
x∈A−Bとすると、x∈Aかつx∉Bなので、x∈Aである。
故に、
（略証終）
例１ Aを自然数全体の集合、Bを偶数全体の集合とすれば、A−Bは奇数全体の集合
例２
§２ 空集合
A={1, 2, 3}、B=｛1, 2, 3, 4, 5｝とする。
このとき、
であるが、AとAの差集合A−A、AとBの差集合は、要素をなにも持たない集合となる。
このように、要素を何ももたない集合を空集合といい、記号
∅または｛｝
であらわす。
さらに、いかなる集合Aに対して
と定義する。
また、
と定義する。
Aを任意の集合とするとき、次の式が成立することは明らかであろう。
問１ A⊂Bならば、A−C⊂B−Cであることを示せ。
【解】
A−C=空集合ならば、A−C⊂B−Cは明らか。
そこで、A−C≠∅とする。x∈A−Cだから、x∈Aかつx∉C。
A⊂Bだから、x∈Bかつx∉C。したがって、x∈B−C。
ゆえに、
A⊂Bならば、A−C⊂B−C
（解答終）
問２ A−B=∅であるための必要十分な条件はA⊂Bであることを示せ。
【解】
AやBが∅のときは明らか。
A≠∅、B≠∅とする。
A−B=∅は、x∈Aかつx∉Bなるxがないことで、x∈Aならばx∈Bであることに他ならない。
したがって、
（解答終）
§３ 補集合
BがAの部分集合である場合、AとBとの差を、BのAに関する補集合（Complementary Set）という。
Aが空集合でない場合、Aの要素は、Bに属するか、A−Bに属するかのいずれか一方だけが成立する。
すなわち、次の関係が成り立つ。
（１） x∈Aならば、x∈Bまたはx∈A−B
（２） x∈Bならばx∉A−B
（３） x∈A−Bならばx∉B
また、
Aに関するAの補集合は空集合∅であり、Aに関する空集合∅の補集合はAである。
定理３ A⊃BならばA−(A−B)=Bである。
【証明】
A−B=Cとする。
まず、A−C⊂Bであることを示す。
A−C=∅であるならば、A−C⊂B。
A−C≠∅のとき、
x∈A−Cとすると、x∈Aかつx∉C、すなわち、x∈Aかつx∉A−B。よって、x∈B。
ゆえに、
A−C=A−(A−B）⊂B
つぎに、B⊂A−Cであることを示す。
B=∅ならばB⊂A−C。
B≠∅のとき、
x∈Bとすると、x∈Aかつx∉A−B、すなわち、x∈Aかつx∉C。ゆえに、x∈A−C。
したがって、
B⊂A−C=A−(A−B)
よって、
A⊃BならばA−(A−B)=B
（証明終）
定理３の逆、
A−(A−B)=BならばA⊃B
が成立するので、
A−(A−B)=BはA⊃Bの必要十分な条件である。
対象となる集合が、固定された集合Xの部分集合であるとき、Xを普遍集合（Universal Set）という。A⊂Xのとき、集合AのXに関する補集合を単に補集合といい、記号
であらわす。
すなわち、
普遍集合Xと空集合∅の補集合は、
となることより、
宿題 定理３の逆
A−(A−B)=BならばA⊃B
を証明せよ。
第１回 集合 [集合論入門]
第１回 集合
§１ 集合の要素と相等
aが集合Aに属しているとき、aは集合Aの要素（元）といい、このことを記号
で表し、aが集合Aの要素でないとき、このことを
で表す。
要素を有限個しか含まない集合を有限集合、そうでない場合を無限集合という。
Aの全ての要素がBの要素であり、Bの全ての要素がAであるとき、すなわち、 x∈Aならばx∈B、かつ、x∈Bならばx∈Aであるとき、集合AとBは等しいといい、このことを
A＝BまたはB=A
で表す。
また、A=Bでないとき、AとBは相異なるといい、
A≠B
で表す。
§２ 集合の表し方
集合の表し方には、集合の要素を列挙する外延的記法と、集合に属する条件を用いて集合を表す内包的記法の２通りがある。
外延的記法の例
内包的記法の例
問１ 以下の内包的記法を外延的記法で表わせ。ただし、Nは自然数全体の集合、Qは有理数全体の集合とする。
【解】
（１） １０未満の自然数の集合は｛1,2,3,4,5,6,7,8,9｝だから、その逆数1/nの集合は
（２） 0<x<100の有理数なので、
また、√xは自然数なので、①を満たす自然数は
自然数は有理数なので、これが求める集合である。
（解答終）
問２ 自然数全体の集合をNとし、Nの各要素xの正の約数をf(x)で表す。このとき、次の問に答えよ。
（１） f(2)、f(4)、f(18)を求めよ。
（２） 
はどのような集合か。
【解】
（１） ２の正の約数は１、２だから、f(2)=2。
４の正の約数は１、２、４だから、f(4)=3。
１８の約数は、1、２、３、６、９、１８だから、f(18)=6。
よって、
f(2)=2、f(4)=3、f(18)=6。
（２） xを１ではない自然数とすると、1とxは、xの約数。f(x)=2なので、xは１と自分自身x以外の約数をもたない。つまり、xは素数。
したがって、素数全体の集合である。
（解答終）
§３ 部分集合
集合Aの要素xがすべてBの要素であるとき、すなわち、
であるとき、AはBの部分集合であるといい、記号
または
で表す。
特に、A⊂BかつA≠Bであるとき、AはBの真部分集合という。
なお、本によっては、AがBの部分集合であることを
AがBの真部分集合であることを
で表すことがある。
例
A=｛1, 2 , 3｝はB={1, 2, 3, 4, 5｝の部分集合であり、Bの真部分集合である。
集合Aの要素はすべて集合Aの要素なので、AはAの部分集合である。すなわち、
自然数全体の集合Nは整数全体の集合Zの部分集合であり、真部分集合である。
定理１ A⊂BかつB⊂Aならば、A=Bである。
【証明】
A⊂BだからAの全ての要素はBの要素であり、B⊂AだからBのすべての要素はAの要素である。したがって、AとBはその全ての要素を共有し、A=Bである。
（証明）
定理２ A⊂B、B⊂CならばA⊂Cである。
【証明】
A⊂Bだからx∈Aならばx∈B、また、B⊂Cだから、x∈Bならばx∈Cである。したがって、x∈Aならばx∈C。
よって、
A⊂B、B⊂CならばA⊂C
（証明）
問３ 定理１を用いてA=Aであることを示せ。
【解】
A⊂AかつA⊃Aなので、定理１より、A=Aである。
（解答終）
［対角線論法の周辺］ [集合論入門]
［対角線論法の周辺］
ネコ先生も仰ってるように、「対角線論法」とか「カントールの定理」とかは、数学的な実務（解析学）においてさえほとんど使いません。例えば「現代解析の基礎，ディユドネ，東京図書」は訳者である森毅大先生の前書きによれば世界で最も格好良い解析学の本ですが、著者ディユドネ自身が最初に次のように書いてます。
「・・・可算集合（注１）のごく初等的な性質である。これは、カントル以後展開された"集合数"の長い理論の出発点である。・・・しかしながら、実数が可算でないという消極的事実を除いては、解析学に集合論を応用するのにこれらの初等的性質以上のことを使うことは、めったにない」
つまり実務（解析学）において「対角線論法」とか「カントールの定理」とかは時々使うだけで、「学生よ、無限集合論で悩むなよ」とディユドは最初に警告してくれてる訳です(^^)。森毅大先生が同書を訳されたのは1971年。自分は1980年の第2刷を持ってますが、2018年の現在においても、同書が世界で最も格好良い解析学の本であり、「学生よ、無限集合論なんかで悩むなよ」の心遣いもそのまま生きてると思います。
では何故ここに出張ってきたかというと、無限集合論のアイデア自体が自分には面白いからです。道具造りの楽しみとして(^^;)。
まず全単射が存在すれば、同数という話。
単射とは関数f：Ａ→Ｂにおいて、1対1対応という事。例えばＡ＝{1，2，3}，Ｂ＝{1，2，3，4，5}とすれば、f(1)＝1，f(2)＝2，f(3)＝3みたいになる事。一般には、f(1)＝f(2)＝f(3)＝5となってても関数なので、一般には関数は単射ではありません。
全射とは関数g：Ｂ→Ａにおいて、対応漏れがない事。g(1)＝1，g(2)＝2，g(3)＝3，g(4)＝1，g(5)＝2みたいな感じ（gは単射ではない）。上への写像などとも呼ばれます。さっきのf(1)＝1，f(2)＝2，f(3)＝3ではＢの要素の4と5が余るので、fは全射ではありません。
重要なのは関数に対する次の規約。
h：Ｘ→Ｙが関数であるとは、各x∈Ｘに対応する（xに依存した）y∈Ｙが一つだけある事。これをy＝h(x)と書く。Ｘを定義域，Ｙを値域と言う。
上記の重要な含みは、全てのx∈Ｘがh(x)∈Ｙを持たなければならない、という事。例えばもしg(4)やg(5)がなければ、そういうものが1個でも定義域にあれば、それは関数じゃない。
またf(1)＝1，2とかになってても駄目。一つだけだから。どうしてかというと、こういうのを許すと関数のグラフが曲線じゃなく帯になるから。
いま集合の要素の個数をCard()で表します（注２）。さっきのＡ，ＢならCard(Ａ)＝3，Card(Ｂ)＝5。
ＡとＢが有限個の要素しか持たなければ（有限集合であれば）、関数の規約を守る限り、次の事実は明らかです（本当は証明しますが）（注３）。
(1) Card(Ａ)＜Card(Ｂ)なら、全射なf：Ａ→Ｂは作れない。
(2) Card(Ａ)＜Card(Ｂ)なら、単射なg：Ｂ→Ａは作れない。
当然ですよね？(^^)。Ａ＝{1，2，3}でf(1)＝1，f(2)＝2，f(3)＝3とＡの要素を使い切ったら全射にするためには、f(1)＝4，f(2)＝5とでもするしかない。しかしこれは関数の規約から不可。一つだけだから。
同様にＢ＝{1，2，3，4，5}でg(1)＝1，g(2)＝2，g(3)＝3としたらＡの要素を使い切るので、今度もＢの要素が余る。単射にするためにはg(4)とg(5)を諦めるしかないが、関数の規約からそれでは関数ではない。
よって、
(3) Card(Ａ)＝Card(Ｂ)の時だけ、全単射なf：Ａ→Ｂがある（真部分集合と全体には全単射なし）。
典型的には、Ａ＝{1，2，3，4，5}，Ｂ＝{1，2，3，4，5}のケース。ところでＡをあなたの5本指の集合Ａ＝{親指，人差し指，中指，薬指，小指}に取り換えても同じ事ができます。これの意味するところは、(3)は「指折り数える行為の数学的定式化」に過ぎないという事です(^^)。何かの個数を知りたい時は「指折り数えて証明するしかない」という事でもあります(^^;)。
無限集合に移行します。無限集合は数え尽くせません。何故なら数え尽くせたら、その瞬間に有限になるからです。有史以来、無限の定義は、
・無限とは有限でない事。
これは現代数学においてもそうです。結論から言うと無限集合論は、最初から数え尽くせないものを扱うよと決めてるのです。では無限集合の同数はどうするかというと、(3)を逆にしてそのまま使います。
(4) 全単射なf：Ａ→Ｂがあるなら、Card(Ａ)＝Card(Ｂ)と決める。
いいですか、これは「決める」ですからね。有限の世界ではこれでうまく行ったという理由だけで、根拠レスに(3)を無限にも適用するんです。無限集合論の全ての理屈はこういうものです。有限ではうまく行ったから無限にも使っちゃえと(^^;)。他にやりようがないから。無限を具体的に調べ尽くして確認するなんて不可能だから。調べ尽くせたら有限だから。
個人的には、有限の論理でどこまで無限を切れるかの試論が無限集合論と思っています。そういう訳で(4)などはすぐに機能不全に陥ります。よく出てくるのが、偶数全体の集合Ｅと自然数全体の集合Ｎの個数比較です。ＥはＮの真部分集合ですから、単射はあるけど全射なんかあろうはずがない。→で対応付けを表す事にします。Ｅの要素→Ｎの要素 です。
0→0，2→2，4→4，・・・
→の右の0，2，4はＮの要素の一つ飛ばしなので、全射ではありません。しかし偶数mは、
m＝2n，n＝0，1，2，・・・
と表せるのでした。n＝m/2，m＝0，2，4，・・・と変形すれば、
0→0，2→1，4→2，・・・
m＝2nとn＝m/2は全単射です。(4)に従えばＥとＮは同数です。ＥはＮの真部分集合なのに！。無限集合の場合は、部分と全体が同数になるのは普通です。しかしここまでして無限を扱う必要はあるんでしょうか？。あるんです。それはディユドネ先生も仰るように「ときどき役に立つから」。ベキ集合を考えるのもときどき役に立つから(^^;)。
Card()の事を集合の濃度と言います。その心は「やっぱ有限の個数とはちょっと違うよね」。本当は「無限集合の個数」と言っても良かったんですけどね。やる事は変わらないから(^^;)。
最初に普通の対角線論法をご紹介します。自然数全体の集合Ｎと実数全体の集合Ｒの個数比較です（やる事は変わらない(^^)）。手始めに解きやすいように問題の形を整えます。
を考えると、x＝－π/2～π/2の範囲で(5)は－∞～∞の値をとり、しかも単調増加です。単調増加なら単射ですよね？。しかも－∞～∞の値をとるので全射ですよね？。よって実数全体Ｒと区間[－π/2，π/2]の間には全単射が存在するので同数です。
y＝tan-1(πx/2)
y＝tan-1(π(x－1)/2)
y＝tan-1(π(2x－1)/2)
とx方向で2/πだけスケール変換して（x＝－1～1）、＋1だけ平行移動し（x＝0～2）、また1/2だけスケール変換すれば、Ｒと区間[0，1]が同数になります。x∈[0，1]を無限小数展開します。
x＝0.α1α2α3α4・・・
αjは、0～9のどれかの数字です。目的はＮとＲの個数比較なので、Ｎと区間[0，1]の個数比較を行います。全単射があれば両者は同数です。そこで「全単射があった」と仮定します。それを絵にすれば具体的な対応付けはさておいて、いずれにしろ、
となるはずです。
i → 0.αi1αi2αi3αi4・・・は、自然数iで実数0.αi1αi2αi3αi4・・・が番号付けられたという意味です。αijのiは付けられた番号，jはそのj位の小数。ただしi≠kなら、0.αi1αi2αi3αi4・・・≠0.αk1αk2αk3αk4・・・です。全単射は単射でなければならないので。そして全射でもなければならないと仮定したのでした。対応漏れがあってはいけません。
(6)の→の右側の対角線αii，i＝1，2，・・・に沿って次のような実数βを構成します。
(7)で構成されるβは明らかに[0，1]の要素です。しかしβの小数以下j位の数字は、jで番号付けられた実数0.αj1αj2αj3αj4・・・αjj・・・のj位の数字と必ず異なるので、(6)に現れるどの実数とも一致しません。つまり、Ｎから区間[0，1]への全単射は、それが具体的にどういうものであれ、必ず番号漏れ必至です。よって、Ｎから区間[0，1]への全単射は作れない事をいま証明した事になります。番号漏れしたので、
Card(Ｎ)＜Card([－1，1])＝Card(Ｒ)
です。
気持ち悪いですよね？。気持ち悪いんですよぉ～！。でもその原因は、(4)が機能不全だからではありません。根はもっと深いんです。
集合Ａのベキ集合（Power Set）を毎回2Ａと書くのは面倒なので、Power Setの頭文字をとってP(Ａ)と書きます。ＡとP(Ａ)との個数比較を行います。Ａ＝{a1，a2，・・・}で表すと、P(Ａ)＝{φ，{a1}，{a1，a2}，・・・，{a1，a2，・・・}}などとなるのでした。(6)と同じように、ＡからP(Ａ)への全単射fを絵にしてみます。
この絵の読み方ですが、各行はP(Ａ)の要素であるＡの部分集合を表していて、各行の0，1並びは、その行のj列が1なら、列ヘッダajを持つＡの部分集合，0ならその部分集合はajを持たない、という意味です。 わかりにくいですが、3行目は{a1，a3，・・・}となるＡの部分集合を表してます。
空集合φはどこまでも0，0，0，・・・の並び、Ａはどこまでも1，1，1，・・・の並びになります。こういう表を用意して、行数が十分あればＡの全ての部分集合を表せますよね？。
行ヘッダのa1，a2，・・・は、Ａの要素aiと、1，0，1，0，・・・などで表されたＡの部分集合が、fで対応するという意味です。全単射は単射なので、i≠kではi行とk行の0，1並びは一致しません。まとめれば、f(ai)＝[1，0，1，0，・・・などで表されるＡの部分集合] 。
さてこの全単射fは全射でしょうか？。要するにa1，a2，・・・の行ヘッダ並びの行数で十分でしょうか？。もう気づいてますよね？(^^)。また対角線に沿って、あり得ないものを作るんですよ(^^;)。ちなみに(8)はExcelで書きました。
(9) 対角線cell(i，i)が0だったら1、1だったら0として作った0，1並びも、
Ａのある部分集合Ｂを表す。
(10) 何故なら行ヘッダa1，a2，・・・の個数はちょうどCard(Ａ)＝Card({a1，a2，・・・})だから。
(11) Ａの部分集合Ｂは、対角線に沿って必ず各行と0，1が違うから、Ｂは(8)に現れるどの部分集合
とも要素1個は必ず違う。
(12) よってＢは(8)に現れるどの部分集合とも一致しない（ai→による対応漏れが起きた！）。
(13) 対応漏れが起きたので、Card(Ａ)＜Card(P(Ａ))。
以上がカントールの定理の図解です（←どこが！？(^^;)）。
Ｂ⊂Ａに対応するb∈Ａ、すなわち全単射なfでf(b)＝Ｂとなるb∈Ａはないといま証明した訳ですが、全単射なfでbがあったとしたらどのような矛盾が惹き起こされるかを、具体的に調べてみましょう。
表(8)の対角成分(i，i)の0，1は、αiに対応するＡの部分集合f(αi)に、αiが属するか属さないかを決めています。
Ｂは(i，i)成分の0，1を反転して作ったＡの部分集合でした。かつfが全単射であるならば、表(8)を作る過程のどこかでＢにも出会っているはずです。ここで「b∈Ｂなのか？」、「b∈Ｂでないのか？」と問います。どちらかであるはずです。
「b∈Ｂ」とする。これは表(8)のf(b)＝Ｂを表す行kにおいて、b＝αkかつ(k，k)：1を意味する。しかしＢは、全ての(i，i)を反転して作ったものだから、同じ行k のk列目の(k，k)成分の値は0。よって「b∈Ｂでない」。
「b∈Ｂでない」とする。これは表(8)のf(b)＝Ｂを表す行kにおいて、b＝αkかつ(k，k)：0を意味する。しかしＢは、全ての(i，i)を反転して作ったものだから、同じ行k のk列目の(k，k)成分の値は1。よって「b∈Ｂ」。
矛盾しました。部分集合Ｂは全単射なf：Ａ→P(Ａ)の存在のもとで、「b∈Ｂ」としても「b∈Ｂでない」としても駄目だめな集合です。bとしてＡの要素のどれを当てても駄目です。さらにＢ＝f(b)です。だったら、
f：Ａ→P(Ａ)を全単射として、xがf(x)に属さないようなxで作ったＡの部分集合Ｂ：
にもたぶん、Ｂ＝f(b)を満たすb∈Ａはないだろうなと予想がつきます。
［カントールの定理の補題］
f：Ａ→P(Ａ)を全単射とする。
に対応するb、すなわちf(b)＝Ｂとなるb∈Ａは存在しない。
［証明］
b∈Ｂとする。b∈ＢならＢ＝f(b)だったから、(15)からb∈Ｂでない。
b∈Ｂでないとする。b∈ＢでないならＢ＝f(b)だったからbはf(b)に属さず、(15)からb∈Ｂ。
矛盾したのでbが存在しないか、fが全単射でないかのどちらか。fが全単射とすれば、bはない。
［証明終］
つまり、
という風に、循環参照が起きています。Ｂの内包的定義は、外延としてのＢに内包定義テストへの差し戻しを要求します。自己言及パラドックスです。これがラッセルのパラドックスの本質でした。一般に対角線論法と呼ばれるものには全て、ラッセルのパラドックスが隠れています。だから気持ち悪いんですよぉ～！(^^;)。
ラッセルのパラドックス http://nekodamashi-math.blog.so-net.ne.jp/2018-02-28-2
しかし今回はパラドックスにはなりません。「fが全単射ならばという制御された状況下で」これが起こった（これを起こした）からです。矛盾しても、fが全単射でないとわかった、もしくはbはなかったと言えるからです。いずれにしろf：Ａ→P(Ａ)は存在しないが結論です（カントールの定理）。
どっちかというと「これを起こした」ですよね？。
ラッセルのパラドックスは、無限集合論や数学基礎論の中で無限を見渡せない人間にとって、非常に強力な証明手段となる得る事がその後わかります。
常に取り扱い注意！ですが。無限世界に望外に存在した、有限論理の通用するひとすじの隘路を辿ってるような感じです。本格的な無限集合の証明を一回でも独力で扱ってみると感じます。無限集合論は、パラドックス地雷の地雷原です(^^;)。
ラッセルのパラドックスを常に間接的に含む対角線論法は、強力でした。それはゲーデルの不完全性定理やチューリングマシンの停止問題の証明で、主役を果たします（←と聞いただけ）。
次にP(Ａ)がＡよりどんだけ多いか体感してみますか（どんだけぇ～！ by Ikko(^^)）。
カントールの定理は、P(Ａ)がＡより少なくとも一個多いとしか言ってません。Card(Ａ)＋1＝Card(P(Ａ))でしょうか？。
そんなはずありません。最初の方で述べたように、無限集合では、ＡとＡの無限部分集合Ｃが同数になるのは普通です。つまりCard(Ａ)＋Card(Ｃ)＝Card(Ａ)くらいのキャパを、Card(Ａ)は持ってます。Ｆがいくら大きい有限集合でも当然、Card(Ａ)＋Card(Ｆ)＝Card(Ａ)です。
nを任意の自然数として、Card(Ａ)＝2･Card(Ａ)＝3･Card(Ａ)＝・・・＝n･Card(Ａ)＝Card(Ａ)＝Card(Ａ2)＝Card(Ａ3)＝・・・＝Card(Ａn)＝・・・、などを証明できます。ＡnはＡのn個の直積集合です。
Card(Ａ)より少なくとも一個多いCard(Ｓ)を持つ集合Ｓって、途轍もなくでかいんですよ！。実数と自然数との個数比較に戻ります。そこでは実数の集合Ｒと区間[0，1]は同数で、任意のx∈[0，1]は、
x＝0.γ1γ2γ3γ4・・・
(16)
と表せるのでした。γjは0～9の数字のどれかで10進展開を念頭においてます。・・・は自然数の集合Ｎの個数に等しい桁数です。Card(Ｎ)＝
で表します（アレフゼロと読んで(^^)）。は可算無限と呼ばれます。(16)の桁数は可算無限桁です。
(16)を有限桁で打ち切った姿を想像します。要するにある自然数mより先のγjは全て0です（ない）。(16)をm桁で打ち切った場合、(16)は何個の実数を表せるでしょう？。各γjは0～9のどれか（10個）なので、10m個ですよね？。
という記号を、集合の濃度として正確に定義する方法が、じつはあります。意味は10m個と同じです。なので
という事になります。ところがkが自然数（ある有限集合の濃度）の場合、
を証明できちゃうのです。特にk＝2の場合、
です。
すなわち、ネコ先生の記号であれば＝Card(2Ｎ)＝Card(P(Ｎ))は、Card(Ｒ)に等しいという結論になります。実数の個数は、自然数の集合の部分集合全体の数に等しい（現行集合論を信じれば(^^)）。
がどんだけでかいかは、有限の世界でも体感できます。nを自然数として、普通はn→∞と書くところをn→と書いても、ここまで来れば、そんなに問題じゃないですよね？（無限の理屈は、全て有限の理屈の外挿(^^;)）。
実数の無限個数に比べれば、自然数の無限個数なんてカスです。実数の個数に比べれば、自然数の個数なんて有限といっしょです。(16)は可算無限桁でしたが、Card(Ａ)桁の(16)は（のようなものは）想像できますよね？。いずれにしろ有限桁しか書けず後は・・・で誤魔化す人間は、Card(Ａ)桁の(16)も、(16)のようにしか書けません(^^;)。10Card(Ａ)＝2 Card(Ａ) は、この時も健在です。
次の式は絶対に「書いたらあかん」ですが、これと同じ意味と解釈できる定理は証明できるはずです。集合Ｓは有限集合から始める事にして・・・、
P(Ａ)の個数に比べたらＡの個数なんてカスです。有限といっしょです。
ところでいわゆる数の構成の経緯を考えてみると、離散量を表すものとして自然数Ｎは導入されました。有理数Ｑは、離散量の間を埋める形で連続量として導入されました。ところが√(2)が有理数でない事をピタゴラスは証明してしまった（年代を考えるとすごいよな）。有理数Ｑは連続じゃなかった。実数：Ｑの完備化はその1000年以上後でやっと完成します。
物理的現実には、離散量と連続量しかないように見える。じゃあ有理数は何なのか？。疑似連続量？。それは本質的に離散量なのか？。ある意味そうだと受け取れる結果もカントールは出しました。Card(Ｎ)＝Card(Ｑ)がそれです。では物理的現実には離散量と連続量しかないとすれば、Card(Ｎ)＜Card(Ｓ)＜Card(Ｒ)となる無限集合Ｓはないはずだ。自分はこういう風にカントールは推理したと憶測します。
［連続体仮説］
Card(Ｎ)＜Card(Ｓ)＜Card(Ｒ)となる無限集合Ｓはない。
2Card(Ａ)＝Card(P(Ａ))の関係は、2Card(Ｎ)＝Card(Ｒ)＝Card(P(Ｎ))の関係と本質的に同じでした。
［一般連続体仮説］
Card(Ａ)＜Card(Ｓ)＜Card(P(Ａ))となる無限集合Ｓはない。
この辺りはコーエンの仕事になり、連続体仮説は現行集合論の内部では証明できない事がわかってます。その仕事はゲーデルの不完全性定理の続きと考える事もできるので、ここにも対角線論法は関係してるのかな？。
・・・「思えば遠くへ来たもんだ（by 武田鉄矢）」。連続体仮説なんてはっきり言って数学の人外魔境です。あんまり関わらない方がいい。
・こうまでしてパラドックス地雷を避けながら無限集合論をやる必要なんかあるのでしょうか？。
だからときどき消極的事実を使うんですよ(^^;)。測度論で有理数の集合が測度零集合であるのを示すのにカントールの定理を使ってたようなそうでないような・・・。こういうのにもあんまり関わらない方が、無難な気が(^^;)・・・。
（執筆：ddt³さん）
（注１） 可付番集合ともいう。
というふうに集合の元（要素）のすべてに自然数の番号を付けられる、割り当てられる集合のこと。
有限集合と可算集合を高々可算の集合という。
（注２） cardinal number（基数）、集合の濃度（元の個数）の略語。集合Aの濃度を｜A｜と表記する場合もある。
（注３） 定理 ２つの集合A、Bに対し、次の２つは同値である。
（１） AからBへの単射がある
（２） BからAへの全射がある
ただし、（２）から（１）への証明には選択公理が必要。
fをAからBへの写像、すなわち、f:A→Bとする。
任意のa、a'∈Aに対して、a≠a'ならばf(a)≠f(a')が成り立つとき、fを単射という。
全てのb∈Bに対して、b=f(a)であるa∈Aが存在するとき、fを全射という。（高校数学では、「AからBへの上の写像」という）
fが全射でかつ単射であるとき全単射（高校数学では、１対１の対応）という。
「集合AからBへの単射（BからAへの全射）が存在するならば｜A｜≦｜B｜」と、集合の濃度の大小を定義する。
集合AからBへの全単射（１対１対応）が（ひとつでも）存在するならば、AとBは対等であるといい、記号A〜Bであらわす。このとき、AとBの濃度｜A｜と｜B｜は等しいと定義する。
｜A｜≦｜B｜かつ｜A｜≠｜B｜ならば、｜A｜＜｜B｜
そして、
｜A｜≦｜B｜かつ｜A｜≧｜B｜ならば、｜A｜＝｜B｜ （カントール・ベルンシュタインの定理）
Aを自然数全体の集合｛1, 2, 3, ・・・｝、Bを偶数全体の集合｛2, 4, 6, ・・・}とする。
このとき、f(1)=2, f(2)=4, f(3)=6, f(n)=2n, ・・・とすると、これはAからBへの全単射（１対１対応）となるので、
となる。この他に、整数全体の集合、有理数全体の集合、代数的数全体の集合の濃度などもであることが知られている。
なお、実数の濃度、無理数の濃度は
（連続体の濃度。非可算濃度のひとつ）とあらわし、
という関係がある。
非可算集合の濃度は、実数全体の集合Rの冪集合、そのまた冪集合、そのまた冪集合・・・の濃度という具合に、無数に作り出すことが可能。
（注：ネムネコ）
個数ってなんだろう？ 同数ってどういうこと？ [集合論入門]
個数ってなんだろう？ 同数ってどういうこと？
§１ 個数って何だ？ 同数ってどういうこと？
また、ネムネコが⑧以下なこと、あるいは、⑩以上なことを言い出したと思うかもしれないけれど、これからネムネコが数学の記事の内容と深い関係があるので、少し考えてみようじゃないか。
A=｛ネコ, イヌ、 サル｝、B=｛鰹節, ジャーキー, バナナ｝というものの集まり（集合）があるとする。
さてさて、
集合AとBの元（要素）の個数はどちらが多いでしょうか？
「AとBともに元の数は３だから等しい、同数だ。こんなことは見ればすぐにわかるだろう。」
もっともな答えだ。しかし、この解答は、我々が数という概念を有し、しかも、「ひとつ、ふたつ、みっつ、・・・」と数を表す言葉を持っているからできることだ。数を知らない小さな子どもが「ひとつ、ふたつ、みっつ」と集合AとBの元の個数を数え上げ、それから、「どちらもみっつだから、等しい」なんて芸当はできないだろう。だから、小さな子どもを納得させるためには、小さな子どもの目の前で、（ネコ、鰹節）、（イヌ、ジャーキー）、（サル、バナナ）と１対１に対応させ、AとBの元の数が同数であることを示すしかないに違いない。
現に我々は、小学校に入学してから、算数学習の小道具として、数を学ぶために「おはじき」を渡されたではないか。
原始的な、未開の――どちらも差別語になるかもしれない(>_<)――の部族の中には、両手の指で折れる１０までの数しかないところもあるらしい。ネムネコが中学生の頃に読んだ本には、「１、２、３、いっぱい」という風に、数は１、２、３の３種類しかないところがあると書かれていた。日本のように、とんでもなく大きい数にまで、数え方、単位がある国の方が異例中の異例だ。
https://ja.wikipedia.org/wiki/%E7%84%A1%E9%87%8F%E5%A4%A7%E6%95%B0
それでも、３まで知っていれば、A=｛ネコ, イヌ、 サル｝、B=｛鰹節, ジャーキー, バナナ｝の場合については、数え上げることで、この両者が同数であることを確認できる。しかし、AとBの元の個数が１０を越えていたら、小さな子どものように、集合AとBの元を１対１に対応させ、同数であることを確かめる以外に方策はないケロ。
このことを数学的に書けば、AからBへの写像fのなかに、
f(ネコ)=鰹節, f(イヌ)=ジャーキー, f(サル)=バナナ
と１対１の対応（全単射）の写像fが存在するってことになるのでしょう。そして、この１対１対応（全単射）が一つでも存在すれば、AとBは同数であるということになる。
しかし、この１対１の対応は３³=３×３×３=２７通りある１対１の写像の一つにしかすぎないのだ。
我々は、
f(ネコ)=バナナ, f(イヌ)=鰹節, f(サル)=ジャーキー
という組み合わせなどを考えることなく、先に示した
f(ネコ)=鰹節, f(イヌ)=ジャーキー, f(サル)=バナナ
などのたった一つのAからBへの１対１対応の写像の存在を根拠にAとBの元の個数が同数であると判断している。このことを、無証明に、アプリオリに、我々は何の疑いもなく受け入れているのだ。
それでも、A、Bの元の個数がともに３個ならば、１対１の写像の数は２７通りだから、この２７通りの写像をすべて列挙して確かめることができるだろう。
しかし、AとBの元の個数がともに１０個ずつならば、１対１の写像の数は１０¹⁰=１０億となり、１０個になったら、実質、確かめる術がない、お手上げになってしまう。
有限の場合ですら、「原理的に全てを調べられる」と「実際に全てを調べられる」とは違うってわけだにゃ。
でだ、
ここでAとBの他に自然数の集合K={1, 2, 3}が登場する。
集合Aの元の個数を「ひとつ、ふたつ、みっつ」と数え上げることは、たとえば、
g(ネコ）=1, g(イヌ)=2, g(サル)=3
と、Aの元とKの元を１対１に対応させ、AとKの元を、ともにもれなく、１対１の対応で結びつけることに他ならない。
次は、集合Bの元をすべて数え上げて、集合Bの元とKの元を、たとえば、
h(鰹節)=1, h(ジャーキー)=2、 h(バナナ)=3
といった具合にBとKの元をともに過不足なく１対１の対応で結びつけ、BとKが同数であることを確認する。
そして、Aの元の個数がKの元の個数と等しく、かつ、Bの元の個数とKの元の個数が等しいから、AとBの元の個数は等しいと判断する。
集合A、B、Cの元の個数をそれぞれ｜A｜、｜B｜、｜K｜とするとき、
と判断しているんだケロよ。
これに対して、AからBへの１対１対応の場合は、
であることを直接示している。
ネコと鰹節といった直接的な現物対応ですら胡散臭いところがあるというのに、ネコと１、鰹節と１、または、１と鰹節、といったモノと抽象的な数との対応、そして、それを取り持つものというわけのわからないものを使っているので、両者の数を数えて同数であると判断することの胡散臭さは、勢い、その２乗くらいになってしまう（笑）。
だから、我々、⑨の一族、眷属は、原始的な、プリミティヴで、より曖昧が少なく確実な、AとBを直接比較する手法を選択すべきに違いない(^^ゞ
さてさて、A、Bを３個という有限集合から無限集合へと拡張しよう。
そして、有限集合のときと同様に、
無限集合AからBへの１対１対応（全単射）が一つでも存在するならば、AとBの元の個数、｜A｜と｜B|が等しい、
としたら、どうなるのであろうか。
Aを自然数全体の集合、つまり、
とし、Bを偶数全体の集合、すなわち、
とする。
とすると、これはAからBへの１対１対応（全単射）になる。
AからBへの１対１対応の写像が一つあればAとBの元の個数は等しいとなるので、
となる。
同様に、奇数全体の集合｛1, 3, 5, ・・・｝をCとするとき、
とすると、これは自然数全体の集合Aから奇数全体の集合Cへの１対１の写像になっているので、
となる。
仮に、自然数全体の集合Aの元の個数を
（「あれふ・ぜろ」と読む）とした場合、
偶数全体の集合Bと奇数全体の集合Cとの共通部分は無い、つまり、B∩C=∅（集合BとCは互いに素）なので、
である。ここで、記号「＋」は直和（注）を表す。
A、B、Cが有限集合の場合、（１）が成立するとき、
となるので、これから類推すると、
といった（奇妙な）等式が得られる。
さらに、有限集合の場合、（１）のとき
が成立するので、無限集合の場合も同様と考えると、
とさらに奇妙なことが起きる(^^ゞ
つまり、無限集合を扱う場合、我々の常識はほとんど通用しないのであった。
（注）
互いに素な集合A、Bの和集合をAとBの直和といい、これを記号A+Bで表す。
つまり、A∩B=∅のとき、
たとえば、A=｛1, 2｝、B=｛3｝とすると、AとBの交わり（共通部分）はなく、A∩B=∅。このとき、
（注終）
このあたりの事情はは、∞の演算に似ている。
は演算規則として認めるけれど、
という算術は認めないからね〜。
地動説、ならびに、地動説を唱えて宗教裁判にかけられ、裁判後に「それでも地球は動いている」と呟いたとされるガリレオさんは、「自然数全体の集合、偶数全体の集合、そして、奇数全体の集合の元の個数は同数であるに違いない」と考えた。
しかし、
ガリレオさんの時代は、
偶数全体の集合は、自然数全体の集合Aの真部分集合であり、BはAの部分である。そして、部分は全体より必ず小さい。全体は部分よりも必ず大きい
とされており、天動説同様に、このことは絶対の真理とされていたので、
ガリレオさんは、ついぞ、「自然数全体の集合の元の数と偶数全体の集合の数は同じである」と言うことができなかった。
だって、これは地動説以上の危険思想だから。
無限に喩えられるキリスト教の神そのもの、その唯一絶対性、万能性を揺るがしかねない超〜危険思想だからね〜。
こんなことを人前で言ったら、ローマ教会は絶対に黙っちゃ〜いない。そして、ガリレオさんは火炙りを避けられなかったと思うよ。
無限集合、集合論の創始者とされるカントールは、「ガリレオは、大胆に、前進すべきであった」と言ったとか、言わなかったとか。
そりゃ〜、そう言うのは簡単だけれど、
そこから前進し、その研究成果を公表したら、間違いなく、異端審問でひどい拷問を受けたあと、その先には火炙りが待ち構えているんだから、前進はできないって。
ひそかに下克上を企んでいるネムネコですら、思わず、二の足を踏んでしまうにゃ。
こんなことで死ぬのは、ゴメンである。
§２ 秀吉サルさんと１対１対応のお話
あるとき、秀吉サルさんは、「この山に木は何本あるんだろう？」と疑問に思った。
そこで、賢い秀吉サルさんは、配下の動物たちに、「お前ら、できるだけ多くのヒモを持ってこい」と命じた。
秀吉サルさんは、結構、おっかないから、配下の動物は、「いったい、これで何を始めるつもりなのだろう」と疑問に思いつつも、ヒモをいっぱい集めてきたにゃ。
そして、山のように集まったヒモを見て、秀吉サルさんは、「お前ら、ヒモの数を数えろ」と命じた。そして、配下の動物たちがヒモの数を数え終えると、「そのヒモをあの山にある全ての木（の枝）に結んでこい。一本の木に一本のヒモだから、間違えるんじゃないぞ」と命じた。
配下の動物たちは、なにがなんだかわからないまま、秀吉サルさんに命じられるままに、そのヒモを山にあるすべての木に結んだ。そして、それを終えると、秀吉サルさんのもとに帰っていった。
秀吉サルさんは、配下の動物たちが全て戻ってくると、今度は余ったヒモの数を数えさせたにゃ。
そして、秀吉サルさんは、残ったヒモの数から山にある木の本数を知ることができたそうな。
めでたし、めでたし。
これを数学的に書くと、
Aを「山の木のあつまり」、Bを「集めたヒモのあつまり」、さらに、B₁をBの部分集合とし、fをAからBへの写像、すなわち、
とする。
秀吉サルさんは、
という１対１の対応fを利用し、山にある全ての木の本数を知ろうとしたんだケロ。
そして、これは、（無限）集合間の元（要素）の個数の大小関係をはかるために使われる、唯一と言ってよい、集合論の手法なんだにゃ。
秀吉サルさんは、１対１の対応、ならびに、１対１の対応を使った物の個数を知る方法を知っていて、賢いにゃ。
これも眉唾話しなのだけれど、
秀吉サルさんから褒美を下される際、何を希望するか尋ねられたソロリキツネは、今日は米1粒、翌日には倍の2粒、その翌日には更に倍の4粒と、日ごとに倍の量の米を100日間もらう事を希望した。米粒なら大した事はないと思った秀吉サルさんは簡単に承諾したが、日ごとに倍ずつ増やして行くと100日後には膨大な量になる事に途中で気づき、他の褒美に変えてもらった。
https://goo.gl/zcCBZ6
