axjack's blog

### axjack is said to be an abbreviation for An eXistent JApanese Cool Klutz ###

a < b ⇔ W(a) ⊂ W(b)

Wを整列集合、a,b∈Wとする
a < b ⇔ W(a) ⊂ W(b)すなわち
i) a < b ⇒ W(a) ⊂ W(b)
ii) W(a) ⊂ W(b) ⇒ a < b
を示せ
────────────
i)
x∈W(a) ⇒ x < a ⇒ x < b ⇒ x∈W(b)
ii)
W(a) ⊂ W(b)とする。
整列集合より、
a=b, b<a, a<bのいずれかが成り立つ。
消去法で議論する
a = bのときW(a) = W(b)となり
W(a) ⊂ W(b)に矛盾する。
b < a のときi)からW(b) ⊂ W(a) となり
W(a) ⊂ W(b)に矛盾する。
したがってa < bが成り立つ。

以上のi, ii)より a<b ⇔ W(a)⊂W(b)
∎

整列集合の補題1.(松坂和夫「集合・位相入門」 p.101)

補題1.
Jが整列集合Wの部分集合で
x∈J, y∈W, y < x ⇒ y∈J
を満たすとする。
このとき
J=WまたはJ=W(a)となるa∈Wが存在する。
────────────
J≠W としW\J≠∅とする
整列性からW\Jは最小元を持つ
m = min W\Jとする
明らかにm∈W\Jである
さてJ=W(m)を示す

[W(m) ⊆ J]
x∈W(m)を任意にとる
するとx < m である
mはW\Jの最小元なので
x∉W\Jである

🔰「W\Jの最小元はmということは、
mより小さい要素はW\Jに属さない。
つまりx∉W\Jが言える。なのでx∈J。」🔰

したがってx∈Jである

[J ⊆ W(m)]
x∈Jを任意にとる
x > m :
　仮定 x∈J, y<x⇒y∈Jより
　m < xだからm∈Jとなる。
　しかしm∉Jなので矛盾。
x = m :
　x∈Jから m∈Jとなって矛盾。
したがってx < mすなわちx∈W(m)

以上よりJ=W(m)
∎

整列集合周りの補題など

👑整列集合：
(W,≦)を順序集合とする。
Wの非空部分集合が最小元を持つとき、
(W,≦)を整列集合という。
つまり、
整列集合(W,≦)が与えられたとき
空でないWの部分集合は最小元を持つ
ということ。

整列集合は全順序：
Wの要素が1個なら非空部分集合S={a}は最小元aを持つ。
Wの要素が2個以上とする。
任意にa,b∈Wを取る。S={a,b}とする。
Sは非空部分集合であるから、
Wの整列性よりSは最小元を持つ。
a≠bのとき、もしmin S = aならばa≦b。もしmin S = bならば b≦a。
a=bのときa≦b または b≦a。
いずれのケースでも比較可能である。
よってWの任意の2元は比較可能であるから、Wは全順序である∎

【用語】切片,初期区間(initial segment)
W(a) := { x∈W | x < a }
をWの切片という。
a∈Wより真に小さい要素を集めた集合が切片である。

📌命題
W(a) = ∅ならばaはWの最小元である。
W(a) = ∅
⇒ x<aを満たすxが存在しない
⇒ ¬( ∃x∈W : x < a )
⇒ ∀x∈W: a ≦ x ←Wの最小元
したがって a = min W
∎

🔑定理 11.1：超限帰納法
(W,≦)を整列集合とする。
各a∈Wに対して命題P(a)が与えられ
1) P(min W)が真
2) min Wとは異なる
　任意のa∈Wと
　任意のb∈W(a)
　について
　P(b)が真ならばP(a)が真である
この時、
任意のa∈WについてP(a)は真である

🔎証明
A⊆W、A ={ x∈W | P(x)は偽 }
とおく。A≠∅とする。
つまり、命題が偽になる要素があると仮定する
Wの整列性からminAが取れる。
P(minA)は偽よりminA≠minWである
次に b∈W(minA)を任意に取る
P(b)が真ならばP(minA)が真である
矛盾である
よって、A=∅
つまり、
P(x)が偽になる要素x∈Wは存在しない。
したがって
任意のa∈WについてP(a)は真∎


