エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

エレファントな整数論(22)

写像の性質の続き

前回の議論では足りないところがあるので追加していきます。証明はまとめることができると思うのですが、できませんでした。集合論の中の自然数論のような話題だと思うので、まとめて書かれているところがあると思うのですが、見つけることはできませんでしたので必要と思われるものを書いていきます。

全射・単射

X, Y を集合、 f: X \to Y を写像とします。任意の x_1, x_2 \in X に対して f(x_1) = f(x_2) ならば x_1 = x_2 であるとき、 f を単射と呼びます。任意の y \in Y に対して y = f(x) となる x \in X が存在するとき、 f を全射と呼びます。 f が全射かつ単射であるとき全単射と呼びます。

f: X \to Y に対して \overline{f^{-1}}: Y \to \mathfrak{P}(X) を \overline{f^{-1}}(y) = \{x \in X \mid f(x) = y\} とおきます( \mathfrak{P}(X) は X の部分集合全体の集合)。

  • (MP1) f \ は単射 \iff 任意の \ y \in Y \ に対して \ \#\overline{f^{-1}}(y) \le 1
  • (MP2) f \ は全射 \iff 任意の \ y \in Y \ に対して \ \#\overline{f^{-1}}(y) \ge 1
  • (MP3) f \ は全単射 \iff 任意の \ y \in Y \ に対して \ \#\overline{f^{-1}}(y) = 1

となります。ここで \#\overline{f^{-1}}(y) は \overline{f^{-1}}(y) の元の個数を表します。ここでは 0、 1、 2 以上の場合に分けるためにこの記法を使います。(後で自然数を定義するので自然数の全体は使いません)

逆写像

f が全単射であるとき、任意の y \in Y に対して \overline{f^{-1}}(y) の元の個数が 1 なので、 y に \overline{f^{-1}}(y) の元を対応させる写像 f^{-1}: Y \to X を定義することができます。

任意の x \in X に対して f^{-1}(f(x)) \in \overline{f^{-1}}(f(x)) = \{x\} となるので ​ f^{-1} \circ f は X の恒等写像となります。

任意の y \in Y に対して f^{-1}(y) \in \overline{f^{-1}}(y) となるので
f^{-1}(y) \in \overline{f^{-1}}(y) \iff f(f^{-1}(y)) = y
であることから f \circ f^{-1} は Y の恒等写像となります。

f^{-1} を f の逆写像と呼びます。

以上の議論から

集合 X, Y に対して全単射 f: X \to Y が存在するとき X \sim Y と表し、 X と Y は濃度が等しいといいます。上の議論より \sim は同値関係となります。

全射・単射の性質

f: X \to Y を単射、 g, h: Z \to X は f \circ g = f \circ h を満たす写像とします。 z \in Z とすると f(g(z)) = f(h(z)) となり、 f は単射なので g(z) = h(z) となります。よって g = h となります。よって

f: X \to Y を全射、 g, h: Y \to Z は g \circ f = h \circ f を満たす写像とします。 y \in Y とすると f は全射なので f(x) = y となる x \in X が存在します。 g(f(x)) = h(f(x)) となり、 g(y) = h(y) となります。よって g = h となります。よって

  • (MP6) f: X \to Y が全射、 g, h: Y \to Z が g \circ f = h \circ f を満たす写像ならば g = h となります。

f: X \to Y、 g: Y \to Z に対して

f: X \to Y に対して f(X) = \{ f(x) \mid x \in X \} ( f の像)とすると、全射 \tilde{f}: X \to f(X)、 \tilde{f}(x) = f(x) が存在します。 X/f = \{ \overline{f^{-1}}(y) \mid y \in Y \} ( f に関する同値類全体の集合)とすると、単射 \bar{f}: X/f \to Y、 \bar{f}(\overline{f^{-1}}(y)) = y が存在します。

X \xrightarrow{f_1} X/f \xrightarrow{f_2} f(X) \xrightarrow{f_3} Y を

  • x \in \overline{f^{-1}}(y)) のとき f_1(x) = \overline{f^{-1}}(y))
  • f_2(\overline{f^{-1}}(y)) = y
  • f_3(y) = y

とすると

となります。よって f_2 は全単射、 f_1 は全射、 f_3 は単射となります。よって

  • (MP13) X \xrightarrow{f_1} X/f \xrightarrow{f_2} f(X) \xrightarrow{f_3} Y とすると f_2 は全単射、 f_1 は全射、 f_3 は単射となります。
  • (MP14) f: X \to Y が単射ならば g \circ f が恒等写像となる g: Y \to X が存在する
    • [証明] f が単射ならば f_1 は単射、したがって全単射となります。よって f_2 \circ f_1 の逆写像 f_1^{-1} \circ f_2^{-1}: f(X) \to X が存在します。 g: Y \to X を f_1^{-1} \circ f_2^{-1} を拡張する写像とすると g \circ f が恒等写像となります。
  • (MP15) f: X \to Y が全射ならば f \circ g が恒等写像となる g: Y \to X が存在する
    • [証明] f が全射ならば f_3 は全射、したがって全単射となります。よって f_3 \circ f_2 の逆写像 f_2^{-1} \circ f_3^{-1}: Y \to X/f が存在します。 h: X/f \to X を S \in X/f に対して S を X の部分集合としたときの S の元の一つに対応させる写像とすると、 f_1 \circ h は X/f の恒等写像となります。 g = h \circ f_2^{-1} \circ f_3^{-1}: Y \to X とすると g \circ f が恒等写像となります。
(MP16) 集合 X, Y に関する以下の条件(FS1*)、(FS2*)は同値となります。

[証明] (FS1*) \Longrightarrow (FS2*): (FS1*)を仮定し、 g: Y \to X を全射とします。 f: X \to Y を f(x) \in g^{-1}(x) となるように定義することができます。 f は単射となり、(FS1*)より全単射となります。よって g = f^{-1} は全単射となります。

(FS2*) \Longrightarrow (FS1*): (FS2*)を仮定し、 f: X \to Y を単射とします。 g: Y \to X を y \in f(X) のとき g(y) \in f^{-1}(y) となるように定義することができます。 y \notin f(X) のときは g(y) 任意の X の元とします。 g は全射となり、(FS2*)より全単射となります。よって f = g^{-1} は全単射となります。[証明終わり]

有限集合

上の議論より集合 X に対して以下の条件(FS1)、(FS2)は同値となります。これらの条件が成り立つとき、 X を有限集合と呼びます。有限集合でないとき無限集合と呼びます。

(FM1) Y が有限集合、 f: X \to Y が単射ならば、 X は有限集合となります。

[証明] g: X \to X を単射とします。

y \in f(X) とすると \overline{f^{-1}}(y) は空ではないので、その一つの元をとる写像を h: f(X) \to X とします。 f を X から f(X) への写像と見たものを \tilde{f}: X \to f(X) とすると、 \tilde{f} \circ h は f(X) の恒等写像となります。よって h は単射となり、 \tilde{f} \circ g \circ h: f(X) \to f(X) は単射となります。

g': Y \to Y を
g'(y) = \begin{cases} \tilde{f}(g(h(y))) & (y \in f(X)) \\ y & (y \notin f(X)) \end{cases}
とおくと単射となります。 Y が有限集合なので g' は全単射となります。

よって \tilde{f} \circ g \circ h も全単射となり、 \tilde{f} は全単射なので g は全射となります。よって X は有限集合となります。[証明終わり]

(FM2) X が有限集合、 f: X \to Y が全射ならば、 Y は有限集合となります。

[証明] g: Y \to Y を単射とします。

y \in Y とすると \overline{f^{-1}}(y) は空ではないので、その一つの元をとる写像を h: Y \to X とします。 h は単射となり、 h を Y から h(Y) への写像と見たものを \tilde{h}: Y \to h(Y) とすると、 \tilde{h} は全単射となります。よって \tilde{h} \circ g \circ \tilde{h}^{-1}: h(Y) \to h(Y) は単射となります。

g': X \to X を
g'(x) = \begin{cases} \tilde{h}(g(\tilde{h}^{-1}(x))) & (x \in h(Y)) \\ x & (x \notin h(Y)) \end{cases}
とおくと単射となります。 X が有限集合なので g' は全単射となります。

よって \tilde{h} \circ g \circ \tilde{h}^{-1} も全単射となり、 \tilde{h} は全単射なので g は全射となります。よって Y は有限集合となります。[証明終わり]

(FM3) X が有限集合ならば X の任意の部分集合は有限集合となります。

[証明] (FM1)より成り立ちます。[証明終わり]

(FM4) X が有限集合ならば X の任意の同値類全体の集合は有限集合となります。

[証明] (FM2)より成り立ちます。[証明終わり]

(FM5) X が有限集合、 X と Y は濃度が等しいならば Y は有限集合となります。

これは明らかに成り立ちます。

(FM6) Z = X \cup Y、 X が有限集合、 Y = \{y\} ならば Z は有限集合となります。

[証明] y \in X ならば Z = X は有限集合となります。 y \notin X とします。

f: Z \to Z を単射とします。

f(X) \subseteq X とすると f の X への制限は X から X への単射となり、 X が有限集合であることから全射となります。 f は単射なので f(y) \notin X となって f(y) = y となります。よって f は全射となります。

f(X) \not\subseteq X とします。 f は単射なので y \in f(X) となります。 f は単射なので y = f(x) となる x \in X がただ一つ存在します。また、 f は単射なので f(y) \in X となります。 g: X \to X を g(x) = f(y)、 v \ne x のとき g(v) = f(v) と定義することができ、 g は単射となります。 X が有限集合であることから g は全射となります。

任意の w \in X に対して w \ne f(y) ならば w = g(v) = f(v) となる v \in X が存在します。よって f は全射となり、 Z は有限集合となります。[証明終わり]

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)

  • 発売日: 2016/05/24
  • メディア: 単行本

エレファントな整数論(21)

