数学構成論第一部
一階述語論理
数学とはなにか
数学とは, 以下からなる構造体である.
スタート地点
(1) 定義:ことばのとりきめ
(2) 公理:「議論の仕方」と「議論の開始地点」を定める.
導くもの
(1) 命題:きめられた議論の仕方でスタート地点から与えられたもの.
(2) 定理:命題のうち特に有用だとコンセンサスを得られたもの.
(3) 補題:命題のうち他の命題を得るために特に有用だとコンセンサスを得られたもの.
(4) 系:命題のうち他の命題からただちに得られるもの.
以下の項目において, self-contained性という概念を重要視する.数学的な記述がself-containedとは, それを読むために, 数学的な前提知識をまったく要求しないことを意味する.
言語と一階述語論理
添え字のために用いる$0, 1, \dots$の記号はものを数えるために私たちが用いる数として用いるため, 後述する集合論によって得られる自然数集合$\mathbb{N}$とは異なるものであるとみなし, それによってこの議論の妥当性が失われることはない.区別のためメタ自然数とよぶ.
言語$L$は以下の要素をもつ.
(1) 変数記号$x_0, x_1, \dots$
(2) アリティというメタ自然数をもつ関数記号$f_0, f_1,\dots$
(3) アリティという0でないメタ自然数をもつ関係記号$R_0, R_1, \dots$
(4) 論理記号$\land, \vee, \Rightarrow, \neg, \bot$
(5) 量化子$\forall, \exists$
(6) アリティ2の関係記号$=$
アリティ0の関数記号を特に定数記号とよぶ.
言語$L$に対し, $L$-項を以下で定める.
(1) 変数記号と定数記号は$L$-項.
(2) 0でないアリティ$n$をもつ関数記号$f$と$L$-項$t_1, \dots, t_n$に対し, $f(t_1, \dots, t_n)$は$L$-項.
(3) 以上のみが$L$-項.
言語$L$に対し, $L$-原子論理式を以下で定める.
(1) $\bot$は$L$-原子論理式.
(2) $L$-項$t_0, t_1$に対し$t_0 = t_1$は$L$-原子論理式.
(3) アリティ$n$をもつ関係記号$R$と$L$-項$t_1, \dots, t_n$に対し$R(t_1, \dots, t_n)$は$L$-原子論理式.
(4) 以上のみが$L$-原子論理式.
言語$L$に対し, $L$-論理式を以下で定める.
(1) $L$-原子論理式は$L$-論理式.
(2) $L$-論理式$\psi, \varphi$, 変数記号$x$に対し, $\psi \land \varphi, \psi \vee \varphi, \psi \Rightarrow \varphi, \neg \psi, \forall x \ \psi, \exists x \ \psi$は$L$-論理式.
(3) 以上のみが$L$-論理式.
可読性のため, 言語$L$の$L$-論理式$\varphi, \psi$に対し$\forall x \ \psi, \exists x \ \psi$をそれぞれ$\forall x [\psi], \exists x [\psi]$とも書くなど, 階層構造をわかりやすくするために適宜括弧を用いる.
言語$L$の$L$-論理式の自由変数, 束縛変数を以下で定める.
(1) $L$-項$t$の自由変数は$t$に出現する変数記号すべてである.$L$-項$t$は束縛変数をもたない.
(2) $L$-原子論理式$\psi$の自由変数は$\psi$に出現するすべての$L$-項$t$の自由変数すべてである.$L$-原子論理式$\psi$は束縛変数をもたない.
(3) $L$-論理式$\psi$に対し, $\neg\psi$の自由変数, 束縛変数はそれぞれ$\psi$の自由変数, 束縛変数である.
(4) $L$-論理式$\psi, \varphi$に対し, $\psi \land \varphi, \psi \vee \varphi, \psi \Rightarrow \varphi$の自由変数, 束縛変数はそれぞれ$\psi$の自由変数であるか$\varphi$の自由変数である変数記号すべて, $\psi$の束縛変数であるか$\varphi$の束縛変数である変数記号すべてである.
(5) $L$-論理式$\psi$, 変数記号$x$に対し$\forall x [\psi], \exists x [\psi]$の自由変数, 束縛変数はそれぞれ$x$を除く$\psi$の自由変数, $x$と$\psi$の束縛変数すべてである.
自由変数でも束縛変数でもある変数記号を含む$L$-論理式も考えることができるが, これらを使うことを避け, その$L$-論理式全体で使われていないものに変数記号を使い替えることで, このような変数記号がなくなるようにすることができる.以下, $L$-論理式といえばこのように変形したもののみを考える.
言語$L$とメタ自然数$n$に対し, 変数記号$x_0, \dots, x_n$に注目するとき$L$-論理式$\psi$を$\psi(x_0, \dots, x_n)$と表すことにする.
変数記号$x$と$L$-論理式$\psi(x)$と, $\psi$の束縛変数を含まない$L$-項$t$に対し, 変数記号すべては$L$-項であることから, $\psi$に含まれる自由変数の$x$をすべて$t$に置き換えたものは$L$-論理式となる.これを$\psi(x \leadsto t)$或いは単に$\psi(t)$と表す.
言語$L$と$L$-論理式$\psi, \varphi$, 変数記号$x, y$に対し, 以下の略記法を定める.
(1) $(\psi \Rightarrow \varphi) \land (\varphi \Rightarrow \psi)$を$\psi \Leftrightarrow \varphi$と略記する.
(2) $\exists x [\psi(x)] \land \forall y [\psi(x \leadsto y) \Rightarrow (x = y)]$を$\exists!x[\psi(x)]$と表す.
言語$L$の$L$-項$t$と$L$-論理式$\psi$, メタ自然数$n$に対し,
(1) $t$が自由変数をもたないとき, $t$は閉項であるという.
(2) $\psi$が自由変数をもたないとき, $\psi$は閉論理式であるという.
(3) $\psi$が自由変数$x_1, \dots, x_n$をもつとき, $\forall x_1\dots \forall x_n [\psi(x_1, \dots, x_n)]$を$\psi$の全称閉包という.自由変数の定義を繰り返し用いることで全称閉包が閉論理式であることがわかる.
言語$L$に対し, 推論規則の公理を導入する.これにより, 形式的証明というものが可能となり, 言語$L$が命題を生成する能力を得る. pdf を参照.
言語$L$の$L$-論理式$\psi, \varphi$, $L$-項$t$, 変数記号$x$に対し, 以下が成り立つ.証明はpdfを参照.
(1) $\psi \Rightarrow \psi$
(2) $(\psi \Rightarrow \varphi) \Leftrightarrow (\neg\psi \vee \varphi)$
(3) $(\psi \Rightarrow \varphi) \Leftrightarrow (\neg\varphi \Rightarrow \neg\psi)$
(4) $\neg(\psi \vee \varphi) \Leftrightarrow \neg\psi \land \neg\varphi$
(5) $\neg(\psi \land \varphi) \Leftrightarrow \neg\psi \vee \neg\varphi$
(6) $\neg \forall x [\psi(x)] \Leftrightarrow \exists x [\neg\psi(x)]$
(7) $\neg \exists x [\psi(x)] \Leftrightarrow \forall x [\neg\psi(x)]$
3.を対偶証明法といい, $\neg\varphi \Rightarrow \neg\psi$を$\psi \Rightarrow \varphi$の対偶という.
4, 5, 6, 7はあわせてDe Morganの法則とよばれている.「法則」といっても証明可能なので以下De Morganの定理とよぶ.
言語$L$と$=$に関して, 以下の公理を導入する.$\psi$を$L$-論理式とする.
(1) $\forall x [x = x]$
(2) $\forall x \forall y [x = y \Rightarrow \psi(x) \Leftrightarrow \psi(y)]$
公理的集合論(1)
集合の言語とその公理
以下, 「(言語$L$で)成り立つ」とは一階述語論理と言語$L$を用いて証明できることをいう.
集合の言語$L_{ZFC}$は変数記号とアリティ$2$の関係記号$\in, =$をもち, 関数記号をもたない.
$L_{ZFC}$の変数記号を集合という.
$x, y$を集合とするとき, $\neg(x \in y)$を$x \notin y$, $\neg(x = y)$を$x \neq y$と略記する.
$\forall x \forall y$のように$\forall$が続く場合, $\forall x, y$のような略記を用いる.$\exists $に対しては混乱のもととなるため, この記法は用いない.
$x, X$を集合, $\psi(x)$を$L_{ZFC}$-論理式とする.
(1) $\forall x [x \in X \Rightarrow \psi(x)]$を$\forall x \in X [\psi(x)]$と略記する.
(2) $\exists x [x \in X \land \psi(x)]$を$\exists x \in X [\psi(x)]$と略記する.
以下において,
(1) ある記法$P$を$L_{ZFC}$-論理式$\psi$により定義するとき, $P :\Leftrightarrow \psi$と表す.
(2) ある集合$X$を$Y$という既知の集合によって定義するとき, $X \coloneqq Y$と表す.
$x, y$を集合とする.
$x \subset y :\Leftrightarrow \forall z [z \in x \Rightarrow z \in y]$と定め, このとき$x$は$y$の部分集合であるという.
$\forall x, y [x \subset y \land y \subset x \Rightarrow x = y]$という外延性公理を導入する.下記の公理において存在が保証される集合が$=$であるかどうかを除いてただひとつであることを主張するために有用である.
$\forall x, y \exists z \forall a [a \in z \Leftrightarrow (a = x \vee a = y)]$という対の公理を導入する.
この公理で存在が保証される集合$z$は$x, y$のみに依存する.
$\{x, y\}$と表し, $\{x, x\}$を特に$\{x\}$と略記する.
$\forall x \exists y \forall z [z \in y \Leftrightarrow \exists a \in x [z \in a]]$という和集合の公理を導入する.
この公理で存在が保証される集合$y$は$x$のみに依存する.
$\bigcup x$と表し, $x$のunionという.$\bigcup x, y$を特に$x \cup y$と略記し, $x$と$y$の和集合とよぶ.
対の公理と和集合の公理を合わせることで, $\{x, y, z\} = \{x, y\} \cup \{z\}$のような集合が得られる.このような記法を外延的記法という.
$\forall x \exists y \forall a [a \in y \Leftrightarrow a \subset x]$というベキ集合の公理を導入する.
この公理で存在が保証される集合は$x$のみに依存する.
$2^x$または$\mathcal{P}(x)$と表し, $x$のベキ集合という.
$n$をメタ自然数とし, $\psi$を$n+2$個の自由変数をもち$y$を自由変数にもたない$L_{ZFC}$-論理式とする.
$\forall x, t_1, \dots, t_n\exists y \forall z [z \in y \Leftrightarrow (z \in x) \land \psi(x, z, t_1, \dots, t_n)]$という分出公理を導入する.
この公理で存在が保証される集合$y$は$x, t_1, \dots, t_n$のみに依存する.
$\{z \in x \mid \psi(x, z, t_1, \dots, t_n)\}$と表す.このような記法を内包的記法という.
$n$をメタ自然数とし, $\psi$を$n+3$個の自由変数をもつ$L_{ZFC}$-論理式とする.
$\forall X, t_1, \dots, t_n [\forall x \in X \exists! y [\psi(x, y, X, t_1, \dots, t_n)]\Rightarrow \exists Y\forall z[z \in Y \Leftrightarrow \exists a \in X [\psi(a, z, X, t_1, \dots, t_n)]]]$
という置換公理を導入する.
$\exists x [\exists a \in x [\forall b \in a [\bot]] \land \forall y \in x [y \cup \{y\} \in x]]$という無限公理を導入する.
この公理で存在が保証される集合$x$をこの資料では$\infty_1$と表すことにする.
$\forall x [\forall a \in x [\bot] \vee \exists y \in x \forall z [z \notin x \vee z \notin y]]$という正則性公理を導入する.
以上の公理をZFとよぶ.
$\exists x [\forall y \in x [\bot]]$が成り立つ.
この命題で存在がいえる集合$x$は$=$による区別を除きただひとつである.$\varnothing$と略記する.
存在性を主張する場合, ひとつ論理式をみたす集合をとれれば, $\exists E$規則を用いることで主張が従う.
$x = \{a \in \infty_1 \mid \bot\}$を考えると, 分出公理の主張から$\forall y \in x [\bot]$がいえる.
集合$a$に対し, $\forall b \in a[\bot]$が導けたとき, $b \in a \Leftrightarrow \bot \Leftrightarrow b \in x$により外延性公理から$a = x$が導ける.
$x, X$を集合, $\psi(x)$を$L_{ZFC}$-論理式とする.以下が成り立つ.
(1) $\neg(\forall x \in X [\psi(x)]) \Leftrightarrow \exists x \in X [\neg\psi(x)]$
(2) $\neg(\exists x \in X [\psi(x)]) \Leftrightarrow \forall x \in X [\neg\psi(x)]$
- \begin{align} \neg(\forall x \in X [\psi(x)]) &\Leftrightarrow \neg(\forall x[x \in X \Rightarrow \psi(x)]) \\ &\Leftrightarrow \exists x [\neg (x \in X \Rightarrow \psi(x))] \\ &\Leftrightarrow \exists x [\neg (\neg x \in X \vee \psi(x))] \\ &\Leftrightarrow \exists x [\neg \neg x \in X \land \neg \psi(x)] \\ &\Leftrightarrow \exists x [x \in X \land \neg \psi(x)] \end{align}
- \begin{align} \neg(\exists x \in X [\psi(x)]) &\Leftrightarrow \neg(\exists x [x \in X \land \psi(x)]) \\ &\Leftrightarrow \forall x [\neg (x \in X \land \psi(x))] \\ &\Leftrightarrow \forall x [\neg x \in X \vee \neg \psi(x)] \\ &\Leftrightarrow \forall x [x \in X \Rightarrow \neg \psi(x)] \\ &\Leftrightarrow \forall x \in X [\neg \psi(x)] \end{align}
公理的集合論(2)
以下, 変数記号を具体的な集合のように扱う.$x \in X$が導かれたとき, $x$は$X$の元である, または$x$は$X$に含まれるという.また, $X \subset Y$が導かれたとき, $X$は$Y$に包まれるという表現も用いる.
写像
$x, y$を集合とする.
$(x, y) \coloneqq \{x, \{x, y\}\}$を$x, y$の順序対という.
$x \neq y$のとき, $(x, y) \neq (y, x)$となる.実際, $x \neq y$とすれば$x \in (x, y)$だが$x \notin (y, x)$である.このように$\varnothing$でない集合の$\neq$を主張する場合, 一方に含まれるが他方に含まれない元の存在をいえばよい.
「$x, y$を集合とする.」という文言は, $x, y$としてどんな集合をとってもよいことを意味する.以下, 同様の文言で, 条件が合っていればどんな対象もとることができるものとして扱う.
$x, y$を集合とする.
$x \times y \coloneqq \{(a, b) \in \mathcal{P}(\mathcal{P}(x \cup y)) \mid a \in x \land b \in y\}$と定め, $x$と$y$の直積集合という.
$x \neq \varnothing \land y \neq \varnothing \land x \neq y$であれば, $x \times y \neq y \times x$である.実際, $a \in x \land a \notin y$となる元の存在がいえるので, このとき$a \neq b \land b \in y$をみたす集合$b$はかならずとれ, $(a, b) \in x \times y$だが$(a, b) \notin y \times x$である.
$x, y$を集合とする.
$r \subset x \times y$を$x$と$y$の対応という.$x = y$のとき特に関係ともいう.
$x$と$y$の対応$f$であって, $\forall a \in x \exists!b \in y [(a, b) \in f]$をみたすとき, $f$を$x$から$y$への写像とよび,
$f:x \to y$と表す.
$a \in x$に対し$f$が存在を主張する$b \in y$を$f(a)$と表す.
集合代数と写像
$\mathcal{A}, U, \Lambda$を集合とする.
写像$A:\Lambda \to U$を考え, $\lambda \in \Lambda$に対し$A_{\lambda} \coloneqq A(\lambda)$と定めたとき,
$\mathcal{A} = \{A_{\lambda} \mid \lambda \in \Lambda\}$を$\mathcal{A} = \{A_{\lambda}\}_{\lambda \in \Lambda}$と表し, $\mathcal{A}$を$\Lambda$によって添え字づけられた集合の族という.
$X, Y$を集合とする.
(1) $X \neq \varnothing$のとき, $x \in X$をとり, $\bigcap X \coloneqq \{z \in x \mid \forall y \in X [z \in y]\}$と定めると, これはとった$x$の取り方によらない.これを$X$のintersectionという.特に$\bigcap \{X, Y\}$を$X \cap Y$と表し, $X$と$Y$の積集合という.
(2) $X \setminus Y \coloneqq \{a \in X \mid a \notin Y\}$と定め, $X$と$Y$の差集合という.
(3) $X$の部分集合のみに注目しているとき, $A \subset X$に対し$X \setminus A$を特に$A^c$と表し, $A$のcomplementという.
$\mathcal{A} = \{A_{\lambda}\}_{\lambda \in \Lambda}$に対し$\displaystyle\bigcup_{\lambda \in \Lambda}A_{\lambda}$を$\bigcup \mathcal{A}$, $\displaystyle\bigcap_{\lambda \in \Lambda}A_{\lambda}$を$\bigcap \mathcal{A}$と略記する.
$\mathcal{A} = \{A_{\lambda}\}_{\lambda \in \Lambda}$とする.以下が成り立つ.
(1)
\begin{align}
a \in \displaystyle\bigcup_{\lambda \in \Lambda}A_{\lambda} \Leftrightarrow \exists \mu \in \Lambda [a \in A_{\mu}]
\end{align}
(2)
\begin{align}
a \in \displaystyle\bigcap_{\lambda \in \Lambda}A_{\lambda} \Leftrightarrow \forall \mu \in \Lambda [a \in A_{\mu}]
\end{align}
- \begin{align} a \in \bigcup_{\lambda \in \Lambda}A_{\lambda} &\Leftrightarrow a \in \bigcup\mathcal{A} \\ &\Leftrightarrow \exists x[x \in \mathcal{A} \land a \in x] \\ &\Leftrightarrow \exists \mu \in \Lambda [a \in A_{\mu}] \end{align}
- \begin{align} a \in \bigcap_{\lambda \in \Lambda}A_{\lambda} &\Leftrightarrow a \in \bigcap\mathcal{A} \\ &\Leftrightarrow \forall x[x \in \mathcal{A} \land a \in x] \\ &\Leftrightarrow \forall \mu \in \Lambda [a \in A_{\mu}] \end{align}
$X$を集合, $\mathcal{A}=\{A_{\lambda}\}_{\lambda \in \Lambda}$とし, $\forall \lambda \in \Lambda[A_{\lambda} \subset X]$を仮定する.以下が成り立つ.
(1)
\begin{align}
(\bigcup_{\lambda \in \Lambda}A_{\lambda})^c = \bigcap_{\lambda \in \Lambda}A_{\lambda}^c
\end{align}
(2)
\begin{align}
(\bigcap_{\lambda \in \Lambda}A_{\lambda})^c = \bigcup_{\lambda \in \Lambda}A_{\lambda}^c
\end{align}
- \begin{align} a \in \displaystyle(\bigcup_{\lambda \in \Lambda}A_{\lambda})^c &\Leftrightarrow a \in X \land \neg(\exists \mu \in \Lambda [a \in A_{\mu}]) \\ &\Leftrightarrow a \in X \land \forall \mu \in \Lambda [a \notin A_{\mu}] \\ &\Leftrightarrow a \in \bigcap_{\lambda \in \Lambda}A_{\lambda}^c \end{align}
- \begin{align} a \in \displaystyle(\bigcap_{\lambda \in \Lambda}A_{\lambda})^c &\Leftrightarrow a \in X \land \neg(\forall \mu \in \Lambda [a \in A_{\mu}]) \\ &\Leftrightarrow a \in X \land \exists \mu \in \Lambda [a \notin A_{\mu}] \\ &\Leftrightarrow a \in \bigcup_{\lambda \in \Lambda}A_{\lambda}^c \end{align}
$X, Y$を集合, $f:X \to Y$を写像, $A \subset X, B \subset Y$とする.
(1) $f(A) \coloneqq \{f(a) \in Y \mid a \in A\}$と定め, $f$による$A$の像という.$f(X)$を特に$\Im f$と表す.
(2) $f^{-1}(B) \coloneqq \{x \in X \mid f(x) \in B\}$と定め, $f$による$B$の逆像という.
$X, Y$を集合, $f:X \to Y$を写像, $A \subset X, (B_{\lambda})_{\lambda \in \Lambda} \subset Y, B \subset Y$とする.以下が成り立つ.
(1) $A \subset f^{-1}(f(A))$
(2) $f(f^{-1}(B)) \subset B$
(3)
\begin{align}
f^{-1}(\bigcup_{\lambda \in \Lambda}B_{\lambda}) = \bigcup_{\lambda \in \Lambda}f^{-1}(B_{\lambda})
\end{align}
(4)
\begin{align}
f^{-1}(\bigcap_{\lambda \in \Lambda}B_{\lambda}) = \bigcap_{\lambda \in \Lambda}f^{-1}(B_{\lambda})
\end{align}
(5) $f^{-1}(B^c) = (f^{-1}(B))^c$
$=$性の証明は一方に含まれることと他方に含まれることが$\Leftrightarrow$の関係にあればよい.
(1) $a \in A$をとる.$f(a) \in f(A)$から$a \in f^{-1}(f(A))$.
よって$A \subset f^{-1}(f(A))$.
(2) $y \in f(f^{-1}(B))$をとる.$\exists b \in f^{-1}(B) [y = f(b)]$.このとき$f(b) \in B$から$y \in B$.
よって$f(f^{-1}(B)) \subset B$.
(3)
\begin{align}
x \in f^{-1}(\bigcup_{\lambda \in \Lambda}B_{\lambda}) &\Leftrightarrow f(x) \in \bigcup_{\lambda \in \Lambda}B_{\lambda}\\
&\Leftrightarrow \exists \lambda \in \Lambda [f(x) \in B_{\lambda}] \\
&\Leftrightarrow \exists \lambda \in \Lambda [x \in f^{-1}(B_{\lambda})] \\
&\Leftrightarrow x \in \bigcup_{\lambda \in \Lambda}f^{-1}(B_{\lambda})
\end{align}
(4)
\begin{align}
x \in f^{-1}(\bigcap_{\lambda \in \Lambda}B_{\lambda}) &\Leftrightarrow f(x) \in \bigcap_{\lambda \in \Lambda}B_{\lambda}\\
&\Leftrightarrow \forall \lambda \in \Lambda [f(x) \in B_{\lambda}] \\
&\Leftrightarrow \forall \lambda \in \Lambda [x \in f^{-1}(B_{\lambda})] \\
&\Leftrightarrow x \in \bigcap_{\lambda \in \Lambda}f^{-1}(B_{\lambda})
\end{align}
(5)
\begin{align*}
x \in f^{-1}(B^c) &\Leftrightarrow x \in X \land f(x) \in B^c \\
&\Leftrightarrow x \in X \land f(x) \in Y \land f(x) \notin B \\
&\Leftrightarrow x \in X \land x \notin f^{-1}(B) \\
&\Leftrightarrow x \in (f^{-1}(B))^c
\end{align*}
$X$を集合とする.$\text{id}_X:X \to X$を$x \in X$に対し$\text{id}_X(x) \coloneqq x$と定め, $x$の恒等写像という.
$f:X \to Y$という写像を定義する場合, すべての$x \in X$に対して$f(x) \in Y$を定義することで写像$f$を定義したといえる.
$X, Y, Z$を集合, $f:X \to Y, g:Y \to Z$を写像とする.
$g \circ f:X \to Z$を$x \in X$に対し$g \circ f(x) \coloneqq g(f(x))$と定める.$g \circ f$を$f$と$g$の合成写像という.
$f(x) \in Y$は$f$の写像性により$x \in X$によってただひとつであり, $g(f(x))$は$g$の写像性により$f(x) \in Y$によってただひとつであるので, あわせて$g \circ f$の写像性が従う.
公理的集合論(3)
写像による集合の関係づけ
$\forall X [X \subset \varnothing \Rightarrow X = \varnothing]$が成り立つ.
集合$X$に対し, $X \subset \varnothing$と仮定する.
このとき$x \in X \Rightarrow x \in \varnothing$が成り立つ.
$x \in \varnothing \Rightarrow \bot$であるから, $\Rightarrow$の推移律より$x \in X \Rightarrow \bot$.
$\bot E$規則より$\bot \Rightarrow x \in X$が成り立ち, $x \in X \Leftrightarrow \bot$.
よって, $x \in X \Leftrightarrow x \in \varnothing$となるため, $X = \varnothing$.
言語$L$における$\Rightarrow$の推移律は以下のように証明できる.
$\psi, \varphi, \chi$を$L$-論理式とする.
(1) $\psi \Rightarrow \varphi \land \varphi \Rightarrow \chi$を仮定する.
(2) $\psi \Rightarrow \varphi$が導ける.
(3) $\psi$を仮定する.
(4) (3)の仮定と(2)から$\varphi$が導ける.
(5) (1)の仮定から$\varphi \Rightarrow \chi$が導ける.
(6) (4)と(5)から$\chi$が導ける.
(7) (3)の仮定を閉じることで, $\psi \Rightarrow \chi$が導ける.
(8) (1)の仮定を閉じることで, $(\psi \Rightarrow \varphi \land \varphi \Rightarrow \chi) \Rightarrow (\psi \Rightarrow \chi)$が導ける.
(9) 仮定がすべて閉じられたので, $(\psi \Rightarrow \varphi \land \varphi \Rightarrow \chi) \Rightarrow (\psi \Rightarrow \chi)$は仮定なしの命題となった.
$X$を集合とする.$X \times \varnothing = \varnothing$, $\varnothing \times X = \varnothing$が成り立つ.
$X \times \varnothing = \{(x, y) \mid x \in X \land y \in \varnothing\}$となる.
$x \in X \land y \in \varnothing \Leftrightarrow \bot$であるから, $X \times \varnothing = \varnothing$となる.
$\varnothing \times X= \{(x, y) \mid x \in \varnothing \land y \in X\}$となる.
$x \in \varnothing \land y \in X \Leftrightarrow \bot$であるから, $\varnothing \times X = \varnothing$となる.
$X$を集合とする.
対応$R_1 \subset \varnothing \times X, R_2 \subset X \times \varnothing$に対し, $R_1 = \varnothing, R_2 = \varnothing$が成り立つ.すなわちこれらの集合上の対応はただひとつしかない.
命題2により, $R_1 \subset \varnothing$, $R_2 \subset \varnothing$となるので,
命題1より$R_1 = \varnothing, R_2 = \varnothing$
上記の対応は$\bot E$により写像の条件をみたしている.これを空写像とよぶ.
命題3により, 集合$X$に対して$f_1:\varnothing \to X, f_2:X \to \varnothing$の空写像がそれぞれただひとつであることが従う.
$X, Y$を集合, $f:X \to Y$を写像とする.
(1) $f:\text{inj.} :\Leftrightarrow \forall x_1, x_2 \in X [f(x_1) = f(x_2) \Rightarrow x_1 = x_2]$と定める.
(2) $f:\text{surj.} :\Leftrightarrow \Im f = Y$と定める.
(3) $f:\text{bij.} :\Leftrightarrow f:\text{inj.} \land f:\text{surj.}$と定める.
(4) $f:\text{mono} :\Leftrightarrow \forall W \forall g_1:W \to X:$写像$\forall g_2:W \to X:$写像$[f \circ g_1 = f \circ g_2 \Rightarrow g_1 = g_2]$と定める.
(5) $f:\text{epi} :\Leftrightarrow \forall Z \forall g_1:Y \to Z:$写像$\forall g_2:Y \to Z:$写像$[g_1 \circ f = g_2 \circ f \Rightarrow g_1 = g_2]$と定める.
(6) $f:\text{bij.}$が存在するとき, $X \cong Y$ in Setと表し, $X$と$Y$は(集合の意味で)同型という.
$n$をメタ自然数とする.以下, TFAEと書いて論理式またはその略記$\psi_1, \psi_2, \dots, \psi_n$を列挙することを, $\psi_1 \Leftrightarrow \psi_2 \Leftrightarrow \cdots \Leftrightarrow \psi_n$の略記とみなす.証明の際には$\psi_1 \Rightarrow \psi_2, \psi_2 \Rightarrow \psi_3, \dots, \psi_n \Rightarrow \psi_1$を証明することで証明したこととみなせる.
$X, Y$を集合, $f:X \to Y$を写像とする.TFAE.
(1) $f:\text{inj.}$
(2) $\forall A \subset X [f^{-1}(f(A)) = A]$
(3) $f:\text{mono}$
$((1) \Rightarrow (2))$
$f:\text{inj.}$とする.$\forall A \subset X [f^{-1}(f(A)) \subset A]$を示す.
$A \subset X, x \in f^{-1}(f(A))$をとる.$f(x) \in f(A)$から$\exists a \in A [f(x) = f(a)]$.$f:\text{inj.}$から$x = a \in A$.
よって$\forall A \subset X [f^{-1}(f(A)) \subset A]$
$((2) \Rightarrow (3))$
$\forall A \subset X [f^{-1}(f(A)) = A]$とし, 集合$W$と$g_1, g_2:W \to X:\text{写像}$が$f \circ g_1 = f \circ g_2$をみたすとする.
$w \in W$をとり, $A = \{g_1(w)\}, B = \{g_2(w)\} \subset X$とおく.
$f(A) = f(B)$から$\{g_1(w)\} = A = f^{-1}(f(A)) = f^{-1}(f(B)) = B = \{g_2(w)\}$となり,
$g_1(w) = g_2(w)$から$g_1 = g_2$.
よって$f:\text{mono}$.
$((3) \Rightarrow (1))$
$f:\text{mono}$とする.$x_1, x_2 \in X$を$f(x_1) = f(x_2)$をみたすようにとる.
$W = \{s, t\}$と$g_1, g_2:W \to X:\text{写像}$を$w \in W$に対し
$g_1(w) =
\begin{cases}
x_1 & (w = s) \\
x_2 & (w = t) \\
\end{cases}
g_2(w) =
\begin{cases}
x_2 & (w = s) \\
x_1 & (w = t) \\
\end{cases}
$と定める.$f(x_1) = f(x_2)$から$f \circ g_1(w) = f(x_1) = f \circ g_2(w)$となるため$g_1 = g_2$となり$x_1 = g_1(a) = g_2(a) = x_2$.
よって$f:\text{inj.}$
証明中の
$g_1(w) =
\begin{cases}
x_1 & (w = s) \\
x_2 & (w = t) \\
\end{cases}
$という表現は, $w = s$のとき$g_1(w) = x_1$, $w = t$のとき$g_2(w) = x_2$であることを表す.
$X, Y$を集合, $f:X \to Y$を写像とする.TFAE.
(1) $f:\text{epi}$
(2) $\forall B \subset Y [f(f^{-1}(B)) = B]$
(3) $f:\text{surj.}$
$((1) \Rightarrow (2))$
$f:\text{epi}$とする.$B \subset f(f^{-1}(B))$を示す.
$Z = \{s, t\}$と$g_1, g_2:Y \to Z$を$y \in Y$に対し
$g_1(y) = s,
g_2(y) =
\begin{cases}
s & (y \in f(f^{-1}(B)) \cup B^c) \\
t & (y \in B \setminus f(f^{-1}(B)))
\end{cases}
$と定める.
$x \in X$に対し, $f(x) \in B$なら$x \in f^{-1}(B)$から$f(x) \in f(f^{-1}(B))$となり, $g_2 \circ f(x) = s$.
$f(x) \in B^c$なら$g_2 \circ f(x) = s$.どちらの場合も$g_1 \circ f = g_2 \circ f$となる.
$f:\text{epi}$から$g_1 = g_2$となり$\forall y \in Y [g_2(y) = s]$.
$g_2(y) = t$となる$y \in Y$がないことがわかるので, $B \setminus f(f^{-1}(B)) = \varnothing$.
よって$B \subset f(f^{-1}(B))$.
$((2) \Rightarrow (3))$
$\forall B \subset Y [f(f^{-1}(B)) = B]$とする.$y \in Y$をとる.$B = \{y\}$と定めると, $f(f^{-1}(\{y\})) = B = \{y\}$となる.$f^{-1}(\{y\}) = \varnothing$とすると$f(\varnothing) = \varnothing \neq \{y\}$となり矛盾.よって$f^{-1}(\{y\}) \neq \varnothing$となり, $\text{Im}f = Y$.
よって$f:\text{surj.}$
$((3) \Rightarrow (1))$
$f:\text{surj.}$とする.集合$Z$と$g_1, g_2:Y \to Z:\text{写像}$が$g_1 \circ f = g_2 \circ f$をみたすとする.$f:\text{surj.}$から$\forall y \in Y \exists x \in X [f(x) = y]$.
$g_1 \circ f(x) = g_2 \circ f(x)$なので$g_1(y) = g_2(y)$から$g_1 = g_2$.
よって$f:\text{epi}$.
$X, Y$を集合, $X \neq \varnothing, f:X \to Y$を写像とする.TFAE.
(1) $f:\text{bij.}$
(2) $\exists g:Y \to X:$写像$[g \circ f = \text{id}_X \land f \circ g = \text{id}_Y]$
(3) $\exists g:Y \to X:$写像$[g \circ f = \text{id}_X] \land \exists h:Y \to X:$写像$[f \circ h = \text{id}_Y]$
$((1) \Rightarrow (2))$
$y \in Y$に対し$f:\text{surj.}$から$f^{-1}(\{y\}) \neq \varnothing$.
$x_1, x_2 \in f^{-1}(\{y\}) \Rightarrow f(x_1) = y = f(x_2) \Rightarrow x_1 = x_2$となり$\exists! x \in X [x \in f^{-1}(\{y\})]$がいえる.
$g$を$y \in Y$に対し$g(y) \in f^{-1}(\{y\})$をみたすようにとると, $g:Y \to X$は写像となる.
$x \in X$に対し$f:\text{inj.}$から$g \circ f(x) = g(f(x)) = x$から$g \circ f = \text{id}_X$.
$y \in Y$に対し$f \circ g(y) = f(g(y)) = y$から$f \circ g = \text{id}_Y$.
$((2) \Rightarrow (3))$
$h$として$g$をとればよい.
$((3) \Rightarrow (1))$
$\exists g:Y \to X:\text{写像} [g \circ f = \text{id}_X] \land \exists h:Y \to X:\text{写像} [f \circ h = \text{id}_Y]$とする.
$y \in Y$に対し$x = h(y)$とおく.
$f(x) = f(h(y)) = y$から, $f:\text{surj.}$
$x_1, x_2 \in X$に対し$f(x_1)=f(x_2)$とする.$x_1 = g(f(x_1)) = g(f(x_2)) = x_2$となる.
$x_1 = x_2$から, $f:\text{inj.}$
よって, $f:\text{bij.}$
$X, Y$を集合, $X \neq \varnothing, f:X \to Y:\text{bij.}$とする.
このとき, $g, h:Y \to X:$写像を
$g \circ f = h \circ f = \text{id}_X, f \circ g = f \circ h = \text{id}_Y$であるようにとると, $g = h$が成り立つ.
$f:\text{surj.}$から, $f:\text{epi}$となり, $g = h$.
$W, X, Y, Z$を集合, $f:W \to X, g:X \to Y, h:Y \to Z$を写像とする.このとき, $(h \circ g) \circ f = h \circ (g \circ f)$(結合律という.)が成り立つ.
$W = \varnothing$のときは空写像がただひとつであることから成り立つ.
$w \in W$がとれるとき, $(h \circ g) \circ f(w) = (h \circ g)(f(w)) = h(g(f(w))) = h(g \circ f(w)) = h \circ (g \circ f)(w)$となる.
結合律のため, 写像の合成において括弧を使わない.
$X$を集合, $A \subset X$とする.写像$\iota:A \to X$を$a \in A$に対し$\iota(a) = a$と定めると$a \in X$であるから写像となる.$\iota$を包含写像という.
$X$を写像, $A \subset X$とする.包含写像$\iota:A \to X$に対し, $\iota:\text{mono}$が成り立つ.
$W$を集合, $f, g:W \to A$を写像とし, $\iota \circ f = \iota \circ g$が成り立つと仮定する.
$W = \varnothing$のときは空写像がただひとつであることから成り立つ.
$w \in W$に対し, $f(w) = \iota(f(w)) = \iota \circ f(w) = \iota \circ g(w) = \iota(g(w)) = g(w)$となるため, $f = g$.
よって, $\iota:\text{mono}$.
$X, Y$を集合, $A \subset X$, $B \subset Y$, $f:X \to Y$を写像とする.
(1) $f\mid_A:A \to Y$を$f\mid_A \coloneqq f \circ \iota$と定め, $f$の$A$への制限という.
(2) $f\mid_B:f^{-1}(B) \to B$を$x \in f^{-1}(B)$に対し$f\mid_B(x) \coloneqq f(x)$と定め, $f$の$B$への制限という.
$X, Y$を集合, $f:X \to Y:\text{inj.}$とする.
このとき, $f\mid_{\Im f}:\text{bij.}$
$f:\text{inj.}$により$f^{-1}(\Im f) = f^{-1}(f(X)) = X$であるから, 写像は$f:X \to \Im f$となる.
ここで, $\Im (f\mid_{\Im f}) = \Im f$であるから, $f:\text{surj.}$となる.
よって, $f:\text{bij.}$がいえる.
同値関係と商集合
$X$を集合とする.関係$R \subset X \times X$において,$x, y \in X$が$(x, y) \in R$をみたすとき, $xRy$と表す.
関係$\sim \subset X \times X$が同値関係であるとは, 以下をみたすことをいう.
(1) $\forall x \in X [x \sim x]$(反射律という.)
(2) $\forall x, y \in X [x \sim y \Rightarrow y \sim x]$(対称律という.)
(3) $\forall x, y, z \in X [x \sim y \land y \sim z \Rightarrow x \sim z]$(推移律という.)
$X$を集合, $\sim \subset X \times X$を同値関係とする.
$x \in X$に対し, $[x] \coloneqq \{y \in X \mid x \sim y\}$を$x$の同値類という.
$X / \sim \coloneqq \{[x] \in 2^X \mid x \in X\}$を$X$の$\sim$による商集合という.
$X$を集合, $\sim \subset X \times X$を同値関係, $x, y \in X$とする.
$x \sim y \Leftrightarrow [x] = [y]$が成り立つ.
$(\Rightarrow)$
$x, y \in X$に対し$x \sim y$とする.
$z \in X$をとり, $x \sim z$とすると, 対称律から$z \sim x$であり, 仮定から$x \sim y$であり, 推移律から$z \sim y$がいえ, 対称律から$y \sim z$が従うので, $[x] = [y]$が成り立つ.
$(\Leftarrow)$
$x, y \in X$に対し$[x] = [y]$とすると, 反射律から$x \in [x] = [y]$となり, $x \sim y$がいえる.
$X$を集合, $\sim \subset X \times X$を同値関係とする.
命題5により, $x, y \in X$に対し$x \sim y$が成り立つとき, $[x] = [y]$なので, $[x]$という同値類における$x$を$y$に取り換えても$X / \sim$という集合を考えるうえでは同じ振舞いをする.
この意味で$[x]$というときの$x$は恣意的に選ばれたものといえる.この$x$を$[x]$の代表元という.
$X, Y$を集合, $\sim \subset X \times X$を同値関係とする.
写像$f:X / \sim \to Y$に対し, $x, y \in X$が$x \sim y$をみたすなら, $f([x]) = f([y])$である.
この性質をwell-defined性という.
命題11より$[x] = [y]$であるから, 写像の定義により$f([x]) = f([y])$が成り立つ.
同時に, 商集合からの写像$f$を, 代表元を恣意的に選んで定義したい場合, well-defined性をチェックする必要がある.
$X$を集合, $\sim \subset X \times X$を同値関係とする.
$\pi:X \to X / \sim$を$x \in X$に対し$\pi(x) = [x]$と定める.$\pi$を自然な射影という.
このとき, $\pi:\text{epi}$.
$Y$を集合, $f, g:X / \sim \to Y$を写像であって, $f \circ \pi = g \circ \pi$をみたすものとする.
$C \in X / \sim$とすると, $\exists x \in X [[x] = C]$が成り立つ.
ひとつ$[x] = C$をみたす$x \in X$をとれば, $[x] = \pi(x)$であるから,
$f(C) = f(\pi(x)) = f \circ \pi (x) = g \circ \pi (x) = g(\pi(x)) = g(C)$が成り立ち, $f = g$.
よって, $\pi:\text{epi}$.
選択公理
$\forall x [\varnothing \notin x \Rightarrow \exists f:x \to \bigcup x:$写像$\forall a \in x [f(a) \in a]]$という選択公理を導入する.
この公理で存在が保証される写像を選択関数という.
公理的集合論(4) 順序と順序数(1)
順序
&&&def 順序
$X$を集合とする.関係$\le \subset X \times X$が半順序であるとは, 以下をみたすことをいう.
(1) $\forall x \in X [x \le x]$(反射律)
(2) $\forall x, y \in X [x \le y \land y \le x \Rightarrow x = y]$(反対称律)
(3) $\forall x, y, z \in X [x \le y \land y \le z \Rightarrow x \le z]$(推移律)
さらに$\forall x, y \in X [x \le y \vee y \le x]$(全順序律)をみたすとき, $\le$を全順序という.
半順序$\le$は全順序でないとき, $\exists x, y \in X [\neg(x \le y) \land \neg(y \le x)]$をみたす.この条件をみたす$x, y$を比較不能という.
集合$X$と半順序$\le$の組$(X, \le)$を半順序集合という.
集合$X$と全順序$\le$の組$(X, \le)$を全順序集合という.
$X$を集合とする.関係$\le$を$x \in X$に対し$x \le x$であり, $x, y \in X$に対し$x \neq y$のとき$x, y$は比較不能であると定めると, $\le$は半順序となる.この半順序を$X$の自由半順序とよぶ.
$(X, \le)$を全順序集合とする.
関係$< \subset X \times X$を$x, y \in X$に対し$x < y :\Leftrightarrow x \le y \land x \neq y$と定める.$<$を狭義全順序という.
$(X, \le)$を全順序集合, $<$を狭義全順序とする.以下が成り立つ.
(1) $\forall x \in X [\neg(x < x)]$(非反射律)
(2) $\forall x, y \in X [x < y \Rightarrow \neg(y < x)]$(非対称律)
(3) $\forall x, y, z \in X [(x < y \land y < z) \Rightarrow x < z]$(推移律)
(4) $\forall x, y \in X [x \le y \Leftrightarrow (x < y \land x \neq y) \vee (\neg(x < y) \land (x = y))]$
(5) $\forall x, y \in X [(x < y \land (x \neq y) \land \neg(y < x)) \vee (\neg(x < y) \land (x = y) \land \neg(y < x)) \vee (\neg(x < y) \land (x = y) \land y < x)]$
以下$x < y, x = y, y < x$のいずれかひとつだけが成り立つという.(三一律)
- $x \in X$をとる.$x = x$であるため, $\neg(x < x)$が成り立つ.
- $x, y \in X$をとり, $x < y$と仮定する.
もし$y < x$とすれば, $x \le y \land y \le x$から$x = y$が導けるが, これは$x < y$に矛盾し, $\neg(y < x)$が導ける.
よって, $x < y \Rightarrow \neg(y < x)$が成り立つ. - $x, y, z \in X$をとり, $x < y \land y < z$と仮定する.$\le$の推移律により, $x \le z$である.$x = z$と仮定すると$x < y \land y < x$となり(2)により$\bot$が導かれ, $\neg I$により$x \neq z$となり, $x < z$が導ける.
よって, $(x < y \land y < z) \Rightarrow x < z$が成り立つ. - $(\Rightarrow)$
$x, y \in X$が$x \le y$をみたすと仮定する.
このとき, $x = y$であれば$\neg(x < y) \land (x = y)$が成り立ち, $x \neq y$であれば$(x < y) \land (x \neq y)$が成り立つ.
排中律$(x = y) \vee (x \neq y)$により$(x < y \land x \neq y) \vee (\neg(x < y) \land (x = y))$が成り立つ.
$(\Leftarrow)$
$x, y \in X$が$(x < y \land x \neq y) \vee (\neg(x < y) \land x = y)$をみたすと仮定する.
$x < y \land (x \neq y)$のとき, 定義から$x \le y$がいえる.
$\neg(x < y) \land (x = y)$のとき, 反射律から$x \le y$が成り立つ. - $x, y \in X$をとる.$\le$の全順序律より$x \le y \vee y \le x$が成り立つ.
(4)から, $(x < y \land (x \neq y)) \vee (\neg(x < y) \land (x = y)) \vee (y < x \land (y \neq x)) \vee (\neg(y < x) \land (y = x))$
$(\neg(x < y) \land (x = y)) \Leftrightarrow (x = y) \Leftrightarrow (\neg(y < x) \land (y = x))$である.
(1)(2)より三項は排他的.
よって, $(x < y \land (x \neq y) \land \neg(y < x)) \vee (\neg(x < y) \land (x = y) \land \neg(y < x)) \vee (\neg(x < y) \land (x = y) \land y < x)$が成り立つ.
$(X, \le)$を半順序集合, $A \subset X$とする.
(1) $\forall b \in A [a \le b]$が成り立つ$a \in A$が存在するとき, $a$を$\min A$と表し$A$の最小元という.
(2) $x \in X$が$\forall b \in A [x \le b]$をみたすとき, $x$を$A$の下界という.
(3) $A$の下界全体の集合を$L$とおく.$l = \max L$が存在するとき, $l$を$\inf A$と表し$A$の下限という.
(4) $\forall b \in A [b \le a \Rightarrow b = a]$が成り立つ$a$を$A$における極小元という.
(5) $\forall b \in A [b \le a]$が成り立つ$a \in A$が存在するとき, $a$を$\max A$と表し$A$の最大元という.
(6) $x \in X$が$\forall b \in A [b \le x]$をみたすとき, $x$を$A$の上界という.
(7) $A$の上界全体の集合を$U$とおく.$u = \min U$が存在するとき, $u$を$\sup A$と表し$A$の上限という.
(8) $\forall b \in A [a \le b \Rightarrow b = a]$が成り立つ$a$を$A$における極大元という.
$(X, \le)$を半順序集合, $A \subset X$とする.
(1) $\min A$は存在すればただひとつである.
(2) $\max A$は存在すればただひとつである.
- $a, b \in A$が$\min A$の条件を満たすと仮定する.
このとき, $a \le b \land b \le a$が成り立ち, $a = b$がいえる. - $a, b \in A$が$\max A$の条件を満たすと仮定する.
このとき, $a \le b \land b \le a$が成り立ち, $a = b$がいえる.
同様に, $\inf A, \sup A$も存在すればただひとつである.
順序数の導入
集合$x$が順序数であるとは, 以下をみたすことをいう.
(1) $\forall a \in x [a \subset x]$(推移的集合である)
(2) $(x, \subset)$が全順序集合となり, $\in$が$\subset$の狭義全順序となる.
(3) $\forall S \subset x [S \neq \varnothing \Rightarrow \exists l \in S [l = \min S]]$($(x, \subset)$が整列集合である)
$x$を集合とする.$x \notin x$が成り立つ.
$\{x\}$に正則性公理を適用すると, $x \cap \{x\} = \varnothing$が導ける.
よって, $x \notin x$が成り立つ.
$x$を順序数とする.以下が成り立つ.
(1) $\forall y \in x [y = \{z \in x \mid z \in y\}]$
(2) $\forall y \in x [y:\text{順序数}]$
- $R = \{z \in x \mid z \in y\}$とおき, $y \in x$と仮定する.
$z \in y$とする.$x$は順序数なので推移的集合であり, $z \in x$が成り立つ.
よって$z \in R$となり, $y \subset R$が成り立つ.
$z \in R$とすると$z \in y$となるので, $R \subset y$が成り立つ. - $y \in x, z \in y, a \in z$をとる.
$x$は順序数であるから推移的集合であり, $y \subset x$が成り立つ.$z \in y$から$z \in x$が従う.
$z \in x$から$z \subset x$が成り立つ.$a \in z$から$a \in x$が従う.
ゆえに, $a, z, y \in x$であり, $a \in z, z \in y$であるから, $\in$の推移律により$a \in y$が成り立つ.
よって, $z \subset y$が成り立ち, $y$は推移的集合.
$y \subset x$により, 全順序集合としての$(y, \subset)$が得られ, $\in$が$\subset$の狭義全順序となる.
$\varnothing \neq S \subset y$をとると, $y \subset x$により$\varnothing \neq S \subset x$であるから$\min S$が存在する.
ゆえに, $(y, \subset)$は整列集合.
よって, $y$は順序数.
$\{A_{\lambda}\}_{\lambda \in \Lambda}$を"$\varnothing$でない順序数"の族とする.このとき, $\bigcap_{\lambda \in \Lambda}A_{\lambda}$は順序数.
$s = \bigcap_{\lambda \in \Lambda}A_{\lambda}$とおく.
$x \in s$と仮定する.このとき$\bigcap$の定義から$\forall \mu \in \Lambda [x \in A_{\mu}]$が成り立つので, その$\mu$をひとつとる.
$A_{\mu}$は順序数であるから推移的集合であり, $x \subset A_{\mu}$が成り立つ.
$\subset$の推移律により, $x \subset s$が成り立つ.
ゆえに$s$は推移的集合.
$x, y \in s$とすると$\forall \mu \in \Lambda [x, y \in A_{\mu}]$が成り立つので, その$\mu$をひとつとる.
このとき, $A_{\mu}$は順序数なので, $x \in y \Leftrightarrow x \subset y \land x \neq y$が成り立つ.
また, $\varnothing \neq S \subset s$をとると$S \subset A_{\mu}$であるから$\min S$が存在する.
よって, $\bigcap_{\lambda \in \Lambda}$は順序数.
$x, y$を順序数とする.$x \in y, x = y, y \in x$のいずれかひとつのみが成り立つ.
$x \notin x, y \notin y$により$=$と$\in$は同時に成り立つことはない.
また, $x \in y \land y \in x$と仮定すると, $x \in y \subset x$により$x \in x$が導かれ, 矛盾.ゆえに上記は同時に成り立つことはない.
$z = x \cap y$とおくと, 補題により$z$は順序数となる.
定義より$z \subset x, z \subset y$が成り立つ.
$x \neq z, y \neq z$と仮定すると, 上記とあわせて$z \in x, z \in y$が成り立つ.
このとき, $z \in z$となり矛盾.ゆえに$x = z \vee y = z$が成り立つ.
$x = z$のとき, $x = x \cap y$となる.
$\forall a [a \in x \Leftrightarrow a \in x \land a \in y]$から$\forall a \in x [a \in y]$がいえ, $x \subset y$が成り立つ.
このとき, $x \in y \vee x = y$が成り立つ.上記よりいずれか一方のみが成り立つ.
$y = z$のとき$y = x \cap y$となる.
$\forall a [a \in y \Leftrightarrow a \in x \land a \in y]$から$\forall a \in y [a \in x]$がいえ, $y \subset x$が成り立つ.
このとき, $y \in x \vee x = y$が成り立つ.上記よりいずれか一方のみが成り立つ.
どちらの場合も命題が成り立つ.
$\Lambda$を集合, $A = \{A_{\lambda}\}_{\lambda \in \Lambda}$を順序数の族とする.
$\bigcup_{\lambda \in \Lambda}A_{\lambda}$は順序数であり, $\sup A = \bigcup_{\lambda \in \Lambda}A_{\lambda}$が成り立つ.
(順序数性)
$s = \bigcup_{\lambda \in \Lambda}A_{\lambda}$とおく.
$x \in s$と仮定する.このとき$\bigcup$の定義から$\exists \mu \in \Lambda [x \in A_{\mu}]$が成り立つので, その$\mu$をひとつとる.
$A_{\mu}$は順序数なので推移的集合であり, $x \subset A_{\mu}$が成り立つ.
定義より$A_{\mu} \subset s$であるから, $\subset$の推移律より$x \subset s$が成り立つ.
ゆえに$s$は推移的集合.
$x, y \in s$とする.このとき, $\exists\mu \in \Lambda[x \in A_{\mu}], \exists\kappa \in \Lambda[y \in A_{\kappa}]$が成り立つので, その$\mu, \kappa$をひとつとる.
三一律により, $A_{\mu} \subset A_{\kappa}$と$A_{\kappa} \subset A_{\mu}$のいずれかが成り立つ.
$A_{\mu} \subset A_{\kappa}$としても一般性を失わない.
このとき, $x, y \in A_{\kappa}$が成り立つため, $x \in y \Leftrightarrow x \subset y \land x \neq y$が成り立つ.
ゆえに, $\in$が$\subset$の狭義全順序になっている.
$\varnothing \neq S \subset s$をとる.
$x_0 \in S$をひとつとる.このとき, $\exists \mu \in \Lambda [x_0 \in A_{\mu}]$が成り立つので, その$\mu$をひとつとる.
$X = S \cap A_{\mu}$を考えると, $\varnothing \neq X \subset A_{\mu}$であるから, $l = \min X$が存在する.
$x \in S$に対し, $x \in l$と仮定する.
このとき, $l \in A_{\mu}$であり, $A_{\mu}$は順序数であり推移的集合だから$x \in A_{\mu}$がいえる.これは$l = \min X$に矛盾し, $l = \min S$が成り立つ.
ゆえに$s$は整列集合.
よって$\bigcup_{\lambda \in \Lambda}A_{\lambda}$は順序数.
(sup性)
$\forall \lambda \in \Lambda [A_{\lambda} \subset s]$であるから$s$は$\{A_{\lambda}\}_{\lambda \in \Lambda}$の上界.
$\{A_{\lambda}\}_{\lambda \in \Lambda}$の上界$M$をとる.
$x \in s$をとる.このとき, $\exists \mu \in \Lambda [x \in A_{\mu}]$が成り立つので, その$\mu$をひとつとる.
$M$は$\{A_{\lambda}\}_{\lambda \in \Lambda}$の上界であるから, $A_{\mu} \subset M$が成り立つ.ゆえに$x \in M$となり, $s \subset M$がいえる.
よって, $s = \sup A$となる.
一般性を失わないとは, あるふたつの事柄を入れ替えた関係$xRy, yRx$のようなものについて$xRy \vee yRx$が成り立つとき,
$xRy$についての証明における$x, y$を入れ替えることで$yRx$についての証明ができることをいう.
以下, WLOG$xRy$と略記する.
$\Lambda$を集合, $\varnothing \neq A = \{A_{\lambda}\}_{\lambda \in \Lambda}$を順序数の族とする.
このとき, $\min A$が存在する.
$A \neq \varnothing$に対し正則性公理を適用すると, $\exists l \in A [l \cap A = \varnothing]$が成り立つので, この$l$をひとつとる.
$a \in A$をとると, $a, l$は順序数であるから, 三一律により$a \in l, a = l, l \in a$のいずれかひとつだけが成り立つ.
$a \in l$と仮定すると, $a \in l \cap A$となり矛盾する.
よって, $l = \min A$となる.
$X$を集合とする.以下が成り立つとき, $X:\text{順序数}$となる.
(1) $X$は推移的集合.
(2) $\forall x \in X [x:\text{順序数}]$
$X$は推移的集合であり, $\forall x \in X [x:\text{順序数}]$であると仮定する.
三一律により, $\subset$が全順序, $\in$が$\subset$の狭義全順序となる.
$\varnothing \neq S \subset X$をとると$S$は順序数の族であるから, 命題により$\min S$が存在する.
ゆえに$X$は整列集合.
よって, $X$は順序数.
$\varnothing$は$\bot E$により順序数の条件をみたす.これを$0$という.
$x$を順序数とするとき, $\text{suc}(x) \coloneqq x \cup \{x\}$は順序数である.
$a \in \text{suc}(x)$をとる.このとき, $a \in x \vee a = x$が成り立つ.
$a \in x$のとき, $x$は順序数なので推移的集合であり, $a \subset x$が成り立つ.
$a = x$のとき, 定義より$a \subset x$が成り立ち, つくりかたから$x \subset \text{suc}(x)$がわかるので, $a \subset \text{suc}(x)$が成り立つ.($\subset$の推移律は$\Rightarrow$の推移律により成り立つ.)
ゆえに$\text{suc}(x)$は推移的集合.
$x$は順序数なので$(x, \subset)$が全順序集合となる.$x$は推移的集合なので$\forall a \in \text{suc}(x) [a \subset x]$が成り立つ.
ゆえに$(\text{suc}(x), \subset)$は全順序集合.
また, $\forall S \subset \text{suc}(x)$, $S \neq \varnothing$に対し,
$S \subset x$をみたすとき, $\exists l \in S [l = \min S]$が成り立つ.
$\neg(S \subset x)$をみたすとき, $x \in S$となる.
$S = \{x\}$のとき, 定義より$x = \min S$となる.
$S \neq \{x\}$のとき, $S' = S \setminus \{x\}$を考えると, $S' \neq \varnothing$となり, $S \subset \text{suc}(x)$から$S' \subset x$となる.
$x$は整列集合なので$l = \min S'$をとれる.
$l \in \text{suc}(x) \land l \neq x$であるから$l \in x$が成り立ち, $x$は推移的集合なので$l \subset x$が成り立つため, $l = \min S$となる.
ゆえに$\text{suc}(x)$は整列集合.
よって, $\text{suc}(x)$は順序数.
$y$を順序数とする.$\exists x$:順序数$[y = \text{suc}(x)]$が成り立つとき, $y$を後続順序数という.
$0$でも後続順序数でもない順序数を極限順序数という.
超限帰納法
$\alpha$を順序数, $\psi(x)$を$L_{ZFC}$-論理式とする.
$\forall x \in \alpha \forall y \in x [\psi(y) \Rightarrow \psi(x)] \Rightarrow \forall z \in \alpha [\psi(z)]$が成り立つ.
$\forall x \in \alpha \forall y \in x [\psi(y) \Rightarrow \psi(x)]$とし, $\exists z \in \alpha [\neg\psi(z)]$と仮定する.
$S = \{\beta \in \alpha \mid \neg\psi(\beta)\}$とおく.
仮定より$S \neq \varnothing$であり, $S \subset \alpha$であるから$s_0 = \min S$が存在する.
最小元の定義より,$\forall \zeta \in \alpha [(\zeta \subset s_0 \land \zeta \neq s_0) \Rightarrow \zeta \in S]$である.
$\zeta \in s_0 \Leftrightarrow (\zeta \subset s_0 \land \zeta \neq s_0)$から, $\forall \zeta \in s_0 [\psi(\zeta)]$が成り立つ.
ゆえに$\psi(s_0)$となるが, これは$\neg\psi(s_0)$に矛盾する.
よって, $\forall z\in \alpha [\psi(z)]$が成り立つ.
公理的集合論(5) 順序と順序数(2)
$\mathbb{N}$
&&&def inductive set
集合$X$が以下の条件をみたすとき, inductive setであるという.
(1) $\varnothing \in X$
(2) $x \in X \Rightarrow x \cup \{x\} \in X$
$A = \{A_{\lambda}\}_{\lambda \in \Lambda}$をinductive setの族とする.
$\bigcap_{\lambda \in \Lambda} A_{\lambda}$はinductive set.
$A$はinductive setの族であるから, $\forall \lambda \in \Lambda [\varnothing \in A_{\lambda}]$が成り立つ.
ゆえに定義から$\varnothing \in \bigcap_{\lambda \in \Lambda}A_{\lambda}$.
\begin{align}
a \in A &\Leftrightarrow \forall \lambda \in \Lambda [a \in A_{\lambda}] \\
&\Rightarrow \forall \lambda \in \Lambda [a \cup \{a\} \in A_{\lambda}] \\
&\Rightarrow a \cup \{a\}\in \bigcap_{\lambda \in \Lambda}A_{\lambda}
\end{align}
よって, $\bigcap_{\lambda \in \Lambda}A_{\lambda}$はinductive set.
$\eta$をinductive setとする.
$A = \{x \in \eta \mid \forall \zeta:\text{inductive set} [x \in \zeta]\}$とおく.
$\bigcap A$は$\eta$のとりかたによらない.
$\eta, \theta$をinductive setとし, $B = \{x \in \theta \mid \forall \zeta':\text{inductive set} [x \in \zeta']\}, N = \bigcap A, M = \bigcap B$, $K = \eta \cap \theta$とおく.
命題により, $K$はinductive setである.
$N \subset K, M \subset K, K \subset \eta, K \subset \theta$が成り立つ.
$N \subset \theta, M \subset \eta$が導ける.
定義よりそれぞれ$M \subset N, N \subset M$が導ける.
よって$N = M$であり, $\eta$のとりかたによらない.
命題により, $\eta$をinductive setとして$\mathbb{N} \coloneqq \bigcap \{x \in \eta \mid \forall \zeta:\text{inductive set} [x \in \zeta]\}$と定めると, これは$\eta$のとりかたによらずただひとつ.また, 無限公理で存在が保証される$\infty_1$は定義よりinductive setであるから, inductive setは存在し, $\mathbb{N}$も存在する.
$\varnothing \in \mathbb{N}$を$0$, $\{\varnothing\} = \varnothing \cup \{\varnothing\} \in \mathbb{N}$を$1$と略記する.
写像$\text{suc}:\mathbb{N} \to \mathbb{N}$を$n \in \mathbb{N}$に対し$\text{suc}(n) \coloneqq n \cup \{n\}$と定める.$\text{suc}(n)$を$n$のsuccessorという.
$\mathbb{N}$について, 以下が成り立つ.
(1) $\forall n \in \mathbb{N} [\text{suc}(n) \neq 0]$
(2) $\forall A \subset \mathbb{N}:\text{inductive set}[A = \mathbb{N}]$
(3) $\psi$を自由変数をひとつもつ$L_{ZFC}$-論理式とするとき,
$(\psi(0) \land \forall x \in \mathbb{N} [\psi(x) \Rightarrow \psi(\text{suc}(x))]) \Rightarrow \forall n \in \mathbb{N} [\psi(n)]$ ($n$に関するinduction)
(4) $\forall n \in \mathbb{N} [n:\text{順序数}]$
(5) $\mathbb{N}:\text{順序数}$
(6) $\text{suc}:\text{inj.}$
- 定義より$n \in \text{suc}(n)$であるから, $\text{suc}(n) \neq \varnothing = 0$が成り立つ.
- $A \subset \mathbb{N}:\text{inductive set}$をとる.このとき命題で$\eta$のとりかたによらないことがわかるので, $\eta$として$A$を選ぶと, $\mathbb{N} \subset A$が成り立ち, よって$A = \mathbb{N}$が成り立つ.
- $\Psi = \{n \in \mathbb{N} \mid \psi(n)\}$とおき, $(\psi(0) \land \forall x \in \mathbb{N} [\psi(x) \Rightarrow \psi(\text{suc}(x))])$と仮定する.
仮定より, $0 \in \Psi \land \forall x \in \Psi [\text{suc}(x) \in \Psi]$が成り立つ.
これは$\Psi:\text{inductive set}$の定義そのもの.
定義より$\Psi \subset \mathbb{N}$であるから, (2)より$\Psi = \mathbb{N}$が成り立つ. - $n$に関するinductionを用いる.$\psi(n) :\Leftrightarrow n:\text{順序数}$と定める.
case1.$\psi(0)$
$0:\text{順序数}$である.
case2.$\psi(n) \Rightarrow \psi(\text{suc}(n))$
$n \in \mathbb{N}$に対し, $n:\text{順序数}$と仮定する.
このとき, 後続順序数が順序数であることから$\text{suc}(n):\text{順序数}$.
よって, $\forall n \in \mathbb{N} [n:\text{順序数}]$が成り立つ. - $n$に関するinductionを用いて, $\forall n \in \mathbb{N} [n \subset \mathbb{N}]$を証明する.
case1.$\psi(0)$
$\bot E$により$\varnothing \subset \mathbb{N}$が成り立つ.
case2.$\psi(n) \Rightarrow \psi(\text{suc}(n))$
$n \in \mathbb{N}$に対し, $n \subset \mathbb{N}$と仮定する.
$\{n\} \subset \mathbb{N}$であるから, $\text{suc}(n) \subset \mathbb{N}$が成り立つ.
ゆえに$\mathbb{N}$は推移的集合.
また, (4)により$\forall n \in \mathbb{N} [n:\text{順序数}]$である.
命題により$\mathbb{N}$は順序数. - 集合$X$と$f, g:X \to \mathbb{N}$をとり, $\text{suc} \circ f = \text{suc} \circ g$と仮定する.
$x \in X$をとると, $f(x) \cup \{f(x)\} = g(x) \cup \{g(x)\}$が成り立つ.
$(f(x) \in g(x) \vee f(x) = g(x)) \land (g(x) \in f(x) \vee g(x) = f(x))$
$f(x) \neq g(x)$と仮定すると, $f(x) \in g(x) \land g(x) \in f(x)$が導ける.
$\mathbb{N}$は推移的集合であるから, $f(x) \in f(x)$となり, 正則性公理の言い換えにより矛盾.
ゆえに, $\text{suc}$はmonoであり, inj.
inductionを行うとき, 命題としては$x$と$n$とで変数記号を分けて書いたが, (4)のように以下混乱が起こらない場合は基本的に同じ記号を用いる.
この記事を高評価した人
この記事に送られたバッジ
投稿者
