2010 年改訂
集合入門
集合と写像の基礎概念
酒井 克郎
筑波大学・数学系
Basic Concepts of
Sets and Maps
c
2004
K. Sakai
集合と写像の基礎概念
はじめに
集合と写像の概念は , 現代数学の土台である. 何故なら , 集合の上に様々な数学
的構造を導入することにより, 数学の理論が展開さるからである. 「集合入門」 の
講義では , 集合と写像に関する基礎的な概念や性質などを学ぶ.
このノートは , 教科書というより学習帳として , 「集合入門」の講義で扱う事柄
をまとめたものである. 定理や補題などの証明はその方針や概略にとどめ, 簡単な
命題は演習としたので , 自分自身で詳細な証明を与え , このノートを完成させても
らいたい. 定理や補題などの証明の詳細は講義で行うが , まず自分自身で証明を試
みてもらいたい. 少なくとも証明しようとしている命題は何を主張しているのか ,
関係する概念はどのような定義であったか , どんな方針で証明を行うのか , など 予
め考えて講義に臨むなら , 講義で行う証明が複雑であっても, それについて行くこ
とが出来るであろう. 演習は必ず自分で証明を試みてもらいたい. ヒントがあるも
のでも, まずヒントを見ずに考えて, ど のように考えたらよいのか , 何をしたらよ
いか , 見当のつかない時に参照すべきである.
4 章までに , 集合と写像に関する基礎的事項を扱い, 集合や写像に関する命題を
どのように証明するかを学ぶ. 現代数学を学ぶ上で , 集合族と商集合の概念は不可
欠であるが , 2.3, 4.1, 4.2, 4.4 節ではをこれらの概念を扱う. 5 章では , 自然数から
始めて , 整数, 有理数, 実数, 複素数がどのように構成できるか示すが , この数の構
成を学ぶことにより, 商集合の扱いに慣れることが出来るであろう. 6 章以降は ,
集合論の初等的部分であり, 集合の濃度, 整列集合, 順序数などを扱う. 7 章で扱う
Zorn の補題や超限帰納法は , 数学の様々な分野で用いる重要な道具である.
このノートの内容は , 5 章を除き, 松坂和夫 著「集合・位相入門」(岩波書店) の
前半部分に対応しているので , この本を参照すれば , 証明の詳細が分かる. この本
以外にも, 同じ範囲を扱った多くの教科書が出版されている. 演習を行う場合や予
習, 復習を行う場合に , そうした本を活用できる. また, 証明を自分のノートにまと
める際には , 一楽重雄 監修「集合と位相 そのまま使える答えの書き方」(講談社サ
イエンティフィク) は参考になる. よく理解できないところは , 一人で悩まず躊躇
せずに先輩や教師などに相談すべきである.
2004 年 4 月
c
2004
K. Sakai
酒井 克郎
2004 年 12 月, 2005 年 12 月, 2010 年 6 月 改訂
i
目次
1
2
3
4
5
6
集合と条件 . . . . . . . . . . . . . . . . .
1.1
集合と要素 . . . . . . . . . . . . .
1.2
条件および “ならば ” とその否定 .
1.3
全称記号と存在記号 . . . . . . . .
集合の演算 . . . . . . . . . . . . . . . . .
2.1
和集合, 共通部分, 差集合, 補集合 .
2.2
直積集合 . . . . . . . . . . . . . . .
2.3
巾集合と集合族 . . . . . . . . . . .
写像 . . . . . . . . . . . . . . . . . . . . .
3.1
写像の概念 . . . . . . . . . . . . .
3.2
写像による像および逆像 (原像) . .
3.3
全射, 単射, 全単射 . . . . . . . . .
3.4
写像の合成 . . . . . . . . . . . . .
選出公理, 順序, 同値関係 . . . . . . . . . .
4.1
無限直積集合 . . . . . . . . . . . .
4.2
選出公理 . . . . . . . . . . . . . . .
4.3
順序 . . . . . . . . . . . . . . . . .
4.4
同値関係と商集合 . . . . . . . . . .
数の体系 . . . . . . . . . . . . . . . . . . .
5.1
代数的構造 . . . . . . . . . . . . .
5.2
自然数 — Peano の公理 . . . . . .
5.3
整数 . . . . . . . . . . . . . . . . .
5.4
有理数 . . . . . . . . . . . . . . . .
5.5
実数 — Cauchy 列 . . . . . . . . .
複素数 . . . . . . . . . . . . . . . .
5.6
5.7
Dedekind の切断による実数の構成
集合の濃度 . . . . . . . . . . . . . . . . .
6.1
集合の対等, 濃度 . . . . . . . . . .
6.2
濃度の大小関係 . . . . . . . . . . .
6.3
可算集合と非可算集合 . . . . . . .
6.4
濃度の演算 . . . . . . . . . . . . .
ii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
2
4
6
6
8
9
14
14
15
16
18
22
22
23
26
29
31
31
33
37
39
41
44
44
47
47
48
49
52
7
8
整列集合と Zorn の補題 . . .
7.1
順序同型 . . . . . . . .
7.2
整列集合 . . . . . . . .
7.3
Zorn の補題と整列定理
7.4
Zorn の補題の応用 . .
順序数 . . . . . . . . . . . . .
8.1
順序数の大小関係 . . .
8.2
順序数の演算 . . . . .
1 学期の講義予定
4 月 — 1, 2 章
5 月 — 3, 4 章
6月—5章
5.7 節は講義で扱わない
2 学期の講義予定
9月—6章
10 月 — 7 章
11 月 — 8 章
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
56
56
57
60
61
63
63
65
1
1.1
集合と条件
集合と要素
集合 (set) とは , “範囲のはっきりしているものの集まり” のことであり, “どん
なものをとっても, それがその集まりの中にあるかないかが判定できる” ようなも
のでなければならない. 一般に , 集合は英語のアルファベットの大文字 A, B, . . . ,
M, N, . . . , X, Y , . . . で表す. A という集合に入っている個々の “もの” を , A の
元 (または要素)(element) と呼ぶ. 一般に , 元は小文字 a, b, . . . , x, y, . . . で表す.
注意: 正確な議論を行うためには , 公理的な議論は避けられないが , ここでは
公理的議論は避け直観的な立場で扱う.
元 a, b, c, x, y から成る集合を {a, b, c, x, y} と表す. ここで , 元の順序を変えて
{y, x, a, c, b} と書いても, また同じ元を繰り返して {a, a, a, b, c, x, x, y} と書いても
同じ集合を表す. さらに , 同じものであっても異なる文字を用いて表す場合もある
ので , 注意が必要である. 例えば , a = b であれば {a, b, c} = {a, c} であり, 逆に
{a, b, c} = {a, c} であれば , a = b または b = c である. 元が a だけから成る集合
は {a} となる. このとき, a = {a} であることに注意せよ. 何も集めていなくても
集合と考え , 空集合 (empty set) と呼び , { } または ∅ と表す. すなわち, 空集合は
元を持たない集合である.
“a が集合 A の元である” ということをつぎのように表す:
a ∈ A (または , A a)
このとき, “a は A に属す”, “a は A に含まれる”, “A は a を含む” などとも言う.
上記の否定をつぎのように表す:
a ∈ A (または , A a)
２つの集合 A, B に対して , B の元がすべて A の元になっているとき, すなわち,
B が A の元以外の元を持たないとき, B は A の部分集合 (subset) であるといい,
つぎのように表す:
B ⊂ A (または , A ⊃ B)
このとき, “B は A に含まれる”, “A は B を含む” などとも言う. この否定をつぎ
のように表す:
B ⊂ A (または , A ⊃ B)
どんな集合 A に対しても, 空集合 ∅ は A の元以外の元を含まないので , ∅ ⊂ A と
なる. 同じ元から成っている集合は同じものであるので , A ⊂ B かつ B ⊂ A であ
るとき, A = B となる. また, a ∈ A と {a} ⊂ A は同じことを意味する. A ⊂ B
かつ A = B であるとき, A は B の真部分集合 (proper subset) であるといい, つ
ぎのように表す:
A B (または , B A)
1
無からの創生: 空集合 ∅ を集合であると認定すれば , 元が１つから成る集合
1 = {∅} が定義できる. ∅ = 1 であるから , 2 = {∅, 1} は２つの元からなる集
合である. (∅ = { } と表せば , 1 = {{ }}, 2 = {{ }, {{ }}}, . . . と括弧だら
け !) この様にして , 自然数 n に対応する集合 n が定義でき, これら n 全体を
考えることにより, N が得られる. この N から Z, Q, R, C を構成することが
できる. この構成法は後で学ぶが , まさに無 (空集合) からすべてが生まれる.
数学の各分野で頻繁に現れるいくつかの基本的な集合は , 固有の記号で表される.
• 自然数全体 — N
• 整数全体 — Z
• 有理数全体 — Q
• 実数全体 — R
• 複素数全体 — C
(natural numbers の頭文字)
(Zahlen [独語：数 (複数)] の頭文字, 英語では integers)
(quotient [商] の頭文字か (?), 英語では rational numbers)
(real numbers の頭文字)
(complex numbers の頭文字)
このとき, N Z Q R C.
1.2
条件および “ならば ” とその否定
条件 P の否定を ¬P と書く. 例えば , ¬(a ∈ A) は a ∈ A のことである. ２つの
条件 P , Q に対して , “P ならば Q である” ということをつぎのように書く:
P ⇒ Q (または , Q ⇐ P )
このとき, P は Q であるための十分条件 (sufficient condition), Q は P であるた
めの必要条件 (necessary condition) であるという. これは “P が成立するときに
は , 必ず Q も成立する” という意味であり, Q が成立しないなら P も成立してい
ないことになるので , P ⇒ Q と ¬Q ⇒ ¬P は同じことを意味し , 後者は前者の対
偶と呼ぶ. また, P ⇒ Q かつ Q ⇒ P のとき, P と Q は互いに同値 (equivalent) で
あるとか , P は Q であるための必要十分条件 (necessary and sufficient condition)
であるといい, つぎのように書く:1
P ⇔Q
P ⇒ Q は “P が成立するときには , 必ず Q も成立する” ということを意味す
るので , “P であっても Q でない” ということが , P ⇒ Q の否定となり, これを
日常会話において “P ならば Q である” というとき, 暗黙のうちに , “P でなければ Q でな
い” (裏) ということまで意味することが多いが , これは “Q ならば P である” (逆) の対偶なので,
P が Q であるための必要十分条件であると言っていることになる. 英語で ⇔ を正確に言い表す
には , “if and only if” と言えばよい. 数学用の造語で “iff” と書くこともある.
1
2
P ⇒ Q と書く. これは “P が成立しても, Q が成立しない” ということ, すなわ
ち “P と ¬Q が共に成立する” ということを意味する. さらに , P ⇔ Q の否定は
P ⇒ Q または Q ⇒ P のことであり, P ⇔ Q と書く. まとめると , つぎのように
なる:
• P ⇒ Q は “P と ¬Q が共に成立する” という意味である.
• P ⇔ Q は “[P かつ ¬Q] または [Q かつ ¬P ] が成立する” という意味である.
注意: P ⇒ Q は P ⇒ Q の否定なので , “P または ¬Q のど ちらかが成立しな
い” ということ , すなわち “P が成立しないか , Q が成立するかのど ちらかである”
ということになるが , このことは , “P が成立するときには , 必ず Q も成立する” と
いうとき, “P が成立しないときには , Q に関して (成立するかしないか ) 何も言及
していない” ということに注意すれば理解できることである.2
同じ陳述や式であっても, 一般には複数の対象が関係しているので , どの対象に
注目するかで見方が変わる. それで , 議論している条件が , どの対象に関する条件
なのか識別することは大切である. 例えば , “同じ 元から成っている集合は同じも
のである” ということを示すつぎの記述について考える:
A=B ⇔ x∈A⇔x∈B
右側の [ ] の中は , x に関する２つの条件が同値であることを示していて , 全体とし
て A と B に関する条件となり, それが左側の [ ] の中の A と B に関する条件と
同値になるということを示している. つぎの部分集合に関する記述も同様である:
A⊂B ⇔ x∈A⇒x∈B
集合 M の元 x に関する条件 P (x) に対し , P (x) を満たす x ∈ M 全体からなる
M の部分集合をつぎのように書く:
{x ∈ M | P (x)}
実数 a < b に対して , a, b を端点とする閉区間, 開区間, 右半開区間, 左半開区間は
それぞれつぎのように定義できる:
[a, b] = {x ∈ R | a x b}, (a, b) = {x ∈ R | a < x < b},
[a, b) = {x ∈ R | a x < b}, (a, b] = {x ∈ R | a < x b}.
さらに , a ∈ R に対して , つぎのような区間も定義できる:
[a, ∞) = {x ∈ R | x a}, (a, ∞) = {x ∈ R | x > a},
(−∞, a] = {x ∈ R | x a}, (−∞, a) = {x ∈ R | x < a}.
2
脚注 1 を参照.
3
集合 M の元 x に関する条件 P (x), Q(x) によって,
A = {x ∈ M | P (x)}, B = {x ∈ M | Q(x)}
と定義されているとき, つぎが成り立つ:
A ⊂ B ⇔ P (x) ⇒ Q(x)
Russell3 の逆理 (パラド クス): “すべての集合の集まり” を Ω とする. もし
Ω が集合ならば Ω ∈ Ω となる. 自分自身を元として含まない集合を第 I 種と
呼び , 第 I 種でない集合, すなわち自分自身を元として含む集合を第 II 種と
呼ぶことにする. このとき, 空集合 ∅ は第 I 種, Ω は第 II 種の集合というこ
とになる. 第 I 種の集合全体を A とすると , A は Ω の部分集合となり, 第 I
種であるか第 II 種である. A が第 I 種なら A の定義から A ∈ A となり, 第
II 種となってしまう. A が第 II 種なら A の定義から A ∈ A となり, 第 I 種
となってしまう. この様に , 単に “ものの集まりが集合である” という定義で
は , 矛盾が生じてしまう. そこで, 集合と認定できるものから始めて, ある確
かな操作で作れるもののみを集合として扱うならば , 問題が生じない.
1.3
全称記号と存在記号
集合 M の元 x に関する条件を P (x) とするとき, “すべての x ∈ M に対して ,
P (x) が成立する” あるいは “すべての x ∈ M は P (x) を満たす” ということをつ
ぎのように書く:4
∀x ∈ M, P (x)
また, “P (x) が成立するような x ∈ M が存在する” あるいは “P (x) を満たす
x ∈ M が存在する” ということをつぎのように書く:5
∃x ∈ M, P (x) (または , ∃x ∈ M such that P (x))
記号 ∀ を全称記号 (universal quantifier), ∃ を存在記号 (existential quantifier) と呼
ぶ. 否定に関しては , つぎのようになる:
• ∀x ∈ M, P (x) の否定は ∃x ∈ M, ¬P (x)
• ∃x ∈ M, P (x) の否定は ∀x ∈ M, ¬P (x)
明らかに , ∀x ∈ M, P (x) は x ∈ M ⇒ P (x) と同じ意味である.
3
バートランド ・ラッセル (Bertrand Arthur William Russell, 1892–1970)
For all x ∈ M , P (x).
5
There exists x ∈ M such that P (x).
4
4
集合 {1, 2, . . . , n} や実数の区間 (0, ∞), [a, b], . . . , などに対して全称記号や存在
記号が用いられる場合が多いが , つぎのように略記することが多い:
∀i = 1, . . . , n; ∃i = 1, . . . , n; ∀ε > 0; ∃δ > 0;
a ∀t b; a ∃s b.
全称記号 ∀ と存在記号 ∃ を含む陳述は , ∀ と ∃ の順序が違えば意味が意味が
まったく異なる. 例えば , A, B ⊂ N に関する次の 2 つ陳述を考えよ:
∀n ∈ A, ∃m ∈ B, n < m,
(1)
∃m ∈ B, ∀n ∈ A, n < m.
(2)
(1) における m はその前に書かれている n に依存しており, 別の n に対しては別
の m で条件を満たせばよいが , (2) における m はその後に書かれている n に依
存しておらず , どんな n に対しても同じ m で条件を満たさなければならない. (1)
は , A を偶数全体とし B を奇数全体としても成り立つので , A の元の数が無限個
であってもよいが , (2) では , A の元の数は有限個でなければならない.
微積分と線形代数の復習
以下の演習問題は微積分と線形代数で学んだ事柄の復習である.
演習 1.1 以下の定義とその否定を記号 (∀, ∃, ⇒ etc.) を用いて表せ.
(1) 実数列 (xn )∞
n=1 が x0 ∈ R に収束する. (limn→∞ xn = x0 )
(2) 実数列 (xn )∞
n=1 が ∞ に発散する. (limn→∞ xn = ∞)
(3) 実数列 (xn )∞
n=1 はコーシー列である.
(4) 部分集合 A ⊂ R は上に有界である.
(5) x0 ∈ R は A ⊂ R の上限である. (sup A = x0 )
(6) 関数 f : R → R が x0 ∈ R において連続である.
(7) 関数 f : R → R が一様連続である.
演習 1.2 以下の定義とその否定を記号 (∀, ∃, ⇒ etc.) を用いて表せ.
(1) x1 , . . . , xk ∈ Rn が一次独立である.
(2) x1 , . . . , xk ∈ Rn が Rn の基底である.
(3) 写像 f : Rn → Rm が線形写像である.
5
2
2.1
集合の演算
和集合, 共通部分, 差集合, 補集合
集合 A と B の元全体からなる集合を A ∪ B と表し , A と B の和集合 (union)
と呼ぶ. 和集合 A ∪ B は A と B を共に含む最小の集合といえる. すなわち,
A ⊂ A ∪ B, B ⊂ A ∪ B;
A ⊂ C, B ⊂ C ⇒ A ∪ B ⊂ C
(最小性)
最小性の証明 x ∈ A ∪ B とすると , x ∈ A または x ∈ B
x ∈ A のとき, A ⊂ C より x ∈ C ; x ∈ B のとき, B ⊂ C より x ∈ C
ど ちらにしても, x ∈ C ∴ A ∪ B ⊂ C
また , A と B に共通に含まれる元全体からなる集合を A ∩ B と表し , A と B の
共通部分 (intersection) と呼ぶ. 共通部分 A ∩ B は A と B に共に含まれる最大の
集合である. すなわち,
A ∩ B ⊂ A, A ∩ B ⊂ B;
C ⊂ A, C ⊂ B ⇒ C ⊂ A ∩ B
(最大性)
最大性の証明 x ∈ C とすると , C ⊂ A より x ∈ A, また C ⊂ B より x ∈ B
これは x ∈ A ∩ B を意味する ∴ C ⊂ A ∩ B
一般に , A ∩ B = ∅ のとき, A と B は交わる (meet, intersect) といい , A ∩ B = ∅
のとき, A と B は交わらない (miss, disjoint) あるいは互いに素であるという. な
お, 記号 ∪ はカップ (cup) と呼び , ∩ はキャップ (cap) と呼ぶ.
以下の基本的な性質が成り立つ:
(1) A ∪ A = A; A ∩ A = A (巾等律)
(2) A ∪ B = B ∪ A; A ∩ B = B ∩ A (交換律)
(3) (A ∪ B) ∪ C = A ∪ (B ∪ C); (A ∩ B) ∩ C = A ∩ (B ∩ C)
(4) (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C);
(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C) (分配律)
(5) (A ∪ B) ∩ A = A; (A ∩ B) ∪ A = A (吸収律)
(結合律)
上の (3) の和集合と共通部分は , それぞれ A ∪ B ∪ C, A ∩ B ∩ C と書いてもよい.
証明 (1)–(3) は定義より明らか .
(4) (前半の分配律) x ∈ (A ∪ B) ∩ C とすると , x ∈ C
さらに x ∈ A ∪ B より, x ∈ A または x ∈ B
x ∈ A のとき, x ∈ C より x ∈ A ∩ C; x ∈ B のとき, x ∈ C より x ∈ B ∩ C
∴ x ∈ (A ∩ C) ∪ (B ∩ C) ∴ (A ∪ B) ∩ C ⊂ (A ∩ C) ∪ (B ∩ C)
6
A ∩ C ⊂ A, B ∩ C ⊂ B より, (A ∩ C) ∪ (B ∩ C) ⊂ A ∪ B
A ∩ C ⊂ C, B ∩ C ⊂ C より, (A ∩ C) ∪ (B ∩ C) ⊂ C
∴ (A ∩ C) ∪ (B ∩ C) ⊂ (A ∪ B) ∩ C
∴ (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
(4) (後半の分配律) x ∈ (A ∪ C) ∩ (B ∪ C) とすると , x ∈ A ∪ C かつ x ∈ B ∪ C
x ∈ C のとき, x ∈ A かつ x ∈ B より x ∈ A ∩ B
すなわち, x ∈ A ∩ B または x ∈ C となるので , x ∈ (A ∩ B) ∪ C
∴ (A ∪ C) ∩ (B ∪ C) ⊂ (A ∩ B) ∪ C
A ⊂ A ∪ C, B ⊂ B ∪ C より, A ∩ B ⊂ (A ∪ C) ∩ (B ∪ C)
C ⊂ A ∪ C, C ⊂ B ∪ C より, C ⊂ (A ∪ C) ∩ (B ∪ C)
∴ (A ∩ B) ∪ C ⊂ (A ∪ C) ∩ (B ∪ C)
∴ (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
(5) 分配律, 巾等律, 交換律により, (A ∪ B) ∩ A = A ∪ (B ∩ A) = (A ∩ B) ∪ A
A ⊂ A ∪ B より, A ⊂ (A ∪ B) ∩ A; A ∩ B ⊂ A より, (A ∩ B) ∪ A ⊂ A
∴ (A ∪ B) ∩ A = (A ∩ B) ∪ A = A
集合 A と B の差集合 (difference) A \ B は , つぎのように定義する:6
A \ B = {x ∈ A | x ∈ B}
def
特に , B ⊂ A の場合, A \ B は B の A における補集合 (complement) と呼ぶ.
演習 2.1 以下を証明せよ:
(1) A \ B = A ⇔ A ∩ B = ∅
(2) A \ B = ∅ ⇔ A ⊂ B
(3) (A \ B) \ C = A \ (B ∪ C)
(4) A \ (B \ C) = (A \ B) ∪ (A ∩ C)
集合 X の部分集合のみを対象とする場合, X を普遍集合 (universal set) と呼ぶ.
この場合には , A (⊂ X) の X における補集合を単に A の補集合といい, Ac と表
す. このとき, A, B ⊂ X に対して , A \ B = A ∩ B c となる. つぎの De Morgan7
の法則 (De Morgan’s laws) が成り立つ:
(A ∪ B)c = Ac ∩ B c ;
(A ∩ B)c = Ac ∪ B c
一般に n 個の集合 A1 , A2 , . . . , An の和集合と共通部分は , つぎのように帰納的
に定義できる:
A1 ∪ A2 ∪ · · · ∪ An = (A1 ∪ · · · ∪ An−1 ) ∪ An ;
A1 ∩ A2 ∩ · · · ∩ An = (A1 ∩ · · · ∩ An−1 ) ∩ An .
n
n
これらの和集合と共通部分に対して , i=1 Ai および i=1 Ai という表記も用いる.
差集合を A − B と表す文献もあるが , 代数的な演算と同時に使用する場合には, 混乱を避ける
ためには , A \ B と表した方がよい.
7
ド ・モルガン (Augustus De Morgan, 1806–71)
6
7
演習 2.2 A1 , . . . , An , B ⊂ X に対して , 以下を証明せよ:
n
Ai ∩ B = ni=1 (Ai ∩ B)
(1)
i=1
n
(2)
Ai ∪ B = ni=1 (Ai ∪ B)
i=1
n
c n
(3)
A
=
Aci
i
i=1
c i=1
n
n
(4)
A = i=1 Aci
n i=1 i
(5) i=1 Ai = (A1 \ A2 ) ∪ · · · ∪ (An−1 \ An ) ∪ (An \ A1 ) ∪ ni=1 Ai
2.2
直積集合
順序対 (ordered pair) とは 2 つのものの順序付けられた組 (a, b) のことであり,
2 つの順序対 (a, b), (a , b ) が等しいとは , つぎのように定義される:
(a, b) = (a , b ) ⇔ a = a , b = b
def
したがって , (a, b) = (b, a) ⇔ a = b となる. 順序対 (a, b) に対して , a をその第
1 座標 (first coordinate) または第 1 成分 (first factor) といい , b をその第 2 座標
(second coordinate) または第 2 成分 (second factor) という.
集合による順序対の定義: 集合の言葉だけを用いて , (a, b) = {{a}, {a, b}} と
順序対を定義できる. 実際, 以下が成立する.
{{a}, {a, b}} = {{a }, {a , b }} ⇔ a = a , b = b
証明 ⇐ は明らかなので , ⇒ を示せばよい
a = a とすると , {a} = {a } より {a} = {a , b }
このとき, a = b = a となり, 矛盾 ∴ a = a
a = b のとき, {a , b } = {a} となり a = b = a ∴ b = b
a = b のとき, {a, b} = {a , b } となり a = a より b =
a ∴ b = b 集合 A の元を第 1 座標, 集合 B の元を第 2 座標とする順序対全体からなる集
合を A × B と表し , A と B の直積 (direct product) と呼ぶ . 直積 A × B の元は
(a, b) という形をしていて , a ∈ A, b ∈ B となっている. 集合 A, B のど ちらか一
方が空集合のとき, それらの直積も空集合である. すなわち, A × ∅ = ∅ × B = ∅.
空でない集合 A, B に対しては , 一般に A × B = B × A であり, A × B = B × A
となるのは A = B に限る.
実際, A = ∅ より ∃a ∈ A, B = ∅ より ∃b ∈ B
∀x ∈ A, (x, b) ∈ A × B = B × A ∴ x ∈ B
∀x ∈ B, (a, x) ∈ A × B = B × A ∴ x ∈ A
これより, A = B を得る
集合 A と A 自身の直積 A × A を A2 と書く. 特に , R2 は座標平面を表す.
注意: 直積集合を表す記号 A × B とその元 (a, b) を表す記号が異なるので , 混
同しないように注意せよ.
8
有限集合の場合, A の元の数が m 個, B の元の数が n 個であれば , A × B の元
の数は mn 個である. 特に , 1 つの元からなる集合の場合には , {a} × {b} = {(a, b)}
となる.
演習 2.3 以下の基本的な性質を証明せよ:
(1) A × (B ∪ C) = (A × B) ∪ (A × C)
(2) A × (B ∩ C) = (A × B) ∩ (A × C)
(3) A × (B \ C) = (A × B) \ (A × C)
(4) (A × B) ∩ (A × B ) = (A ∩ A ) × (B ∩ B )
(5) (A × B) \ (A × B ) = ((A \ A ) × B) ∪ (A × (B \ B ))
(6) (A × B) ∪ (A × B ) = (A ∪ A ) × (B ∪ B )
\ (A \ A ) × (B \ B) ∪ (A \ A) × (B \ B )
同様に , n 個のものの順序付けられた組 (a1 , a2 , . . . , an ) を考える. 順序付けられ
た組 (a1 , a2 , . . . , an ), (a1 , a2 , . . . , an ) が等しいとは , つぎのように定義される:
(a1 , a2 , . . . , an ) = (a1 , a2 , . . . , an ) ⇔ a1 = a1 , a2 = a2 , . . . , an = an
def
順序付けられた組 (a1 , a2 , . . . , an ) に対して , ai をその第 i 座標 (i-th coordinate)
または第 i 成分 (i-th factor) という.
n 個の集合 A1 , A2 , . . . , An の直積 は , Ai の元を第 i 座標とする順序付けられた
組 (a1 , a2 , . . . , an ) 全体からなる集合であり, つぎのように表される:
A1 × A2 × · · · × An または
n
Ai
i=1
各 Ai が同じ集合 A の時には , An と書く. このとき, A の元の数が m 個であれば ,
An の元の数は mn 個である.
注意: 厳密にいえば , (A × B) × C, A × (B × C), A × B × C は互いに異なる. 実
際, (a, b, c) は 3 つのものの組であるが , ((a, b), c) と (a, (b, c)) は 2 つのものの組
であり, (a, b) = a かつ c = (b, c) である. しかし , これらは括弧 ( ) のつけ方の違
いを無視して同一視することが多い.
演習 2.4 以下を証明せよ:
(1) ni=1 Ai ∩ ni=1 Bi = ni=1 (Ai ∩ Bi )
(2) ni=1 Xi \ ni=1 Ai = (xi )ni=1 ∈ ni=1 Xi ∃i = 1, . . . , n, xi ∈ Ai
2.3
巾集合と集合族
集合を元とする集合, すなわち “集合の集合” を集合族 (family of sets) という.
集合族をアルファベットの大文字スクリプト体 A, B, C, . . . , M, N , . . . , X , Y, . . . や
9
ド イツ大文字 A, B, C, . . . , M, N, . . . , X, Y, . . . で表すなら , その元である集合と
区別ができ, 混乱を避けられる. 集合 X のすべての部分集合から成る集合を X の
巾集合 (power set) と呼び , P(X) と表す. 常に , ∅ と X は P(X) の元である. 空
集合 ∅ の巾空間 P(∅) はただ 1 個の元 ∅ のみからなる集合, すなわち P(∅) = {∅}
となり, P(∅) = ∅ であることに注意せよ.
• 元の数が n 個の集合 X の巾集合 P(X) の元の数は 2n である.
X = {a, b, c} の場合に , 巾集合 P(X) の元を列挙して, 元の数が 8 個
(= 23 個) あることを確認せよ. 8
演習 2.5 巾集合に関して , 以下の証明を与えよ:
(1) P(X) ⊂ P(Y ) ⇔ X ⊂ Y
(2) P(X ∩ Y ) = P(X) ∩ P(Y )
(3) P(X ∪ Y ) ⊃ P(X) ∪ P(Y )
(4) P(X ∪ Y ) = P(X) ∪ P(Y ) ⇔ X ⊂ Y または Y ⊂ X
(5) P(X \ Y ) ⊃ P(X) \ P(Y ) ⇔ X ∩ Y = ∅ または X ⊂ Y
(6) P(X \ Y ) ⊂ P(X) \ P(Y ) は常に成立しない
(7) P(X × Y ) ⊃ {A × B | A ∈ P(X), B ∈ P(Y )}
X と Y が共に 2 つ以上の元を持てば , = は成立しない.
ヒント (4) の ⇒ は , 巾集合の元として X ∪ Y を考えよ. (5) の ⇒ を示すには , 一
方の条件を否定すれば , 他方の条件が成立することを示すか , あるいは背理法による.
(6) は ∅ を考えよ.
集合族 A が集合族 M に含まれるとき, A を M の部分集合族 (subfamily of sets)
と呼ぶ. また, P(X) の部分集合族を X の部分集合族 (family of subsets) と呼ぶ.
日本語では , ど ちらも “部分集合族” であるが , 前者は部分族, 後者は部分集合の族
の意味であり, 文脈に注意すれば混乱しない.
集合族 A に対して , A に属する集合の元全体からなる集合を A または A∈ A
と表し , A の和集合と呼ぶ. このとき,
x∈
A ⇔ ∃A ∈ A, x ∈ A
A は A に属するすべての集合を共に含む最小の集合といえる. すなわち,
∀A ∈ A, A ⊂ A,
(∀A ∈ A, A ⊂ C) ⇒
A⊂C
最小性の証明 x ∈ A とすると , ∃A
∈ A, x ∈ A
このとき, A ⊂ C より x ∈ C ∴ A ⊂ C
8
X や ∅ を忘れないこと.
10
(最小性)
また , A に属する集合すべてに共通に含まれる元全体からなる集合を
は A∈ A と表し , A の共通部分と呼ぶ. このとき,
x∈
A また
A ⇔ ∀A ∈ A, x ∈ A
A は A に属するすべての集合に共に含まれる最大の集合といえる. すなわち,
∀A ∈ A, A ⊂ A,
(∀A ∈ A, C ⊂ A) ⇒ C ⊂ A (最大性)
最大性の証明 x ∈ C とすると
, ∀A ∈ A, C ⊂ A より x ∈ A
従って, x ∈ A ∴ C ⊂ A
空集合族の場合: 空集合 ∅ は要素となる集合を 1 つも持たない集合族と考
えられる. すなわち, ∅ は空集合族 (the empty family of sets) とも呼べる
が , ∅ と ∅ はつぎのように見なせる: どんな集合も ∅ には属さないので,
条件 “∃A ∈ ∅, x ∈ A” はどんな x に対しても成立しない. すなわち, 条件
“∃A ∈ ∅, x ∈ A” を満たす x は存在しないので, ∅ = ∅ となる. また, 条件
“∀A ∈ ∅, x ∈ A” は “A ∈ ∅ ⇒ x ∈ A” を意味するので
, どんな x に対して
も成立する. 普遍集合を X として考えている場合には , ∅ = X となる.
集合族 A が集合 Λ の元を添字として用いて, A = {Aλ | λ ∈ Λ} と表されてい
る場合には , A = λ∈Λ Aλ , A = λ∈Λ Aλ と書く. このとき,
x∈
Aλ ⇔ ∃λ ∈ Λ, x ∈ Aλ
λ∈Λ
x∈
Aλ ⇔ ∀λ ∈ Λ, x ∈ Aλ
λ∈Λ
添字の集合が N の場合には , 次のように書くことも多い:
Ai =
a∈A {a},
A=
Ai ,
i=1
i∈
なお, A =
∞
i∈
Ai =
∞
Ai
i=1
P(A) となっていることに注意せよ.
演習 2.6 つぎを示せ:
− n−1 , 1 + n−1 =
− n−1 , 1 + n−1 = [0, 1]
(1)
n∈
n∈
−n
−n
−n
2 ,1− 2
=
2 , 1 − 2−n = (0, 1)
(2)
n∈
n∈
n
[(−1) m, ∞) = [0, ∞)
(3)
(4)
m∈
n∈
[(−1)n m, ∞) = ∅
n∈ m∈
11
演習 2.7 空でない集合族の和集合と共通部分に関して , つぎを証明せよ:
(1)
A ∪
B = (A ∪ B)
(2) A ∩ B
= (A
∪ B) (注意: 右辺は A ∩ B ではない)
(3)
Aλ ∪
Bγ =
(Aλ ∪ Bγ )
(4)
(5)
λ∈Λ
λ∈Λ
(6)
(7)
(8)
Aλ
Aλ
λ∈Λ
λ∈Λ
∩
Aλ
λ∈Λ
∩
∪
Aλ
×
Aλ
×
λ∈Λ
(9) X \
γ∈Γ
γ∈Γ
Aλ
λ∈Λ
Bγ
=
Bγ
γ∈Γ
=
=
(Aλ ∩ Bγ )
(Aλ ∪ Bγ )
(Aλ × Bγ )
(λ,γ)∈Λ×Γ
=
γ∈Γ
(λ,γ)∈Λ×Γ
Bγ
(Aλ ∩ Bγ )
(λ,γ)∈Λ×Γ
=
Bγ
(λ,γ)∈Λ×Γ
=
Bγ
(λ,γ)∈Λ×Γ
γ∈Γ
γ∈Γ
(Aλ × Bγ )
(λ,γ)∈Λ×Γ
(X \ Aλ ) ; X \
λ∈Λ
λ∈Λ
Aλ
=
(X \ Aλ )
λ∈Λ
注意: (6) において , x が右辺の元となる条件は “∀(λ, γ) ∈ Λ × Γ, x ∈ Aλ or
x ∈ Bγ ” であり, (λ, γ) ∈ Λ × Γ を取るたびに , “x ∈ Aλ ” または “x ∈ Bγ ” の
ど ちらかが成立することを意味する. このことと “∀λ ∈ Λ, x ∈ Aλ ” または
“∀γ ∈ Γ, x ∈ Bγ ” が成立することが同値になることは , 自明とは言えない.
ヒント (6) において, λ∈Λ Aλ と γ∈Γ Bγ が共に右辺に含まれることは容易い. 右
辺が左辺に含まれることは , 右辺の元 x が左辺の一方に入らないとき, 他方に入るこ
とを示す.
演習 2.8 ai < bj ∈ R (i, j ∈ N) に対して,
inf an = a− , sup an = a+ , inf bn = b− , sup bn = b+
n∈
n∈
n∈
n∈
とするとき, 以下を証明し , 一般に = が成立しないものには , その反例を与えよ:
(1) n∈ (an , bn ) = (a− , b+ )
(2) n∈ [an , bn ] ⊂ [a− , b+ ] (一般に = は成立しない)
(3) n∈ (an , bn ) ⊃ (a+ , b− ) (一般に = は成立しない)
(4) n∈ [an , bn ] = [a+ , b− ]
ヒント (2) と (3) において = の成立しない例は, b+ , b− がどの bn にも等しくない
場合と a− , a+ がどの an にも等しくない場合を考えよ.
12
[発展事項]
集合列の上極限と下極限: 集合の列 A1 , A2 , . . . の上極限 (limit superior) と呼ばれる集合
lim sup An および下極限 (limit inferior) と呼ばれる集合 lim inf An を , つぎのように定義
する:
∞
∞
∞
∞
Ai , lim inf An =
Ai
lim sup An =
n=1
n=1
i=n
i=n
このとき, つぎが成立する:
x ∈ lim sup An ⇔ ∀n ∈ N, ∃i n such that x ∈ Ai
⇔ 無限個の i ∈ N に対して , x ∈ Ai ;
x ∈ lim inf An ⇔ ∃n ∈ N such that ∀i n, x ∈ Ai
⇔ 有限個の i ∈ N を除いて , x ∈ Ai
例えば , つぎのように A1 , A2 , · · · ⊂ R を定義する:
− 1 − n−1 , 1 − n−1
An = − 1 + n−1 , 1 + n−1
if n is odd,
if n is even.
このとき, lim sup An = [−1, 1], lim inf An = (−1, 1) となる.
−2
0
− 43 6
−5
−1
3
2
3
4
1
発展問題 集合の列 A1 , A2 , . . . の上極限と下極限に関して , 以下の証明を与え, 一般に
= が成立しないものには , その反例を与えよ:
(1) lim sup An ∪ lim sup Bn = lim sup(An ∪ Bn )
(2) lim sup An ∩ lim sup Bn ⊃ lim sup(An ∩ Bn ) (一般に = は成立しない)
(3) lim inf An ∪ lim inf Bn ⊂ lim inf(An ∪ Bn ) (一般に = は成立しない)
(4) lim inf An ∩ lim inf Bn = lim inf(An ∩ Bn )
(5) A1 ⊂ A2 ⊂ · · · または A1 ⊃ A2 ⊃ · · · であれば , lim sup An = lim inf An .
13
写像
3
3.1
写像の概念
集合 X から集合 Y への写像 (map) (または 関数 (function)) とは , 各 x ∈ X に
対して, ある y ∈ Y をただ 1 通りに定める定め方のことである. 一般に , 写像は
f, g, h, . . . や ϕ, ψ, . . . , などの文字を用い, f が X から Y への写像であることを
f : X → Y と表す. また , つぎのように書くこともある:
f
X
/
Y
あるいは
X
f
/
Y
このとき , X を f の定義域 (domain) または始集合 (initial set), Y を終集合 (terminal set) という. 写像 f : X → Y によって , 各 x ∈ X に対してただ 1 通りに定
まる y ∈ Y を f (x) と書き, x の値 (value) または像 (image) と呼ぶ. また, f は x
を f (x) に写すあるいは対応させるといい, このことを x → f (x) と表す. つぎの
X × Y の部分集合 Gr(f ) を f のグラフ (graph) という:
Gr(f ) = {(x, f (x)) | x ∈ X}
写像 f : X → Y , g : U → V に対して , f = g をつぎのように定義する:
f = g ⇔ X = U, ∀x ∈ X, f (x) = g(x)
def
このとき, つぎが成り立つ:
f = g ⇔ Gr(f ) = Gr(g)
• X × Y の部分集合 Γ がある写像 f : X → Y のグラフとなるための必要十
分条件は , 各 x ∈ X に対して , {x} × Y ∩ Γ がただ 1 つの元をもつ集合とな
ることである. すなわち,
∀x ∈ X, ∃1 y ∈ Y such that (x, y) ∈ Γ.
集合による写像の定義: 集合の言葉だけを用いるなら , 写像をそのグラフと同
一視して , 上の Γ のような X × Y の部分集合が写像であると定義できる.
集合 X の各元にそれ自身を対応させる X から X 自身への写像を X の恒等写
像 (identity) といい, idX と表す. すなわち,
∀x ∈ X, idX (x) = x
恒等写像 idX のグラフは X の対角線集合 (diagonal) と呼ばれる以下の集合である:
ΔX = {(x, x) | x ∈ X}
14
集合 Y の元 y0 が 1 つ与えられ , X の任意の元 x を y0 に写す写像を (値 y0 の) 定
値写像 (constant map) という. 値 y0 の定値写像のグラフは X × {y0 } となる.
写像 f : X → Y の定義域を X の部分集合 A に換えた写像を f の A への制限
(restriction) といい, f |A と表す. このとき, Gr(f |A) = Gr(f ) ∩ (A × Y ) となる.
集合 X の恒等写像 idX の A ⊂ X への制限を A の X への包含写像 (inclusion
map) という. 包含写像 i : A → X と恒等写像 idA の違いは , 終集合 X であるか
A であるかの違いだけである.
直積集合 X × Y から X, Y への射影 (projection) prX : X × Y → X, prY :
X × Y → Y を , つぎのように定義する:
∀(x, y) ∈ X × Y, prX (x, y) = x, prY (x, y) = y
それぞれ第 1, 2 座標 (第 1, 2 成分) への射影とも呼び , pr1 , pr2 とも表す.
代数的演算: 代数的な演算も写像とみなせる. 例えば , R 上の加法と乗法は ,
それぞれ (x, y) → x + y, (x, y) → x·y という R2 (= R × R) から R への写
像である.
集合 X から Y への写像全体の成す集合を F(X, Y ) または Y X と表す. X と Y
がそれぞれ m 個, n 個の元からなれば , X から Y への写像は全部で nm 個, すな
わち F(X, Y ) = Y X の元の個数は nm 個である.
定義域や終集合が空集合の場合: X = ∅ や Y = ∅ の場合には , 写像をグラフ
と同一視することにより, つぎのように考えることができる.
(1) X = ∅ のときは , ∅ × Y の部分集合は ∅ のみであるが , X は元を 1 つも
含まないので x ∈ X に関するどんな条件も満たされるので , ∅ × Y の部
分集合である ∅ は写像とみなせる.
(2) X = ∅ かつ Y = ∅ のときは , X × ∅ の部分集合は ∅ のみで , X は少なく
とも 1 つの元 x を含むが , この x ∈ X に対して , ({x} × Y ) ∩ ∅ = ∅ と
なるので , X × ∅ の部分集合である ∅ は写像とはみなせない.
すなわち, Y ∅ = {∅} であり Y ∅ の元の個数は 1 個 (n0 = 1) となるが , X = ∅
であれば ∅X = ∅ であり ∅X の元の個数は 0 個 (m = 0 ⇒ 0m = 0) となる.
3.2
写像による像および逆像 (原像)
集合 X から Y への写像を f : X → Y とする. X の部分集合 A に対して , f に
よる A の元の値全体から成る Y の部分集合を f による A の像 (image) といい,
f (A) と表す. すなわち,
f (A) = {f (x) | x ∈ A}
y ∈ f (A) ⇔ ∃x ∈ A such that y = f (x)
特に , f (X) を f の像 (image) または値域 (range) という. Y の部分集合 B に対
して , f によって B の元に写される X の元全体からなる X の部分集合を f によ
15
る B の逆像 (inverse image) または原像 (preimage) といい, f −1 (B) と表す. すな
わち,
f −1 (B) = {x ∈ X | f (x) ∈ B}
x ∈ f −1 (B) ⇔ f (x) ∈ B
常に , f −1 (Y ) = X である. 各 y ∈ Y に対して , f −1 (y) = f −1 ({y}) と定義する. 各
x ∈ X に対しては , f (x) は Y の元であるが , f −1 (y) は X の部分集合であること
に注意せよ. また , y ∈ f (X) であれば f −1 (y) = ∅ であることにも注意せよ.
y ∈ f (X) ⇔ f −1 (y) = ∅
射影 prX : X × Y → X, prY : X × Y → Y による A ⊂ X と B ⊂ Y の逆像は ,
−1
それぞれ pr−1
X (A) = A × Y および prY (B) = X × B となる.
演習 3.1 写像 f : X → Y による像と逆像に関して, A, B ⊂ X, C, D ⊂ Y およ
び X の部分集合族 {Aλ | λ ∈ Λ} と Y の部分集合族 {Cγ | γ ∈ Γ} に対して , 以下
の証明を与え , 一般に = が成立しないものには , その反例を与えよ:
(1) A ⊂ f −1 (f (A)) (一般に = は成立しない)
(2) f (f −1 (C)) ⊂ C (一般に = は成立しない)
(3) f (A ∪ B) = f (A) ∪ f (B)
(4) f (A ∩ B) ⊂ f (A) ∩ f (B) (一般に = は成立しない)
(5) f (A \ B) ⊃ f (A) \ f (B) (一般に = は成立しない)
(6) 一般に , f (X \ A) と Y \ f (A) の包含関係はど ちらも成立しない
(7) f −1 (C ∪ D) = f −1 (C) ∪ f −1 (D)
(8) f −1 (C ∩ D) = f −1 (C) ∩ f −1 (D)
(9) f −1 (C \ D) = f −1 (C) \ f −1 (D)
(10) f −1 (Y \ C) = X \ f −1 (C)
(11) f ( λ∈Λ Aλ ) = λ∈Λ f (Aλ )
(12) f ( λ∈Λ Aλ ) ⊂ λ∈Λ f (Aλ ) (一般に = は成立しない)
(13) f −1 ( γ∈Γ Cγ ) = γ∈Γ f −1 (Cγ )
(14) f −1 ( γ∈Γ Cγ ) = γ∈Γ f −1 (Cγ )
なお, (4) に対する = が成立しない例は (12) に対する例でもある.
3.3
全射, 単射, 全単射
写像 f : X → Y は , f (X) = Y となるとき, 全射 (surjection) (または , 上への写
像 (onto map)) であるという. つぎの条件は f (X) = Y と同値である:
∀y ∈ Y, ∃x ∈ X such that f (x) = y
16
どんな写像も終集合をその写像の像に限れば全射となるので , 全射であるかど う
かは , 写像の終集合が何であるかによって異なる. また, つぎの条件を満たすとき,
f : X → Y は単射 (injection) (または , 1 対 1 の写像 (one-to-one map)) であると
いう:
∀x, x ∈ X, x = x ⇒ f (x) = f (x )
対偶をとれば , この条件はつぎと同値である:
∀x, x ∈ X, f (x) = f (x ) ⇒ x = x
写像 f : X → Y が全射でないことは , つぎのように表せる:
∃y ∈ Y such that ∀x ∈ X, f (x) = y
一方, f が単射でないことは , つぎのように表せる:
∃x, x ∈ X such that x = x , f (x) = f (x )
全射かつ単射である写像を全単射 (bijection) という. 全単射 f : X → Y に関し
ては , 各 y ∈ Y に対して , f (x) = y となる x ∈ X が一意的に決まるので , 各 y ∈ Y
に対して , こうして決まる x ∈ X を対応させることにより, Y から X への写像が
定まる. この写像を f の逆写像 (inverse map) といい, f −1 : Y → X と表す. この
とき, 逆写像 f −1 も全単射であり, (f −1 )−1 = f となる. 全単射 f の逆写像 f −1 の
グラフ Gr(f −1 ) は , f のグラフ Gr(f ) の第 1, 第 2 座標を入れ替えたものとなる.
Gr(f −1 ) = (y, x) (x, y) ∈ Gr(f ) .
注意: 全単射 f に対しては , f よる y ∈ Y の逆像と逆写像 f −1 による y ∈ Y の
値は同じ記号 f −1 (y) で表される. 前者であれば , 1 つの元からなる X の部分集合
であり, 後者であれば , X の元である. 文脈でど ちらか判断する. しかし , B ⊂ Y
に対して, f −1 (B) は写像 f による逆像とみても, 逆写像 f −1 による像とみても同
じである.
演習 3.2 演習 3.1 (1), (2), (4), (5) に関連して , つぎを証明せよ:
(1) f
(2) f
(3) f
(4) f
が単射
が全射
が単射
が単射
⇔
⇔
⇔
⇔
∀A ⊂ X, f −1 (f (A)) = A (⊃ は無条件で成立)
∀C ⊂ Y, f (f −1(C)) = C (⊂ は無条件で成立)
∀A, B ⊂ X, f (A ∩ B) = f (A) ∩ f (B) (⊂ は無条件で成立)
∀A, B ⊂ X, f (A \ B) = f (A) \ f (B) (⊃ は無条件で成立)
ヒント ⇐ を示すのに , つぎの場合に右側の条件をあてはめよ:
(1) x = x ∈ X に対して, A = {x}.
(2) y ∈ Y に対して, C = {y}. または C = Y .
(3), (4) x = x ∈ X に対して, A = {x}, B = {x }.
17
特に , 0 と 1 の 2 つの元から成る集合を 2 と表す. すなわち, 2 = {0, 1} と書く.
集合 X の部分集合 A の特性関数 (characteristic function) χA : X → 2 をつぎの
ように定義する:
0 if x ∈ A,
χA (x) =
1 if x ∈ A.
特に , χX と χ∅ は , それぞれ値 1 と 0 の定値関数となる.
定理 3.1 写像 ϕ : P(X) → 2X を ϕ(A) = χA と定義すれば , ϕ は全単射となる.
証明 (全射) f ∈ 2X に対して, A = f −1 (1) ∈ P(X) とすれば ,
∀x ∈ X, χA (x) = f (x) ∴ ϕ(A) = χA = f
(単射) A, B ∈ P(X) に対して, ϕ(A) = ϕ(B) とすれば ,
χA = χB より ∀x ∈ X [x ∈ A ⇔ x ∈ B] ∴ A = B
この定理より, m 個の元からなる集合 X の巾集合 P(X) の元の個数が 2m 個で
あることが分かる.
演習 3.3 集合 X の部分集合 A, B の特性関数に関して , つぎを証明せよ:
(1) A ⊂ B ⇔ ∀x ∈ X, χA (x) χB (x)
(2) ∀x ∈ X, χA∩B (x) = χA (x)χB (x)
(3) ∀x ∈ X, χA∪B (x) = χA (x) + χB (x) − χA (x)χB (x)
(4) ∀x ∈ X, χX\A (x) = 1 − χA (x)
(5) ∀x ∈ X, χA\B (x) = χA (x)(1 − χB (x))
発展問題 写像 f : X → Y に対して, 写像 f∗ : P(X) → P(Y ), f ∗ : P(Y ) → P(X) を
つぎのように定義する:
∀A ∈ P(X), f∗ (A) = f (A); ∀B ∈ P(Y ), f ∗ (B) = f −1 (B)
このとき, つぎが成り立つことを示せ:
(1) f が単射 ⇔ f∗ は単射 ⇔ f ∗ は全射
(2) f が全射 ⇔ f∗ は全射 ⇔ f ∗ は単射
ヒント “f が単射 ⇒ f∗ は単射, f ∗ は全射” と “f∗ は全射 ⇒ f が全射” は演習
3.2(1) を参照; “f が全射 ⇒ f∗ は全射, f ∗ は単射” と “f∗ が単射 ⇒ f は単射” は
演習 3.2(2) を参照. “f ∗ が全射 ⇒ f は単射” は {x} = f ∗ (C) が意味することを考
えよ. “f ∗ は単射 ⇒ f が全射” は f ∗ (f (X)) と f ∗ (Y ) を比較せよ.
3.4
写像の合成
一方の終集合ともう一方の定義域が一致する 2 つの写像 f : X → Y と g : Y → Z
に対して , f と g の合成 (composition) g◦f : X → Z を x → g◦f (x) = g(f (x)) に
18
より定義する. 合成写像 g◦f を gf と ◦ を省略して書くことも多い.
X
f
/
Y
g
9
/
Z
gf
写像 f : X → Y の A ⊂ X への制限 f |A は , A の X への包含写像 i : A → X と
f の合成 f ◦i に他ならない. 写像の合成に関して , 結合律が成り立つ. すなわち,
写像 f : X → Y , g : Y → Z, h : Z → W に対して ,
h◦(g◦f ) = (h◦g)◦f.
このとき, h◦g◦f または hgf と書く. また , 任意の写像 f : X → Y に対して,
f ◦idX = f かつ idY ◦f = f であり, f が全単射であれば , f −1 ◦f = idX かつ
f ◦f −1 = idY である.
演習 3.4 写像 f, f : X → Y , g, g : Y → Z の合成に関して , つぎを証明せよ:
(1) ∀A ⊂ X, (g◦f )(A) = g(f (A))
(2) ∀C ⊂ Z, (g◦f )−1 (C) = f −1 (g −1(C))
(3) g◦f が全射 ⇒ g が全射
(4) g◦f が単射 ⇒ f が単射
(5) f が全射, g◦f = g ◦f ⇒ g = g (6) g が単射, g◦f = g◦f ⇒ f = f (7) g◦f が全射, g が単射 ⇒ f が全射
(8) g◦f が単射, f が全射 ⇒ g が単射
演習 3.5 写像 f : X → Y に対して, つぎを示せ:
f が全単射 ⇔ ∃g, g : Y → X such that g◦f = idX and f ◦g = idY
また, このとき g = g = f −1 となることを示せ.
演習 3.6 集合 X から有限集合 Y への全射 f : X → Y に対して, 単射 g : Y →
X で f ◦g = idY となるものが存在することを Y の元の個数による帰納法で示せ.
演習 3.7 共に n 個の元からなる集合 X, Y の間の写像 f : X → Y に対して,
つぎを示せ:
f : 単射 ⇔ f : 全射 ⇔ f : 全単射
ヒント 最初の ⇔ を示せば 十分. まず , ⇒ を n に関する帰納法で示す. ⇐ は演習
3.6 と 3.4(4) を適用.
19
[発展事項]
有限集合間の単射と全射の総数: X の元の個数を m, Y の元の個数を n とする.
I. m n のとき, X から Y への単射の総数はつぎのようになる:
n Pm
= n(n − 1) · · · (n − m + 1) =
n!
(n − m)!
証明 X から Y への単射を定義することは , Y の元を m 個取り出して順番に並べる
ことと同じである.
II. k n のとき, k 個の元からなる Y の部分集合の総数は , つぎのようになる:
n Ck
=
n!
n(n − 1) · · · (n − k + 1)
=
k!
k!(n − k)!
証明 Y から k 個の元を取り出す方法の総数である.
III. n Ck に関して, つぎの公式が成立する:9
n
(1)
(−1)k n Ck = 0 ; (2) n Ck · k Cj = n Cj · n−j Ck−j
(j k n)
k=0
証明 (1) Y の部分集合で奇数個の元を持つものと偶数個の元を持つものの総数が等
しいこと表すが , つぎの性質を持つ全単射 ϕ : P(Y ) → P(Y ) の存在を示せばよい:
B の元の個数は奇数 ⇔ ϕ(B) の元の個数は偶数
このような ϕ は y0 ∈ Y を固定して, つぎのように定義できる:
B \ {y0 } if y0 ∈ B,
ϕ(B) =
B ∪ {y0 } if y0 ∈ B.
(2) n Ck · k Cj =
k!
n!
(n − j)!
n!
·
=
·
= n Cj · n−j Ck−j
k!(n − k)! j!(k − j)!
j!(n − j)! (k − j)!(n − k)!
IV. m n のとき, X から Y への全射の総数 S(m, n) の値はつぎのようになる:
S(m, n) =
n
(−1)n−k n Ck · km
k=0
証明 (1), (2) および帰納法の仮定を用いて, X から Y への写像で全射でないものの
総数は , つぎのように計算できる:
n−1
n Ck
· S(m, k) =
n−1
k
(−1)k−j n Ck · k Cj · j m
k=1 j=0
k=1
=
k
n−1
(−1)k−j n Cj · n−j Ck−j · j m
k=1 j=0
=
=
n−1
n Cj
n−1
(−1)k−j n−j Ck−j
j=0
k=j
n−1
n−j−1
n Cj
j=0
=
· jm
n−1
· jm
(−1)i n−j Ci
i=0
(−1)n−j−1 n Cj · j m
j=0
9
ここでは使わないが ,
n
k=0 n Ck
= 2n (両辺は共に Y の部分集合の総数).
20
X から Y への写像の総数は nm であるから , つぎのように計算できる:
S(m, n) = nm −
n−1
n Ck
· S(m, k)
k=1
= (−1)0 n Cn · nm +
n−1
(−1)n−j n Cj · j m
j=0
=
n
(−1)n−j n Cj · j m
j=0
21
選出公理, 順序, 同値関係
4
この章において , 直積集合を無限の場合への拡張を行うが , そのためには
選出公理と呼ばれる集合論の公理が必要となる. また, 数学では , 集合をまと
めて 1 つの元と見なすというアイデアが , 非常に広く, また深く浸透している
が , その基本的な概念である同値関係と商集合を導入する. さらに , 数学にお
いて , 順序構造, 代数構造, 位相構造という 3 つの基本的構造があるが , ここ
では順序という概念を定義する.
4.1
無限直積集合
集合 X の部分集合 A1 , A2 , . . . , An の直積集合
a = (a1 , a2 . . . , an ) ∈
n
i=1
n
Ai = A1 × A2 × · · · × An は ,
Ai
i=1
を , i → ai ∈ Ai ⊂ X により定義される写像
a : {1, 2, . . . , n} → X
と同一視することにより, つぎのようにみなせる:
n
Ai = a ∈ X {1,2,...,n} | ∀i = 1, . . . , n, a(i) ∈ Ai
i=1
ここで , X Y は Y から X への写像全体の成す集合である.
一般に , 集合 Λ の元 λ によって添字付けられた集合 X の部分集合 Aλ の直積
λ∈Λ Aλ を , つぎのように定義する:
Aλ = a ∈ X Λ ∀λ ∈ Λ, a(λ) ∈ Aλ
λ∈Λ
このとき, a ∈ λ∈Λ Aλ を (aλ )λ∈Λ と表し , aλ を a の λ 座標 (λ-coordinate) また
は λ 成分 (λ-factor) という. このとき, 各 λ ∈ Λ に対して , (aλ )λ∈Λ → aλ により定
義される λ∈Λ Aλ から Aλ への写像を prλ と表し , λ∈Λ Aλ の λ 座標 (または λ
成分) への射影 (projection) という. すなわち,
Aλ , prλ (a) = aλ
∀λ ∈ Λ, ∀a = (aλ )λ∈Λ ∈
λ∈Λ
直積 λ∈Λ Aλ の定義において , 集合の集合である {Aλ | λ ∈ Λ} ではなく, 各
λ ∈ Λ にどんな集合 Aλ が対応しているかが問題となる. すなわち, {Aλ | λ ∈ Λ} =
{Bλ | λ ∈ Λ} であっても λ∈Λ Aλ = λ∈Λ Bλ とは限らない.10 この対応のさせ方
10
A, B = ∅, A = B ⇒ A × B = B × A.
22
λ → Aλ は , Λ から P(X) への写像を定義するが , これを (Aλ )λ∈Λ と表し , Λ によ
り (添字付けられた) 集合族 (indexed family of sets) といい, Λ を添字集合 (index
set) という. 添字集合が N のときには , (Ai )i∈ を集合列 (sequence of sets) とい
∞
∞
い, (Ai )i∈ は (Ai )∞
A
は
A
と書き
,
(a
)
∈
i
i
i
i∈
i=1 と ,
i∈
i∈ Ai は (ai )i=1
i=1
あるいは (a1 , a2 , . . . ) と書くこともある. 各 λ ∈ Λ に対して , Aλ = A のときは ,
Λ
∞
と書
λ∈Λ Aλ は Λ から A への写像全体の成す集合 A となる. また , A は A
∞
くこともあるが , A の元の列全体の成す集合といえる. R (= R ) は実数列全体
の成す集合といえる.
注意: 集合 X を意識せずに集合族 (Aλ )λ∈Λ を扱う場合には , X = λ∈Λ Aλ と考
えればよい.
演習 4.1 同じ 添字集合を持つ X の部分集合の族 (Aλ )λ∈Λ , (Bλ )λ∈Λ に対して,
つぎを証明せよ:
Aλ ⊂
Bλ
(1) (∀λ ∈ Λ, Aλ ⊂ Bλ ) ⇒
λ∈Λ
λ∈Λ
(2)
Aλ ∩
Bλ =
(Aλ ∩ Bλ )
λ∈Λ
4.2
λ∈Λ
λ∈Λ
選出公理
直積集合
λ∈Λ
Aλ に関するつぎの命題は自明である:
(∃λ ∈ Λ such that Aλ = ∅) ⇒
Aλ = ∅
λ∈Λ
つぎの命題はこの命題の裏 (=逆の対偶) であるが , λ∈Λ Aλ の定義において , 本質
的な意味を持つ:
(∀λ ∈ Λ, Aλ = ∅) ⇒
Aλ = ∅
λ∈Λ
添字集合 Λ の元が有限個であれば , Λ = {1, 2, · · · , n} と考え , 各 Ai から 1 つず
n
つ元 ai を選ぶことにより, (a1 , a2 , . . . , an ) ∈ i=1 Ai が得られ , 上の命題が成立す
る. また, Λ の元が無限個であっても, λ∈Λ Aλ = ∅ であれば , a ∈ λ∈Λ Aλ を 1
つ選び , 定値写像 λ → a を考えることにより, λ∈Λ Aλ の元が得られ , 上の命題が
成立する. しかし , 一般の場合には問題が生じる. 実際, 上の命題を書き直すと , つ
ぎのようになる:
(AC) (∀λ ∈ Λ, Aλ = ∅) ⇒ ∃f : Λ →
Aλ such that ∀λ ∈ Λ, f (λ) ∈ Aλ
λ∈Λ
ここでは , 各 λ ∈ Λ に対して aλ ∈ Aλ を 選び出す方法 (選び出し方) f : λ → aλ
が存在することを主張しており, 各 λ ∈ Λ に対して aλ ∈ Aλ が取れるということ
23
だけではない. 集合論におけるこの命題 (AC) を選出公理 (Axiom of Choice) とい
い, 写像 f を (Aλ )λ∈Λ に対する選出関数 (choice function) という.
つぎの命題は選出公理から容易に導ける:
• 全射 f : X → Y に対して , 写像 g : Y → X で f ◦g = idY となるものが存在
する. このとき, g は単射である.
証明 g は集合族 (f −1 (y))y∈Y に対する選出関数として得られる.
注意: Y が有限集合の場合には , 帰納法で示せる (演習 3.6). また, 上の命題か
ら選出公理を導けて, 上の命題は選出公理と同値になることが分かる. 実際, 上
の命題を仮定すれば , X = λ∈Λ {λ} × Aλ , Y = λ∈Λ Aλ とし , f : X → Y を
射影 prY : Λ× Y → Y の X 上への制限として, 上の命題を適用して, (Aλ )λ∈Λ
の選出関数が得られる.
単射に関しては , 選出公理を用いずに , つぎの命題が示せる:
• 単射 f : X → Y に対して, 写像 g : Y → X で g◦f = idX となるものが存在
する. このとき, g は全射である.
証明 f : X → f (X) は全単射であるから, 逆写像 f −1 : f (X) → Y がある
x0 ∈ X を 1 つ取り, つぎのように g : Y → X を定義すればよい:
f −1 (y) if y ∈ f (X),
g(y) =
if y ∈ Y \ f (X)
x0
上の 2 つの命題からつぎの定理が得られる:
定理 4.1 集合 X, Y に対して , X から Y への単射が存在するための必要十分条
件は , Y から X への全射が存在することである. 演習 4.2 選出公理を用いて , つぎを示せ:
(1) 各 λ ∈ Λ に対して Aλ = ∅ であれば , 射影 prλ : λ∈Λ Aλ → Aλ は全射である.
(2) 各 λ ∈ Λ に対して Aλ = ∅ であれば , 演習 4.1(2) の逆が成立する. すなわち,
Aλ ⊂
Bλ ⇒ ∀λ ∈ Λ, Aλ ⊂ Bλ
λ∈Λ
λ∈Λ
ヒント (1) 選出公理により存在が保証される
(aλ )λ∈Λ ∈
に対して, prλ (y) = x となる y ∈ λ∈Λ Aλ を作れ .
λ∈Λ
Aλ を用いて , x ∈ Aλ
(2) を示すのに (1) が適用できる.
演習 4.3 集合 Λ の元によって添字付けられた空でない集合の間の写像 fλ : Xλ →
Yλ に対して , f : λ∈Λ Xλ → λ∈Λ Yλ を , つぎのように定義する:
∀x = (xλ )λ∈Λ ∈
Xλ , f (x) = (fλ (xλ ))λ∈Λ ∈
Yλ
λ∈Λ
λ∈Λ
24
λ∈Λ
prλ
Xλ
f
Xλ
/
λ∈Λ
fλ
Yλ
prλ
/ Yλ
このとき, 選出公理を用いて , つぎを示せ:
(1) f が全射 ⇔ ∀λ ∈ Λ, fλ が全射
(2) f が単射 ⇔ ∀λ ∈ Λ, fλ が単射
ヒント (1) ⇒: 演習 4.2(1) を参照.
⇐: ∀y = (yλ )λ∈Λ ∈ λ∈Λ Yλ , f −1 (y) = λ∈Λ fλ−1 (yλ )
(2) ⇒: 選出公理より存在が保証される (zλ )λ∈Λ ∈ λ∈Λ Xλ を用いて, x = x ∈ Xλ
に対して
, prλ (y) = x, prλ (y ) = x で λ = λ ⇒ prλ (y) = prλ (y ) を満たすような
y, y ∈ λ∈Λ Xλ を作り f が単射であることを適用.
⇐: (xλ )λ∈Λ = (xλ )λ∈Λ ∈ λ∈Λ Xλ であれば , ∃λ ∈ Λ, xλ = xλ
発展問題 A を空でない集合, W を 2 つ以上元を持つ集合とするとき, 写像 f : X → Y
に対して, f∗ : X A → Y A と f ∗ : W Y → W X を, つぎのように定義する:
∀g ∈ X A , f∗ (g) = f ◦g および ∀h ∈ W Y , f ∗ (h) = h◦f
f
/Y
??

∗
?? g f_ W 
?v ?

 h
h◦f ??

? 
X?
A?
??

?? f ◦g
g 

6 ??

W
g
_

??

?
f∗

/Y
X
W
f
このとき, つぎを示せ:
(1) f
(2) f
(3) f
(4) f
が全射
が単射
が全射
が単射
⇔
⇔
⇔
⇔
f∗ が全射 (⇒ を示すのに選出公理が必要)
f∗ が単射
f ∗ が単射
f ∗ が全射
ヒント (1) ⇒: h ∈ Y A に対して, f ◦g = h となるような g ∈ X A は , ∀a ∈ A,
g(a) ∈ f −1 (h(a)) を満たす.
⇐: y ∈ Y に対して, cy ∈ Y A を cy (a) = y となる定値写像とすれば , 条件が適用で
きる. (cy の存在に A = ∅ が必要)
(2) ⇒: g = g ∈ X A とすれば , ∃a0 ∈ A, g(a0 ) = g (a0 ).
⇐: x = x ∈ X に対して, cx , cx ∈ X A をそれぞれ cx (a) = x, cx (a) = x となる定
値写像とすれば , 条件が適用できる.
(3) ⇒: h = h ∈ W Y とすれば , ∃y0 ∈ Y , h(y0 ) = h (y0 ).
⇐: (背理法) f が全射でなければ , ∃y0 ∈ Y \ f (X). W が異なる 2 元を持つことを
用いて , h(y0 ) = h (y0 ) で h(y) = h (y) (y = y0 ) となる h, h ∈ W Y を作り, f ∗ が単
射であることに矛盾を出す.
25
(4) ⇒: g ∈ W X に対して, h◦f = g となるような h ∈ W Y は , y = f (x) ∈ Y ⇒
h(y) = h(f (x)) = g(x) でなければならない.
⇐: (背理法) f が単射でなければ , ∃x0 = x1 ∈ X, f (x0 ) = f (x1 ). W が異なる 2 元
を持つことを用いて , g(x0 ) = g(x1 ) となる g ∈ W X を作り, f ∗ が全射であることに
矛盾を出す.
4.3
順序
集合 X の 2 つの元の間の関係を X 上の 2 項関係 (binary relation) というが ,
“x が y と R という関係にある” ということを xRy と書く. 例えば , N において,
“x = y”, “x < y”, “x は y の約数である”, “x と y は 3 で割ったとき余りが同じ ”,
. . . などは 2 項関係である.
集合による 2 項関係の定義: 2 項関係 R に対して , X 2 の部分集合 Γ =
{(x, y) ∈ X 2 | xRy} を R のグラフというが , X 2 の部分集合 R に対して,
(x, y) ∈ Γ のときに xRy と定義すれば , この 2 項関係 R のグラフは Γ とな
る. こうして, 2 項関係 R とそのグラフ Γ と同一視することができるので,
X 2 の部分集合が X 上の 2 項関係であると定義できる.
集合 X の元の間の相等関係 = は , 対角集合 ΔX によって定義される.
つぎの条件を満たす集合 X 上の 2 項関係 を X における順序 (関係)(order)
という:
(O1 ) ∀x ∈ X, x x
— 反射律 (reflective law)
(O2 ) ∀x, y ∈ X, x y, y x ⇒ x = y
(O3 ) ∀x, y, z ∈ X, x y, y z ⇒ x z
— 反対称律 (antisymmetric law)
— 推移律 (transitive law)
x y かつ x = y のとき, x < y と書き, x y (または x < y) の否定は x y
(または x < y) と書く. また, x y, x < y, x y, x < y は , それぞれ y x,
y > x, y x, y > x とも書く. 2 つの元 x, y ∈ X に対して, x y または x y が
成立するとき, x と y は比較可能 (comparable) であるというが , 任意の 2 つの元
x, y ∈ X が常に比較可能なとき , すなわち, つぎの条件を満たすとき, 順序 を全
順序 (total order) または線形順序 (linear order) という:
(O4 ) ∀x, y ∈ X, x y or x y
— 比較可能律 (comparability law)
順序 に対して , 上のように定義した 2 項関係 < はつぎの 2 条件を満たす:
(O∗1 ) ∀x, y ∈ X, x < y ⇒ x = y
— 非反射律 (irreflexive law)11
(O∗2 ) ∀x, y, z ∈ X, x < y, y < z ⇒ x < z
— 推移律 (transitive law)
この 2 条件を満たす 2 項関係 < を狭義の順序 (order in the strict sense) という.
11
これは , ∀x ∈ X, x < x と同値.
26
演習 4.4 狭義の順序 < が集合 X 上に与えられた時, x < y または x = y を
x y と書くことにすれば , 2 項関係 は条件 (O1 ), (O2 ), (O3 ) を満たし , X 上の
順序となることを示せ.
ヒント (O∗1 ), (O∗2 ) から x < y と y < x は両立しない.
さらに以下の条件を満たす狭義の順序 < を狭義の全順序であるいう.
(O∗3 ) ∀x, y ∈ X, x = y or x < y or x > y
— 三分律 (trichotomy)
注意: 上の条件において, x = y, x < y, x > y のうち唯一つだけが成立する.
順序 (あるいは狭義の順序) が与えられている集合を順序集合 (ordered set) とい
うが , 単なる集合 X ではなく, 順序 という “構造” を持っていることを示すた
め, 集合と順序の組 (X, ) (あるいは集合と狭義の順序の組 (X, <)) で表す. どん
な順序 (あるいは狭義の順序 <) が与えられているのか明確な場合には , 単に X
を順序集合と呼ぶことが多い. 全順序 (あるいは狭義の全順序 <) が与えられて
いる集合を全順序集合 (totally ordered set) または線形順序集合 (linearly ordered
set) という.
例えば , 集合 N, Z, Q, R は , 通常の大小関係で全順序集合であるが , 元を 2 つ
以上持つ集合 X の巾集合 P(X) における包含関係 ⊂ は順序であるが全順序では
ない.
注意: 全順序集合においては , x y の否定は x > y となるが , 一般の場合には ,
x, y ∈ X が比較不可能なときも x y となるので , x y の否定は必ずしも x > y
とはならない.
順序集合 X = (X, ) の部分集合 A に対して, つぎの条件を満たす a ∈ A を A
の最大元 (maximum) (または 最小元 (minimum)) という:
∀x ∈ A, a x (a x)
A の最大元 (最小元) は存在すれば一意的に決まるので , max A (または min A) と
表す. また, つぎの条件を満たす a ∈ A を A の極大元 (maximal element) (または
極小元 (minimal element)) という:
∀x ∈ A, a < x (または a > x)
演習 4.5 A の最大元 (または最小元) は存在すれば , それは A の極大元 (または
極小元) であり, 一意的に決まることを示せ. また, 全順序集合においては , 極大元
(または極小元) は最大元 (または最小元) になることも示せ.
演習 4.6 A の極大元 (または極小元) が存在するが一意的でない例を与えよ.
27
順序集合 X = (X, ) の部分集合 A に対して, つぎの条件を満たす b ∈ X を
(X における) A の上界 (upper bound) (または , 下界 (lower bound)) という:
∀x ∈ A, b x (または b x)
もし A の上界 (または下界) b が A の元であれば , それは A の最大元 (または最
小元) となる. X における A の上界 (または下界) が存在するとき, A は (X に
おいて ) 上に有界 (upper bounded) (または , 下に有界 (lower bounded)) であると
いい, 上にも下にも有界であるとき, 有界 (bounded) であるという. A が上に有
界 (または下に有界) であるとき, A の最小上界 (least upper bound)(または最大下
界 (greatest lower bound)), すなわち, 上界の最小元 (または下界の最大元) を上限
(supremum) (または下限 (infimum)) といい, 存在すればやはり一意的に決まるの
で , sup A (または inf A) と表す. 定義より, c = sup A (または c = inf A) を示すに
は , つぎの 2 つの条件を確かめればよい:
(i) ∀x ∈ A, c x (または c x)
(ii) (∀x ∈ A, b x (または b x)) ⇒ c b (または c b)
演習 4.7 全順序集合においては , (ii) はつぎと同値であることを示せ:
(ii’) ∀x < c (または ∀x > c), ∃a ∈ A such that x < a (または a < x)
演習 4.8 順序集合 X において , A ⊂ B ⊂ X とする. 共に最大元が存在すると
き, max A max B となること , 共に上限が存在するとき, sup A sup B となる
ことを示せ. 最小元と下限に関してはどんなことがいえるか ?
演習 4.9 集合 X の巾集合 P(X) を包含関係 ⊂ による順序集合と考えたとき,
{A, B} ⊂ P(X) の上限 sup{A, B} と下限 inf{A, B} はそれぞれ何になるか .
順序集合 X の順序 を部分集合 Y に制限すれば , Y 上の順序 Y が得られる.
すなわち,
∀x, y ∈ Y, x Y y ⇔ x y
def
このとき, Y = (Y, Y ) を X の部分順序集合 (orderd subset) という. 全順序集合
の部分順序集合は全順序集合である.
A ⊂ Y ⊂ X の場合, A の上限と下限はどこで考えるのか , X なのか Y なのか
問題となるので , supX A, supY A, inf X A, inf Y A と書いて区別する.
演習 4.10 順序集合 X において , A ⊂ Y ⊂ X とする.
(1) A の上限に関して , supX A と supY A が共に存在すれば , supX A supY A が
成立することを示せ. 下限に関しては , どんなことがいえるか ?
(2) supX A は存在するが supY A が存在しない例を与えよ. 下限に関する同様な
例も与えよ.
28
(3) supY A は存在するが supX A が存在しない例を与えよ. 下限に関する同様な
例も与えよ.
演習 4.11 自然数の集合 N において , m ∈ N が n ∈ N で割り切れるという関
係 n|m は N 上の順序となることを示せ. この順序に関して , n > 1 が N \ {1} の
極小元となるためには , n が素数となることが必要十分であることを示せ.
演習 4.12 上記の順序集合 N = (N, | ) における {n, m} ⊂ N の上限 sup{n, m}
と下限 inf{n, m} はそれぞれ何を意味するか ?
4.4
同値関係と商集合
つぎの条件を満たす X 上の 2 項関係 ∼ を同値関係 (equivalence relation) と
いう:
(E1 ) ∀x ∈ X, x ∼ x
— 反射律 (refective law)
(E2 ) ∀x, y ∈ X, x ∼ y ⇒ y ∼ x
— 対称律 (symmetric law)
(E3 ) ∀x, y, z ∈ X, x ∼ y, y ∼ z ⇒ x ∼ z
— 推移律 (transitive law)
例えば , N において, “x = y” や “x と y は 3 で割ったとき余りが同じ ” という
関係は同値関係である. 同値関係を表す記号として , “∼” の他に , “”, “≈”, “∼
=”,
“≡” などの記号が用いられる.
つぎの条件を満たす X の部分集合族 D を X の直和分割 (あるいは単に , 分割)
(decomposition) という:
(1) ∀x ∈ X, ∃D ∈ D such that x ∈ D (すなわち, X = D)
(2) ∀D, D ∈ D, D = D ⇒ D ∩ D = ∅
この条件は , 各 x ∈ X は D のどれかただ 1 つの元 (クラス) に含まれることを意
味し , X の元が D により, クラス分けされていることを示している. 集合 X の直
和分割 D に対して , X 上の 2 項関係 ∼ を , つぎのように定義する:
x ∼ y ⇔ ∃D ∈ D such that x, y ∈ D
def
このとき, ∼ は X 上の同値関係となり, D に付随する同値関係という.
集合 X 上の同値関係 ∼ に対して , 各 x ∈ X の ∼ による同値類 (equivalence
class) [x] を , つぎのように定義する:
[x] = {y ∈ X | x ∼ y}
このとき, つぎが成り立つ:
x ∈ [x]; x ∼ y ⇔ [x] = [y]; [x] = [y] ⇔ [x] ∩ [y] = ∅
29
これより, {[x] | x ∈ X} は X の直和分割となり, ∼ はこの直和分割に付随する同
値関係と一致する. ここで , ある x ∈ X の同値類となっている D ⊂ X (すなわち,
D = [x]) を , 単に X の ∼ による同値類といい, x を D の代表元 (representative)
という. 同値関係 ∼ による同値類全体の成す X の直和分割を X/∼ と表し , X の
∼ による商集合 (quotient set) という. すなわち,
X/∼ = {[x] | x ∈ X}
このとき, x → [x] により定義される写像 π : X → X/∼ を自然な写像 (natural
map), 標準的写像 (canonical map), 商写像 (quoitent map), あるいは , 等化写像
(identification map) などという. ある同値関係による x ∈ X の同値類を表す記号
として , “[x]” の他に , “x”, “[[x]]”, “x” などを用いる.
同値関係と直和分割: X 上の同値関係 ∼ に対して , X の直和分割 D = X/∼
に付随する同値関係は ∼ に一致する (∼ = ∼). 逆に , X の直和分割 D が与
えられたとき, X 上の同値関係 ∼ による同値類全体のなす X の直和分割
は D に他ならない (X/∼ = D). こうして, X 上に同値関係を与えることと
X の直和分割を与えることは , 同じことを意味する.
数学では , ある集合の上に様々な概念や事柄を定義して, それについて議論を進
めていくが , 何かを定義をする場合, “その定義には矛盾がないか ”, 言い換えれば ,
“矛盾無く定義できているか ” が問題となることが多い. “矛盾無く定義できてい
る” ということを “well-defined” であるという. 考えている集合が商集合の場合,
ある概念や事柄を定義するとき, 商集合の元ではなく, その代表元を用いて定義す
ることが少なくない. この場合の “well-defined” の問題は , “代表元の取り方に依
存せずに定義できているかど うか ” ということである.
例えば , つぎのような主張について考える:
• 写像 f : X → Y によって X 上の同値関係 ∼f をつぎのように定義する:
x ∼f y ⇔ f (x) = f (g)
def
この同値関係による x ∈ X の同値類を [x] で表し , π : X → X/∼f を商写像
とする. 写像 f˜ : X/∼f → Y を f˜([x]) = f (x) と定義すると f = f˜π となる.
このとき, 写像 f˜ が well-defined であることが問題となる. すなわち, [x] に対する
値 f˜([x]) が 1 つに定まるためには , [x] = [y] のとき f (x) = f (y) とならなければ
ならない. これは [x] = [y] より x ∼f y であり, ∼f の定義より f (x) = f (y) が言
える. もちろん , この主張において , ∼f が同値関係になることも示す必要がある.12
しかし , このように主張が単なる言い換えや簡単に示せる場合には , 証明は省かれ
て主張のように書かれるので , 自分で上記のことを確認しながら読む必要がある.
注意: 次の章において , 整数, 有理数, 実数 の各節において , 具体的に , 同値関
係, 同値類, well-defined を調べるので, この節の演習は省いた .
12
この例では , X/∼f = {f −1 (y) | y ∈ f (X)} であり, 各 x ∈ X に対し [x] = f −1 (f (x)) となる.
30
5
数の体系
この章では , 自然数をどの様に公理的に定義出来るか , さらに , 整数, 有理
数, 実数, そして複素数を自然数からどの様に構成出来るのかを示す. 教育的
には , 自然数から始めて , 新しい数として , 0 (零), 分数, 小数, (正の) 無理数,
負の数, 虚数を付け加えるという方法で, 数の体系の拡張がなされている. す
なわち, 自然数の集合から始まり, 負でない整数, 負でない有理数, 負でない実
数, 実数, そして複素数の集合へと拡張される. しかし , 数学的には , 代数的構
造を完成させて行くという立場から , それぞれの数の体系の拡張がなされる.
また, 新しい数をもとの体系に付け加えていくのではなく, もとの体系と同等
のものを含む新しい体系を別に作り, もとの体系をそこに含まれている同等の
ものと同一視するという方法により拡張がなされる.
数学においては , どんな場合でも, 出発点は公理的に行なわれる. 数の場
合も同様に , 出発点である自然数は公理的に定義される. すなわち, 自然数の
集合はある一群の公理を満たす集合として定義され , それから , 整数の集合は
自然数の集合の積集合の商集合として , 有理数の集合は整数の集合と自然数
の集合の積集合の商集合として定義される. 実数の集合の構成は , ２通りの方
法, 有理数の集合のある種の部分集合の組の集合として定義する方法とある種
の有理数列の集合の商集合として定義する方法がある. ここでは , 商集合に慣
れるために後者の方法を採用する. 前者は , 参考として章末で紹介する. 複素
数の集合の場合は , 単に実数の集合の積集合として定義される.
5.1
代数的構造
有理数までの拡張は , 代数的構造を中心に考えて行くので , ここで代数的構造に
ついて簡単に概説する. 集合 X 上の演算とは , X 2 = X × X (またはその部分集合)
から X への写像であり, (x, y) ∈ X 2 の値を x + y, x · y, x ◦ y, x ∗ y, などと表す.
集合 X 上の演算 ∗ に関して , つぎの条件を結合律 (accosiative law) という:
∀x, y, z ∈ X, (x ∗ y) ∗ z = x ∗ (y ∗ z)
また, つぎの条件を可換律 (commutative law) という:
∀x, y ∈ X, x ∗ y = y ∗ x
結合律を満たす演算が与えられている集合を半群 (semi-group) といい, さらに可
換律を満たせば , 可換半群 (commutative semi-group) という. 与えられている演
算を明確にするときには , 集合 X と演算 ∗ の組 (X, ∗) で表す. 演算の記号 · が使
われるときは , x·y を xy と省略して書く. 演算の記号 + は可換律を満たす演算に
用いられる. つぎの条件を満たす e ∈ X を単位元 (unit (element)) という:
∀x ∈ X, x ∗ e = e ∗ x = x
単位元が存在する場合, それは唯一である. また, x ∈ X に対して, つぎの条件を
満たす x ∈ X を x の逆元 (inverse element) という:
x ∗ x = x ∗ x = e
31
逆元が存在すれば , x に対して一意的である. x の逆元の逆元は x である. 単位
元があり, 各元に対して逆元がある (可換) 半群を (可換) 群 ((commutative) group)
という. 演算が · のときには , x·y は xy と書き, 単位元は 1, x の逆元は x−1 で表
す. このとき, (x−1 )−1 = x となる. 演算が + の場合には , 単位元は 0 で表し , 零元
(zero, null element) と呼ぶ. また, x の逆元は −x で表す. このとき, −(−x) = x
となる.
集合 X 上の 2 つの演算 +, · に関して , つぎの条件を分配律 (distributive law)
という:
∀x, y, z ∈ X, x(y + z) = xy + xz, (y + z)x = yx + zx
集合 X が分配律を満たす 2 つの演算 +, · を持ち, (X, +) が可換群となり, (X, ·)
が (可換) 半群となるとき, X = (X, +, ·) を (可換) 環 ((commutative) ring) という.
このとき, つぎが成り立つ.
(1) x0 = 0x = 0 ; (2) (−x)y = x(−y) = −(xy) ; (3) (−x)(−y) = xy
証明 (1) x0 + x0 = x(0 + 0) = x0 より, x0 = 0 が 得られ る. 0x = 0 も同
様. (2) xy + (−x)y = (x + (−x))y = 0y = 0 より, (−x)y = −(xy) が得られる.
x(−y) = −(xy) も同様. (3) (−x)(−y) = −(x(−y)) = −(−(xy)) = xy.
可換環 X = (X, +, ·) において , (X \ {0}, ·) が可換群になっているとき, X を
体 (field) というが , (X \ {0}, ·) が可換ではない群の場合には , X を非可換体 (noncommutative field) という. R は体となっているので , 実数体と呼ぶことがある.
体 X = (X, +, ·) に , つぎの条件を満たす全順序 が与えられたとき, X を順
序体 (ordered field) という:
x < y, z ∈ X ⇒ x + z < y + z ;
x < y, z > 0 ⇒ xz < yz
このとき, つぎが成立する:
(1) x < y ⇔ −y < −x ; (2) 0 < 1 ; (3) x > 0 ⇔ x−1 > 0 ;
(4) 0 < x < y ⇒ y −1 < x−1 ; (5) x < y, z < 0 ⇒ xz > yz
証明 (1) x < y の両辺に −x − y を加えれば , −y < −x が得られる. 逆も同様. (2)
1 < 0 とすれば 0 < −1 となるので , 1 < 0 の両辺に −1 をかければ −1 < 0 となり, 矛
盾. (3) x > 0 のとき, x−1 < 0 とすれば , この両辺に x をかければ 1 < 0 となり, 矛盾.
逆も同様. (4) 0 < x < y のとき, (xy)−1 > 0 となるので , x < y の両辺に (xy)−1 をか
ければ y −1 < x−1 が得られる. (5) −z > 0 より, −(xz) = x(−z) < y(−z) = −(yz)
となるので, xz > yz が得られる.
順序体 X においては , 各 x ∈ X に対して絶対値 (absolute value) |x| が , つぎのよ
うに定義できる:
x
if x 0,
|x| =
−x if x < 0.
このとき, つぎが成立する:
|x| 0 ;
|x| = 0 ⇔ x = 0 ;
|xy| = |x| · |y| ;
32
|x + y| ≤ |x| + |y|
5.2
自然数 — Peano の公理
自然数の集合 N は , Peano13 の公理 (Peano Axioms) と呼ばれる次の 5 つの公
理を満たす集合として定義される:
(N1 ) 1 ∈ N
(1 は自然数である)14
(N2 ) ∃S : N → N
(各自然数 x には次の数15 S(x) が唯一つ決まっている)
(N1 ) と (N2 ) における 1 と S に関して , 以下の条件が成立する:
(N3 ) ∀x ∈ N, S(x) = 1
(1 はどんな自然数の次の数にもならない)
(N4 ) S(x) = S(y) ⇒ x = y
(異なる自然数の次の数は互いに異なる)
(N5 ) A ⊂ N が次の 2 条件を満たすならば , A = N となる:
(i) 1 ∈ A,
(ii) x ∈ A ⇒ S(x) ∈ A
後で定義する加法を用いれば , S(x) = x + 1 である. 公理 (N4 ) は S が単射であ
ることを意味する. (N3 ) は 1 ∈ S(N) となるが , (N5 ) より N = {1} ∪ S(N) なので ,
N \ {1} = S(N) となる. また, (N5 ) は (数学的) 帰納法 ((mathematical) induction)
を意味する. 実際, 条件 P (x) に対し , A = {x ∈ N | P (x)} とおけば , A = N と
いうことは “∀x ∈ N, P (x) が成立する” ということを意味する. これを示すには ,
(N5 ) の (i), (ii) を示せばよいが , それは以下を示すことに他ならない:
(i) P (1) が成立,
(ii) P (x) が成立 ⇒ P (x + 1) が成立
注意: Peano の公理を満たす N = (N, 1, S) の存在を示すには , 無限集合の存
在とその性質が必要である. また, このような集合 (体系) は本質的に一意的
である. すなわち, N をアラビア数字全体の集合 {1, 2, 3, . . . } と考えようと ,
ローマ数字全体の集合 {I, II, III, . . . } と考えようと, また英語で one, two,
three, . . . という言葉全体の集合と考えようと, 日本語で イチ, ニ, サン , . . .
という言葉全体の集合と考えようと , さらにそれらが表すもの (概念) 全体の
集合と考えようと , みな同じである. — 本節および 6.3 節の補足事項を参照.
演算: 2 つの元 x, y ∈ N の和 x + y と積 xy (= x·y) をつぎのように帰納的16 に
定義する17 ことにより, N は分配律をみたす加法と乗法を持つが , それぞれに関し
て可換半群となる:
(a-i) x + 1 = S(x),
(m-i) x·1 = x,
(a-ii) x + S(y) = S(x + y);
(m-ii) x·S(y) = x + xy.
13
ペアノ (Giuseppe Peano, 1858–1932)
基礎論では , N は 0 から始める.
15
successor
16
正確には , 再帰的 (recursive) という.
17
実際には , これにより写像としての演算 (x, y) → x + y, (x, y) → xy が定義できることは , 証
明を要することである. — 本節末の補足事項を参照.
14
33
演習 5.1 N における加法と乗法の結合律, 交換律および分配律を証明せよ.
(x + y) + z = x + (y + z) ;
x+y =y+x ;
xy = yx ;
(xy)z = x(yz) ;
x(y + z) = xy + xz
ヒント (x + y) + z = x + (y + z) は z に関する帰納法; x + 1 = 1 + x は結合律と帰
納法; x + y = y + x は結合律と y に関する帰納法; x(y + z) = xy + xz は和に関す
る結合律, 交換律と z に関する帰納法; (xy)z = x(yz) は分配律, 和に関する交換律
と z に関する帰納法. 乗法の可換律を示すには , 分配律 (y + z)x = yx + zx も必要.
この分配律は x に関する帰納法. 1x = x1 は帰納法; xy = yx は分配律と y に関す
る帰納法.
演習 5.2 N における次の加法の簡約律を証明せよ:
x+z =y+z ⇒ x=y
ヒント z に関する帰納法.
N における乗法の簡約律は順序に関する性質を調べた後に扱う.
順序: N は , つぎのように定義される大小関係に関して全順序集合となる:
x < y ⇔ ∃u ∈ N such that y = x + u
def
x y ⇔ x = y or x < y
def
上の定義において , 簡約律 (演習 5.2) により, u が一意的に決まる.
命題 5.1 上で定義した < が N 上の狭義の全順序 (従って , が N 上の全順序) と
なり, この順序に関して 1 が N の最小元となる.
証明 4.3 節の (O∗1 ) – (O∗3 ) を示せばよい.
(O∗1 ): x < x と仮定. ∃u ∈ N such that x = x + u ∴ x + 1 = x + u + 1
簡約律より, 1 = u + 1 = S(1) — (N3 ) に矛盾
(O∗2 ): x < y, y < z とすると , ∃u, v ∈ N such that y = x + u, z = y + v
このとき, z = x + (u + v) となり, x < z
(O∗3 ): (x に関する帰納法; x = 1 の場合が min N = 1 の証明)
x = 1 のとき, “∀y ∈ N, 1 = y or 1 < y” を y に関する帰納法で示す.
y = 1 のとき自明. “1 = y or 1 < y” と仮定すると “1 < y + 1”
次に , “∀y ∈ N, x = y or x < y or y < x” と仮定.
x = y のとき, y < x + 1
x < y のとき, ∃u ∈ N such that y = x + u
u = 1 のとき, x + 1 = y
u = 1 のとき, ∃v ∈ N such that u = v + 1
y = x + (v + 1) = (x + 1) + v より x + 1 < y
y < x のとき, ∃u ∈ N such that x = y + u
x + 1 = y + (u + 1) より y < x + 1
帰納法により, “∀y ∈ N, x + 1 = y or x + 1 < y or y < x + 1” が成立.
演習 5.3 空でない N のどんな部分集合 A も最小元 min A を持つことを示せ.
34
ヒント x ∈ N に関する命題 “∀A ⊂ N, (x ∈ A ⇒ ∃ min A)” を帰納法で証明. x に対
してこの命題を仮定し , S(x) ∈ A とする. A ∪ {x} は最小元 a を持つが , a ∈ A と
a ∈ A の場合に分けて, A の最小元について考えよ.
つぎの (数学的) 帰納法は (N5 ) が意味する帰納法とは異なるものであり, 上の問
題 5.3 にある N の順序に関する性質に基づくものである.
演習 5.4 条件 P (x) に関して , “∀x ∈ N, P (x) が成立する” ことを証明するの
に , つぎを示せば十分であるとこを示せ:
(*) ∀y < x, P (y) が成立 ⇒ P (x) が成立
ヒント (*) には , P (1) が成立することが含まれる. A = {x ∈ N | ¬P (x)} = ∅ とす
れば , 演習 5.3 より A は最小元 a を持つが , (*) と矛盾が生じる.
演習 5.5 N において , 次を証明せよ:
x < y, z ∈ N ⇒ x + z < y + z, xz < yz
演習 5.6 N における次の乗法の簡約律を証明せよ:
xz = yz ⇒ x = y
ヒント 命題 5.1 と演習 5.5 を用いて, 対偶を示す.
[補足事項]
Peano の体系の一意性と帰納的 (再帰的) 定義: N における演算は N2 = N × N から N
への写像であるので, N における加法と乗法を定義するには , 下記の写像を定義しなけれ
ばならない:
+ : N2 (x, y) → x + y ∈ N; · : N2 (x, y) → xy ∈ N
しかし , 下の条件では , 各 x, y ∈ N に対して x + y, xy ∈ N が与えられたにすぎない:18
(a-i) x + 1 = S(x),
(m-i) x·1 = x,
(a-ii) x + S(y) = S(x + y);
(m-ii) x·S(y) = x + xy.
ここでは , 下記の再帰定理を用いて, Peano の公理をみたす体系 (N, 1, S) の一意性と上
の条件により加法と乗法が定義できることを示そう.
定理 5.2 (再帰定理) 集合 W に写像 ϕ : W → W と a ∈ W が与えられたとき, つぎの条
件を満たす写像 f : N → W が一意的に存在する:
(r-i) f (1) = a,
(r-ii) f (S(x)) = ϕ(f (x)).
実際には , 公理 (N2 ) より, 各 y ∈ N に対して, 写像 αy : N x → x + y ∈ N が与えられるが ,
N y → αy ∈ NN が定義されたわけではない. 加法が定義されたならば , 各 y ∈ N に対して, 写像
μy : N x → xy ∈ N が与えられるが , N y → μy ∈ NN が定義されたわけではない.
18
35
証明 f の一意性は帰納法により, 容易に示せる
実際, f : N → W も (r-i), (r-ii) を満たすとき,
f (1) = a = f (1);
f (x) = f (x) ⇒ f (S(x)) = ϕ(f (x)) = ϕ(f (x)) = f (x)
帰納法により, ∀x ∈ N, f (x) = f (x)
∴ f = f
写像 f の存在を示すには , そのグラフの存在を示せばよい.
つぎの条件を満たす N × W の部分集合 A 全体のなす集合族を A とする:
(s-i) (1, a) ∈ A,
(s-ii) (x, y) ∈ A ⇒ (S(x), ϕ(y)) ∈ A
N × W ∈ A より A = ∅ なので , Γ = A と定義でき, Γ ∈ A となる
すなわち, Γ は A の最小元
このとき, prN |Γ : Γ → N が全単射であれば , Γ が求める写像のグラフとなる
(全射) (N5 ) を適用して, prN (Γ) = N を示す
(i) Γ は (s-i) を満たすので , 1 ∈ prN (Γ)
(ii) x ∈ prN (Γ) とすると ∃y ∈ W such that (x, y) ∈ Γ
Γ は (s-ii) を満たすので , (S(x), ϕ(y)) ∈ Γ となり, S(x) ∈ prN (Γ)
(N5 ) より, prN (Γ) = N
(単射) D = {x ∈ N | (x, y), (x, z) ∈ Γ ⇒ y = z} とおき, D = N を示せばよい
そのために, (N5 ) を適用する
(i) 1 ∈ D を示すには, (1, y) ∈ Γ ⇒ y = a を示せばよい
y = a とすれば Γ \ {(1, y)} ∈ A — Γ の最小性に矛盾
(ii) x ∈ D ⇒ S(x) ∈ D が成立しないとすると ∃x ∈ D such that S(x) ∈ D
prN (Γ) = N より ∃y ∈ W such that (x, y) ∈ Γ
このとき, Γ は (s-ii) を満たすので , (S(x), ϕ(y)) ∈ Γ
一方, S(x) ∈ D より, ∃z ∈ X such that (S(x), z) ∈ Γ, z = ϕ(y)
このとき, S は単射なので, Γ \ {(S(x), z)} ∈ A — Γ の最小性に矛盾
(N5 ) より, D = N
この再帰定理を用いて , Peano の公理を満たす体系 (N, 1, S) の一意性が示せる.
定理 5.3 Peano の公理を満たす (N, 1, S) は本質的に一意的である. すなわち, (N , 1 , S )
も Peano の公理を満たすならば , つぎを満たす全単射 h : N → N が一意的に存在する:
h(1) = 1 ;
∀x ∈ N, h(S(x)) = S (h(x))
証明 再帰定理 5.2 を X = N , a = 1 , ϕ = S に適応して,
∃1 h : N → N such that ∀x ∈ N, h(S(x)) = S (h(x))
一方, (N , 1 , S ) に対しても再帰定理 5.2 は成立するので ,
∃1 h : N → N such that ∀x ∈ N , h (S (x)) = S(h (x))
再帰定理 5.2 を X = N, a = 1, ϕ = S に適応すれば ,
写像の一意性より, h h = idN が得られる
同様にして, hh = idN ∴ h は全単射で h = h−1
再帰定理 5.2 の証明と同じ議論で , N における加法と乗法の演算 +, · : N2 → N の存在
を示せるが , ここでは再帰定理 5.2 を応用する.
(加法の定義) 再帰定理を N , S ∈ N と写像 N f → S◦f ∈ N に適用して, つぎの
条件を満たす写像 α : N → N が一意的に存在する:
α(1) = S;
∀y ∈ N, α(S(y)) = S◦α(y)
36
このとき, + : N × N → N を x + y = α(y)(x) と定義すれば , つぎの条件が満たされる:
def
(a-i) x + 1 = α(1)(x) = S(x),
(a-ii) x + S(y) = α(S(y))(x) = S(α(y)(x)) = S(x + y).
(乗法の定義) 再帰定理を N , id ∈ N と写像 N f → S◦f ∈ N に適用して , つぎ
の条件を満たす写像 μ : N → N が一意的に存在する:
μ(1) = id ;
∀y ∈ N, μ(S(y)) = α◦μ(y)
このとき, · : N × N → N を x·y = μ(y)(x) と定義すれば , つぎの条件が満たされる:
def
(m-i) x·1 = μ(1)(x) = x,
(m-ii) x·S(y) = μ(S(y))(x) = α(μ(y)(x))x + μ(y)(x) = x + x·y.
数列の漸化式による定義: 再帰定理 5.2 において , W = R の場合, 写像 f : N → R は
実数列 f (1), f (2), · · · に他ならない. この場合, 再帰定理 5.2 は , 初項の値 a1 と漸化式
an+1 = ϕ(an ) を与えることにより, 数列 (an )n∈ が定義できるということを示している.
最初の第 k 項まで a1 , . . . , ak を与え, 漸化式を写像 ψ : Rk → R によって,
an+k = ψ(an , an+1 , . . . , an+k−1 )
と与えることにより, 数列 (an )n∈ を定義することもあるが , この定義の正当性も再帰定
理 5.2 を用いて示せる. 実際, 再帰定理 5.2 において, W = Rk , (a1 , . . . , ak ) ∈ Rk とし ,
ϕ : Rk → Rk をつぎのように定義された写像とする:
ϕ(x1 , . . . , xk ) = (x2 , . . . , xk , ψ(x1 , . . . , xk ))
この場合に得られる写像 f : N → Rk は f (1) = (a1 , . . . , ak ) でつぎの条件を満たす:
(an+1 , . . . , an+k ) = f (n + 1) = ϕ(f (n)) = (an+1 , . . . , an+k−1 , ψ(an , . . . , an+k−1 ))
この条件は , 漸化式 an+k = ψ(an , . . . , an+k−1 ) に他ならない.
初項 a1 を与え, 漸化式を写像 ψ : n∈ Rn → R によって , an+1 = ψ(a1 , . . . , an ) と
与えることにより, 数列 (an )n∈ を定義する場合には , 再帰定理 5.2 を用いて定義の正
当性を示せる. 実際, 再帰定理 5.2 において , W = n∈ Rn , a1 ∈ R ⊂ n∈ Rn とし ,
ϕ : n∈ Rn → n∈ Rn をつぎのように定義された写像とする:
ϕ(x1 , . . . , xn ) = (x1 , . . . , xn , ψ(x1 , . . . , xn ))
この場合に得られる写像 f : N → n∈ Rn は f (1) = a1 でつぎの条件を満たす:
(a1 , . . . , an+1 ) = f (n + 1) = ϕ(f (n)) = (a1 , . . . , an , ψ(a1 , . . . , an ))
この条件は , 漸化式 an+1 = ψ(a1 , . . . , an ) に他ならない.
5.3
整数
整数は , つぎのように定義される N2 = N × N における同値関係 ∼ による同値
類として定義される. すなわち, 商集合 Z = N2 /∼ が整数の集合である:
(x1 , x2 ) ∼ (y1 , y2 ) ⇔ x1 + y2 = x2 + y1
def
37
演習 5.7 上で定義した ∼ が N2 における同値関係であることを示せ.
ヒント N では定義されていない減法は使用不可. 簡約律 (演習 5.2) を参照.
ここでは , (x1 , x2 ) の ∼ による同値類を x1 , x2 と表すが , 実際には , x1 , x2 が
x1 − x2 を意味することを念頭におけば , 理解し易い. 各 x ∈ N を S(x), 1 ∈ Z と
同一視することにより, N ⊂ Z とみなす. 特に , 1 = S(1), 1 と同一視する. また,
0 = 1, 1 ∈ Z と表す.
演算: つぎのように定義される Z 上の加法と乗法は , N 上の演算の拡張であり,
これらの演算に関して Z は可換環になる:
x1 , x2 + y1 , y2 = x1 + y1 , x2 + y2 def
x1 , x2 · y1 , y2 = x1 y1 + x2 y2 , x1 y2 + x2 y1 def
ここで , N 上の演算の拡張であるというのは , x ∈ N と S(x), 1 ∈ Z を同一視し
た時, N において演算を行った後に同一視したものと , 同一視してから Z において
演算を行ったものが同じになるということである. すなわち,
S(x + y), 1 = S(x), 1 + S(y), 1
S(xy), 1 = S(x), 1 · S(y), 1
演習 5.8 上の演算が well-defined であり, N の演算の拡張であることを示せ.
演習 5.9 Z における加法と乗法の結合律, 交換律および分配律を証明せよ.
演習 5.10 Z における加法に関して , さらにつぎが成立することを示せ:19
∀x ∈ Z, x + 0 = x ;
∀x ∈ Z, ∃1 − x ∈ Z such that x + (−x) = 0
演習 5.11 つぎは Z が可換環であることから成立するが , 定義より直接示せ:
∀x, y ∈ Z, (−x)y = x(−y) = −(xy) ;
∀x ∈ Z, x0 = 0x = 0
順序: つぎのように定義される Z における大小関係 は , N における大小関係
の拡張であり, この に関して Z は全順序集合となる:
x1 , x2 y1, y2 ⇔ x1 + y2 x2 + y1
def
ここで , N における大小関係の拡張であるというのは , x ∈ N と S(x), 1 ∈ Z を
同一視した時, 大小関係が変わらないということである. すなわち,
x y ⇔ S(x), 1 S(y), 1
19
これから加法の簡約律が導かれる.
38
演習 5.12 上の が well-defined であり, N の順序の拡張であることを示せ.
演習 5.13 上で定義した が Z 上の全順序となることを示せ.
演習 5.14 x = x1 , x2 ∈ Z に対して , つぎが成立することを示せ:
x > 0 ⇔ x1 > x2
(x < 0 ⇔ x1 < x2 )
これより, つぎが成立する:
x > 0 ⇔ −x < 0 (x < 0 ⇔ −x > 0)
演習 5.15 N ⊂ Z とみなすとき, N = {x ∈ Z | x > 0} となることを示せ.
演習 5.16 Z において, つぎが成立することを示せ:
x < y, z ∈ Z ⇒ x + z < y + z ;
x < y, z > 0 ⇒ xz < yz
ヒント 前半は定義と N における簡約律 (演習 5.2) および演習 5.5.
後半は z = z1 , z2 > 0 とおけば , ∃u ∈ N such that z1 = z2 + u. 後は , 定義と N に
おける簡約律 (演習 5.2, 5.6) および演習 5.5 を適用.
演習 5.17 Z において, つぎの乗法に関する簡約律を証明せよ:
xz = yz, z = 0 ⇒ x = y
ヒント 対偶を示せ. (演習 5.6 を参照)
5.4
有理数
有理数は , つぎのように定義される Z × N における同値関係 ≈ による同値類と
して定義される. すなわち, 商集合 Q = Z × N/≈ が有理数の集合である.
(x1 , x2 ) ≈ (y1 , y2) ⇔ x1 y2 = x2 y1
def
演習 5.18 ≈ が Z × N における同値関係であることを示せ.
ヒント Z では定義されていない除法は使用不可. 簡約律 (演習 5.17) を参照.
ここでは , (x1 , x2 ) の ≈ による同値類を x1 , x2 と表すが , 実際には , x1 , x2 が x1 /x2 を意味することを念頭におけば , 理解し易い. 各 x ∈ Z を x, 1 ∈ Q と
同一視することにより , Z ⊂ Q とみなす. 特に , 0 = 0, 1 および 1 = 1, 1 と同
一視する.
39
演算: つぎのように定義される Q 上の加法と乗法は , Z 上の演算の拡張であり,
これらの演算に関して Q は体になる:
x1 , x2 + y1 , y2 = x1 y2 + x2 y1 , x2 y2 def
x1 , x2 · y1 , y2 = x1 y1 , x2 y2 def
ここで , Z 上の演算の拡張であるというのは , x ∈ Z と x, 1 ∈ Q を同一視した
時, Z において演算を行った後に同一視したものと, 同一視してから Q において
演算を行ったものが同じになるということである. すなわち,
x + y, 1 = x, 1 + y, 1
xy, 1 = x, 1 · y, 1
演習 5.19 上の演算が well-defined であり, Z の演算の拡張であることを示せ.
演習 5.20 Q における加法と乗法の結合律, 交換律および分配律を証明せよ.
演習 5.21 Q における加法と乗法に関して , さらにつぎが成立することを示せ:
∀x ∈ Q, x + 0 = x ;
∀x ∈ Q \ {0}, x1 = x ;
∀x ∈ Q, ∃1 − x ∈ Q such that x + (−x) = 0
∀x ∈ Q \ {0}, ∃1 x−1 ∈ Q such that x·x−1 = 1
順序: つぎのように定義される Q における大小関係 は , Z における大小関係
の拡張であり, この に関して Q は順序体となる:
x1 , x2 y1 , y2 ⇔ x1 y2 x2 y1
def
ここで , Z における大小関係の拡張であるというのは , x ∈ Z と x, 1 ∈ Q を同一
視した時, 大小関係が変わらないということである. すなわち,
x y ⇔ x, 1 y, 1
演習 5.22 上の が well-defined であり, Z の順序の拡張であることを示せ.
演習 5.23 上で定義した が Q 上の全順序となることを示せ.
演習 5.24 Q は上の で順序体となること , すなわち, つぎが成立することを
示せ:
x < y, z ∈ Q ⇒ x + z < y + z ; x < y, z > 0 ⇒ xz < yz
演習 5.25 (有理数の稠密性) Q が稠密であること , すなわち, つぎが成立する
ことを示せ:
∀x < y ∈ Q ∃z ∈ Q such that x < z < y
ヒント
1
2 (x
+ y) に相当する数を z1 , z2 の形で表し , 上の条件を確かめよ.
40
5.5
実数 — Cauchy 列
次の条件を満たす数列 x = (xi )i∈ を Cauchy20 列 (Cauchy sequence) (あるい
は 基本列 (fundamental sequence)) と呼ぶ:21
∀n ∈ N, ∃i0 ∈ N such that i, j i0 ⇒ |xi − xj | < 1/n
有理数の Cauchy 列全体のなす集合を Cs(Q) と書くことにする. これは , Q の部
分集合である. 実数は , つぎのように定義される Cs(Q) における同値関係 によ
る同値類として定義される. すなわち, 商集合 R = Cs(Q)/ が実数の集合である.
(xi )i∈ (yi )i∈ ⇔ ∀n ∈ N, ∃i0 ∈ N such that i i0 ⇒ |xi − yi | < 1/n
def
演習 5.26 上で定義した が Cs(Q) における同値関係であることを示せ.
ここでは , x = (xi )i∈ の による同値類を [x] と表すが , [x] が limi→∞ xi だと
思えばよい. 例えば , 円周率 π は 3.1, 3.14, 3.141, 3.1416, . . . という数列の同値類
√
であり, 2 の平方根 2 は 1.4, 1.41, 1.414, 1.4142, . . . という数列の同値類である.
注意: 実数を有理数列の極限として定義したいが , その極限となる実数は , 今は
存在していない. まず , 収束する数列は Cauchy 列となること , さらに異なる数
列でも同じ極限を持ち得ることに注意せよ. そこで , Cauchy 列となる有理数列
の集合を考え, 同じ極限を持つ数列を同値だとして, その同値類で有理数列の極
限を表すのである. 実際, どんな実数でも a0 ∈ Z と ai ∈ {0, 1, . . . , 9} (i ∈ N)
を取り, 無限小数 a0 .a1 a2 · · · で表せるが , この無限小数は a0 .a1 , a0 .a1 a2 ,
a0 .a1 a2 a3 , . . . , という数列の極限を表す.22 よって , 0.999 · · · = 1 と書くと
き, 違うものを同じとしているように感じ るかもしれないが , 数列 0.9, 0.99,
0.999, . . . の極限が 1 に等しいことを意味しているのであり, 0.333 · · · = 13
と書いているのと同じ意味である.
各 x ∈ Q を定値数列の同値類 [(x, x, . . . )] ∈ R と同一視することにより, Q ⊂ R
とみなす. このとき, ある項から先が同じ数 x ∈ Q になる有理数列 (xi )i∈ の同値
類 [(xi )i∈ ] は x と同一視される.
演算: つぎのように定義される R 上の加法と乗法は , Q 上の演算の拡張であり,
これらの演算に関して R は体になる:
[(xi )i∈ ] + [(yi )i∈ ] = [(xi + yi )i∈ ]
def
[(xi )i∈ ][(yi )i∈ ] = [(xi yi )i∈ ]
def
20
コーシー (Augustin Louis Cauchy, 1789 – 1857)
ここで , ∀ε > 0, ∃i0 ∈ N, . . . , と定義したいところだが , 実数がまだ定義されていないので ,
1/n で考える. r > 0 に対して
ε > 0 の代わりに n , |x| < r ⇔ −r < x < r.
∞
22
a0 .a1 a2 · · · = n=0 10−n an = limn→∞ i=0 10−i ai
21
41
演習 5.27 上の演算が well-defined であり, Q の演算の拡張であることを示せ.
演習 5.28 R における加法と乗法の結合律, 交換律および分配律を証明せよ.
演習 5.29 R における加法と乗法に関して , さらにつぎが成立することを示せ:
∀x ∈ R, x + 0 = x ;
∀x ∈ R, ∃1 − x ∈ R such that x + (−x) = 0 ;
∀x ∈ R \ {0}, ∃1 x−1 ∈ R such that x·x−1 = 1
∀x ∈ R \ {0}, x1 = x ;
順序: つぎのように定義される R における大小関係 は , Q における大小関係
の拡張であり, この により, R は順序体となる:
[(xi )i∈ ] < [(yi )i∈ ] ⇔ ∃n ∈ N, ∃i0 ∈ N such that i i0 ⇒ yi − xi > 1/n
def
[(xi )i∈ ] [(yi)i∈ ] ⇔ [(xi )i∈ ] = [(yi)i∈ ] or [(xi )i∈ ] < [(yi )i∈ ]
def
演習 5.30 上の が Q の順序の拡張であり, R 上の全順序となることを示せ.
ヒント 全順序を示すのには , [(xi )i∈N ] = [(yi )i∈N ] のとき, [(xi )i∈N ] < [(yi )i∈N ] また
は [(xi )i∈N ] > [(yi )i∈N ], すなわち, ∃n ∈ N, ∃i0 ∈ N such that ∀i i0 , yi − xi > 1/n
or ∀i i0 , xi − yi > 1/n となることを示さなければならない. [(xi )i∈N ] = [(yi )i∈N ]
より, ∃m ∈ N, ∀i ∈ N, ∃j > i such that |xj − yj | > 1/m. このことと (xi )i∈N ,
(yi )i∈N が Cauchy 列であることを組合せて考えよ.
演習 5.31 R が順序体となること , すなわち, つぎが成立することを示せ:
x < y ⇒ ∀z ∈ R, x + z < y + z;
x < y, z > 0 ⇒ xz < yz
演習 5.32 (実数における有理数の稠密性) Q が R において稠密であること , す
なわち, つぎが成立することを示せ:
∀x < y ∈ R, ∃z ∈ Q such that x < z < y
ヒント x = [(xi )i∈N ], y = [(yi )i∈N ] とするとき, [(xi )i∈N ] < [(z, z, . . . )] < [(yi )i∈N ]
となる z ∈ Q の存在を示すのだが , ∃n ∈ N, ∃i0 such that i i0 ⇒ xi + 1/n <
z < yi − 1/n となる z ∈ Q を探せば よい. x < y より, ∃m ∈ N, ∃i1 ∈ N such that
i i1 ⇒ yi − xi > 1/m. さらに, (xi )i∈N , (yi )i∈N が Cauchy 列であることより,
∃i0 i1 such that i, j i0 ⇒ |xi − xj |, |yi − yj | < 1/4m. このとき, i i0 に対し
て, xi0 , yi0 , xi , yi の大小を考慮せよ.
定理 5.4 (Archimedes23 の公理) 任意の正の実数 x, y に対して , y < nx となる
自然数 n が存在する.
演習 5.33 任意の正の実数 t に対して, 1/n < t となる自然数 n が存在するこ
とを示し , Archimedes の公理を証明せよ.
23
アルキメデス (Archimedes, 287 B.C.(?)–212 B.C.)
42
ヒント t = [(ti )i∈N ] とすると , t > 0 より, ∃k ∈ N, ∃i0 ∈ N such that ∀i i0 ,
ti > 1/k. このとき, n = 2k が求めるもの.
x, y > 0 に対して, t = y −1 x > 0 に上を適用すれば Archimedes の公理が得られる.
数列 (xi )i∈ に対して , つぎの条件を満たす x ∈ R を (xi )i∈ の極限 (limit) と呼
び , (xi )i∈ は x に収束 (convergent) するという. このことを limi→∞ xi = x また
は xi → x (i → ∞) などと表す.
∀n ∈ N, ∃i0 ∈ N such that i i0 ⇒ |xi − x| < 1/n
演習 5.34 上の定義において , 1/n は ε > 0 で置き換えてもよいことを示せ. す
なわち, 次の条件が上の定義の条件と同値になることを示せ:
∀ε > 0, ∃i0 ∈ N such that i i0 ⇒ |xi − x| < ε
演習 5.35 有理数の Cauchy 列 (xi )i∈ は x = [(xi )i∈ ] ∈ R に収束すること , す
なわち, x = [(xi )i∈ ] = limi→∞ xi を示せ.
ヒント 各 xi は [(xi , xi , . . . )] と同一視していることに注意せよ. ∀n ∈ N, ∃i0 ∈ N
such that i, j i0 ⇒ |xi − xj | < 1/2n (i.e., −1/2n < xi − xj < 1/2n) であるが , xi
は (xi , xi , . . . ) の第 j 項, xj は (xi )i∈N の第 j 項と見なして考えよ.
定理 5.5 (実数の完備性) 実数の Cauchy 列 (xi )i∈ はある実数 x ∈ R に収束する.
演習 5.36 演習 5.35 を用いて , 実数の完備性 (上の定理) を証明せよ.
ヒント xi = [(xi,j )j∈N ] とすると , 演習 5.35 より, ∃n(i) ∈ N such that ∀j n(i),
|xi − xi,j | < 1/i このとき, (xi,n(i) )i∈N ∈ Cs(Q) となり, x = [(xn(i),m(i) )i∈N ] ∈ R を
得る. 演習 5.35 より, x = limi→∞ xi,n(i) に注意すれば , x = limi→∞ xi が示せる.
定理 5.6 (Weierstrass24 の公理) R の空でない部分集合が上に有界であれば上
限を持ち, 下に有界であれば下限を持つ.
演習 5.37 実数の完備性を用いて , Weierstrass の公理を証明せよ.
ヒント A ⊂ R が上に有界の場合 (下に有界の場合も同様), x1 ∈ R を A の上界,
a1 ∈ A とし , 12 x1 + 12 a1 が A の上界であれば , この値を x2 とし , a2 = a1 とする. そ
うでなければ , この値を a2 とし , x2 = x1 とする. x1 , a1 から x2 , a2 を定義した方
法を繰り返すことにより, (xi )i∈N , (ai )i∈N が帰納的に定義できる. このとき, (xi )i∈N
は Cauchy 列となることを示せば , 実数の完備性より x = limi→∞ xi ∈ R を得るが ,
これが A の上限となることが分かる.
24
ワイエルシュトラウス (Karl Theodor Wilhelm Weierstrass, 1815–97)
43
5.6
複素数
複素数は実数の組として定義される. すなわち,
C = R × R = (x, y) x, y ∈ R
が複素数の集合である. ここでは , 各 x ∈ R を (x, 0) ∈ C と同一視することによ
り, R ⊂ C とみなす. 特に 0 = (0, 0), 1 = (1, 0) ∈ C と同一視する. また , i = (0, 1)
と表せば , どんな複素数も (x, y) = x + yi と表せる.
演算: つぎのように定義される C 上の加法と乗法は , R 上の演算の拡張であり,
これらの演算に関して C は体となる.
(x1 , x2 ) + (y1 , y2) = (x1 + y1 , x2 + y2 )
def
(x1 , x2 ) · (y1 , y2 ) = (x1 y1 − x2 y2 , x1 y2 + x1 y2 + x2 y1 )
def
演習 5.38 上の演算は R の演算の拡張であり, (C, +, · ) が体となることを示せ.
順序体 R 上の順序を拡張して , C を順序体とすることは出来ない. C は代数的
閉体となる. すなわち,
• C の元を係数とする代数方程式は必ず C の中に根 (解) を持つ.
これを Gauss25 の定理あるいは代数学の基本定理 (fundamental theorem of algebra) という. この証明はここでは扱わないが , 純粋に代数的なものから位相幾何的
なものまで , 様々な証明が知られている.
5.7
Dedekind の切断による実数の構成
この節では , 実数の一般的な構成法を示す. Q の部分集合の組 (A1 , A2 ) で , つぎの条件
を満たすものを Q の切断 (cut), あるいは , Dedekind26 の切断 (Dedekind cut) と呼ぶ:
(i) A1 = ∅, A2 = ∅ ;
(ii) Q = A1 ∪ A2 ;
(iii) a1 ∈ A1 , a2 ∈ A2 ⇒ a1 < a2
このとき, つぎの３つの場合が可能である:
(a) A1 には最大数があり, A2 には最小数がない;
(b) A1 には最大数がなく, A2 には最小数がある;
(c) A1 には最大数がなく, A2 には最小数がない.
実数は , (a) または (c) をみたす Q の切断として定義される. すなわち, 実数の集合 R は
つぎのように定義される:
R = (A1 , A2 ) (A1 , A2 ) は A2に最小数がない Q の切断
ここで , 切断 (A1 , A2 ) は , 切断の切口 inf A2 (= sup A1 ) を表しているのである.
25
ガウス (Carl Friedrich Gauss, 1777–1855)
デデキント (Julius Wilhelm Richard Dedekind, 1831–1916)
26
44
切断に関する注意: Q の切断 (A1 , A2 ) は , A1 = Q \ A2 より, A2 だけで完全に決ま
るので, つぎの条件を満たす A ⊂ Q を Q の切断と呼び , そのうち最小数がないもの
全体を R と定義することも出来る.
(i) ∅ = A = Q ;
(ii)
a ∈ A, a < b ⇒ b ∈ A
各 x ∈ Q に対して, Ax1 = a ∈ Q a x , Ax2 = a ∈ Q a > x = Q \ Ax1 とすると,
(a) を満たす Q の切断 (Ax1 , Ax2 ) ∈ R が得られる. 実際, x = max Ax1 となる. 各 x ∈ Q を
(Ax1 , Ax2 ) ∈ R と同一視することにより Q ⊂ R とみなす. よって , (c) を満たす Q の切断
が無理数である.
順序: つぎのように定義される R における大小関係 は , Q における大小関係の拡張
であり, この により, R は全順序集合となる:
(A1 , A2 ) (B1 , B2 ) ⇔ A1 ⊂ B1 (⇔ A2 ⊃ B2 )
def
演習 5.39 上の が Q の順序の拡張であり, R 上の全順序となることを示せ.
演習 5.40 Q が R において稠密であること, すなわち, つぎが成立することを示せ:
∀x < y ∈ R, ∃z ∈ Q such that x < z < y
定理 5.7 (実数の連続性) R の切断を Q の切断と同様に定義する (条件 (ii) は R =
A1 ∪ A2 ). このとき, R の切断 (A1 , A2 ) について , A1 に最大数があるか A2 に最小数があ
るかのど ちらかである.
演習 5.41 実数の連続性 (上の定理) を証明せよ.
ヒント (A1 , A2 ) = (A1 ∩Q, A2 ∩Q) は Q の切断で , (a) のときは , max A1 = max A1 ;
(b) のときは , min A2 = min A2 ; (c) のときは , この切断 (A1 , A2 ) の表す実数を z と
y
すれば , ∀x ∈ A1 , ∀y ∈ A2 , Ax1 A1 A1 , すなわち, x < z < y となり, z = max A1
か z = min A2 となる.
演習 5.42 (Weierstrass の公理) R の空でない部分集合が上に有界であれば上限を
持ち, 下に有界であれば下限を持つことを証明せよ.
ヒント A ⊂ R が上に有界の場合 (下に有界の場合も同様), 上界を A2 し , A1 = R\A2
とすると , R の切断 (A1 , A2 ) が得られる. max A1 が存在しないことを示せば , 実数
の連続性より, min A2 = sup A が存在する.
−
演習 5.43 α = (A1 , A2 ) ∈ R に対して, −α = (A−
1 , A2 ) ∈ R を
−
A−
A−
2 = − x x ∈ A1 , x = max A1 ,
1 = Q \ A2
と定義するとき, α > 0 ⇔ −α < 0
(α < 0 ⇔ −α > 0) を示せ.
演算: 2 つの実数 (A1 , A2 ) と (B1 , B2 ) の和 (A1 , A2 ) + (B1 , B2 ) = (C1 , C2 ) をつぎのよ
うに定義する:
C2 = x + y x ∈ A2 , y ∈ B2 , C1 = Q \ C2
def
def
(A1 , A2 ) 0, (B1 , B2 ) 0 の場合に積 (A1 , A2 ) · (B1 , B2 ) = (D1 , D2 ) を次のように定義
する:
D2 = xy x ∈ A2 , y ∈ B2 , D1 = Q \ D2
def
def
一般の場合には , α < 0, β 0; α 0, β < 0; α < 0, β < 0 に応じて, それぞれ
αβ = −((−α)β); αβ = −(α(−β)); αβ = (−α)(−β) と定義する.
45
演習 5.44 上の演算が well-defined であり, Q の演算の拡張であることを示せ.
演習 5.45 R における加法と乗法の結合律, 交換律および分配律を証明せよ.
演習 5.46 R における加法と乗法に関して, さらにつぎが成立することを示せ:
∀x ∈ R, x + 0 = x ;
∀x ∈ R \ {0}, x1 = x ;
∀x ∈ R, ∃1 − x ∈ R such that x + (−x) = 0 ;
∀x ∈ R \ {0}, ∃1 x−1 ∈ R such that x·x−1 = 1
演習 5.47 R が順序体となること, すなわち, つぎが成立することを示せ:
x < y ⇒ ∀z ∈ R, x + z < y + z ;
x < y, z > 0 ⇒ xz < yz
演習 5.48 (Archimedes の公理) 任意の正の実数 x, y に対して , y < nx となる自然
数 n が存在することを証明せよ.
ヒント 0 < n−1 < y −1 x なる n ∈ N を見付ける. Q の切断で y −1 x = (A1 , A2 ) と表
すと , y −1 x > 0 より ∃r ∈ A such that r > 0. このとき, 0 < r < y −1 x より, r ∈ Q
の分数表示を考えよ.
参考書: Dedekind の切断による実数の構成に関しては , つぎの書籍に丁寧な解
説がある:
• 吉永悦男 : 初等解析学 — 実数＋イプシロン・デルタ＋積分, 培風館, 1994.
46
6
集合の濃度
有限個の元しか持たない集合であれば , その元の個数を数えて何個の元を
持つということが出来る. そして , 2 つの集合の元の個数を比較して , 元の個
数が同じとか違うとか , また, 一方が他方より多いとか少ないとかを知ること
が出来る. この章では , 無限個の元を持つ 2 つの集合に対して , どのように元
の個数を比較することが出来るのか , すなわち, 個数としての自然数 (基数) の
無限への拡張を考える. 無限といっても無限に多くの無限があり, それらの間
に大小関係があり, 和や積を考えることも出来るのである. 無限に関する理解
を深め, 有限と無限の違いを明確にする.
6.1
集合の対等, 濃度
集合 X, Y に対して, 全単射 f : X → Y が存在するとき, X は Y と対等
(equipotent) であるといい, X ∼ Y と表す. また, X が Y と対等でないときは ,
X ∼ Y と表す. 集合間の対等であるという関係に関して, つぎの同置関係と同じ
性質が成り立つ:
(1) X ∼ X;
(2) X ∼ Y ⇒ Y ∼ X;
(3) X ∼ Y, Y ∼ Z ⇒ X ∼ Z
集合 A, B の元の個数が有限の場合, 個数を数え上げなくても A ∼ B (元の間に
一対一の対応が付く) ならば , A と B の元の個数は同じである. 実際, A が n 個の
元を持つとき, 元の個数を数え上げることは , {1, 2, . . . , n} から A への全単射を定
義することであり, A ∼ {1, 2, . . . , n} であることに他ならない. 集合の元の個数の
概念を有限でない場合にも拡張して , A ∼ B のとき, A と B は同じ濃度または基
数 (power,27 cardinality, cardinal number) を持つといい, card A = card B と表す.
card A = card B ⇔ A ∼ B ⇔ ∃h : A → B — bijection
def
def
自然数 n ∈ N を集合の濃度を表す標識として用いる:
card A = n ⇔ A ∼ {1, 2, . . . , n}
def
すなわち, card A = n は A が n 個の元を持つという意味である. また, card A = 0
は A が 1 つも元を持たない, つまり A = ∅ を意味する. 自然数と 0 によって表さ
れる濃度を有限濃度 (finite cardinal) と呼ぶ. 一般の集合の濃度を表す標識として ,
ド イツ小文字 l, m, n, p, q, . . . などが用いられる. 自然数の集合 N と実数の集合 R
の濃度は , それぞれ , 可算濃度 (countable cardinal), 連続体の濃度 (the cardinality
of the continuum) と呼ばれ , 特別に ℵ0 と c が用いられる.28 すなわち,
ℵ0 = card N,
27
c = card R
原語はド イツ語の Mächtigkeit.
ℵ はヘブライ文字でアレフと読む. ℵ0 はアレフ・ゼロと読む. c はド イツ文字 (c) でツェ−と
読む.
28
47
濃度の実体: 濃度とは何かを説明せずに , 集合の濃度が等しい (同じ濃度を持
つ) ということを定義した. 濃度は集合の持つ “性質” と考えることも出来る
が , つぎのような “もの” とも考えることが出来る. 集合全体は集合ではない
が , “数学的に範囲のはっきりした集まり” であり, 素朴な定義による “広い意
味での集合” には違いない. 集合全体に限らず, ある種の集合の集まりで集合
ではないものを扱う必要がある. 一般に , ある種の集合から成る “広い意味で
の集合” を類 (class) と呼ぶ. 集合に関する演算は , 類に対しても適応できる
が , 関係 ∈ の左側に集合ではない類は置いてはならない. すなわち, “集合で
はない類が類の元となることはない” という規則を設ける. 集合全体の成す
類 Sets において , 対等という関係は同値関係になり, Sets を同値類に類別で
きる. このとき, 各同値類が濃度であると定義することができる. この定義に
よれば , ℵ0 は N の属する同値類を表し , c は R の属する同値類を表す.
6.2
濃度の大小関係
集合 A, B に対して , 濃度の大小関係をつぎのように定義する:
card A card B ⇔ ∃f : A → B — injection
def
注意: 上の定義において, card A = card A かつ card B = card B のとき,
card A card B ⇔ card A card B を調べる必要がある.
演習 6.1 濃度の大小関係が well-defined であることを示せ. (上記の注意を参照)
定理 6.1 (Bernstein29 の定理) 集合 A から B への単射, および B から A への
単射が存在すれば , A から B への全単射が存在する. すなわち,
card A card B, card B card A ⇒ card A = card B
証明の方針 f : A → B, g : B → A を単射とする. f (A) = B の場合のみ考えれ
ばよい. B0 = B \ f (A)
∞ とおき, Ai = g(Bi−1 ), Bi = f (Ai ) と帰納的に定義して ,
∞
A∗ = i=1 Ai , B∗ = i=0 Bi とすると B∗ = B0 ∪ f (A∗ ), g(B∗ ) = A∗ となる. f は
単射であるから , f (A \ A∗ ) = f (A) \ f (A∗ ) = (B \ B0 ) \ f (A∗ ) = B \ B∗ . よって,
f |A \ A∗ : A \ A∗ → B \ B∗ および g|B∗ : B∗ → A∗ は全単射. これらを用いて , A
から B への全単射を定義する.
A1
A
f
g
B
29
g
B0
A2
f
g
B1
f
f (A)
ベルンシュタイン (Sergei Natanovich Bernstein, 1880–1968)
48
g
B2
対等という言葉を用いれば , Bernstein の定理はつぎのようになる.
系 6.2 A が B のある部分集合と対等であり, B が A のある部分集合と対等であ
るならば , A は B と対等である.
定理 4.1 を用いると Bernstein の定理はつぎのように言い換えれる.
系 6.3 (1) A から B への単射と全射が (別々に ) 存在すれば , A から B への全単
射が存在する.
(2) A から B への全射, および B から A への全射が存在すれば , A から B への
全単射が存在する.
濃度の大小関係に関して , 定義と Bernstein の定理より, つぎの順序と同じ性質
が成り立つ:
(1) m m;
(2) m n, n m ⇒ m = n;
(3) m n, n p ⇒ m p
濃度 m, n に対して , m n であって , m = n のときには , m < n と書く. つぎの
定理は濃度の比較定理と呼ばれる:
定理 6.4 (濃度の比較定理) 濃度の大小関係に関して , 任意の 2 つの濃度 m, n は
比較可能である. すなわち, m n または n m が成立する.
注意: この定理の証明は 7.4 節で与えるが , 7 章で証明する整列定理と整列集
合の比較定理の系として得られる. 整列定理は Zorn の補題を用いて示され
るが , この定理は Zorn の補題を用いて直接証明することもできる.
6.3
可算集合と非可算集合
有限濃度を持つ集合を有限集合 (finite set) といい , 有限でない集合を無限集合
(infinite set) という. また, 集合 A が可算濃度を持つとき, すなわち, card A = ℵ0
のとき, A を可算集合 (countable set, enumerable set) という. 可算集合 A は N
と対等となるので , 全単射 h : N → A がある. 各 i ∈ N に対して , h(i) = ai とす
れば , A = {ai | i ∈ N} と表せる. 従って , その元に 1, 2, . . . と番号付けができる集
合が可算集合である.
定理 6.5 どんな無限集合 X に対しても, N から X への単射 h : N → X が存在
する. すなわち, どんな無限集合も必ず可算部分集合を含む.
証明の方針 X を無限集合と x1 ∈ X を取る. 互いに異なる元 x1 , . . . , xn ∈ X が取
れたとすると , X = {x1 , . . . , xn } より, xn+1 ∈ X \ {x1 , . . . , xn } が取れる. 帰納法に
より, xi ∈ X (i ∈ N) が xi = xj (i = j) となるように取れる. {xi | i ∈ N} ⊂ X が
求めるもの.
49
注意: 上の議論には 選出公理 が関係しているが , 一般的に上のような証明で許され
る. 厳密には , 各 i ∈ N に対して, xi が存在することと集合 {xi | i ∈ N} あるいは点
列 (xi )i∈N が存在することには違いがある. このことを意識すれば , つぎのように証
明すればよい.
無限集合 X の有限部分集合全体を Fin(X) とする. 選出公理より, ϕ : Fin(X) → X
で ϕ(A) ∈ X \ A となる写像が取れる. 写像 h : N → X を h(1) = ϕ(∅) (= x1 ),
h(n + 1) = ϕ({h(1), . . . , h(n)}) と帰納的 (再帰的) に定義できる. このとき, h は単
射となり, h(N) は X の可算部分集合となる.
写像 h に関しても厳密には再帰定理による. すなわち, ϕ̃ : Fin(X) → Fin(X) を
ϕ̃(A) = A ∪ {ϕ(A)} と定義して, 再帰定理を適応すれば , 写像 h : N → Fin(X)
で h (1) = {x1 } かつ h (n + 1) = ϕ̃(h (n)) となるものが一意的に決まる. ここで ,
ϕ̃(h (n)) \ h (n) = {ϕ(h (n))} なので , 写像 h : N → X は h(n) = ϕ(h (n)) と定義
できる.
可算部分集合を含む集合は無限集合であるから , 上の定理 6.5 の逆も成立する.
よって , つぎが成立する:
X — infinite ⇔ card X ℵ0
こうして , 可算濃度は最小の無限濃度といえる.
定理 6.6 無限集合は , その自身と対等となる真部分集合を含むが , 有限集合は , そ
のどんな真部分集合とも対等にならない.
証明の方針 前半は, 定理 6.5 より, 無限集合 A が可算部分集合 B を含むことに注
意. N ∼ N \ {1} より, ∃b ∈ B, B ∼ B \ {b}. これを用いて , A ∼ A \ {b} が示せる.
後半は , 演習 3.7 を用いることができる.
この定理によれば , その自身と対等となる真部分集合を含むか含まないかによっ
て , その集合が無限であるか有限であるかが決まる. すなわち, その自身と対等と
なる真部分集合を含む集合は無限集合であり, そのどんな真部分集合とも対等にな
らない集合は有限集合である.
演習 6.2 無限集合から有限部分集合を除いても, 濃度は変わらないことを示せ.
ヒント 上の定理の証明 (後半) を参考にせよ.
演習 6.3 N2 = N × N は可算集合であることを示せ.
ヒント 対応 (m, n) → 2m−1 (2n − 1) は N2 から N への全単射.
(別の方法) N2 の元を N で番号付けることにより, N から N2 への全単射が定義で
きる.
演習 6.4 Z と Q が可算であることを示せ.
ヒント Bernstein の定理の系 6.3(1) が適用できる.
50
集合 X は , 有限または可算であるとき, 高々可算 (at most countable) であると
いい, 高々可算でないとき, 非可算 (uncountable) であるという. すなわち,
X — at most countable ⇔ card X ℵ0
X — uncountable ⇔ card X > ℵ0
演習 6.5 高々可算な集合に関して , つぎを示せ:
(1) 2 つの高々可算な集合の直積集合は高々可算である. すなわち,
card A, card B ℵ0 ⇒ card A × B ℵ0
(2) それぞれ高々可算である集合の高々可算な和集合は高々可算である. すなわち,
Aλ ℵ0
card Λ ℵ0 , ∀λ ∈ Λ, card Aλ ℵ0 ⇒ card
λ∈Λ
(3) 無限集合に高々可算な集合を加えても濃度は変わらない. すなわち,
card A ℵ0 , card B ℵ0 ⇒ card A ∪ B = card A
ヒント (1) は , A × B から N2 への単射を作れ . (2) は , Λ × N から λ∈Λ Aλ への
全射を作れ . (3) を示すのに A ∩ B = ∅ と仮定してよい. A の可算部分集合を C と
すれば , card C = card C ∪ B となる. これを用いて, A ∼ A ∪ B を示す.
演習 6.6 R \ Q ∼ R を示せ.
ヒント 演習 6.5(3) が適用できる.
定理 6.7 R は非可算集合である. すなわち, c > ℵ0 である.
証明の方針 どんな写像 h : N → R も全射とはならないことを示す. 各 h(n) を 10
進法 無限小数 展開でつぎのように一意的に表す:30
h(n) = h0 (n) +
∞
10−i hi (n), h0 (n) ∈ Z, hi (n) = 0, 1, . . . , 9
i=1
各 i ∈ N に対して
, hi (i) が奇数なら xi = 2, hi (i) が偶数なら xi = 1 とする. この
∞
とき x = i=1 10−i xi ∈ h(N).
上の証明で用いられた論法は , Cantor31 の対角線論法 (Cantor’s diagornal process) と呼ばれている. つぎの定理の証明にも同様の論法が用いられる:
定理 6.8 (Cantor の定理) 任意の集合 X に対して , card P(X) > card X.
30
31
例えば , 1 は 0.999 · · · と表す.
カントール (Georg Ferdinand Ludwig Philipp Cantor, 1845–1918)
51
証明の方針 x → {x} により X から P(X) への単射が得られ るので card X card P(X). よって, どんな写像 h : X → P(X) も全射とはならないことを示せばよ
いが , A = {x ∈ X | x ∈ h(x)} ∈ P(X) を考えれば , A ∈ h(X).
Cantor の逆理 (パラド クス): Russell の逆理により, “すべての集合の集ま
り” Ω を集合すると矛盾が生じたが , 上の定理を用いると濃度に関する別の矛
盾が生じる. もし Ω が集合ならば Ω の部分集合も集合であるから , Ω の元と
なる. すなわち, P(Ω) ⊂ Ω となり, card P(Ω) card Ω. これは上の定理に
矛盾する.
定理 6.5 によれば , ℵ0 は最小の無限濃度である. 最小の非可算濃度を ℵ1 と表す
が , 定理 6.7 の主張は c ℵ1 に他ならない. つぎの主張を連続体仮説32 (continuum
hypothesis) という:
c = ℵ1
連続体仮説は証明不可能: K. Gödel33 と P.J. Cohen34 により, この連続体仮
説は肯定も否定も出来ないことが示された.
[補足事項]
Peano の体系の存在: 定理 6.6 によれば , 無限集合はその真部分集合と対等な集合であ
る. このような無限集合が存在することを用いて , Peano の体系の存在が示せる.
無限集合 X が存在すれば , 全射ではない単射 f : X → X が存在する
a ∈ X \ f (X) を取り, X の部分集合族 A をつぎのように定義する:
A = {A ⊂ X | a ∈ A, f (A) ⊂ A}.
X ∈ A より A = ∅ なので , N = A が得られ , N ∈ A となる
f (N ) ⊂ N より f |N : N → N を得る
このとき, (N, a, f |N ) は Peano の公理 (N3 ), (N4 ), (N5 ) を満たす
実際, (N3 ) と (N4 ) は明らか
(N5 ): A ⊂ N で (i) a ∈ A かつ (ii) x ∈ A ⇒ f (x) ∈ A とすれば ,
A ∈ A より N ⊂ A ∴ A = N
6.4
濃度の演算
濃度の和: 濃度 m, n の和 m + n を , 集合 A, B で card A = m, card B = n かつ
A ∩ B = ∅ となるものを取り, つぎのように定義する:
m + n = card(A ∪ B)
演習 6.7 上の定義が well-defined であることを示せ.
32
仮説はかつて仮設と書いた .
ゲーデル (Kurt Gödel, 1906–78)
34
コーエン (Paul Joseph Cohen, 1934– )
33
52
ヒント 定義において , 条件を満たす集合 A, B が取れること, また, そのような集合
A, B の取り方によらずに濃度 m + n が決まることを示せ.
濃度の和に関して , 以下の基本的な性質が成り立つ:
(1) m + 0 = m
(2) m + n = n + m
(3) (m + n) + p = m + (n + p)
(4) m m , n n ⇒ m + n m + n
上の (1)–(3) は定義から自明 (各自で確認せよ).
演習 6.8 上記の基本的性質 (4) の証明を与えよ.
可算集合と高々可算な集合の和集合は可算 (演習 6.5(2)) なので , 任意の n < ℵ0
に対して, n + ℵ0 = ℵ0 であり, ℵ0 + ℵ0 = ℵ0 であるが , 一般につぎの定理が成り
立つ.
定理 6.9 濃度 m, n に対して , m ℵ0 かつ n m のとき,
m+n=m
注意: Zorn の補題と呼ばれる定理が必要なので, この定理 6.9 の証明は後で
与える (7.4 節).
濃度の積: 濃度 m, n の積 mn を , 集合 A, B で card A = m, card B = n となる
ものを取り, つぎのように定義する:
mn = card(A × B)
演習 6.9 上の定義が well-defined であることを示せ.
ヒント 定義において , 集合 A, B の取り方によらずに濃度 mn が決まることを示せ.
濃度の積に関して , 以下の基本的な性質が成り立つ:
(1) m · 0 = 0, m · 1 = m
(2) mn = nm
(3) (mn)p = m(np)
(4) (m + n)p = mp + np
(5) m m , n n ⇒ mn m n
上の (1), (4) は定義から自明; (2), (3) も簡単 (各自で確認せよ).
演習 6.10 上記の基本的性質 (5) の証明を与えよ.
53
定理 6.10 互いに交わらない集合の族 (Aλ )λ∈Λ において , card Λ = n かつ各 λ ∈ Λ
に対して , card Aλ = m のとき,
Aλ = mn
card
λ∈Λ
証明の方針 card A = m となる集合を 1 つ取り, A × Λ から card
射を作る.
λ∈Λ Aλ
への全単
上の定理において , Λ が有限の場合を考えれば , 濃度の和と積に関して , つぎの
関係が得られる:
m
· · + m = mk
+ ·
k個
可算集合と高々可算な集合の直積は可算 (演習 6.5(1)) なので , 任意の n < ℵ0 に
対して , nℵ0 = ℵ0 であり, ℵ0 ℵ0 = ℵ0 であるが , 一般につぎの定理が成り立つ.
定理 6.11 濃度 m, n に対して , m ℵ0 かつ 1 n m のとき,
mn = m
注意: 定理 6.9 と同様に Zorn の補題が必要なので , この定理 6.11 の証明も
後で与える (7.4 節).
濃度の巾: 濃度 m, n に対して , 巾 n を , 集合 A, B で card A = m, card B = n
となるものを取り, つぎのように定義する:
n = card B A
演習 6.11 上の定義が well-defined であることを示せ.
ヒント 定義において, 集合 A, B の取り方によらずに濃度 nm が決まることを示せ.
濃度の巾に関して , 以下の基本的な性質が成り立つ:
(1) n1 = n, 1 = 1
(2) p p = p+
(3) (mn) = m n
(4) (p ) = p
(5) m m , n n ⇒ n n 上の (1) は定義から自明 (各自で確認せよ).
演習 6.12 上記の基本的性質 (2)–(5) の証明を与えよ.
54
定理 6.12 集合の族 (Aλ )λ∈Λ において, card Λ = n かつ各 λ ∈ Λ に対して,
card Aλ = m であれば ,
card
Aλ = m
λ∈Λ
証明の方針 card A = m となる集合を 1 つ取り, AΛ から card
を作る.
λ∈Λ
Aλ への全単射
上の定理において , Λ が有限の場合を考えれば , 濃度の積と巾に関して , つぎの
関係が得られる:
m
· · m = mk
·
k個
定理 6.13 集合 X に対して ,
card P(X) = card 2X = 2card X
(ここで , 2 = {0, 1})
証明の方針 濃度の巾の定義から , 定理 3.1 に帰着.
定理 6.14 c = 2ℵ0 .
証明の方針 写像 ϕ, ψ : {0, 1}N → [0, 1] をつぎのようにと定義する:
ϕ(f ) =
∞
2−i f (i) ;
ψ(f ) =
∞
i=1
3−i f (i).
i=1
ϕ が全射であり, ψ が単射であることを示せば , Bernstein の定理より, card{0, 1}N =
card[0, 1] = card R が得られる.
任意の 2 n < ℵ0 に対して,
2ℵ0 nℵ0 ℵℵ0 0 (2ℵ0 )ℵ0 = 2ℵ0 ℵ0 = 2ℵ0
であるから , 2ℵ0 = nℵ0 = ℵℵ0 0 となるが , 一般につぎの定理が成り立つ:
定理 6.15 濃度 m, n に対して , m ℵ0 かつ 2 n m のとき,
n = 2
演習 6.13 濃度の巾に関する基本的な性質と定理 6.8, 6.11, 6.13 を用いて, 上の
定理 6.15 を証明せよ.
0
ヒント 上に述べた 2ℵ0 = nℵ0 = ℵℵ
0 の証明を参照.
一般連続体仮説: 定理 6.14 によれば , 連続体仮説は ℵ1 = 2ℵ0 となり, ℵ0 <
m < 2ℵ0 となる濃度 m が存在しないことを主張している. 任意の濃度 n に
対して n < m < 2 となる濃度 m が存在しないとう主張を一般連続体仮説
(generalized continuum hypothesis) という. K. Gödel と P.J. Cohen によ
り, 連続体仮説と同様に , 一般連続体仮説も肯定も否定も出来ないことが示さ
れた.
55
整列集合と Zorn の補題
7
この章では , 4.3 節で定義を与えた順序集合を扱うが , 集合論における非常
に重要な整列集合の概念を導入する. 自然数に関する命題を証明する場合, 帰
納法は非常に有用であるが , この整列集合においては , 帰納法を拡張した超限
帰納法が使える. また, 数学の様々な分野において広く用いられている Zorn
の補題と呼ばれる定理を証明し , これを応用して, “どんな集合の上にも順序
を入れて整列集合に出来る” という整列定理と , 6 章で述べた濃度に関する定
理 6.4, 6.9, 6.11 の証明を与える.
7.1
順序同型
順序集合 X = (X, X ), Y = (Y, Y ) に対して , つぎ の条件を満たす全単射
f : X → Y を順序同型写像 (order isomorphism) というが , このような f が存在
するとき, X は Y に順序同型 (order isomorphic) であるといい, X Y と表す:
∀x, x ∈ X, x X x ⇔ f (x) Y f (x )
定義から明らかに , 順序同型写像の逆写像も順序同型写像となり, 順序同型写像の合
成写像も順序同型写像となる. このことから , 順序集合 X = (X, X ), Y = (Y, Y )
Z = (Z, Z ) の順序同型に関して , 同値関係と同じつぎの性質が成り立つ:
(1) X X;
(2) X Y ⇒ Y X;
(3) X Y, Y Z ⇒ X Z
順序集合 X, Y が互いに順序同型となるとき, X と Y は同じ順序型 (order type)
を持つといい, ord X = ord Y と書く.
ord X = ord Y ⇔ X Y ⇔ ∃h : X → Y — order isomorphism
def
def
全単射とは限らないが , 順序集合の間の写像 f : X → Y が順序同型写像と同じ
条件を満たすとき, 順序単射 (order injection) という.
演習 7.1 その名の示すように , 順序単射 f : X → Y は必ず単射となり, その像
f (X) は Y の順序部分集合として , X に順序同型となることを示せ.
つぎの条件を満たす写像 f : X → Y は順序を保つ (order preserving) という:
∀x, x ∈ X, x X x ⇒ f (x) Y f (x )
順序単射は順序を保つ単射であるが , 順序を保つ単射は順序単射とは限らない. 実
際, X = (P({0, 1}), ⊂), Y = (N, ) とし , f : X → Y をつぎのように定義すれば
f は順序単射とはならない順序を保つ単射である:
f (∅) = 1, f ({0}) = 2, f ({1}) = 3, f ({0, 1}) = 4
56
演習 7.2 順序集合の間の写像 f : X → Y に対して , つぎの条件は互いに同値
になることを示せ:
(a) f は順序同型写像;
(b) f は全単射であり, f と f −1 は順序を保つ;
(c) f は全射となる順序単射.
演習 7.3 どんな開区間 (a, b) も R と順序同型になることを示せ.
ヒント まず , (−1, 1) (あるいは , 他のある開区間) から R への順序同型写像を作って
見よ.
演習 7.4 N, Z, Q, R は , どの 2 つも互いに順序同型にはならないことを示せ.
ヒント 順序同型で保たれる性質で, それぞれに特有なものを見付けよ.
集合 X 上の実数値関数全体の成す集合 RX 上に順序を , つぎのように定義する:
f g ⇔ ∀x ∈ X, f (x) g(x)
def
演習 7.5 上に定義した R
X
上の関係 が順序となることを示せ.
演習 7.6 集合 X に対して , A ⊂ X に特性関数 χA : X → {0, 1} ⊂ R を対応さ
せることにより, 巾集合 P(X) = (P(X), ⊂) から RX への順序単射が得られるこ
とを示せ.
7.2
整列集合
以下, 断らない限り, 順序集合の順序は で表す. つぎの性質を持つ順序集合
W を整列集合 (well-ordered set), その順序を整列順序 (well-order) という:
∅ = A ⊂ W ⇒ ∃ min A
この定義から直ちに分かるように , 整列集合のどんな部分順序集合も整列集合にな
る. 自然数の集合 N は整列集合である (演習 5.4). 空集合も整列集合である.
演習 7.7 整列集合は全順序集合となることを示せ.
ヒント x, y ∈ X に対して, {x, y} ⊂ X を考えよ.
整列集合 W と a ∈ W に対して , つぎのように定義される部分集合 W (a) を a
による W の切片 (initial segment) という:
W (a) = {x ∈ W | x < a}
特に , a = min W のとき W (a) = ∅ である.
全順序集合 X において, a < b となる X の元に対して , a < x < b となる X の
元が存在しないとき, a は b の直前 (predecessor) の元, b は a の直後 (successor)
の元と呼ぶ.
57
演習 7.8 整列集合 W の切片に関して , つぎを示せ:
(1) ∀a ∈ W, sup W (a) = a または sup W (a) は a の直前の元
(2) W (a) ⊂ W (b) ⇔ a b
(3) ∀a < b ∈ W, W (b)(a) = W (a)
演習 7.9 整列集合の間の順序同型写像 f : W → W に対して , つぎが成り立つ
ことを示せ:
∀a ∈ W, f (W (a)) = W (f (a))
補題 7.1 整列集合 W においては , つぎの条件を満たす A ⊂ W は W 自身に限る:
a ∈ W, W (a) ⊂ A ⇒ a ∈ A
証明の方針 A = W とすると , W \ A = ∅. ∴ ∃a = min(W \ A). このとき, W (a) ⊂ A
となるが , 上の条件を適用して矛盾を出す.
整列集合の代表的にな例である N には , (数学的) 帰納法があり, n ∈ N に関す
る命題を証明するのに非常に有用な道具となっている. 整列集合 W に対しては ,
これに対応する超限帰納法 (transfinite induction) がある.
定理 7.2 (超限帰納法) 整列集合 W の元 x ∈ W に関する条件 P (x) が与えられ
ているとき , すべての x ∈ W に対して , P (x) が成立することを証明するのに , 以
下のことを示せば十分である:
(∗) ∀x < a, P (x) が成立 ⇒ P (a) が成立
証明 A = {x ∈ W | P (x)} とおけば , (∗) は “W (a) ⊂ A ⇒ a ∈ W ” となる.
上の補題より, A = W , すなわち, ∀x ∈ W , P (x) が成立する.
注意: 上の条件 (∗) は P (min W ) が成立することを含んでいる.
補題 7.3 (切片の特徴付け ) 整列集合 W において, A W が切片になるために
は , つぎの条件を満たすことが必要十分である:
x ∈ A, y ∈ W, y < x ⇒ y ∈ A (i.e., ∀x ∈ A, W (x) ⊂ A)
証明の方針 切片 W (a) が上の条件を満たすのは明らか. 逆に , 条件を満たす A W
に対して, a = min(W \ A) とおけば , A = W (a) が背理法で示せる.
補題 7.4 整列集合 W の自己順序単射 f : W → W はつぎの性質を持つ:
∀x ∈ W, x f (x)
証明の方針 M = {x ∈ W | f (x) < x} = ∅ を示せばよい. M = ∅ と仮定すると
∃a = min M . f が順序単射より, f (a) ∈ M が示せて矛盾が導ける.
58
補題 7.5 整列集合 W において , つぎが成り立つ:
(1) ∀a ∈ W, W W (a)
(2) a = b ∈ W ⇒ W (a) W (b)
証明の方針 順序同型写像が存在したとして, 補題 7.4 より矛盾を出す.
定理 7.6 整列集合 W , W が順序同型であれば , W から W への順序同型写像は
一意的に決まる. 特に , W から W 自身への順序同型写像は恒等写像に限る.
証明の方針 f, g : W → W を順序同型写像として, 各 a ∈ W に対して f (a) = g(a)
を示すのに, 補題 7.5(2) より, W (f (a)) W (g(a)) を示せばよいが , 演習 7.9 が適
用できる.
補題 7.7 整列集合 W , W が順序同型であれば , 任意の a ∈ W に対して , W (a) W (a ) となる a ∈ W が一意的に決まる.
証明の方針 f : W → W を順序同型写像とすれば , W (a) W (f (a)) より a = f (a)
とすればよい. 一意性は補題 7.5(2) を適用.
つぎの定理は整列集合の比較定理と呼ばれる:
定理 7.8 (整列集合の比較定理) 任意の整列集合 W , W に対して , つぎの 3 つの
場合のうちいずれか 1 つだけが成り立つ:
(1) W W (2) ∃a ∈ W , W W (a )
(3) ∃a ∈ W, W (a) W 証明の方針 補題 7.5(1) を用いれば , 3 つの場合のいずれの 2 つも両立しないことが
示せる. 3 つの場合のいずれか 1 つが成り立つことを示すために , A ⊂ W , A ⊂ W をつぎのように定義する:
A = {x ∈ W | ∃x ∈ W , W (x) W (x )},
A = {x ∈ W | ∃x ∈ W, W (x) W (x )}.
補題 7.7 と 7.3 を用いて , A, A はそれぞれ W , W に等しいか, またはそれらの切片
となることが示せる. 補題 7.5(2) を用いて , 全単射 f : A → A で , ∀x ∈ A, W (x) W (f (x)) を満たすものが得られ , さらに補題 7.7 を用いれば , f が順序同型写像で
あることも示せ, A A となる.
つぎの 4 つの場合が考えられる: (1) A = W , A = W ; (2) A = W , ∃a ∈ W , A =
W (a ); (3) A = W , ∃a ∈ W, A = W (a); (4) ∃a ∈ W, A = W (a), ∃a ∈ W , A =
W (a ). (1), (2), (3) のそれぞれの場合には , 対応する結論が得られ , (4) の場合には
矛盾があり, 生じ得ない.
59
7.3
Zorn の補題と整列定理
順序集合 X は , その任意の (空でない) 全順序部分集合が上に有界になるとき,
帰納的 (inductive) であるという. つぎの定理は Zorn35 の補題 (Zorn’s lemma) と
呼ばれ , 存在定理を証明するのに非常に便利である:
定理 7.9 (Zorn の補題) 帰納的順序集合 X には極大元が存在する.
証明の概略 X が極大元を持たないと仮定して, 矛盾を導く. W を X の整列部分集
合全体とする. このとき, ∅ ∈ W と見なす. X は帰納的なので , 任意の W ∈ W は上
に有界だが , W のどの上界も極大ではないので, 選出公理より, つぎの性質を持つ写
像 ϕ : W → X が存在:
∀W ∈ W, ∀x ∈ W, x < ϕ(W )
(ϕ(W ) は W の上界で W に含まれないもの )
この ϕ を用いて , つぎのように Wϕ ⊂ W を定義:
Wϕ = {W ∈ W | ∀x ∈ W, x = ϕ(W (x))}
このとき, ϕ(∅) = x0 ∈ X とすると {x0 } ∈ Wϕ より, Wϕ = ∅.
(1) 互いに異なる W, W ∈ Wϕ に対して, 一方が他方の切片となる.
∵) 必要であれば W と W を入れ 替えて, W \ W = ∅ としてよい.
∃x = min(W \ W ). このとき, W (x) ⊂ W となるが , W = W (x) と仮
定すると , ∃y = min(W \ W (x)). このとき, W (y) ⊂ W (x). 補題 7.3
より, W (y) = W (x) または W (y) は W (x) の切片であることが分か
る. W (y) = W (x) のとき, y = ϕ(W (y)) = ϕ(W (x)) = x ∈ W となり
矛盾. ∃z ∈ W (x) such that W (y) = W (z) のときも , y = ϕ(W (y)) =
ϕ(W (z)) = z ∈ W (x) となり矛盾. 従って, W = W (x).
(2) W0 = Wϕ ∈ Wϕ
∵) (W0 ∈ W) ∅ = ∀A ⊂ W0 , ∃W ∈ Wϕ such that A ∩ W = ∅.
∴ ∃a = min(A ∩ W ). このとき, (1) により, a = min A が示せる.
(W0 ∈ Wϕ ) ∀x ∈ W0 , ∃W ∈ Wϕ such that x ∈ W . このとき, (1) によ
り, W0 (x) = W (x) が示せる. ∴ ϕ(W0 (x)) = ϕ(W (x)) = x.
(2) より, W0 ∪ {ϕ(W0 )} ∈ Wϕ が示せ, W0 ∪ {ϕ(W0 )} ⊂
W0 — ϕ の取り方に矛盾. 故に , X は極大元を持つ.
Wϕ = W0 より ϕ(W0 ) ∈
注意: 上の証明では , 整列部分集合が上に有界であることしか用いていない.
上に概説した証明は , 参考書である 松阪和夫著「集合・位相入門」(岩波書店)
の証明とは異なり, 下の論文に基づくものである:
J. Lewin, A simple proof of Zorn’s lemma, Amer. Math. Monthly
98 (1991), 353–354.
Zorn の補題の証明は , この他にも様々な方法があり, それぞれアイデアがあっ
て興味深い.
35
ツォルン (Max A. Zorn, 1906–93)
60
扱っている集合が整列集合になれば , 超限帰納法が使えて非常に便利である. つ
ぎの定理はそのことが可能であることを示しており, (Zermelo36 の) 整列定理 (wellordering theorem) と呼ばれ , Zorn の補題 (定理 7.9) を適用して証明できる:
定理 7.10 (整列定理) どのような集合 X もある順序で整列順序となる.
証明の方針 X の空でない部分集合 W とその上に定義された整列順序 の組 (W, )
全体からなる集合を W とし , W 上につぎのように順序を定義する:
(W, ) (W , ) ⇔ (W, ) = (W , ) or (W, ) は (W , ) の切片
def
このとき, W = (W, ) が帰納的順序集合となることを示し Zorn の補題を適用. W
は極大元 (W0 , 0 ) を持つが , 極大性を利用して X = W0 が示せて, 結果を得る.
これまで , 選出公理 ⇒ Zorn の補題 ⇒ 整列定理と証明を行ってきたが , 整列定
理から選出公理が簡単に導くことが出来, 選出公理, Zorn の補題, 整列定理は互い
に同値な命題といえる.
整列定理 ⇒
選出公理の証明 (Aλ )λ∈Λ を各 Aλ が空ではない集合族とする. 整列定
理を X = λ∈Λ Aλ に対して適用し , X を整列集合とすれば , 選出関数 f : Λ → X
が f (λ) = min Aλ と定義できる.
7.4
Zorn の補題の応用
ここで , 6 章で証明を与えずに述べた 3 つの定理 6.4, 6.9, 6.11 の証明を与える.
まず , 定理 6.4 である濃度の比較定理は , 整列定理と整列集合の比較定理を用いれ
ば簡単に示せる.
濃度の比較定理の証明 任意の濃度 m, n に対して, m = card X, n = card Y となる
集合 X, Y を取り, 整列定理を適用して整列集合とする. このとき, 整列集合の比較
定理より, (1) X Y , (2) X は Y の切片に順序同型, (3) Y は X の切片に順序同型,
のどれか 1 つが成り立つ. (1), (2), (3) に応じて, m = n, m n, m n が得られる.
演習 7.10 Zorn の補題を用いて , 濃度の比較定理を直接証明せよ.
ヒント 上記の証明のように集合 X, Y を取り, X の部分集合 A と単射 f : A → Y
の組 (A, f ) 全体からなる集合を M とする. X の部分集合として, 一点集合を考えれ
ば , M = ∅ が分かる. M につぎのように順序を定義して, Zorn の補題を適用:
(A, f ) (A , f ) ⇔ A ⊂ A and f = f |A
def
M の極大元 (A0 , f0 ) に対して, A0 = X であれば m n, そうでなければ f0 (A0 ) = Y
となり, n m が得られる.
Zorn の補題を用いて , 定理 6.9, 6.11, すなわち, つぎの証明を与える:
36
ツェルメロ (Ernst Friedrich Ferdinand Zermelo, 1871-1953)
61
(1) m ℵ0 , n m ⇒ m + n = m (定理 6.9);
(2) m ℵ0 , 1 n m ⇒ mn = m (定理 6.11).
(1) では , m m + n m + m = 2m が成り立つので , つぎの定理に帰着する:
定理 7.11 m ℵ0 ⇒ 2m = m.
証明の方針 m = card X とし , X の部分集合 A と全単射 f : A → A × {0, 1} の組
(A, f ) 全体からなる集合を M とする. m ℵ0 = 2ℵ0 より, M = ∅ が示せる. M に
つぎのように順序を定義して, Zorn の補題を適用:
(A, f ) (A , f ) ⇔ A ⊂ A and f = f |A
def
M の極大元 (A0 , f0 ) に対して, X \ A0 が可算集合を含まないことが示せる. よって,
X \ A0 が有限となり, card A0 = card X から結果を得る. (演習 6.2 参照)
(2) では , m mn mm = m2 が成り立つので , つぎの定理に帰着する:
定理 7.12 m ℵ0 ⇒ m2 = m.
証明の方針 m = card X とし , X の部分集合 A と全単射 f : A → A2 の組 (A, f )
全体からなる集合を M とする. m ℵ0 = ℵ20 より, M = ∅ が示せる. M に前定理
のように順序を定義して, Zorn の補題が適用. M の極大元 (A0 , f0 ) に対して, その
極大性と前定理を利用して, X \ A0 が A0 と対等な集合を含まないことが示せる. こ
うして , card(X \ A0 ) < card A0 となり, 定理 6.9 から card A0 = card X となるの
で , 結果を得る.
線形空間 V において , 部分集合 M がつぎの条件を満たすとき 1 次独立 (linearly
independent) であるという:
∀x1 , . . . , xn ∈ B, xi = xj (i = j), ∀t1 , . . . , tn ∈ R,
t1 x1 + · · · + tn xn = 0 ⇒ t1 = · · · = tn = 0.
また, V の任意の元が M の有限個の元の 1 次結合として一意的に表せるとき, す
なわち, つぎの条件を満たすとき, M は V を生成する (generate) という:
∀x ∈ V, ∃x1 , . . . , xn ∈ B, ∃t1 , . . . , tn ∈ R such that x = t1 x1 + · · · , tn xn
1 次独立な B ⊂ V で V を生成するものを , V の基底 (basis) という.
演習 7.11 Zorn の補題を用いて , どんな線形空間 V (= {0}) にも基底が存在す
ることを証明せよ.
ヒント 1 次独立な V の部分集合で包含関係 ⊂ に関して極大なものが存在するこ
とを Zorn の補題を用いて示し , それが V の基底になることをその極大性を用いて
示せ.
62
8
順序数
自然数には , 1 個, 2 個, 3 個, . . . とものの個数を数える基数としての役割
と, 1 番目, 2 番目, 3 番目, . . . とものに順番を付ける序数としての役割があ
る. 英語では , 基数は , one, two, three, . . . , 序数は , first, second, third, . . . ,
と呼び方も異なる. 基数の無限への拡張は 6 章で扱った. この章では , 序数の
無限への拡張である順序数を導入する. 有限では , 基数と序数の違いはあまり
明確ではないが , 無限になるとその違いは非常に顕著なものとなる.
8.1
順序数の大小関係
ある集合の元に順番を付けるということは , 整列順序を与えるということに他なら
ない. 有限集合で元の個数が n ならば , どのように整列順序を入れても {1, 2, . . . , n}
と順序同型であるが , 無限集合であれば , 整列順序の入れ方によっては , その順序
型が異なる. 例えば , 自然数の集合 N であっても順序を変えて , 2 から始めて小さ
い順に全部数えた後で , 1 を最後の数 (最大の元) として数えると , 自然な順序を持
つ本来の N とは異なる順序型をもつ整列集合になる.
整列集合の順序型を順序数 (ordinal number) というが , ど のような整列順序が
与えられているかを示すものである. 自然数 n ∈ N を n 個の元を持つ整列集合の
順序型を表す標識として用いる. すなわち,
n = ord{1, 2, . . . , n} (= ord{0, 1, . . . , n − 1}).
def
また, ∅ も整列集合と考えて , ord ∅ = 0 と表す. さらに , ord N = ω と表す. 一般の
順序数を表すために , ギリシャ小文字 α, β, . . . , μ, ν, . . . , などが用いられる.
順序数 α, β に対して , 整列集合 A, B で ord A = α, ord B = β となるものをと
り, A が B の切片に順序同型となるとき, α は β より小さい , あるいは β は α よ
り大きいといい, α < β あるいは β > α と表す.
演習 8.1 順序数の大小関係 α < β が well-defined であることを示せ.
順序数 α, β に対して, 定理 7.8 は , つぎの 3 つの場合のうちいずれか 1 つだけ
が成り立つことを意味する:
α < β, α = β, α > β.
α < β または α = β であるとき, α β, あるいは β α と表す. 順序数の大小関
係に関して, 順序と同じつぎの性質が成り立つ:
(1) α α;
(2) α β, β α ⇒ α = β;
(3) α β, β γ ⇒ α γ.
順序数全体は集合とは呼べないが , ある順序数より小さな順序数全体は集合とな
り, 大小関係により整列集合となる. 実際, 順序数 α に対して , ord Wα = α となる
63
整列集合 Wα をとって , Ord(α) をつぎのように定義する:
Ord(α) = {ord Wα (x) | x ∈ Wα }.
def
このとき, Ord(α) は α より小さい順序数全体となり, Ord(α) Wα となる.
演習 8.2 上述のこと, すなわち, つぎのことを示せ:
(1) Ord(α) は α より小さい順序数全体からなる集合である.
(2) Ord(α) Wα .
ヒント (1) で示すことは , ∀x ∈ Wα , ord Wα (x) < α と ∀β < α, ∃x ∈ Wα ,
ord Wα (x) = β. (2) で示すことは , x → ord Wα (x) が Wα から Ord(α) の順序
同型写像となること .
演習 8.3 順序数からなる任意の集合は , 大小関係に関して整列集合となること
を示せ.
ヒント 順序数からなるどんな空でない集合 M も最小元を持てばよい. α ∈ M を取
り, α = min M であれば , Ord(α) ∩ M が最小元を持てばよい. Ord(α) が整列集合
であることに注目.
順序数全体は集合ではない : 順序数全体 Ord が集合であるとすると , 順序集
合の大小関係で Ord は整列集合となる. Ord の順序型である順序数を α と
すれば , 演習 8.2 によれば Ord(α) の順序型である順序数は α であるので
Ord(α) Ord となる. しかし , Ord(α) は Ord の切片であるので, 整列集合
の比較定理に矛盾する.
順序数 α に対して, Ord(α) の濃度を α の濃度という. このとき, Ord(α) の定
義より, α の濃度は ord Wα = α となる整列集合 Wα の濃度 card Wα に等しい. ま
た, Ord(α) が可算であるか非可算であるかに応じて , α は可算であるとか非可算
であるとかという.
演習 8.4 任意の濃度 m に対して , m を濃度とする最小の順序数が存在するこ
とを示せ.
ヒント card A = m となる集合 A に, 整列定理を適用して整列順序を入れ整列集合
とする. すべての元 x ∈ A に対して , card A(x) < m となるときとそうでないときに
分けて考えよ.
濃度全体は集合ではない : 濃度 m より小さい濃度の順序数全体 Ord は , m
を濃度とする最小の順序数を α とすれば , Ord(α) と等しいので, 集合となる.
濃度の全体 Card が集合であるとすると , Ord = ∈Card Ord も集合とな
り, Ord が集合ではないことに矛盾する.
64
8.2
順序数の演算
順序数の和: 順序数 α, β の和 α + β を定義するために , 整列集合 A = (A, A ),
B = (B, B ) で ord A = α, ord B = β かつ A ∩ B = ∅ となるものをとり, A ∪ B
上につぎのように順序 を定義すると , A ∪ B = (A ∪ B, ) は整列集合となるの
で , α + β = ord(A ∪ B) と定義する:
x y ⇔ (x ∈ A, y ∈ B) or (x ∈ A, y ∈ A, x A y)
def
or (x ∈ B, y ∈ B, x B y).
演習 8.5 順序数 α, β の和 α + β が well-defined であることを示せ.
ヒント ord A = α, ord B = β かつ A ∩ B = ∅ となる整列集合 A, B が取れること ,
上で定義された が A ∪ B 上の整列順序となること , α + β が A, B の取り方に依
存しないことを示せ.
演習 8.6 順序数の和に関して , つぎの基本的な性質が成り立つを示せ:
(1) α + 0 = 0 + α = α;
(2) (α + β) + γ = α + (β + γ);
(3) α < β ⇔ ν + α < ν + β.
(4) α < β ⇒ ∃1 ν such that β = α + ν.
注意: 上記 (1) は定義より自明.
一般に , α < β であっても, α + ν < β + ν とは限らない.
演習 8.7 任意の n < ω に対して , 0 + ω = ω = n + ω を示せ.
順序数の和に関する交換律 α + β = β + α は , 一般に成り立たない.
演習 8.8 1 + ω = ω < ω + 1 を示せ.
ヒント 最初の等号は前の演習. 不等号は, ord W = ω + 1 となる整列集合 W とし
て, つぎの R の順序部分集合を考えよ:
W = {(n − 1)/n | n ∈ N} ∪ {1}.
演習 8.9 R の整列部分集合 W で ord W = ω + ω となる例を上げよ.
順序数の積: 順序数 α, β の積 αβ を定義するために , 整列集合 A = (A, A ),
B = (B, B ) で ord A = α, ord B = β となるものをとり, A × B 上につぎのように
順序 を定義すると , A×B = (A×B, ) は整列集合となるので , αβ = ord(A×B)
と定義する:
(x, y) (x , y ) ⇔ (x <A x ) or (x = x , y B y ).
def
この順序を辞書式順序 (lexicographic order) という.
65
演習 8.10 順序数 α, β の積 αβ が well-defined であることを示せ.
ヒント 上で定義された が , A × B 上の整列順序となること , αβ が A, B の取り
方に依存しないことを示せ.
演習 8.11 順序数の積に関して , つぎの基本的な性質が成り立つことを示せ:
(1) 1α = α1 = α; 0α = α0 = 0;
(2) (αβ)γ = α(βγ);
(3) α(β + γ) = αβ + αγ;
(4) α < β, ν > 0 ⇒ να < νβ;
(5) α < β ⇒ αν βν.
注意: 上記 (1) は定義より自明.
演習 8.12 0 < n < ω に関する帰納法を用いて , つぎを示せ:
α
· · + α = αn
+ ·
n個
演習 8.13 R の整列部分集合 W で ord W = ωω となる例を上げよ.
順序数の積に関する交換律 αβ = βα は , 一般に成立しない.
演習 8.14 1 < n < ω に対して , nω = ω < ωn を示せ.
また , 演習 8.11(3) とは逆側の分配律 (α + β)γ = αγ + βγ も, 一般に成立しない.
演習 8.15 (1 + 1)ω < 1ω + 1ω を示せ.
一般に , α < β であっても αν < βν とは限らない.
演習 8.16 α < β であるが , αν = βν となる例を上げよ.
66
索引
ℵ0 , アレフ・ゼロ, aleph zero, 47
∩, キャップ , cap, 6
∪, カップ , cup, 6
c, ツェ−, tse, 47
共通部分, intersection, 6, 11
極限, limit, 43
極小元, minimal element, 27
極大元, maximal element, 27
値, value, 14
Archimedes (アルキ メデ ス) の公理, Archimedes’ Axiom, 42, 46
グラフ , graph, 14
群, group, 32
結合律, accosiative law, 31
元, element, 1
原像, preimage, 16
1 対 1 の写像, one-to-one map, 17
一般連続体仮説, generalized continuum hypothesis, 55
合成, composition, 18
恒等写像, identity, 14
Cauchy (コーシー) 列, Cauchy sequence, 41
上に有界, upper bounded, 28
上への写像, onto map, 16
well-defined, 30
再帰定理, Recursion Theorem, 35
再帰的定義, recursive definition, 33, 35
最小元, minimum, 27
最大元, maximum, 27
差集合, difference, 7
座標, coordinate, 8, 9, 22
三分律, trichotomy, 27
Gauss (ガウス) の定理, Gauss’ Theorem, 44
下界, lower bound, 28
可換環, commutative ring, 32
可換群, commutative group, 32
可換半群, commutative semi-group, 31
可換律, commutative law, 31
下極限, limit inferior, 13
下限, infimum, greatest lower bound, 28
可算集合, countable set, enumerable set, 49
可算濃度, countable cardinal, 47
環, ring, 32
関数, function, 14
Cantor (カントール ) の逆理, Cantor’s Paradox, 52
Cantor (カントール ) の対角線論法, Cantor’s
diagornal process, 51
Cantor (カントール ) の定理, Cantor’s Theorem, 51
始集合, initial set, 14
辞書式順序, lexicographic order, 65
自然数, natural numeber, 33
自然数の集合, N, 33
自然な写像, natural map, 30
下に有界, lower bounded, 28
実数, real number, 41, 44
実数の完備性, 43
実数の集合, R, 41, 44
実数の連続性, 45
射影, projection, 15, 22
写像, map, 14
集合, set, 1
集合族, family of sets, 9
集合列, sequence of sets, 23
終集合, terminal set, 14
収束, convergent, 43
十分条件, sufficient condition, 2
順序 (関係), order, 26
順序型, order type, 56
順序集合, ordered set, 27
基数, cardinal number, 47
帰納的, inductive, 60
帰納的定義, inductive definition, 33, 35
基本列, fundamental sequence, 41
逆写像, inverse map, 17
逆像, inverse image, 16
狭義の順序, order in the strict sense, 26
狭義の全順序, total order in the strict sense,
27
67
順序数, ordinal number, 63
順序数の積, 65
順序数の和, 65
順序体, ordered field, 32
順序単射, order injection, 56
順序対, ordered pair, 8
順序同型, order isomorphic, 56
順序同型写像, order isomorphism, 56
順序を保つ, order preserving, 56
上界, upper bound, 28
上極限, limit superior, 13
上限, supremum, least upper bound, 28
商写像, quoitent map, 30
商集合, quotient set, 30
真部分集合, proper subset, 1
高々可算, at most countable, 51
単位元, unit (element), 31
単射, injection, 17
値域, range, 15
稠密, 40, 42
超限帰納法, transfinite induction, 58
直後, successor, 57
直積, direct product, 8, 22
直前, predecessor, 57
直和分割, decomposition, 29
Zorn (ツォルン ) の補題, Zorn’s lemma, 60
定義域, domain, 14
定値写像, constant map, 15
Dedekind の切断, Dedekind cut, 44
推移律, transitive law, 26
De Morgan (ド ・モルガン ) の法則, De Morgan’s laws, 7
等化写像, identification map, 30
同値, equivalent, 2
同値関係, equivalence relation, 29
同値類, equivalence class, 29
特性関数, characteristic function, 18
制限, restriction, 15
整数, integer, 37
整数の集合, Z, 37
成分, factor, 8, 9, 22
整列集合, well-ordered set, 57
整列集合の比較定理, 59
整列順序, well-order, 57
整列定理, well-ordering theorem, 61
絶対値, absolute value, 32
切断, cut, 44
切片, initial segment, 57
切片の特徴付け , 58
零元, zero, null element, 32
線形順序, linear order, 26
線形順序集合, linearly ordered set, 27
全射, surjection, 16
選出関数, choice function, 24
選出公理, Axiom of Choice, 24
全順序, total order, 26
全順序集合, totally ordered set, 27
全称記号, universal quantifier, 4
全単射, bijection, 17
2 項関係, binary relation, 26
濃度, power, cardinality, 47
濃度の積, 53
濃度の比較定理, 49
濃度の巾, 54
濃度の和, 52
半群, semi-group, 31
反射律, reflective law, 26
反対称律, antisymmetric law, 26
像, image, 14, 15
添字集合, index set, 23
添字付けられた集合族, indexed family of sets,
23
存在記号, existential quantifier, 4
非可換体, non-commutative field, 32
比較可能, comparable, 26
比較可能律, comparability law, 26
非可算, uncountable, 51
必要十分条件, necessary and sufficient condition, 2
必要条件, necessary condition, 2
非反射律, irreflexive law, 26
標準写像, canonical map, 30
体, field, 32
対角線集合, diagonal, 14
代数学の基本定理, fundamental theorem of
algebra, 44
対等, equipotent, 47
代表元, representative, 30
互いに素, disjoint, 6
複素数の集合, C, 44
複素数, complex number, 44
部分集合, subset, 1
部分 (集合) 族, subfamily of sets, 10
部分集合 (の) 族, family of subsets, 10
部分順序集合, orderd subset, 28
普遍集合, universal set, 7
68
分割, decomposition, 29
分配律, distributive law, 32
Peano (ペアノ) の公理, Axioms of Peano, 33
巾集合, power set, 10
Bernstein の定理, Bernstein’s Theorem, 48
包含写像, inclusion map, 15
補集合, complement, 7
交わらない, miss, disjoint, 6
交わる, meet, intersect, 6
無限集合, infinite set, 49
有界, bounded, 28
有限集合, finite set, 49
有限濃度, finite cardinal, 47
有理数, rational number, 39
有理数の集合, Q, 39
要素, element, 1
Russell (ラッセル ) の逆理, Russell’s Paradox,
4
連続体仮説, continuum hypothesis, 52
連続体の濃度, the cardinality of the continuum, 47
Weierstrass (ワイエルシュトラウス) の公理,
Weierstrass’ Axiom, 43, 45
和集合, union, 6, 10
69

C : y = ax 1 - SUUGAKU.JP

シュレディンガー作用素 H に対して, [T,H]=

設計等委託成績評定通知書（修正）

C : y = ax 1 - SUUGAKU.JP

株式会社ジオックス

自転車再生・販売事業の廃止について（PDF：89KB）

5番 r を 0 以上の整数とし、数列 {an} を次のように定める。 a1 = r, a2 = r

10：00～個人質問（5人）(PDF文書

，V [ ¯X] = σ k] E[X E[(Xk − µ)(X ` − µ)] = E[X k X` − µ X k − µ X ` + µ2

問題 0. 所属・学年・番号，氏名