「エレファントな整数論(3)」で書いたような内容ですが、また書き直していきます。

全射・単射・有限集合

X, Y を集合、 f: X \to Y を写像とします。任意の x_1, x_2 \in X に対して f(x_1) = f(x_2) ならば x_1 = x_2 であるとき、 f を単射と呼びます。任意の y \in Y に対して y = f(x) となる x \in X が存在するとき、 f を全射と呼びます。 f が全射かつ単射であるとき全単射と呼びます。

f が全単射であるとき、 f は全射なので y \in Y に対して y = f(x) となる x が存在し、 f は単射なのでこの x は一意的となります。よって g: Y \to X を g(y) = x と定義することができます。 g \circ f = 1_X ( X の恒等写像)、 f \circ g = 1_Y ( Y の恒等写像)となります。 g を f の逆写像と呼び f^{-1} と書きます。

集合 X に対して以下の条件(F1)が成り立つとき、 X を有限集合と呼びます。有限集合でないとき無限集合と呼びます。

(F1)は以下の(F2)と同値となります。

[証明] (F1) \Longrightarrow (F2): (F1)を仮定し、 f: X \to X を全射とします。(選択公理より) g: X \to X を g(x) \in f^{-1}(x) となるように定義することができます。 g は単射となり、(F1)より全単射となります。よって f = g^{-1} は全単射となります。

(F2) \Longrightarrow (F1): (F2)を仮定し、 f: X \to X を単射とします。 g: X \to X を x \in f(X) のとき g(x) \in f^{-1}(x) となるように定義することができます。 x \notin f(X) のときは g(x) 任意の X の元とします。 g は全射となり、(F2)より全単射となります。よって f = g^{-1} は全単射となります。[証明終わり]

順序関係

集合 O 上の二項関係 \le が

  • 反射律: 任意の x \in O に対して x \le x
  • 推移律: 任意の x , y, z \in O に対して x \le y \le z ならば x \le z

を満たすとき前順序と呼びます。さらに

  • 反対称律: 任意の x , y \in O に対して x \le y かつ y \le x ならば x = y

を満たすとき半順序と呼びます。単に順序という場合は半順序のことを表すとします。さらに

  • 任意の x , y \in O に対して x \le y または y \le x

を満たすとき全順序と呼びます。

x \le y を y \ge x と書くこともできます。 x \le y かつ x \ne y のとき x < y、 x \ge y かつ x \ne y のとき x > y と書きます。

集合 O 上の二項関係 \le が前順序のとき二項関係 \cong を
x \cong y \iff x \le y \ かつ \ y \le x
とおくと

  • 反射律: 任意の x \in O に対して x \cong x
  • 推移律: 任意の x , y, z \in O に対して x \cong y \cong z ならば x \cong z
  • 対称律: 任意の x , y \in O に対して x \cong y ならば y \cong x

を満たすので同値関係となります。この同値関係による同値類の全体を \bar{O} とおきます。 x \in O を含む同値類を \bar{x} とおきます。

x \cong x'、 y \cong y' とします。 x \le y ならば x' \le x \le y \le y' より x' \le y'、 x' \le y' ならば x \le x' \le y' \le y より x \le y となるので、

  • x \le y \iff x' \le y'

が成り立ちます。よって \bar{O} に二項関係 \leqq を \bar{x} \leqq \bar{y} \iff x \le y と定義することができます。 \leqq は半順序となります。

集合 O 上の前順序 \le に対して、

  • (WF1) O の任意の空でない部分集合が極小元を持つ

が成り立つとき \le は整礎(well-founded)であるといいます。(Wikipediaでは、二項関係に対して「整礎」が定義されています。また、半順序に対しても「整礎」が定義されています。ここでは、前順序に対して「整礎」を定義します。)

(WF1) は、以下の条件(WF2)と同値となります。
  • (WF2) O の元からなる無限降下列が存在しない

[証明] (WF1)⇒(WF2): (WF1)を仮定します。 x_1 > x_2 > x_3 > \cdots を O の元の無限個の列とすると、(WF1)より X = \{x_1, x_2, x_3, \cdots \} の極小元が存在します。極小元を x_i とすると x_i > x_{i+1} であり、これは x_i が極小元であることに反します。よって(WF2)が成り立ちます。

(WF2)⇒(WF1): (WF1)が成り立たないと仮定します。極小元を持たない O の空でない部分集合 X が存在します。 X は極小元を持たないので x \in X に対して x > y となる y \in X が存在します。この y を y(x) と書くことにします。

X は空でないので x_1 \in X が存在します。 x_{i+1} = y(x_i) と帰納的に定義すると x_1 > x_2 > x_3 > \cdots という無限個の列が存在するので(WF2)が成り立ちません。[証明終わり]

\le が全順序であるとき、整列順序と呼び、 O を整列集合と呼びます。

写像と順序の関係

M を集合、 s: M \to M を写像とします。 M の部分集合全体の集合を \mathfrak{P}(M) とします。 \bar{s}: \mathfrak{P}(M) \to \mathfrak{P}(M) を \displaystyle \bar{s}(X) = \bigcup_{x \in X} \{s(x)\} = \{ s(x) \mid x \in X \} とします。

  • \mathcal{R}_x = \{ X \in \mathfrak{P}(M) \mid x \in X \ かつ \ \bar{s}(X) \subseteq X \}

とおきます。

s^*: M \to \mathfrak{P}(M) を x \in M に対して

  • \displaystyle s^*(x) = \bigcap \mathcal{R}_x

( \mathcal{R}_x に属する M の部分集合全体の共通部分)とおくと(これは s^*(x) = \{x, s(x), s^2(x), \cdots \} = \{ s^n(x) \mid n \in \mathbb{N} \} を表すものとなります)

  • (O1-1) x \in s^*(x)
  • (O1-2) \bar{s}(s^*(x)) \subseteq s^*(x)

が成り立ちます。よって

  • (O1) s^*(x) \in \mathcal{R}_x

となります。また、

  • (O2) X \in \mathcal{R}_x \implies s^*(x) \subseteq X

が成り立ちます。また、(O1-1)、(O1-2)より

  • (O3) s(x) \in s^*(x)

が成り立ちます。以下の(O4)が成り立ちます。

(O4) s^*(x) \supseteq s^*(y) \iff y \in s^*(x)

[証明] s^*(x) \supseteq s^*(y) とすると (O1-1)より y \in s^*(y) \subseteq s^*(x) となります。

x \in M に対して X = \{ y \in s^*(x) \mid s^*(x) \supseteq s^*(y) \} とおきます。 x \in X、 \bar{s}(X) \subseteq X となるので X \in \mathcal{R}_x となります。よって s^*(x) = \bigcap \mathcal{R}_x \subseteq X となります。

y \in s^*(x) とすると y \in s^*(x) \subseteq X となるので s^*(x) \supseteq s^*(y) となります。[証明終わり]

(O5) s^*(x) = \{x\} \cup s^*(s(x))

[証明] (\subseteq) : (O1-1)より x \in s^*(x)、(O1-2)、(O3)より s^*(s(X)) \subseteq s^*(x) となるので成り立ちます。

(\supseteq) : X = \{x\} \cup s^*(s(x)) とおきます。 x \in X、 \bar{s}(X) \subseteq X となるので X \in \mathcal{R}_x となります。よって s^*(x) = \bigcap \mathcal{R}_x \subseteq X となります。[証明終わり]

(O6) \bar{s}(s^*(x)) = s^*(s(x))

[証明] (\subseteq) : (O5)より \bar{s}(s^*(x)) \subseteq \{s(x)\} \cup \bar{s}(s^*(s(x))) \subseteq s^*(s(x)) となるので成り立ちます。

(\supseteq) : X = \bar{s}(s^*(x)) とおきます。 s(x) \in X、 \bar{s}(X) \subseteq X となるので X \in \mathcal{R}_{s(x)} となります。よって s^*(s(x)) = \bigcap \mathcal{R}_{s(x)} \subseteq X となります。[証明終わり]

x, y \in M に対して

  • x \le y \iff s^*(x) \supseteq s^*(y)

と定義すると \supseteq が前順序であることから \le は前順序となります。定義と(O4)より

  • (O7) x \le y \iff y \in s^*(x)

が成り立ちます。(O3)、(O7)より

  • (O8) x \le s(x)

が成り立ちます。

x_0 \in M をとり N = s^*(x_0) とおきます。

(帰納法) N \in \mathcal{R}_{x_0} となるので x \in N に関する条件 p(x) が

  • p(x_0)
  • p(x) \implies p(s(x))

を満たすならば任意の x \in N に対して p(x) が成り立ちます。

写像の分類

以下の条件を考えます。

  • (N_1) 任意の x \in N に対して s(x) \ne x
  • (N_2) 任意の x \in N に対して s(x) \ne x_0
  • (N_3) N 上で s は単射
  • (N_4) N 上で \le は全順序
  • (N_5) N は無限集合

これらの条件により以下の表のようにタイプ T_1 から T_5 に分類することができます。

タイプ N_1 N_2 N_3 N_4 N_5 図式
T_1 = N_1 \land N_2 \land N_3 ○ ○ ○ ○ ○ 0 \to 1 \to \cdots
T_2 = N_1 \land N_2 \land \neg N_3 ○ ○ × × × 0 \to 1 \to \cdots \to n \to \cdots \to n
T_3 = N_1 \land \neg N_2 ○ × ○ × × 0 \to 1 \to \cdots \to 0
T_4 = \neg N_1 \land N_2 × ○ × ○ × 0 \to 1 \to \cdots \to n \to n
T_5 = \neg N_1 \land \neg N_2 × × ○ ○ × 0 \to 0

この表は「○」のところは成り立ち、「×」のところは成り立たないことを表しています。「図式」のところは各タイプの意味を表すものが書かれています。タイプ T_1 が自然数を表すものとなります。この表が成り立つことを次回以降示していきたいのですが、この表は自然数の定義となるものなので、自然数を使わない形で示していく予定です。

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)

  • 発売日: 2016/05/24
  • メディア: 単行本