🔑定理 11.2
Wを整列集合とし
f: W→Wを単射かつ順序を保つ写像とする
この時、任意のx∈Wについて
x ≦ f(x)が成り立つ。
🔎証明
A = {x ∈ W | f(x) < x}が非空だと仮定する
A⊆WよりWの整列性からmin Aが存在する
a = min Aとおく
a∈Aなので、
f(a) < aを満たす
fは順序を保つ単射であるから
f( f(a) ) < f(a) が成り立つ
よって f(a)∈Aである
するとf(a) < aとなるため
aの最小性に矛盾
よってA=∅
したがって
任意のx∈Wについて
x ≦ f(x)が成り立つ。∎


────────────
🔑定理 11.3
Wを整列集合とする。
a,b∈W、a<bとする。
この時、
(W(a), ≦)と(W(b), ≦)は順序同型でない
🔎証明
W(a) = { x∈W | x < a }
W(b) = { x∈W | x < b }
とおく。
W(a)⊂W(b)である。
順序同型写像f: W(b) → W(a)
が存在すると仮定する
またW(a)⊂W(b)から
包含写像inc: W(a)→W(b)が存在する

さてa∈W(b)を取る
aでfを送るとf(a)∈W(a)
するとf(a) < aが成り立つ
　
さらにf(a)をincで送り
f(a)∈W(b)
ここでinc∘fは順序を保つ写像かつ単射であるから順序を保つ単射g = inc∘f: W(b)→W(b)を用いてg(a) < aが示せた。
これは定理11.2 に矛盾する
したがって、W(b)→W(a)への
順序同型写像は存在しない∎

────────────
🔑定理11.4
(W,≦), (W*,≦*)を整列集合とし
W1 ⊆ Wを
W1 = { a∈W | あるa*∈W*が存在しW(a)とW*(a*)が順序同型 } により定める
このとき、
　W1=Wであるか
　または、あるa1∈Wが一意的に存在し
　W1=W(a1)となる
────────────
W1≠W, W\W1 ≠ ∅ とする。
整列性より
m = min(W\W1) が存在する

さてW1 = W(m)を示す

【 W(m) ⊆ W1 】
x∈W(m)を任意に取る
すると x < m である
mはW\W1の最小元であるから
x∉W\W1
よって x∈W1
したがって W(m) ⊆ W1

【 W1 ⊆ W(m) 】
背理法で示す。
「x∈W1 かつ x∉W(m) となる x が存在する」
と仮定し、矛盾を導く

仮定よりx∈W1のため
あるx*∈W*が存在し
W(x)とW*(x*)は順序同型を満たすため
順序同型写像 f: W(x) → W*(x*)
が存在する

また仮定より
x∉W(m)なのでx < mでない
よって m ≦ x
さらに x ∈ W1とm∈W\W1から x ≠ m
m < x
よって m ∈ W(x)
したがってW(m)⊆W(x)である

さてm* = f(m)とおく
f(W(m)) = W*(m*)を示す。

①f( W(m) ) ⊆ W*(m*)
z∈W(m)を任意に取る
z < mよりf(z) < f(m)
よってf(z) < m*
つまりf(z) ∈ W*(m*)
したがってf( W(m) ) ⊆ W*(m*)が成り立つ

②W*(m*) ⊆ f( W(m) )
z*∈W*(m*)を任意に取る
z* < m*である
fの全射性からあるz∈W(x)が存在し
z* = f(z)を満たす。
よってz* < m* すなわち f(z) < f(m)
fは順序同型なので順序を反映し
f(z) < f(m) ⇒ z < m を得る
よってz ∈ W(m)
ゆえに z* = f(z) ∈ f( W(m) )
したがって W*(m*) ⊆ f( W(m) )が成り立つ

以上よりf(W(m)) = W*(m*)が成り立つ。
したがって
W(m)とW*(m*)は順序同型であるから
W1の定義に照らし合わせると
m ∈ W1を満たす。

しかしm ∈ W\W1であったから
m ∈ W1はm ∉ W1に矛盾する。
よってW1 ⊆ W(m)が成り立つ。

以上より
W(m)⊆W1, W1⊆W(m)が成り立つので
W1=W(m)

