対を使用して写像を作り、集合の濃度比較について記述します。Bernsteinの定理、Cantorの定理を目標にします。
a
順序対
\(\mathbb{W}\)(ss,s)F … \(\mathsf{pr}\)abbr … \(\langle X , Y \rangle\) ≈ \(\mathsf{pr} ( X , Y )\)
\(\mathbb{W}\)(s,s) … \(\triangleleft\) \(\triangleright\)
◁. … \(\triangleleft \langle x , y \rangle = x\)
▷. … \(\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\) \(\mathbb{W}.\)
直積
\(\mathbb{W}\)(ss,s) … \(\times\)^^pr. … \(X \times Y = \{ \langle x , y \rangle \mid x \in X , y \in Y \}\)
一般の集合に対して定義域・値域を作ります。
\(\mathbb{W}\)(s,s)F … \(\triangleleft\) \(\triangleright\)
^◁. … \(\triangleleft ( R ) = \{ x \mid \exists y \, \langle x , y \rangle \in R \}\)
^▷. … \(\triangleright ( R ) = \{ y \mid \exists x \, \langle x , y \rangle \in R \}\)
\(\mathbb{W}\)(ss,s) … *^ap
*^ap. … \(R ( A ) = \{ y \mid \exists x ( x \in A , \langle x , y \rangle \in R ) \}\)
関係
\(\mathbb{W}_+\)(,c) … \(\text{Rel}\)Rel. … \(\text{Rel} = \{ R \mid \forall p \in R . \exists x , y p = \langle x , y \rangle \}\)
Rel.' … \(\text{Rel} = \{ R \mid R \subset \triangleleft ( R ) \times \triangleright ( R ) \}\) \(\blacktriangleleft\) \(\mathbb{W}.\)
Rel.. … \(\text{Rel} = \{ R \mid \forall x \in R . x = \langle \triangleleft x , \triangleright x \rangle \}\) \(\blacktriangleleft\) \(\mathbb{W}.\)
逆関係、合成
\(\mathbb{W}\)(s,s) … \(^\leftrightarrow\)^sw. … \(R ^\leftrightarrow = \{ \langle y , x \rangle \mid \langle x , y \rangle \in R \}\)
^sw:0 … \(R \subset X \times Y \Longrightarrow R ^\leftrightarrow \subset Y \times X\) \(\blacktriangleleft\) \(\mathbb{W}.\)
^sw:I … \(R \in \text{Rel} \Longrightarrow R ^\leftrightarrow \, \! ^\leftrightarrow = R\) \(\blacktriangleleft\) \(\mathbb{W}.\)
\(\mathbb{W}\)(ss,s) … \(\circ\)
∘. … \(S \circ R = \{ \langle x , z \rangle \mid \exists y \, ( \langle x , y \rangle \in R , \langle y , z \rangle \in S ) \}\)
comp:0 … \(R \subset X \times Y , S \subset Y \times Z \Longrightarrow S \circ R \subset X \times Z\) \(\blacktriangleleft\) \(\mathbb{W}.\)
comp:A … \(R , S , T \in \text{Rel} \Longrightarrow ( T \circ S ) \circ R = T \circ ( S \circ R )\) \(\blacktriangleleft\) \(\mathbb{W}.\)
comp:X … \(R , S \in \text{Rel} \Longrightarrow ( R \circ S ) ^\leftrightarrow = S ^\leftrightarrow \circ R ^\leftrightarrow\) \(\blacktriangleleft\) \(\mathbb{W}.\)
b
写像
\(\mathbb{W}\)(ss,s) … \(\to\)→. … \(X \to Y = \{ f \subset X \times Y \mid \forall x \in X . \exists! y \, ( \langle x , y \rangle \in f ) \}\)
単射・全射・全単射
\(\mathbb{W}\)(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 \}\)
\(\mathbb{W}_+\)(cc,c) … \(\cap\)
\(\mathbb{W}\)(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 )\)
c
写像による濃度の比較
\(\mathbb{W}\)(ss,p) … \(\stackrel{\#}=\) \(\stackrel{\#}\le\) \(\stackrel{\#}<\)=#. … \(X \stackrel{\#}= Y \Longleftrightarrow \exists f \, f \in X \stackrel{\rm IS}\to Y\)
le#. … \(X \stackrel{\#}\le Y \Longleftrightarrow \exists f \, f \in X \stackrel{\rm I}\to Y\)
<#. … \(X \stackrel{\#}< Y \Longleftrightarrow X \stackrel{\#}\le Y , X \stackrel{{\tt /}}{\stackrel{\#}=} Y\)
カントール＝ベルンシュタインの定理
カントール＝ベルンシュタインの定理\(X \stackrel{\#}\le Y , Y \stackrel{\#}\le X \Longrightarrow X \stackrel{\#}= Y\) \(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s0
対角線
カントールの定理\(X \stackrel{\#}< \wp X\)
\(\blacktriangleleft\) \(\mathbb{W}.\) ，ax_s0