位相のこころ Math＆Science (ちくま学芸文庫)

位相のこころ Math＆Science (ちくま学芸文庫)

初等整数論入門 Math＆Science (ちくま学芸文庫)

初等整数論入門 Math＆Science (ちくま学芸文庫)

エレファントな整数論(20)

「不等式の方法」で証明を書いていこうと思いますが、その前に必要なことを「集合と位相」に従って書いておきます。

集合と写像

f: C \to Z、 A, B \subseteq C、 X, Y \subseteq Z とします。 f(A)、 f^{-1}(X) を以下のように定義します。

  • x \in f(A) \iff \exists a \in A ( x = f(a) )
  • a \in f^{-1}(X) \iff f(a) \in X

以下のことが成り立ちます。(「集合と位相」定理5.2 を参照)

(1-1) f(A \cup B) = f(A) \cup f(B)

[証明]
\begin{eqnarray*} x \in f(A \cup B) & \iff & \exists a \in A \cup B ( x = f(a) ) \\ & \iff & \exists a \in C (a \in A \cup B \land x = f(a) ) \\ & \iff & \exists a \in C ( (a \in A \lor a \in B) \land x = f(a) ) \\ & \iff & \exists a \in C ( (a \in A \land x = f(a) ) \lor ( a \in B \land x = f(a) ) \\ & \iff & \exists a \in C ( a \in A \land x = f(a) ) \lor \exists a \in C ( a \in B \land x = f(a) ) \\ & \iff & x \in f(A) \lor x \in f(B) \\ & \iff & x \in f(A) \cup f(B) \\ \end{eqnarray*}
[証明終わり]

(1-2) f(A \cap B) \subseteq f(A) \cap f(B)

[証明]
\begin{eqnarray*} x \in f(A \cap B) & \iff & \exists a \in A \cap B ( x = f(a) ) \\ & \iff & \exists a \in C (a \in A \cap B \land x = f(a) ) \\ & \iff & \exists a \in C ( (a \in A \land a \in B) \land x = f(a) ) \\ & \iff & \exists a \in C ( (a \in A \land x = f(a) ) \land ( a \in B \land x = f(a) ) \\ & \implies & \exists a \in C ( a \in A \land x = f(a) ) \land \exists a \in C ( a \in B \land x = f(a) ) \\ & \iff & x \in f(A) \land x \in f(B) \\ & \iff & x \in f(A) \cap f(B) \\ \end{eqnarray*}
[証明終わり]

(1-3) f^{-1}(X \cup Y) = f^{-1}(X) \cup f^{-1}(Y)

[証明]
\begin{eqnarray*} a \in f^{-1}(X \cup Y) & \iff & f(a) \in X \cup Y \\ & \iff & f(a) \in X \lor f(a) \in Y \\ & \iff & a \in f^{-1}(X) \lor a \in f^{-1}(Y) \\ & \iff & a \in f^{-1}(X) \cup f^{-1}(Y) \\ \end{eqnarray*}
[証明終わり]

(1-4) f^{-1}(X \cap Y) = f^{-1}(X) \cap f^{-1}(Y)

[証明]
\begin{eqnarray*} a \in f^{-1}(X \cap Y) & \iff & f(a) \in X \cap Y \\ & \iff & f(a) \in X \land f(a) \in Y \\ & \iff & a \in f^{-1}(X) \land a \in f^{-1}(Y) \\ & \iff & a \in f^{-1}(X) \cap f^{-1}(Y) \\ \end{eqnarray*}
[証明終わり]

(1-5) A \subseteq f^{-1}(f(A))

[証明]
\begin{eqnarray*} a \in A & \implies & f(a) \in f(A) \\ & \iff & a \in f^{-1}(f(A)) \\ \end{eqnarray*}
[証明終わり]

(1-6) f(f^{-1}(X)) \subseteq X

[証明]
\begin{eqnarray*} x \in f(f^{-1}(X)) & \iff & \exists a \in f^{-1}(X) ( x = f(a) ) \\ & \iff & \exists a \in C ( f(a) \in X \land x = f(a) ) \\ & \iff & x \in X \land \exists a \in C ( x = f(a) ) \\ & \iff & x \in X \land x \in f(C) \\ \end{eqnarray*}
[証明終わり]

(1-7) f(A) \setminus f(B) \subseteq f(A \setminus B)

[証明]
\begin{eqnarray*} x \in f(A \setminus B) & \iff & \exists a \in A \setminus B ( x = f(a) ) \\ & \iff & \exists a \in C (a \in A \setminus B \land x = f(a) ) \\ & \iff & \exists a \in C ( a \in A \land a \notin B \land x = f(a) ) \\ & \Longleftarrow & \exists a \in C ( a \in A \land x = f(a) ) \land \forall a \in C ( a \in B \implies x \ne f(a) ) \\ & \iff & x \in f(A) \land x \notin f(B) \\ & \iff & x \in f(A) \setminus f(B) \\ \end{eqnarray*}
[証明終わり]

(1-8) f^{-1}(X) \setminus f^{-1}(Y) = f^{-1}(X \setminus Y)

[証明]
\begin{eqnarray*} a \in f^{-1}(X \setminus Y) & \iff & f(a) \in X \setminus Y \\ & \iff & f(a) \in X \land f(a) \notin Y \\ & \iff & a \in f^{-1}(X) \land a \notin f^{-1}(Y) \\ & \iff & a \in f^{-1}(X) \setminus f^{-1}(Y) \\ \end{eqnarray*}
[証明終わり]

集合系と写像の関係

f: X \to Y、 X の部分集合系 (A_\lambda \mid \lambda \in \Lambda)、 Y の部分集合系 (B_\mu \mid \mu \in M) に対して以下が成り立ちます。(「集合と位相」問5.4 を参照)

(2-1) \displaystyle f(\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} f(A_\lambda)

[証明]
\begin{eqnarray*} y \in f(\bigcup_{\lambda \in \Lambda} A_\lambda) & \iff & \exists x \in X (x \in \bigcup_{\lambda \in \Lambda} A_\lambda \land y = f(x) ) \\ & \iff & \exists x \in X ( \exists \lambda \in \Lambda (x \in A_\lambda) \land y = f(x) ) \\ & \iff & \exists x \in X ( \exists \lambda \in \Lambda (x \in A_\lambda \land y = f(x))) \\ & \iff & \exists \lambda \in \Lambda (\exists x \in X (x \in A_\lambda \land y = f(x))) \\ & \iff & \exists \lambda \in \Lambda (y \in f(A_\lambda)) \\ & \iff & y \in \bigcup_{\lambda \in \Lambda} f(A_\lambda) \\ \end{eqnarray*}
[証明終わり]

(2-2) \displaystyle f(\bigcap_{\lambda \in \Lambda} A_\lambda) \subseteq \bigcap_{\lambda \in \Lambda} f(A_\lambda)

[証明]
\begin{eqnarray*} y \in f(\bigcap_{\lambda \in \Lambda} A_\lambda) & \iff & \exists x \in X (x \in \bigcap_{\lambda \in \Lambda} A_\lambda \land y = f(x) ) \\ & \iff & \exists x \in X ( \forall \lambda \in \Lambda (x \in A_\lambda) \land y = f(x) ) \\ & \iff & \exists x \in X ( \forall \lambda \in \Lambda (x \in A_\lambda \land y = f(x))) \\ & \implies & \forall \lambda \in \Lambda (\exists x \in X (x \in A_\lambda \land y = f(x))) \\ & \iff & \forall \lambda \in \Lambda (y \in f(A_\lambda)) \\ & \iff & y \in \bigcap_{\lambda \in \Lambda} f(A_\lambda) \\ \end{eqnarray*}
[証明終わり]

(2-3) \displaystyle f^{-1}(\bigcup_{\mu \in M} B_\mu) = \bigcup_{\mu \in M} f^{-1}(B_\mu)

[証明]
\begin{eqnarray*} x \in f^{-1}(\bigcup_{\mu \in M} B_\mu) & \iff & f(x) \in \bigcup_{\mu \in M} B_\mu \\ & \iff & \exists \mu \in M (f(x) \in B_\mu) \\ & \iff & \exists \mu \in M (x \in f^{-1}(B_\mu)) \\ & \iff & x \in \bigcup_{\mu \in M} f^{-1}(B_\mu) \\ \end{eqnarray*}
[証明終わり]

(2-4) \displaystyle f^{-1}(\bigcap_{\mu \in M} B_\mu) = \bigcap_{\mu \in M} f^{-1}(B_\mu)

[証明]
\begin{eqnarray*} x \in f^{-1}(\bigcap_{\mu \in M} B_\mu) & \iff & f(x) \in \bigcap_{\mu \in M} B_\mu \\ & \iff & \forall \mu \in M (f(x) \in B_\mu) \\ & \iff & \forall \mu \in M (x \in f^{-1}(B_\mu)) \\ & \iff & x \in \bigcap_{\mu \in M} f^{-1}(B_\mu) \\ \end{eqnarray*}
[証明終わり]

上極限集合・下極限集合

集合系 (E_n \mid n \in \mathbb{N}) に対して

  • 上極限集合 \displaystyle \limsup_{n \to \infty} E_n = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n
  • 下極限集合 \displaystyle \liminf_{n \to \infty} E_n = \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} E_n

を定義します。上極限集合、下極限集合について以下が成り立ちます。(「集合と位相」問5.6 を参照)

(3-1) \displaystyle \liminf_{n \to \infty} E_n \subseteq \limsup_{n \to \infty} E_n

[証明] 任意の n \in \mathbb{N} に対して n \ge k_0 ならば x \in E_n となる k_0 \in \mathbb{N} が存在するとします。任意の k \in \mathbb{N} に対して m = \max(k_0, k) とおくと m \ge k_0 なので x \in E_m となります。よって
\begin{eqnarray*} x \in \liminf_{n \to \infty} E_n & \iff & x \in \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} E_n \\ & \iff & \exists k \in \mathbb{N} ( \forall n \in \mathbb{N} (n \ge k \implies x \in E_n)) \\ & \implies & \forall k \in \mathbb{N} ( \exists n \in \mathbb{N} (n \ge k \land x \in E_n)) \\ & \iff & x \in \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n \\ & \iff & x \in \limsup_{n \to \infty} E_n \\ \end{eqnarray*}
[証明終わり]

