このページでは、この本で使う基礎をaからdまで順に準備します。aでは論理と集合のことばを導入します。すべてを一般化するのではなく、カントールの定理とカントール＝ベルンシュタインの定理へ進むために必要な記号を、使う順に導入します。
この本で量化するものは集合です。クラスは、条件で集合を指定するための内部的な書き方として必要な場所でだけ用い、クラスそのものを量化しません。
a 論理、集合
一階論理
word(,p) … \(\top\) \({\perp}\)word(p,p) … \(\neg\)
word(pp,p) … \(,\) \(\mathbin{\rm o\!r}\) \(\Rightarrow\) \(\Leftrightarrow\) \(\Longrightarrow\) \(\Longleftrightarrow\)
word(vp,p)R … \(\forall\) \(\exists\)
\(\forall x P\) は「すべての集合xについてP」、 \(\exists x P\) は「ある集合xが存在してP」と読まれます。
制限付き多重量化子は、後の証明で繰り返し使われます。
abbr … \(\forall x_{1} , \cdots , x_{\tt n} \mathop{{\sf A}} . P\) ≈ \(\forall x_{1} \cdots \forall x_{\tt n} ( x_{1} \mathop{{\sf A}} , \cdots , x_{\tt n} \mathop{{\sf A}} \Longrightarrow ( P ) )\)
abbr … \(\exists x_{1} , \cdots , x_{\tt n} \mathop{{\sf A}} . P\) ≈ \(\exists x_{1} \cdots \exists x_{\tt n} ( x_{1} \mathop{{\sf A}} , \cdots , x_{\tt n} \mathop{{\sf A}} , ( P ) )\)
2項述語
word(ss,p) … \(\in\) \(\subset\) \(=\)\(x \in X\) が「xはXの元である」、 \(X \subset Y\) は「XはYの部分集合である」と、 \(X = Y\) は「XとYは等しい」と読まれます。
例えば\(\in\) の否定を \(\notin\) で作る事ができます。
word(\({\tt x}\)\({\tt y}\),p→\({\tt x}\)\({\tt y}\),p) … \({\tt /}\)
lower … \(A \stackrel{{\tt /}}{\mathbin{{\sf p}}} B\) ≃ \(\neg ( A \mathbin{{\sf p}} B )\)
内包記法
\(\{ x \mid P \}\) はPを満たすxの集まり、というクラスになります。word(vp,c)F … \(\mathsf{cls}\)
abbr … \(\{ x \mid P \}\) ≈ \(\mathsf{cls} ( x , P )\)
これも制限付きで使用されることが多いです。
abbr … \(\{ x \mathop{{\sf A}} \mid P \}\) ≈ \(\{ x \mid x \mathop{{\sf A}} , ( P ) \}\)
以下の左辺では \(\mathop{{\sf X}}\) が表記上無視されます。
abbr … \(\{ T \mid P \}\) ≈ \(\{ x \mid \exists \mathop{{\sf X}} ( ( P ) , x = T ) \}\)
「(クラスの)元である」という関係が重要です。
word(sc,p) … \(\in\)
cvt … \(X \in \{ x \mid P \}\) ≃ \(P\) の \(x\) に \(X\) を代入したもの
例 \(Y \in \{ X \mid x \in X \}\) ≃ \(x \in Y\)
2項述語の定義
クラスの2項述語およびその一階言語のへの翻訳規則を与えます。word(cc,p) … \(\subset\) \(=\)
sub_. … \(X \subset Y \Longleftrightarrow \forall x \in X . x \in Y\)
=_. … \(X = Y \Longleftrightarrow \forall x \, ( x \in X \Leftrightarrow x \in Y )\)
集合は自然にクラスと見なされます。
Form内でc-Formがあるべき所にあるs-Form \({\tt X}\) は \(\{x \mid x \in {\tt X}\}\) に置き換えられます。
例 \(x \in X\) → \(x \in \{ x \mid x \in X \}\)
通常の教科書と逆で、この教科書では\(\subset\)の定義が\(\subset\)の定義から誘導されます。
sub. … \(X \subset Y \Longleftrightarrow X \subset Y\)
次の\(\Longleftarrow\)は外延性公理と呼ばれます。
=s. … \(X = Y \Longleftrightarrow X = Y\)
b 集合の作成
空集合・外延記法
まず、元を一つも持たない集合を用意します。word(,s) … \(\emptyset\)
\0. … \(\emptyset = \{ x \mid {\perp} \}\)
\(x \notin \emptyset\) \(\blacktriangleleft\) W.
\(\emptyset \subset X\) \(\blacktriangleleft\) W.
\0.. … \(x = \emptyset \Longleftrightarrow \not\exists y \, ( y \in x )\) \(\blacktriangleleft\) W.
次に、指定した元だけを持つ集合を作ります。1以上の自然数 \({\tt n}\) に対して
word(s\(^{\tt n}\),s)F … \(\mathsf{set}_{\tt n}\)
abbr … \(\{ x_{1} , \cdots , x_{\tt n} \}\) ≈ \(\mathsf{set}_{\tt n} ( x_{1} , \cdots , x_{\tt n} )\)
set\({\tt n}\). … \(\{ x_{1} , \cdots , x_{\tt n} \} = \{ v \mid v = x_{1} \mathbin{\rm o\!r} \cdots \mathbin{\rm o\!r} v = x_{\tt n} \}\)
合併、共通部分、差
二つの集合から、元の条件によって集合を作ります。word(ss,s) … \(\cup\) \(\cap\) \(\mathop\setminus\)
cup. … \(X \cup Y = \{ x \mid x \in X \mathbin{\rm o\!r} x \in Y \}\)
cap. … \(X \cap Y = \{ x \mid x \in X , x \in Y \}\)
dif. … \(X \mathop\setminus Y = \{ x \mid x \in X , x \notin Y \}\)
総合併、総共通部分
word(s,s)R … \(\bigcup\) \(\bigcap\)Cup. … \({\bigcup} \stackrel{\star}{=} {\bigcup}\)
Cap. … \(\exists X \, X \in \mathcal{X} \Longrightarrow \bigcap \mathcal{X} = \bigcap \mathcal{X}\)
Cap.' … \(\mathcal{X} \neq \emptyset \Longrightarrow \bigcap \mathcal{X} = \bigcap \mathcal{X}\) \(\blacktriangleleft\) W.
\(X = \bigcup \{ X \}\) \(\blacktriangleleft\) W.
\(X = \bigcap \{ X \}\) \(\blacktriangleleft\) W.
\(X \cup Y = \bigcup \{ X , Y \}\) \(\blacktriangleleft\) W.
\(X \cap Y = \bigcap \{ X , Y \}\) \(\blacktriangleleft\) W.
\(X = \bigcup _{ x \in X } \{ x \}\) \(\blacktriangleleft\) W.
冪集合
集合Xの部分集合を、すべて一つの集合に集めます。word(s,s) … \(\wp\)
wp. … \(\wp X = \{ A \mid A \subset X \}\)
\(\wp X\) はXの冪集合と呼ばれ、最後のカントールの定理で再び主役になります。
wp0 … \(\wp \emptyset = \{ \emptyset \}\) \(\blacktriangleleft\) W.
wp1 … \(\wp \{ x \} = \{ \emptyset , \{ x \} \}\) \(\blacktriangleleft\) W.
c 関係
順序対
word(ss,s)F … \(\mathsf{pr}\)abbr … \(\langle X , Y \rangle\) ≈ \(\mathsf{pr} ( X , Y )\)
\(\langle x , y \rangle\) をxとyの順序対と呼びます。
word(s,s) … \(\triangleleft\) \(\triangleright\)
pr<. … \(\triangleleft \langle x , y \rangle = x\)
pr>. … \(\triangleright \langle x , y \rangle = y\)
pr:0 … \(\langle x_{0} , y_{0} \rangle = \langle x_{1} , y_{1} \rangle \Longleftrightarrow x_{0} = x_{1} , y_{0} = y_{1}\) \(\blacktriangleleft\) W.
直積と関係
word(ss,s) … \(\times\)^^pr. … \(X \times Y = \{ \langle x , y \rangle \mid x \in X , y \in Y \}\)
\(X \times Y\) をXとYの直積と呼びます。
\(R \subset X \times Y\) のとき、RをXからYへの関係と呼びます。
定義域・値域・像
word(s,s)F … \(\triangleleft\) \(\triangleright\)^pr<. … \(\triangleleft ( R ) = \{ x \mid \exists y \, \langle x , y \rangle \in R \}\)
^pr>. … \(\triangleright ( R ) = \{ y \mid \exists x \, \langle x , y \rangle \in R \}\)
\(\triangleleft ( R )\) をRの定義域、 \(\triangleright ( R )\) をRの値域と呼びます。
word(ss,s) … *^ap
*^ap. … \(R ( A ) = \{ y \mid \exists x ( x \in A , \langle x , y \rangle \in R ) \}\)
\(R ( A )\) をRによるAの像と呼びます。
逆関係と合成
word(s,s) … \(^\leftrightarrow\)^sw. … \(R ^\leftrightarrow = \{ \langle y , x \rangle \mid \langle x , y \rangle \in R \}\)
\(R ^\leftrightarrow\) をRの逆関係と呼びます。
word(ss,s) … \(\circ\)
comp. … \(S \circ R = \{ \langle x , z \rangle \mid \exists y \, ( \langle x , y \rangle \in R , \langle y , z \rangle \in S ) \}\)
\(S \circ R\) をSとRの合成と呼びます。
d 写像
一意の量化子
word(vp,p)R … \(!\) \(\exists!\)am1. … \(! x P \Longleftrightarrow \forall y , z \in \{ x \mid P \} . y = z\)
exi!. … \(\exists! x P \Longleftrightarrow \exists x P , ! x P\)
abbr … \(! x \mathop{{\sf A}} . P\) ≈ \(! x ( x \mathop{{\sf A}} , ( P ) )\)
abbr … \(\exists! x \mathop{{\sf A}} . P\) ≈ \(\exists! x ( x \mathop{{\sf A}} , ( P ) )\)
写像
word(ss,s) … \(\to\)->. … \(X \to Y = \{ f \subset X \times Y \mid \forall x \in X . \exists! y \, ( \langle x , y \rangle \in f ) \}\)
\(f \in X \to Y\) のとき、fをXからYへの写像と呼びます。
単射・全射・全単射
word(ss,s) … \(\stackrel{\rm I}\to\) \(\stackrel{\rm S}\to\)->I. … \(X \stackrel{\rm I}\to Y = \{ f \in X \to Y \mid \forall y \, ! x \, \langle x , y \rangle \in f \}\)
->S. … \(X \stackrel{\rm S}\to Y = \{ f \in X \to Y \mid \forall y \in Y . \exists x \, \langle x , y \rangle \in f \}\)
\(f \in X \stackrel{\rm I}\to Y\) のときfは単射、 \(f \in X \stackrel{\rm S}\to Y\) のときfは全射です。
word(ss,s) … \(\stackrel{\rm IS}\to\)
->IS. … \(X \stackrel{\rm IS}\to Y = ( X \stackrel{\rm I}\to Y ) \cap ( X \stackrel{\rm S}\to Y )\)
\(f \in X \stackrel{\rm IS}\to Y\) のときfは全単射です。