一意性：
a1,a2∈W, W1=W(a1)=W(a2)とする。
a1≠a2と仮定する。
整列性よりa1<a2としてよい。
するとa1∈W(a2)である。
しかしW(a2)=W(a1)であるからa1∈W(a1)となる。
これはa1<a1を意味し矛盾。
したがってa1=a2であり一意である。
∎

問10.4 無理数全体の集合とℝの濃度が等しいことを示せ。

🔎証明
ℚを有理数全体の集合
ℝを実数全体の集合
ℚ≠ℝ
ℚ⊆ℝ
¬(ℝ⊆ℚ)
ℚは可算無限
ℝは非可算無限
であることを既知とする。

濃度の比較：
ℚ⊆ℝから
inc: ℚ→ℝの包含写像incが存在し
incは単射である
またℚは可算無限、ℝは非可算無限である
よってcard ℚ < card ℝ

ℝ\ℚが存在すること：
x0∈ℝ\ℚ が取れることを確認する
ℝ\ℚ=∅を仮定する
ℝ\ℚ = { x∈ℝ | x∉ℚ } が∅であるとは、
ℝ⊆ℚと同値である
するとℝ⊆ℚかつℚ⊆ℝ⇔ℝ=ℚとなり矛盾
よってℝ\ℚ≠∅

ℝの構成：
A,B⊆ℝとし、x0∈ℝ\ℚを任意に固定する
A = { rx0 | r∈ℚ\{0} }
B = ℝ \ (ℚ∪A)
により定める。
すると、ℝ = ℚ ⊔A ⊔ Bである。

ℚ∩A=∅を示す
a∈ℚ∩Aが取れると仮定する。
すると、aは有理数かつa=qx0と表せる
ここでq∈ℚ\{0}である
したがってx0 = a/q∈ℚとなるが矛盾
よってℚ∩A=∅でありℚとAは互いに素

定義より
Bとℚは互いに素
BとAも互いに素
よってℝ = ℚ ⊔A ⊔ Bは成り立つ

ℚ→ℚ\{0}に全単射が存在すること
確認：
ℕ~ℚより全単射g: ℕ→ℚが取れる
任意のn∈ℕに対してg(n)∈ℚ
ここでg(1)=0とおく。
写像f:ℚ→ℚ\{0}を
f( g(n) ) = g(n+1)と定める。
fの値域の確認
f(g(n))=g(n+1)であり
n∈ℕよりn+1≧2
gは単射でg(1)=0なので、k≧2のときg(k)≠0
よってf(x)≠0よりf(ℚ)=ℚ\{0}
さてfは全単射となることを確認する
単射性：
n,m∈ℕを任意にとる
f(g(n)) = f(g(m))とすると
g(n+1) = g(m+1)でありgの単射性から
n+1 = m+1 ⇒ n=m
よってg(n)=g(m)よりfは単射
全射性：
y∈ℚ\{0}とする
gの全射性から
y = g(k)を満たすk∈ℕが見つかる
またy≠0でg(1)=0よりk≧2
ここでn=k-1とおくと
f(g(n))=g(n+1)=g(k)=yとなる
よってfは全射
したがって、ℚ~ℚ\{0}

A,B⊆ℝとし、x0∈ℝ\ℚを任意に固定する
A = { rx0 | r∈ℚ\{0} }
全単射h: ℚ\{0} → Aが存在することを示す
q ∈ ℚ\{0}を任意にとる
h(ℚ) = { qx0 | q∈ℚ\{0} } = Aよってhは全射
次にh(q1)=h(q2)を仮定する
このときx0q1 = x0q2 ⇒ q1 = q2
よってhは単射
したがって、hは全単射であるから
Q\{0} ~ A

いま、ℕ~ℚ~ℚ\{0}~Aである。
よってAは可算無限であるから
ℚ∪Aも可算無限である
したがってℚ∪A~A

補題：(ℚ∪A) ∪ B ~ A ∪ B
恒等写像idB : B→Bとする
ℚ、A、Bは互いに素であることに注意。
g: (ℚ∪A)∪B→A∪Bを次に定める
g(x) =
　・f(x) if x∈ℚ∪A
　・idB(x) if x∈B
全射性：
g(ℚ∪A) = f(ℚ∪A) = A
g(B) = idB(B) = B より全射である。
単射性
a,b∈ℚ∪Aのとき、fの単射性よりgは単射
a,b∈Bのとき、idBの単射性よりgは単射
a∈ℚ∪A, b∈Bの時、
g(a)∈A, g(b)∈BだがAとBは互いに素なので交差しない。すなわちg(a)≠g(b)よりgは単射
よってgは単射である