(3-2) 「すべての n \in \mathbb{N} に対して A_n \subseteq B_n」が成り立つとき \displaystyle \limsup_{n \to \infty} A_n \subseteq \limsup_{n \to \infty} B_n、 \displaystyle \liminf_{n \to \infty} A_n \subseteq \liminf_{n \to \infty} B_n

[証明] 定義より
\displaystyle \limsup_{n \to \infty} A_n = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} A_n \subseteq \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} B_n = \limsup_{n \to \infty} B_n
\displaystyle \liminf_{n \to \infty} A_n = \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} A_n \subseteq \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} B_n = \liminf_{n \to \infty} B_n
[証明終わり]

(3-3) \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) = \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n

[証明] \displaystyle x \in \limsup_{n \to \infty} (A_n \cup B_n) \setminus \limsup_{n \to \infty} A_n = \left( \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} (A_n \cup B_n) \right) \setminus \left( \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} A_n \right) とすると \displaystyle x \notin \bigcup_{n=k_0}^{\infty} A_n となる k_0 \in \mathbb{N} が存在します。

k \ge k_0 ならば \displaystyle x \notin \bigcup_{n=k}^{\infty} A_n であり、 \displaystyle x \in \bigcup_{n=k}^{\infty} (A_n \cup B_n) = \left( \bigcup_{n=k}^{\infty} A_n \right) \cup \left( \bigcup_{n=k}^{\infty} B_n \right) より \displaystyle x \in \bigcup_{n=k}^{\infty} B_n となります(*1)。

また、 \displaystyle x \in \bigcup_{n=k_0}^{\infty} B_n より k \le k_0 ならば \displaystyle x \in \bigcup_{n=k}^{\infty} B_n となります(*2)。

(*1)、(*2)より \displaystyle x \in \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} B_n = \limsup_{n \to \infty} B_n となります。よって \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) \subseteq \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n が成り立ちます。

(3-2)より \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) \supseteq \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n が成り立つので \displaystyle \limsup_{n \to \infty} (A_n \cup B_n) = \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n が成り立ちます。[証明終わり]

(3-4) \displaystyle \liminf_{n \to \infty} (A_n \cap B_n) = \liminf_{n \to \infty} A_n \cap \liminf_{n \to \infty} B_n

[証明] ド・モルガンの法則より \displaystyle \left( \limsup_{n \to \infty} E_n \right)^c = \left( \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n \right)^c = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n^c = \liminf_{n \to \infty} E_n^c
が成り立ちます。(3-3)より
\begin{eqnarray*} \liminf_{n \to \infty} (A_n \cap B_n) & = & \left( \limsup_{n \to \infty} (A_n \cap B_n)^c \right)^c \\ & = & \left( \limsup_{n \to \infty} (A_n^c \cup B_n^c) \right)^c \\ & = & \left( \limsup_{n \to \infty} A_n^c \cup \limsup_{n \to \infty} B_n^c \right)^c \\ & = & \left( \limsup_{n \to \infty} A_n^c \right)^c \cap \left( \limsup_{n \to \infty} B_n^c \right)^c \\ & = & \liminf_{n \to \infty} A_n \cap \liminf_{n \to \infty} B_n \end{eqnarray*}
となります。[証明終わり]

極限集合

集合系 (E_n \mid n \in \mathbb{N}) に対して上極限集合と下極限集合が一致するとき、これを極限集合といい \displaystyle \lim_{n \to \infty} E_n = \limsup_{n \to \infty} E_n = \liminf_{n \to \infty} E_n で表します。極限集合について以下が成り立ちます。(「集合と位相」問5.7 を参照)

(4-1) 「(条件*)すべての n \in \mathbb{N} に対して E_n \subseteq E_{n+1}」が成り立つとき \displaystyle \lim_{n \to \infty} E_n = \bigcup_{n=0}^{\infty} E_n

[証明] (条件*)より \displaystyle \bigcap_{n=k}^{\infty} E_n = E_k となるので \displaystyle \liminf_{n \to \infty} E_n = \bigcup_{k=0}^{\infty} \bigcap_{n=k}^{\infty} E_n = \bigcup_{k=0}^{\infty} E_k となり、 \displaystyle \limsup_{n \to \infty} E_n = \bigcap_{k=0}^{\infty} \bigcup_{n=k}^{\infty} E_n \subseteq \bigcup_{n=0}^{\infty} E_n = \liminf_{n \to \infty} E_n が成り立ちます。

また (3-1)より \displaystyle \liminf_{n \to \infty} E_n \subseteq \limsup_{n \to \infty} E_n となるので、 \displaystyle \limsup_{n \to \infty} E_n = \liminf_{n \to \infty} E_n = \bigcup_{n=0}^{\infty} E_n が成り立ちます。[証明終わり]

(4-2) 「(条件*)すべての n \in \mathbb{N} に対して E_n \supseteq E_{n+1}」が成り立つとき \displaystyle \lim_{n \to \infty} E_n = \bigcap_{n=0}^{\infty} E_n

[証明] (条件*)より任意の n \in \mathbb{N} に対して E_n^c \subseteq E_{n+1}^c となるので、
(4-1)より \displaystyle \limsup_{n \to \infty} E_n^c = \liminf_{n \to \infty} E_n^c = \bigcup_{n=0}^{\infty} E_n^c が成り立ちます。各項の補集合をとるとド・モルガンの法則より \displaystyle \liminf_{n \to \infty} E_n = \limsup_{n \to \infty} E_n = \bigcap_{n=0}^{\infty} E_n が成り立ちます。[証明終わり]

\displaystyle \lim_{n \to \infty} A_n、 \displaystyle \lim_{n \to \infty} B_n がともに存在すれば以下が成り立ちます。(「集合と位相」問5.8 を参照)

(5-1) \displaystyle \lim_{n \to \infty} (A_n \cup B_n) = \lim_{n \to \infty} A_n \cup \lim_{n \to \infty} B_n

[証明] (3-2)、(3-1)、(3-3)より
\begin{eqnarray*} \liminf_{n \to \infty} A_n \cup \liminf_{n \to \infty} B_n & \subseteq & \liminf_{n \to \infty} (A_n \cup B_n) \\ & \subseteq & \limsup_{n \to \infty} (A_n \cup B_n) \\ & = & \limsup_{n \to \infty} A_n \cup \limsup_{n \to \infty} B_n \\ \end{eqnarray*}
となります。 \displaystyle \liminf_{n \to \infty} A_n = \limsup_{n \to \infty} A_n、 \displaystyle \liminf_{n \to \infty} B_n = \limsup_{n \to \infty} B_n ならば上記の式の項はすべて等しくなります。[証明終わり]

(5-2) \displaystyle \lim_{n \to \infty} (A_n \cap B_n) = \lim_{n \to \infty} A_n \cap \lim_{n \to \infty} B_n

[証明] (3-4)、(3-1)、(3-2)より
\begin{eqnarray*} \liminf_{n \to \infty} A_n \cap \liminf_{n \to \infty} B_n & = & \liminf_{n \to \infty} (A_n \cap B_n) \\ & \subseteq & \limsup_{n \to \infty} (A_n \cap B_n) \\ & \subseteq & \limsup_{n \to \infty} A_n \cap \limsup_{n \to \infty} B_n \\ \end{eqnarray*}
となります。 \displaystyle \liminf_{n \to \infty} A_n = \limsup_{n \to \infty} A_n、 \displaystyle \liminf_{n \to \infty} B_n = \limsup_{n \to \infty} B_n ならば上記の式の項はすべて等しくなります。[証明終わり]

順序関係

集合 X 上の二項関係 \le が

  • 反射律: 任意の x \in X に対して x \le x
  • 推移律: 任意の x , y, z \in X に対して x \le y \le z ならば x \le z
  • 反対称律: 任意の x , y \in X に対して x \le y かつ y \le x ならば x = y

を満たすとき半順序と呼びます。単に順序(順序関係)という場合は半順序のことを表すとします。さらに

  • 任意の x , y \in X に対して x \le y または y \le x

を満たすとき全順序と呼びます。

集合 X の部分集合の全体を X の冪集合と呼び \mathfrak{P}(X) で表します。 A \subseteq B で決まる \mathfrak{P}(X) 上の二項関係 \subseteq は順序関係となります。これを \mathfrak{P}(X) 上の包含関係と呼びます。(「集合と位相」例8.1 を参照)

同値関係

集合 X 上の二項関係 \cong が

  • 反射律: 任意の x \in X に対して x \cong x
  • 推移律: 任意の x , y, z \in X に対して x \cong y \cong z ならば x \cong z
  • 対称律: 任意の x , y \in X に対して x \cong y ならば y \cong x

を満たすとき同値関係と呼びます。

集合 X 上の同値関係 \cong が与えられたとき、 x \in X に対して X の部分集合 C(x) = \{ y \in X \mid x \cong y \} を x の同値類と呼びます。同値類全体の集合を集合 X の同値関係 \cong による商集合と呼び、 X/\cong と書きます。 x \in X を C(x) \in X/\cong に対応させる全射 f を X から X/\cong への自然な射影と呼びます。 \cong が同値関係であることから、同値類の全体は、集合 X を互いに交わらない部分集合に分割します。

f: X \to Y に対して、 x \cong y \iff f(x) = f(y) で定義される X 上の関係 \cong は同値関係となります。 \cong を f に付随する同値関係と呼びます。 C(x) = C(y) \iff f(x) = f(y) となるので、同値類 C(x) に f(x) を対応させる写像 g: {X/\cong} \to f(Y) を定義することができます。 g は全単射となります。(「集合と位相」問8.3 を参照)

集合と位相(増補新装版)(数学シリーズ)

集合と位相(増補新装版)(数学シリーズ)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)

新版 集合と位相 そのまま使える答えの書き方 (KS理工学専門書)

  • 発売日: 2016/05/24
  • メディア: 単行本

中間報告(5)

中間報告

このブログは、論理プログラミングに実行順序を指定する機能を追加してサーバーで動作するような無限に動作するプログラムを記述することを一つの目標としています。この方法についていろいろな案を考えていきたいと思います。

前回の中間報告以降更新したもの

エレファントな整数論

素因数分解の一意性の説明のところまで終わった状況です。今後はこの説明の中の数学的帰納法の部分について記法を考えていきます。できればプログラミング言語で使えるようにしたいと考えています。

ある定義を変数を使った不等式のような形で書いて、単一化のように不等式の両辺が一致する代入を考えることで、この代入で数学的帰納法を表すことができると考えられます。今後はこの方法について考えていきます。数学的帰納法についてもう少し考えてみる予定です。

エレファントな線形代数

連立一次方程式の解法や行列のランクなどは行列の行の順序に依存しないので、行列を使わなくても説明できる部分が多いのではないかということでやっていたのですが、行列を使わないと説明が難しい部分がけっこうあるということがわかってきました。

今後は行列を使わなくても良い部分について上記の不等式の方法で記述することを考えていきます。

前回の中間報告以降更新していないもの

エレファントな関数論

コーシーの積分定理の証明について調査中です。今後はこれが不等式の方法で記述できるかどうか調べていきたいと思います。リウヴィルの定理、解析接続についてもうまく記述できるかどうかを考えていきたいと思います。

エレファントなポアンカレ予想

「エレファントな線形代数」で行列のランクの説明を書こうとしていますが、これができれば、ホモロジーの計算の記述をしようと考えています。

論理プログラミング的リーマン予想

「エレファントな関数論」で解析接続の記述ができれば、それを使ってリーマン予想の記述をしようと考えています。

半環上のフラクタル代数

Prologの実行順序を説明しようとしています。

論理プログラミング

無限に続く入出力を、論理プログラミングを使って極限として記述する方法を考えています。

フラクタル代数言語 Fractal

論理プログラミング言語であるPrologのような言語に、実行順序を指定する機能を追加する方法を考えています。

斜めの線を使わない圏論

極限、随伴を不等式の方法で説明することはできないか調べてみる予定です。

関数プログラミング

関数プログラミングの実行順序について調べようとしています。

群論の計算

不等式の方法で説明できる部分がないか調べてみる予定です。

今後の予定

P≠NP予想、リー代数についても不等式の方法で説明できるものがあるのか少し調べてみましたが、今のところは何もできていません。そのほかのいろいろな事例についても考えてみる予定です。

エレファントな線形代数(5)

行列式

「現代数学のエレファント」の記事で行列式を使って説明を書いていましたが、計算が長くなりすぎるため中断していました。しかし行列式を使わないとうまく説明できないことがあるので、もう一度説明していきます。

線型写像

V を体 K 上の n 次元ベクトル空間、 W を体 K 上の m 次元ベクトル空間とします。 f: V \to W が

  • 任意の u, v \in V に対して f(u + v) = f(u) + f(v)
  • 任意の v \in V、任意の a \in K に対して f(av) = af(v)

を満たすとき、 V から W への線型写像と呼びます。 V から W への線型写像の全体を \mathbf{Lin}(V, W) と書くことにします。 \mathbf{Lin}(V, W) に和とスカラー倍を

  • f, g \in \mathbf{Lin}(V, W) に対して (f + g)(v) = f(v) + g(v) \ (v \in V)
  • f \in \mathbf{Lin}(V, W)、 a \in K に対して (af)(v) = f(av) \ (v \in V)

と定義すると K 上の mn 次元ベクトル空間となります。

外積

まず外積の説明を書いていきます。外積に関しては以前書いたものとほとんど同じです。

V を体 K 上の n 次元ベクトル空間、 \{e_1, e_2, \cdots , e_n\} を基底とします。
E_k = \{e_{ { i_{1} } }\wedge e_{ {i_{2} }}\wedge \cdots \wedge e_{ { i_{k} } }\mid 1\leq i_{1} < i_{2} < \cdots < i_{k}\leq n\}
を基底とする K 上のベクトル空間(に以下のような演算を定義したもの)を k-次外冪と呼び \bigwedge^k(V) と書きます(この定義はWikipediaによる)。 \bigwedge^k(V) の次元は二項係数 \binom{n}{k} となります。

これらのベクトル空間の直和(すべての E_k を基底とする 2^n 次元ベクトル空間)
\displaystyle \textstyle \bigwedge (V)=\bigwedge ^{0}(V)\oplus \bigwedge ^{1}(V)\oplus \bigwedge ^{2}(V)\oplus \cdots \oplus \bigwedge ^{n}(V)
(に以下のような演算を定義したもの)を外積代数と呼びます(この定義はWikipediaによる)。ここで \bigwedge^0(V) = K、 \bigwedge^1(V) = V とします。

\bigwedge (V) に演算
\wedge \colon \bigwedge (V) \times \bigwedge (V) \to \bigwedge (V)
を定義します。

まず V \times V に制限した演算を考えます。
\wedge_1 \colon V \times V \to \bigwedge^2 (V) を
\displaystyle \left(\sum_{i=1}^{n} a_i e_i\right) \wedge_1 \left(\sum_{j=1}^{n} b_j e_j\right) = \sum_{i=1}^{n} \sum_{j=i+1}^{n} (a_i b_j - a_j b_i) (e_i \wedge e_j)
と定義すると
\displaystyle \left(\sum_{i=1}^{n} a_i e_i\right) \wedge_1 \left(\sum_{j=1}^{n} b_j e_j\right) = \sum_{i=1}^{n} \sum_{j=1}^{n} a_i b_j (e_i \wedge e_j)
を満たします。

  • (多重線型性)
    • 任意の u, v, w \in V に対して (u + v) \wedge_1 w = (u \wedge_1 w) + (v \wedge_1 w)
    • 任意の u, v, w \in V に対して u \wedge_1 (v + w) = (u \wedge_1 w) + (v \wedge_1 w)
    • 任意の u, v \in V、任意の a \in K に対して au \wedge_1 v = u \wedge_1 av = a(u \wedge_1 v)
  • 任意の v \in V に対して v \wedge_1 v = 0

が成り立ちます。

\wedge_k \colon \bigwedge^k (V) \times V \to \bigwedge^{k+1} (V) を k=1 のときは \wedge_1、 k \ge 2 のときは
(e_{ { i_{1} } }\wedge e_{ {i_{2} }}\wedge \cdots \wedge e_{ { i_{k} } }) \wedge_k e_j
= \begin{cases} - ( (e_{ { i_{1} } } \wedge e_{ {i_{2} }} \wedge \cdots \wedge e_{ { i_{k-1} } }) \wedge_{k-1} e_j) \wedge e_{ { i_{k} } } & (i_k > j のとき) \\ 0 & (i_k = j \ のとき) \\ e_{ { i_{1} } } \wedge e_{ {i_{2} }} \wedge \cdots \wedge e_{ { i_{k} } } \wedge e_j & (i_k < j のとき) \\ \end{cases}
と帰納的に定義することができます。

これを繰り返して \wedge_{k,l} \colon \bigwedge^k (V) \times \bigwedge^l (V) \to \bigwedge^{k+l} (V) を定義することができます。

  • (結合性)
    • 任意の x \in \bigwedge^k (V)、 y \in \bigwedge^l (V)、 z \in \bigwedge^m (V) に対して (x \wedge_{k,l} y) \wedge_{k+l,m} z = x \wedge_{k,l+m} (y \wedge_{l,m} z)
  • (多重線型性)
    • 任意の x, y \in \bigwedge^k (V)、 z \in \bigwedge^l (V) に対して (x + y) \wedge_{k,l} z = (x \wedge_{k,l} z) + (y \wedge_{k,l} z)
    • 任意の x \in \bigwedge^k (V)、 y, z \in \bigwedge^l (V) に対して x \wedge_{k,l} (y + z) = (x \wedge_{k,l} y) + (x \wedge_{k,l} z)
    • 任意の x \in \bigwedge^k (V)、 y \in \bigwedge^l (V)、任意の a \in K に対して ax \wedge_{k,l} y = x \wedge_{k,l} ay = a(x \wedge_{k,l} y)

が成り立ちます。

\wedge_{*} \colon \bigwedge (V) \times \bigwedge (V) \to \bigwedge (V) を
\displaystyle \left(\sum_{i=1}^{n} x_i \right) \wedge_* \left(\sum_{j=1}^{n} y_j \right) = \sum_{i=1}^{n} \sum_{j=1}^{n} (x_i \wedge_{i,j} y_j)
( x_i \in \bigwedge^i (V)、 y_j \in \bigwedge^j (V))と定義すると

  • (結合性)
    • 任意の x, y, z \in \bigwedge (V) に対して (x \wedge_{*} y) \wedge_{*} z = x \wedge_{*} (y \wedge_{*} z)
  • (多重線型性)
    • 任意の x, y, z \in \bigwedge (V) に対して (x + y) \wedge_{*} z = (x \wedge_{*} z) + (y \wedge_{*} z)
    • 任意の x, y, z \in \bigwedge (V) に対して x \wedge_{*} (y + z) = (x \wedge_{*} y) + (x \wedge_{*} z)
    • 任意の x, y \in \bigwedge (V)、任意の a \in K に対して ax \wedge_{*} y = x \wedge_{*} ay = a(x \wedge_{*} y)