したがってgは全単射であり、
(ℚ∪A)∪B ~ A∪B

以上より
ℝ = ℚ∪A∪B と補題より
ℝ ~ ℚ∪A∪B ~ A∪Bが成り立つ

定義より
A∪B = ℝ\ℚであるから
A∪Bは実数全体から有理数を除外した集合つまり無理数全体の集合である
したがって、無理数全体の集合(A∪B)とℝの濃度が等しいことが示せた∎

📌ベルンシュタインの定理

────────────
A,Bを空でない集合とする。
単射f:A→B、単射g:B→Aが存在するとき、
AとBは対等である。
────────────
🔎証明
[準備]
B0 = B \ f(A)
i≧1に対して
　Ai = g( B_{i-1} )
　Bi = f(Ai)
　S = ⋃Ai
　T = ⋃B_{i-1}
とおく。
A\S ⊔ S = A
B\T ⊔ T = B
である。
────────────
[補題]
補題1：f(A\S)=B\T
f(A\S)
= f(A) \ f(S) ∵fの単射性
= f(A) \ f(⋃Ai)
= (B\B0) \ ⋃f(Ai)
= (B\B0) \ ∪Bi
= B \ (B0 ⋃ Bi)
= B \ T

補題2：g(T)=S
g(T)
= g(∪B_{i-1})
= ⋃g(B_{i-1})
= ⋃Ai
= S

補題1からf(A\S) = B\Tより
f|A\S : A\S → B\Tは全単射となる。

補題2からg(T) = Sより
g|T : T→S は全単射となる。
よってg|Tは逆写像が存在し
(g|T)‪⁻¹‬ : S → Tも全単射となる。
────────────
[h: A→Bの構成]
h : A→B
　a∉Sのときf(a)
　a∈Sのとき(g|T)‪⁻¹‬(a)
と定める。
このhが全単射であることを以下で示す。
────────────
[hの範囲]
hの定義域/値域を確認すると、
・h(A\S) = f(A\S)
・h(S) = (g|T)‪⁻¹‬(S)
である。

補題からf(A\S) = B\T, (g|T)‪⁻¹‬(S) = Tより
h(A\S) ∩ h(S) = B\T ∩ T = ∅
よってh(A\S)とh(S)は互いに素。
またh(A\S)∪h(S)=B\T∪T=Bである。

[hの全射性]
h(A)
= h(A\S ⊔ S)
= h(A\S) ∪ h(S)
= f(A\S) ∪ (g‪|T)‪⁻¹‬(S)
= B\T ∪ T
= B
よってhは全射。

[hの単射性]
①a1,a2がA\Sに属するとき
h(a1) = f(a1) , h(a2) = f(a2)
fの単射性からf(a1)=f(a2)⇒a1=a2
よってhは単射。

②a1,a2がSに属するとき
h(a1)=(g|T)‪⁻¹‬(a1) , h(a2)=(g|T)‪⁻¹‬(a2)
(g|T)‪⁻¹‬の単射性から
(g|T)‪⁻¹‬(a1) = (g|T)‪⁻¹‬(a2)⇒a1=a2
よってhは単射。

③a1がA\Sに属し、a2がSに属するとき
A\S ∩ S = ∅よりa1≠a2 である
また
・h(a1) = f(a1)∈B\T
・h(a2) = (g|T)‪⁻¹‬(a2)∈T
であって、B\T ∩ T=∅であるから
f(a1) ≠ (g|T)‪⁻¹‬(a2)を得る。
よってhは単射。
したがって①②③より、hは単射。


以上より、hは全単射である。
したがって、単射f:A→B、単射g:B→Aが存在するとき、AとBは対等である。∎

fが単射のとき、∩f(Aλ) (λ∈Λ) ⊂ f(∩Aλ) (λ∈Λ)

数学 基本概念 集合論

X,Y,Λを非空な集合とする。f: X→Yを単射な写像とし、Λを添字集合とするXの部分集合族を(A_\lambda)_{\lambda\in\Lambda}とする。