が成り立ちます。

\wedge_* を \wedge と書くと \bigwedge (V) に演算
\wedge \colon \bigwedge (V) \times \bigwedge (V) \to \bigwedge (V)
が定義できます。

  • (結合性)
    • 任意の x, y, z \in \bigwedge (V) に対して (x \wedge y) \wedge z = x \wedge (y \wedge z)
  • (多重線型性)
    • 任意の x, y, z \in \bigwedge (V) に対して (x + y) \wedge z = (x \wedge z) + (y \wedge z)
    • 任意の x, y, z \in \bigwedge (V) に対して x \wedge (y + z) = (x \wedge y) + (x \wedge z)
    • 任意の x, y \in \bigwedge (V)、任意の a \in K に対して ax \wedge y = x \wedge ay = a(x \wedge y)
  • 任意の v \in V に対して v \wedge v=0

が成り立ちます。

この演算を外積と呼びます。外積によって \bigwedge (V) は体 K 上の単位的結合代数となります。

行列式

V を体 K 上の n 次元ベクトル空間、 \{e_1, e_2, \cdots , e_n\} を基底、 \varphi: V \to V を線型写像とします。
\bigwedge^{n}(V) は 1 次元で e_{1} \wedge \cdots \wedge e_{n} が基底となります。

\bigwedge^{n} \varphi : \bigwedge^{n} (V) \to \bigwedge^{n} (V) を \left( \bigwedge^{n} \varphi \right) ( e_{1} \wedge \cdots \wedge e_{n} ) = \varphi (e_{1}) \wedge \cdots \wedge \varphi (e_{n}) とすると \bigwedge^{n} \varphi は線型写像となります。

\bigwedge^{n} : \mathbf{Lin}(V, V) \to \mathbf{Lin}(\bigwedge^{n} (V), \bigwedge^{n} (V)) を \bigwedge^{n}(\varphi) = \bigwedge^{n} \varphi となる写像とすると、 \bigwedge^{n} は線型写像となります。

よって a \in K が存在して \left( \bigwedge^{n} \varphi \right) ( e_{1} \wedge \cdots \wedge e_{n} ) = a( e_{1} \wedge \cdots \wedge e_{n} ) となります。この a を \varphi の行列式と呼び \det \varphi と書きます。

偶置換・奇置換

「群論の計算(9)」で書いた内容ですが、ここにも書いておきます。この議論はもう少し簡単になるかもしれません。

置換 \sigma \in S_n に対して \sigma で順序が逆になる (i, j) の組の数、すなわち
T_\sigma = \{ (i, j) | i = 1, 2, \cdots, n , j = i+1, i+2, \cdots , n, \sigma(i) > \sigma(j) \}
の元の数 t_\sigma を \sigma の転倒数と呼びます。

j = i+1 として \mu = (ij) 、 \tau = \sigma \mu とおきます。 \tau の転倒数、すなわち
T_\tau = \{ (i, j) | i = 1, 2, \cdots, n , j = i+1, i+2, \cdots , n, \tau(i) > \tau(j) \}
の元の数を t_\tau とおきます。

  • \tau(i) = \sigma ( \mu (i)) = \sigma(j)
  • \tau(j) = \sigma ( \mu (j)) = \sigma(i)
  • \tau(k) = \sigma(k) \ (k \ne i, k \ne j)

が成り立つので

  • (i, j) \not \in T_\sigma のときは T_\tau = T_\sigma \cup \{ (i, j) \} 、 t_\tau = t_\sigma + 1
  • (i, j) \in T_\sigma のときは T_\tau = T_\sigma \setminus \{ (i, j) \} 、 t_\tau = t_\sigma - 1

となります。

これをバブルソートの手順のように繰り返して、 n を保存する置換を作ります。 \sigma(i) = n のとき
\xi = \sigma (i,i+1) (i+1,i+2) \cdots (n-1,n)
( (ij) をここでは (i,j) と書いています)とおくと、 \xi(n) = n となります。よって n-1 の場合に帰着させることができます。 n-1 以下にさらにバブルソートの手順のように行うと e = \sigma \mu_1 \mu_2 \cdots \mu_m という形にすることができます。ここで e は恒等写像、 \mu_i は互換となります。 \sigma = \mu_m \mu_{m-1} \cdots \mu_1 となるので \sigma は互換の積の形で表すことができます。

よって任意の置換は互換の積の形で表すことができます。

次に互換 \lambda = (ij) ( i \lt j)を考えます。 \lambda は上記の手順と同様に
(i, i+1) (i+1, i+2) \cdots (j -1, j)
で i の位置を j の位置に移動して
(j-2, j-1) (j-3, j-2) \cdots (i, i+1)
で j-1 の位置を i の位置に移動したと考えることができます。よって \lambda は奇数個の隣接する互換の積として表すことができます。

よって \sigma = \lambda_1 \lambda_2 \cdots \lambda_l ( \lambda_i は互換)とすると

  • \sigma の転倒数が偶数ならば l は偶数
  • \sigma の転倒数が奇数ならば l は奇数

となります。

よって置換を互換の積として表したとき、互換の個数が偶数なのか奇数なのかは置換によって決まっていることがわかります。偶数の互換の積として表される置換を偶置換、奇数の互換の積として表される置換を奇置換と呼びます。

行列式の成分による表示

\varphi: V \to V を線型写像とします。 n 行 n 列の行列 A を i 行 j 列成分を a_{ij} が
\displaystyle \varphi(e_i) = \sum_{j=1}^{n} a_{ij} e_j = a_{i1} e_1 + a_{i2} e_2 + \cdots + a_{in} e_n
を満たすものとします。

J = \{1, 2, \cdots, n\} とおきます。 e_j \wedge e_j = 0 より e_{j_1} \wedge \cdots \wedge e_{j_n} \ne 0、 k \ne l ならば j_k \ne j_l となります。よって e_{j_1} \wedge \cdots \wedge e_{j_n} \ne 0 のとき \sigma: J \to J を \sigma(k) = j_k とすると \sigma は全単射となります。 J から J への全単射全体の集合を S_n とすると \sigma \in S_n となります。よって
\begin{eqnarray*} & & \{(j_1, \cdots, j_n) \in J^n \mid e_{j_1} \wedge \cdots \wedge e_{j_n} \ne 0\} \\ & = & \{(j_1, \cdots, j_n) \in J^n \mid \sigma \in S_n \ が存在して \ (j_1, \cdots, j_n) = (\sigma(1), \cdots, \sigma(n)) \} \\ & = & \{ (\sigma(1), \cdots, \sigma(n)) \mid \sigma \in S_n \} \\ \end{eqnarray*}、
\begin{eqnarray*} & & \left( {\bigwedge}^{n} \varphi \right) ( e_{1} \wedge \cdots \wedge e_{n} ) \\ & = & \varphi (e_{1}) \wedge \cdots \wedge \varphi (e_{n}) \\ & = & \left( \sum_{j=1}^{n} a_{1j} e_j \right) \wedge \cdots \wedge \left( \sum_{j=1}^{n} a_{nj} e_j \right) \\ & = & \sum_{j_1=1}^{n}\cdots \sum_{j_n=1}^{n} a_{1j_1} \cdots a_{nj_n} (e_{j_1} \wedge \cdots \wedge e_{j_n}) \\ & = & \sum_{(j_1, \cdots, j_n) \in J^n} a_{1j_1} \cdots a_{nj_n} (e_{j_1} \wedge \cdots \wedge e_{j_n}) \\ & = & \sum_{\sigma \in S_n} a_{1\sigma(1)} \cdots a_{n\sigma(n)} (e_{\sigma(1)} \wedge \cdots \wedge e_{\sigma(n)}) \\ & = & \sum_{\sigma \in S_n} (\operatorname {sgn} \sigma ) a_{1\sigma(1)} \cdots a_{n\sigma(n)} (e_1 \wedge \cdots \wedge e_n) \\ \end{eqnarray*}
となります。ここで \operatorname {sgn} \sigma は
e_{\sigma(1)} \wedge \cdots \wedge e_{\sigma(n)} = (\operatorname {sgn} \sigma ) (e_1 \wedge \cdots \wedge e_n)
を満たすものとします。 \operatorname {sgn} \sigma = 1 または \operatorname {sgn} \sigma = -1 となります。 \operatorname {sgn} \sigma = 1 のとき \sigma を偶置換、 \operatorname {sgn} \sigma = -1 のとき \sigma を奇置換となります。「偶置換・奇置換」の議論より
\operatorname {sgn} \sigma \tau = (\operatorname {sgn} \sigma)(\operatorname {sgn} \tau)
が成り立ちます。

よって \tau = \sigma^{-1} と考えると
\displaystyle \sum_{\sigma \in S_n} (\operatorname {sgn} \sigma ) a_{1\sigma(1)} \cdots a_{n\sigma(n)} (e_1 \wedge \cdots \wedge e_n) = \sum_{\tau \in S_n} (\operatorname {sgn} \tau ) a_{\tau(1)1} \cdots a_{\tau(n)n} (e_1 \wedge \cdots \wedge e_n)
が成り立ちます。(*1)

行列の基本変形

行列の基本変形について、Wikipediaに従って行列の形で書いていきます。

E を単位行列、 I_{ij} を (i,j) 成分が 1 でそれ以外の成分が 0 であるような行列とします。以下のような (n, n) 行列を基本行列と呼びます。

A を (n, n) 行列とするとき

  • A に P(i, j) を左からかけると、 i 行と j 行が交換される。
  • A に Q(i, c) を左からかけると、 i 行が c 倍される。
  • A に T(i, j, c) を左からかけると、 i 行に j 行の c 倍が加わる。
  • \det P(i, j) = 1
  • \det Q(i, c) = c
  • \det T(i, j, c) = 1

が成り立ちます。

行列の基本変形と掃き出し法

K' = K(x_{11}, \cdots, x_{1n}, \cdots, x_{n1}, \cdots, x_{nn})、 X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{n1} & x_{n2} & \cdots & x_{nn} \\ \end{pmatrix} とします。

Y = \begin{pmatrix} y_{11} & y_{12} & \cdots & y_{1n} \\ y_{21} & y_{22} & \cdots & y_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ y_{n1} & y_{n2} & \cdots & y_{nn} \\ \end{pmatrix}、 v_i = \begin{pmatrix} y_{i1} & y_{i2} & \cdots & y_{in} \end{pmatrix} のとき Y = [ v_1, v_2, \cdots, v_n ] と書くことにします。

[ v_1, v_2, \cdots, v_k ] + [ u_1, u_2, \cdots, u_l ] = [ v_1, v_2, \cdots, v_k, u_1, u_2, \cdots, u_l ] とします。

v = \begin{pmatrix} y_{1} & y_{2} & \cdots & y_{n} \end{pmatrix}、 u = \begin{pmatrix} z_{1} & z_{2} & \cdots & z_{n} \end{pmatrix} のとき v \stackrel{i}{\to} u = v - \cfrac{y_i}{z_i} u、 [ v_1, v_2, \cdots, v_k ] \stackrel{i}{\to} u = [ v_1 \stackrel{i}{\to} u, v_2 \stackrel{i}{\to} u, \cdots, v_k \stackrel{i}{\to} u ] とします。

X に対して X_i、 v_{ij} = \begin{pmatrix} x[i,j,1] & x[i,j,2] & \cdots & x[i,j,n] \end{pmatrix} を以下のように決めます。

  • X_1 = [ v_{11}, v_{12}, \cdots, v_{1n} ] = X
  • X_k = [ v_{k1}, v_{k2}, \cdots, v_{kn} ] = [ v_{k1}, \cdots, v_{ki} ] + [ v_{ik}, \cdots, v_{in} ] \stackrel{i}{\to} v_{ii} (k=i+1)

X_k = T \left(k, i, -\cfrac{x[i,k,i]}{x[i,i,i]} \right) \cdots T \left(n, i, -\cfrac{x[i,n,i]}{x[i,i,i]} \right) X_i となります。

よって \det X = \det X_1 = \det X_2 = \cdots = \det X_n = x[1,1,1] x[2,2,2] \cdots x[n,n,n] となります。

A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{pmatrix} を K の元を成分とする行列とします。 x \in K' の X の各元に A の各元をそれぞれ代入したものを x \mid (X=A) と書くことにします。

1 = \det X \mid (X=E) = x[1,1,1] x[2,2,2] \cdots x[n,n,n] \mid (X=E) となるので \det X \ne 0 となります。 \det X \ne 0 である行列 X を正則行列と呼びます。

\sigma, \tau \in S_n とします。 X に対して
X^{\sigma,\tau} = \begin{pmatrix} x_{\sigma(1)\tau(1)} & x_{\sigma(1)\tau(2)} & \cdots & x_{\sigma(1)\tau(n)} \\ x_{\sigma(2)\tau(1)} & x_{\sigma(2)\tau(2)} & \cdots & x_{\sigma(2)\tau(n)} \\ \vdots & \vdots & \ddots & \vdots \\ x_{\sigma(n)\tau(1)} & x_{\sigma(n)\tau(2)} & \cdots & x_{\sigma(n)\tau(n)} \\ \end{pmatrix} とおきます。(*1)の結果より \det X^{\sigma,\tau} = (\operatorname{sgn} \sigma) (\operatorname{sgn} \tau) \det X となります。

A を K の元を成分とする行列、 \det A^{\sigma,\tau} を \det X^{\sigma,\tau} と同様に A の行を \sigma、列を \tau で置換した行列とします。 \det A \ne 0 ならば
\det A^{\sigma,\tau} = \det X^{\sigma,\tau} \mid (X=A) = (\operatorname{sgn} \sigma) (\operatorname{sgn} \tau) \det X \mid (X=A) = (\operatorname{sgn} \sigma) (\operatorname{sgn} \tau) \det A \ne 0
となります。

エレファントな線形代数(4)

順序に依存する掃き出し法

ここで再び順序に依存する場合を考えます。