[定理] \displaystyle \bigcap_{\lambda\in\Lambda} f(A_\lambda) \subset f\left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)

[証明]
まず、
\displaystyle y\in\bigcap_{\lambda\in\Lambda} f(A_\lambda) を任意に取る。
集合族の共通部分の定義より、
各 \displaystyle \lambda\in\Lambdaに対して、 \displaystyle y\in f(A_\lambda)
像の定義より、
各 \displaystyle \lambda\in\Lambdaに対して、ある \displaystyle x_\lambda\in A_\lambdaが存在し、 \displaystyle y=f(x_\lambda)

次に、
固定した \displaystyle \lambda_0\in\Lambdaに対して
\displaystyle y=f(x_{λ_0})となる \displaystyle x_{λ_0}\in A_{\lambda_0}を一つ選ぶ。
任意の \displaystyle \lambda\in\Lambdaに対して \displaystyle y=f(x_\lambda)を満たす \displaystyle x_\lambdaが存在する。
この時、 \displaystyle y=f(x_{\lambda_0})=f(x_\lambda)が成り立ち、fの単射性から、 \displaystyle x_{\lambda_0}=x_\lambdaである。 \displaystyle x_\lambda\in A_\lambdaより \displaystyle x_{\lambda_0}\in A_\lambdaも成り立つ。これが全ての \displaystyle \lambdaについて言えるため、 \displaystyle x_{\lambda_0}\in\bigcap_{\lambda\in\Lambda} A_\lambdaも成り立つ。

したがって \displaystyle y=f(x_{\lambda_0})\in f\left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)
よって \displaystyle \bigcap_{\lambda\in\Lambda} f(A_\lambda) \subset f\left(\bigcap_{\lambda\in\Lambda} A_\lambda\right)
■

下界集合の包含関係、下限の大小関係、sup・infの単調性

数学 基本概念

\displaystyle A \subset B ならば \displaystyle \sup A \le \sup Bであった。
では \displaystyle \infについては \displaystyle \inf A \ge \inf Bなのか？これを確認する

下界集合の包含関係

\displaystyle L_A = \{ w \in \mathbb{R} \mid \forall x \; x \in A \Rightarrow w \le x \}
\displaystyle L_B = \{ w \in \mathbb{R} \mid \forall y \; y \in B \Rightarrow w \le y \}
とする。 \displaystyle L_B \subset L_Aを確かめる。
\displaystyle w \in L_Bを任意に一つ取ると
任意の \displaystyle y \in Bについて \displaystyle w \le yである。
ところで \displaystyle A \subset Bより任意のAの要素は必ずBに属するので、 \displaystyle x \in A \Rightarrow x \in B
よって \displaystyle w \le xが言えてつまり \displaystyle w \in L_A。以上より \displaystyle L_B \subset L_Aが示された。

下限の大小関係

\displaystyle s = \inf A は
\displaystyle s \in L_Aかつ任意の \displaystyle u \in L_Aについて \displaystyle u \le s
\displaystyle t = \inf B は
\displaystyle t \in L_B かつ任意の \displaystyle u \in L_Bについて \displaystyle u \le t
である。

では \displaystyle t = \inf Bを取る。すると \displaystyle t \in L_B。 \displaystyle L_B \subset L_Aより \displaystyle t \in L_A。ここで \displaystyle s = \inf Aは \displaystyle L_Aの任意の要素 \displaystyle uについて \displaystyle u \le sが成り立つ。 \displaystyle tは \displaystyle L_Aに属するので従って \displaystyle t \le s。以上より \displaystyle \inf B \le \inf Aが示された。

────────────

sup・infの単調性

\displaystyle A \subset Bのとき
・ \displaystyle \sup A \le \sup B
・ \displaystyle \inf A \ge \inf B
であることを確かめた。

ここから各 \displaystyle kについて
\displaystyle A_{k+1} \subset A_k ならば
\displaystyle \sup A_{k+1} \le \sup A_k
\displaystyle \inf A_{k+1} \ge \inf A_k
が言える。

したがって、集合の減少列
\displaystyle A_1 \supset A_2 \supset \cdots \supset A_k \supset \cdots
に対して
上限については単調非増加列
　 \displaystyle \sup A_1 \ge \sup A_2 \ge \cdots \ge \sup A_k \ge \cdots
下限については単調非減少列
　 \displaystyle \inf A_1 \le \inf A_2 \le \cdots \le \inf A_k \le \cdots
が得られる。

A⊂B ならばsup A ≤ sup B：部分集合と上限の関係

数学 基本概念

A, Bを非空とし、 \displaystyle A \subset Bとする。

上界集合の比較

上界(upper limit)
A,Bの上界集合をそれぞれ

  • \displaystyle U_A = \{ u \in \mathbb{R} \mid \forall x (x \in A \Rightarrow x \le u) \}
  • \displaystyle U_B = \{ u \in \mathbb{R} \mid \forall y (y \in B \Rightarrow y \le u) \}

とする。

\displaystyle U_B \subset U_Aを示せ。

証明：
\displaystyle u \in U_B \Rightarrow u \in U_Aを示せば良い。
まず \displaystyle u \in U_Bを任意に取る。
\displaystyle uは上界なので \displaystyle \forall y (y \in B \Rightarrow y \le u)。
また、 \displaystyle A \subset Bから \displaystyle \forall x (x \in A \Rightarrow x \in B)。
従って \displaystyle \forall x (x \in A \Rightarrow x \le u)を得る。
以上より \displaystyle u \in U_A、すなわち \displaystyle U_B \subset U_Aが示された。


上限の比較

上限(sup)
A, Bの上限を以下とする。

\displaystyle s = \sup A とは、
\displaystyle s \in U_A かつ \displaystyle \forall u \in U_A\ (s \le u)

\displaystyle t = \sup B とは、
\displaystyle t \in U_B かつ \displaystyle \forall u \in U_B\ (t \le u)

とする。

\displaystyle \sup A \le \sup B（ \displaystyle s \le t）を示せ。

証明：
\displaystyle tは上界なので \displaystyle t \in U_B。上界集合の包含関係 \displaystyle U_B \subset U_Aより \displaystyle t \in U_A。従って \displaystyle tは \displaystyle Aの上界である。
また仮定より \displaystyle sは \displaystyle \forall u \in U_A\ (s \le u)を満たす。特に \displaystyle s \le tである。
従って \displaystyle \sup A \le \sup Bが示された。

以下雰囲気解説：

包含関係：

A⊂BなのでAはBに包まれている状態。AよりもBの方が大きい集合だと想像する。Aの要素は必ずBの要素になっている。

上界集合：

Dを集合として、Dの中で一番大きい奴と等しいかそれよりも大きい奴を全て集めた集合がDの上界集合。つまりDの上界集合の要素はDのあらゆる要素よりも大きい(もしDに最大値が存在すればその最大値は上界集合に属する)。x∈Dならばx≦uとなるuを集めたものがDの上界集合。

上界集合の包含関係：

Aの上界集合とBの上界集合を比べると、
Bの上界集合⊂Aの上界集合となる。
これを確認する。まずBの上界集合から任意に要素uを一つ取る。このときx∈B ⇒ x≦uが必ず成り立つ。ところでA⊂Bだからx∈A⇒x∈Bも必ず成り立つ。二つを繋げると、x∈A⇒x∈B⇒x≦uとなって、x∈A⇒x≦uと言える。つまり、uはAの上界に属する。これを包含関係で書くと、UB⊂UAとなる。雑に言えば、包含関係の内側をA、外側をBと認識したとき、外側の上界集合は内側の上界集合に包まれる、ということ。

上限の大小関係：

sup BはBの上限である。t,uをBの上界集合の要素としたとき、任意のuについてt ≦ uを満たすスペシャルなtがsup Bである。つまり、上界集合の最小値がsup Bである。最小上界とも言う。同様に、sup Aについても、s,uをAの上界集合の要素としたとき、任意のuについてs≦uを満たすスペシャルなsがsup Aである。

さて、s=sup A, t=sup Bとすると、
tはBの上界集合に属するので、t∈UBである。次にUB⊂UAよりtはAの上界集合にも属する。ところで、s=sup AはAの上界集合の中でも一番小さいものであるから、sはtと等しいかそれよりも大きいと言える。なのでs≦t記法を改めるとsup A ≦ sup Bとなる。

axjack is said to be an abbreviation for An eXistent JApanese Cool Klutz.