E = [ e_{1}, e_{2}, \cdots, e_{n} ] とし、以下のように R = [ r_{1}, r_{2}, \cdots, r_{n} ] を決めます(順序に依存する列をこのように書くことにします)。
\left\{ \begin{matrix} E_1 = E & = & [ e_{11}, e_{12}, \cdots, e_{1n} ] \\ E_2 & = & [ e_{22}, e_{23}, \cdots, e_{2n} ] \\ & \vdots \\ E_n & = & [ e_{nn} ] \\ \end{matrix} \right.
とします。

d(e, r, v_i) を e \stackrel{i}{-} r をと書くことにします。

  • e, r \notin \mathcal{R}^*_i ならば e \stackrel{i}{-} r が存在する
  • e \stackrel{i}{-} r \in \mathcal{R}^*_i \cup \mathcal{O} ( \mathcal{O} は e \stackrel{i}{-} r が存在しないことを表す)
  • e, r \in \mathcal{R}^*_j ならば e \stackrel{i}{-} r \in \mathcal{R}^*_j

とします。

\left\{ \begin{matrix} e_{22} & = & e_{12} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ e_{23} & = & e_{13} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ & \vdots \\ e_{2n} & = & e_{1n} \stackrel{1}{-} e_{11} & \in & \mathcal{R}^*_1 \cup \mathcal{O} \\ \end{matrix} \right.

\left\{ \begin{matrix} e_{33} & = & e_{23} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ e_{34} & = & e_{24} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ & \vdots \\ e_{3n} & = & e_{2n} \stackrel{2}{-} e_{22} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cup \mathcal{O} \\ \end{matrix} \right.

\begin{matrix} & \vdots & \\ e_{nn} & = & e_{n-1,n} \stackrel{n-1}{-} e_{n-1,n-1} & \in & \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} \cup \mathcal{O} \end{matrix}

\begin{array} {ccl} r_n & = & e_{nn} & \in & \mathcal{R}_n \cup \mathcal{O} = \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} \\ r_{n-1} & = & e_{n-1,n-1} \stackrel{n}{-} r_n & \in & \mathcal{R}_{n-1} \cup \mathcal{O} \cup \mathcal{O} \\ r_{n-2} & = & e_{n-2,n-2} \stackrel{n-1}{-} r_{n-1} \stackrel{n}{-} r_n & \in & \mathcal{R}_{n-2} \cup \mathcal{O} \\ & \vdots & \\ r_{1} & = & e_{11} \stackrel{2}{-} r_{2} \stackrel{3}{-} r_{3} \stackrel{4}{-} \cdots \stackrel{n}{-} r_n & \in & \mathcal{R}_{1} \cup \mathcal{O} \end{array}

掃き出し法の順序の置換

上記の数式を以下のように書くことにします。

\begin{cases} [ e_{i+1,i+1}, e_{i+1,i+2}, \cdots, e_{i+1,n} ] = [ e_{i,i+1}, e_{i,i+2}, \cdots, e_{i,n} ] \stackrel{i}{-} e_{ii} \\ r_{i} = e_{ii} \stackrel{i+1}{-} r_{i+1} \stackrel{i+2}{-} r_{i+2} \stackrel{i+3}{-} \cdots \stackrel{n}{-} r_n \end{cases}

ここで \sigma、 \tau を \{1, 2, \cdots, n\} の置換( \sigma は行の置換、 \tau は列の置換を表す)とします。

E^\sigma = [ e^\sigma_{1}, e^\sigma_{2}, \cdots, e^\sigma_{n} ] とし、 R^{\sigma\tau} = [ r^{\sigma\tau}_{1}, r^{\sigma\tau}_{2}, \cdots, r^{\sigma\tau}_{n} ]、 E^{\sigma\tau}_i = [ e^{\sigma\tau}_{i1}, e^{\sigma\tau}_{i2}, \cdots, e^{\sigma\tau}_{in} ] を以下のように決めます。
\begin{cases} E^{\sigma\tau}_1 = E^{\sigma} \\ [ e^{\sigma\tau}_{\sigma(i+1)\tau(i+1)}, e^{\sigma\tau}_{\sigma(i+1)\tau(i+2)}, \cdots, e^{\sigma\tau}_{\sigma(i+1)\tau(n)} ] \\ = [ e^{\sigma\tau}_{\sigma(i)\tau(i+1)}, e^{\sigma\tau}_{\sigma(i)\tau(i+2)}, \cdots, e^{\sigma\tau}_{\sigma(i)\tau(n)} ] \stackrel{\tau(i)}{-} e^{\sigma\tau}_{\sigma(i)\tau(i)} \\ r^{\sigma\tau}_{\sigma\tau(i)} = e^{\sigma\tau}_{\sigma(i)\tau(i)} \stackrel{\tau(i+1)}{-} r^{\sigma\tau}_{\sigma\tau(i+1)} \stackrel{\tau(i+2)}{-} r^{\sigma\tau}_{\sigma\tau(i+2)} \stackrel{\tau(i+3)}{-} \cdots \stackrel{\tau(n)}{-} r^{\sigma\tau}_{\sigma\tau(n)} \end{cases}

\sigma, \tau に対して e^{\sigma\tau}_{\sigma(t)\tau(t)} が存在する最大の t を \mathrm{rank}^{\sigma\tau}(E) とします。すべての \sigma, \tau に関して最大の \mathrm{rank}^{\sigma\tau}(E) を \mathrm{rank}(E) とします。

\mathrm{rank}^{\sigma\tau}(E) = n のとき [E^{\exists\sigma} \to\to R^{\exists\tau}] と書くことにします。この計算から以下のことが導けるかどうか調べます。以下では [E^{\exists\sigma} \to\to R^{\exists\tau}] の中の E、 R は順序があるリストを表し、それ以外は順序のない通常の集合を表すとします。

  • [E^{\exists\sigma} \to\to R^{\exists\tau}] \iff E \twoheadrightarrow R
  • \mathrm{rank}(E) = n \iff E \twoheadrightarrow_\exists R
  • E \twoheadrightarrow R_1, E \twoheadrightarrow R_2 \implies R_1 = R_2

エレファントな線形代数(3)

掃き出し法の順序に依存しない記法(3)

解が一意的となるように書き直したいと思います。

有理数全体の体 \mathbb{Q} に \alpha_{11}, \cdots, \alpha_{1n}, \cdots, \alpha_{n1}, \cdots, \alpha_{nn}, \beta_1, \cdots, \beta_n を付け加えて拡大した体を K とします。

V = K^n、 U = \{u_1, u_2, \cdots, u_n\} を V の基底とします。

W = K^n とし、ベクトル空間 W^+ = W \times K の部分空間全体の集合を \mathcal{P} とします。
\mathcal{E} = \{ Kw \mid w \in W^+ \} \subseteq \mathcal{P} とおきます。 \mathcal{E} の元 K(a_1, a_2, \cdots, a_n, b) が一次方程式 a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b を 表すとします。

h: \mathcal{E} \times V \to \{0, 1\} ( 1 は「真」を、 0 は「偽」を表すとします)を、 e = K(a_1, a_2, \cdots, a_n, b) \in \mathcal{E} と v = x_1 u_1 + x_2 u_2 + \cdots + x_n u_n \in V に対して、 a_1 x_1 + a_2 x_2 + \cdots + a_n x_n = b のとき h(e, v) = 1、 a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \ne b のとき h(e, v) = 0 とします。

i = 1, 2, \cdots, n に対して、 \mathcal{Q}^*_i = \{ r \in \mathcal{E} \mid h(r, u_i) = 1 \}、 \displaystyle \mathcal{Q}_i = \bigcap_{j \in \{1, 2, \cdots, n\} \setminus \{ i \}} \mathcal{Q}^*_j、 \mathcal{R} = \mathcal{Q}_1 \cup \mathcal{Q}_2 \cup \cdots \cup \mathcal{Q}_n とおきます。

\mathcal{E}' \subseteq \mathcal{E} に対して \mathcal{E}' の元すべての W^+ の部分空間としての和を \sum \mathcal{E}' と書くことにします。

(1) 任意の e_1, e_2 \in \mathcal{E}、 i \in \{1, 2, \cdots, n\} に対して、 W^+ の部分空間として e \subseteq (e_1 + e_2) \cap \sum \mathcal{Q}^*_i となる e \in \mathcal{E} が一意的に存在します。

[証明] w_1 を a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1、 w_2 を a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 とすると、
h(K(c_1 w_1 + c_2 w_2), u_i) = 1 \iff c_1 a_{1i} + c_2 a_{2i} = 0
となります。

w = w_1 - \cfrac{a_{1i}}{a_{2i}} w_2 は h(Kw, u_i) = 1 を満たし、 w \in K w_1 + K w_2 より K w \subseteq K w_1 + K w_2 となります。

逆に w = c_1 w_1 + c_2 w_2、 h(Kw, u_i) = 1 とすると w = c_1 (w_1 - \cfrac{a_{1i}}{a_{2i}} w_2) \in K (w_1 - \cfrac{a_{1i}}{a_{2i}} w_2) となります。よって K w = K (w_1 - \cfrac{a_{1i}}{a_{2i}} w_2) となるので、このような K w は一意的となります。[証明終わり]

e \in \mathcal{E} に対して S(e) = \{ v \in V \mid h(e, v) = 1 \}、 E \subseteq \mathcal{E} に対して \displaystyle S(E) = \bigcap_{e \in E} S(e) とします。 S(e)、 S(E) は V の部分空間となります。

S(E) = S(R) かつ R \subseteq \mathcal{R} となる R を E の解とします。このとき E \twoheadrightarrow R と書くことにします。 E \twoheadrightarrow R となる R が存在することを E \twoheadrightarrow_\exists R と書くことにします。

E_0 \subseteq \mathcal{E} を
\left\{ \begin{matrix} \alpha_{11} x_1 + \alpha_{12} x_2 + \cdots + \alpha_{1n} x_n = \beta_1 \\ \alpha_{21} x_1 + \alpha_{22} x_2 + \cdots + \alpha_{2n} x_n = \beta_2 \\ \vdots \\ \alpha_{n1} x_1 + \alpha_{n2} x_2 + \cdots + \alpha_{nn} x_n = \beta_n \\ \end{matrix} \right.
に対応する一次方程式の集合、 U_0 = U とします。

E_i = E'_{i+1} + \{ e_i \}、 U_i = U_{i+1} + \{ v_i \} ( + は集合の直和)とします。

\displaystyle V_i = \sum_{u \in U_i} K u とおくと V_i = V_{i+1} \oplus K v_{i+1} ( \oplus はベクトル空間の直和)となります。

\mathcal{R}^*_i = \{ r \in \mathcal{E} \mid h(r, v_i) = 1 \}、 \displaystyle \mathcal{R}_i = \bigcap_{j \in \{1, 2, \cdots, n\} \setminus \{ i \}} \mathcal{R}^*_j とおきます。

e_1, e_2 \in \mathcal{E}、 i \in \{1, 2, \cdots, n\} に対して e \subseteq (e_1 + e_2) \cap \sum \mathcal{R}^*_i となる e \in \mathcal{E} を d(e_1, e_2, v_i) と書くことにします。

E_{i+1} = \{ d(e', e_i, v_{i+1}) \mid e' \in E'_{i+1} \} とおきます。

(2) E_{i} \subseteq \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_i

[証明] E_{i} の定義より E_{i} \subseteq \mathcal{R}^*_i となります。

また、 e_1, e_2 \in \mathcal{R}^*_j とすると d(e_1, e_2, v_i) \subseteq e_1 + e_2 であることから d(e_1, e_2, v_i) \in \mathcal{R}^*_j となります。よって E_{i} \subseteq \mathcal{R}^*_j ならば E_{i+1} \subseteq \mathcal{R}^*_j となります。

よって主張が成り立ちます。[証明終わり]

(3) S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i)

[証明] e' \in E'_i をとり、 e' を Kw'、 e_i を Kw''、 d(e', e_i, v_i) を Kw とおくと。 w \in Kw' + Kw'' となります。 w = aw' + bw'' となる a, b \in K が存在します。 x = aw'、 y = bw'' とおくと、 w = x + y となります。 e' \in E'_i をとると
\begin{eqnarray*} v \in S(e') \cap S(e_i) & \iff & h(e', v) = h(e_i, v) = 1 \\ & \iff & h(Kx, v) = h(Ky, v) = 1 \\ & \iff & h(Kw, v) = h(Ky, v) = 1 \\ & \iff & h(d(e', e_i, v_i), v) = h(e_i, v) = 1 \\ & \iff & v \in S(d(e', e_i, v_i)) \cap S(e_i) \end{eqnarray*}
となります。よって S(E'_i) \cap S(e_i) = S(E_i) \cap S(e_i) となります。[証明終わり]

(4) S(E_i) = S(E_{i+1}) \cap S(e_{i+1})

[証明] (3)より S(E_i) = S(E'_{i+1}) \cap S(e_{i+1}) = S(E_{i+1}) \cap S(e_{i+1}) となります。[証明終わり]

(5) E_{n-1} \subseteq \mathcal{R}

[証明] (2) より E_{n-1} \subseteq \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_{n-1} となるので成り立ちます。[証明終わり]

(6) E_{i+1} \twoheadrightarrow R_{i+1}、 R_{i+1} = \{ r_{i+2}, \cdots, r_n \}、 r_{j} \in \mathcal{R}^*_{j}、 E_i = E_{i+1} + \{ e_{i+1} \} ならば E_{i} \twoheadrightarrow R_{i} となる R_{i} が存在します。

[証明] S(E_{i+1}) = S(R_{i+1}) かつ R_{i+1} \subseteq \mathcal{R}、 R_{i+1} = \{ r_{i+2}, \cdots, r_n \} ( r_{j} \in \mathcal{R}^*_{j})とします。

d(e_i, r_j, v_j) を e_i -_d (r_j, v_j) をと書くことにします。 e_i \in \mathcal{R}^*_{i}、 r_j \in \mathcal{R}_{j} のとき e_i -_d (r_j, v_j) \in \mathcal{R}^*_{i} \cap \mathcal{R}^*_{j} となるので
r_{i+1} = e_{i+1} -_d (r_{j+2}, v_{j+2}) -_d (r_{j+3}, v_{j+3}) -_d \cdots -_d (r_{n-2}, v_{n-2}) -_d (r_{n-1}, v_{n-1}) \\ \in \mathcal{R}^*_{i+2} \cap \mathcal{R}^*_{i+3} \cap \cdots \cap \mathcal{R}^*_{n-1}
となります。(2)より r_{i+1} \in \mathcal{R}^*_1 \cap \mathcal{R}^*_2 \cap \cdots \cap \mathcal{R}^*_i となるので r_{i+1} \in \mathcal{R}_{i+1} となります。

R_i = R_{i+1} + \{ r_{i+1} \} とおくと S(E_{i}) = S(R_{i}) かつ R_{i} \subseteq \mathcal{R} となります。[証明終わり]

(7) E_{0} \twoheadrightarrow_\exists R_0

[証明] (6)より
\begin{eqnarray*} E_0 \twoheadrightarrow_\exists R_0 & \Longleftarrow & E_1 \twoheadrightarrow_\exists R_1 \\ & \Longleftarrow & E_2 \twoheadrightarrow_\exists R_2 \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & E_{n-1} \twoheadrightarrow_\exists R_{n-1} \end{eqnarray*}
となります。最後の項は(5)より R_{n-1} = E_{n-1} とおけば成り立ちます。[証明終わり]