$R:A\leftarrow B, S:A\leftarrow C$に対して、$X:B\leftarrow C$についての条件\[R\circ X\subseteq S\tag{*}\]を考える。表現行列で言えば$RX\leq S$である。ここで$\leq$は「対応する各要素（ブール値）がいずれも$\leq$」と定義される半順序である。$R,S$を列ごとに分けたベクトルをそれぞれ$b_i,c_j$とおくと、(*)は各$j$について\[\bigoplus_i b_iX_{ij}\leq c_j\]が成り立つことと同値である。これは結局、さらに各$i$について\[b_iX_{ij}\leq c_j\]すなわち\[b_i\leq c_j\vee X_{ij}=0\]が成り立つことにほかならない。$b_i\not\leq c_j$のときは$X_{ij}=0$でなければならないが、$b_i\leq c_j$のときは$X_{ij}$は$0,1$のいずれの値もとりうる。各$i,j$について$X_{ij}$のとりうる最大値を並べたものが$R\backslash S$の表現行列となる。
2項関係の除算
$A,B,C$は集合、$S,R$はそれぞれ$B\times C,A\times C$上の2項関係とする。$A\times B$上の任意の2項関係$X$について\[X\circ S\subseteq R\Leftrightarrow\forall a\in A,c\in C[_aX\circ S_c\rightarrow{}_{a}R_c]\]\[\Leftrightarrow\forall a\in A,c\in C[\exists b\in B[{}_aX_b\wedge{}_bS_c]\rightarrow{}_{a}R_c]\]\[\Leftrightarrow\forall a\in A,c\in C,b\in B[({}_aX_b\wedge{}_bS_c)\rightarrow{}_{a}R_c]\]\[\Leftrightarrow\forall a\in A,b\in B,c\in C[{}_aX_b\rightarrow({}_bS_c\rightarrow{}_{a}R_c)]\]\[\Leftrightarrow\forall a\in A,b\in B[{}_aX_b\rightarrow\forall c\in C[{}_bS_c\rightarrow{}_aR_c]]\]\[\Leftrightarrow X\subseteq\{\langle a,b\rangle\in A\times B\mid\forall c\in C[{}_bS_c\rightarrow{}_aR_c]\}\]
この右辺を$R/S$と定義する。すなわち$X\circ S\subseteq R\Leftrightarrow X\subseteq R/S$である。一般に$K=\bigcup\{X\mid X\subseteq K\}$であるので、$R/S$は$\bigcup\{X\mid X\circ S\subseteq R\}$と書くこともでき、これを定義としてもよい。
エンダートン『論理学への数学的手引き』演習問題1.2.10
【補題】整式の集合$\Sigma_1,\Sigma_2$について、(A)「$\Sigma_1\vDash\sigma$ならば$\Sigma_2\vDash\sigma$」と(B)「$\Sigma_1\ni\sigma$ならば$\Sigma_2\vDash\sigma$」とは同値である。
（証明）$\Sigma_1\vDash\sigma$は$\Sigma_1\ni\sigma$よりも弱い仮定であるので(A)⇒(B)である。また(B)は「$\Sigma_1$の要素はすべて、$\Sigma_2$を充足するいかなる割り当てによっても真となる」、つまり「$\Sigma_2$を充足する割り当ては$\Sigma_1$をも充足する」ということを主張しているから、(B)⇒(A)も成り立つ。□
【演習10】(a)「整式の有限集合でサイズ$n$のものは、自身と同値で独立な部分集合を持つ」という命題を$\varphi(n)$とし、すべての自然数$n$に対して$\varphi(n)$が成り立つことを数学的帰納法により示す。$\varphi(0)$は、整式の空集合が独立の定義を満たすことから成立する。任意に自然数$n$をとって$\varphi(n)$を仮定し、$\varphi(n+1)$を導く。整式の有限集合でサイズ$n+1$のもの$\Sigma$を任意にとると、$\Sigma$が独立であれば自身が所期の部分集合となる。$\Sigma$が独立でないとき、$\alpha\in\Sigma$かつ$\Sigma\backslash\{\alpha\}\vDash\alpha$なる整式$\alpha$がとれる。$\Sigma\backslash\{\alpha\}
$は$\Sigma$と同値であり（上の補題に注意）、またサイズ$n$であるので、帰納法の仮定$\varphi(n)$により、同値で独立な部分集合を持つ。この集合はもとの$\Sigma$から見ても同値で独立な部分集合となる。
(b)整式の無限集合$\Sigma=\{A_1,A_1\wedge A_2,A_1\wedge A_2\wedge A_3,\ldots\}$が反例となることを示す。$\Sigma$の部分集合が独立であるのは一点集合か空集合のときだけである（さもないと「最も短い整式」が他から含意される）が、いずれにしても$\Sigma$と同値ではあり得ない。
(c)各$n\in\mathbb{N}$に対し$\sigma_0\rightarrow(\sigma_1\rightarrow(\sigma_2\rightarrow\cdots\rightarrow(\sigma_{n-1}\rightarrow\sigma_n)\cdots))$のことを$\gamma_n$と書く。$\Gamma=\{\gamma_n\mid n\in\mathbb{N}\}$からトートロジーをすべて除いたもの$\Gamma'$が所期の集合となることを示す。
・$\Sigma$との同値性：どの$\gamma_n\in\Gamma$に対しても$\Sigma\supseteq\{\sigma_n\}\vDash\gamma_n$、一方どの$\sigma_n\in\Sigma$に対しても$\Gamma\supseteq\{\gamma_0,\gamma_1,\ldots\gamma_n\}\vDash\sigma_n$であるから、$\Sigma$と$\Gamma$は同値である。さらに、トートロジーは整式のいかなる集合によっても含意されるから、$\Gamma(\supseteq\Gamma')$と$\Gamma'$も同値である。
・独立性：$\gamma_i\in\Gamma'$を任意にとり、$\Gamma'\backslash\{\gamma_i\}\not\vDash\gamma_i$を示す。$\gamma_i$はトートロジーではないため、これを偽にする真理値割り当て$v$が存在する。$\gamma_i$の定義から、$v$により$\sigma_0,\ldots,\sigma_{i-1}$はすべて真に、$\sigma_i$は偽になるので、$v$は$\Gamma'\backslash\{\gamma_i\}$を充足する。
20230531輪講の復習用問題
●写像$f:X\to Y$と$A\subseteq X, B\subseteq Y$について、$A$の$f$による像$f[A]$の定義は\[\{f(x)\in Y\mid x\in A\}\]あるいは\[\{y\in Y\mid\exists x\in A[y=f(x)]\}\]です。$B$の$f$による原像$f^{-1}[B]$の定義を答えてください。
●写像$f:\mathbb{R}\to\mathbb{R}, x\mapsto x^2$による、
(1)$\{2\}$の像、
(2)$\{-2,2\}$の像、
(3)$\{4\}$の原像、
(4)$\{-1,4\}$の原像
を、それぞれ答えてください。
●正誤を答えてください。一般に(1)像の原像は、(2)原像の像は
(A)もとの集合に等しくなる、
(B)もとの集合を包含する、
(C)もとの集合に包含される。
(20230623追記）
$A\subseteq f^{-1}[f[A]]$の証明：
任意に$a\in A$をとると、像の定義から$f(a)\in f[A]$である。すると原像の定義から$a\in f^{-1}[f[A]]$である。
$f[f^{-1}[B]]\subseteq B$の証明：
任意に$y\in f[f^{-1}[B]]$をとると、像の定義により、$y=f(x)$なる$x\in f^{-1}[B]$がとれる。原像の定義により$f(x)\in B$であるから$y\in B$である。
20230510輪講の予習用チェックポイント
【問題】実数$x,y$が$2x+y^2=4$を満たしながら動くとき、$x^2+y^2$のとりうる値の範囲を求めよ。
$2x+y^2=4$を満たす実数$x,y$の具体例をいくつか挙げてください。それぞれに対して、$x^2+y^2$の値は何になりますか。
$k=-1,0,1,2,3,4$に対して、それぞれ$x^2+y^2$は$k$という値をとりうるかどうかを答えてください。
一般に、「$x^2+y^2$が$k$という値をとりうるかどうか」は、どうすれば調べることができますか。
[20230512追記]
復習用問題：
・$2x+y^2=4$を満たし、$x^2+y^2$の値を$7$にする実数の組$(x,y)$を求めてください。
・$x$についての方程式$x^2-2x+4=k$が実数解を持つ限りにおいて、「それらがともに$2$を超える」という事態は起こらないことを証明してください。
20230426輪講のノート
『論理学で学ぶ数学』p61、Theme 4の別解。
$(ax+b)(ax+c)< 0\Leftrightarrow{\rm min}\{b,c\}< -ax< {\rm max}\{b,c\}$から、\[\exists x\in\mathbb{R}[(ax+b)(ax+c)< 0]\]\[\Leftrightarrow(a=0\wedge{\rm min}\{b,c\}<0< {\rm max}\{b,c\})\vee(a\neq0\wedge{\rm min}\{b,c\}< {\rm max}\{b,c\})\]\[\Leftrightarrow(a=0\wedge bc< 0)\vee(a\neq0\wedge b\neq c)\]である。したがって、求めるべき条件はこれを否定した\[(a=0\wedge bc\geq0)\vee(a\neq0\wedge b=c)\]となる。
Suc-帰納法と累積帰納法
Suc-帰納法：\[(P(0)\wedge \forall k[P(k)\rightarrow P(k+1)])\rightarrow\forall n[P(n)]\tag{1}\]
累積帰納法：\[\forall n[\forall m< n[P(m)]\rightarrow P(n)]\rightarrow\forall n[P(n)]\tag{2}\]
(1)⇒(2)：図式(1)のもと、$\forall n[\forall m< n[P(m)]\rightarrow P(n)]$なる任意の述語$P$をとり、$\forall n[P(n)]$を導く。$Q(n)\equiv\forall m< n[P(m)]$とおくと、$Q(0)$が成り立つ。また上の仮定は$\forall n[Q(n)\rightarrow P(n)]$と書けるから、$Q(k)$なる任意の$k$について$P(k)$も成立し、$Q(k)\wedge P(k)$すなわち$Q(k+1)$が成り立つ。すると図式(1)から$\forall n[Q(n)]$が成り立ち、これは$\forall n[P(n)]$を含意する。
(2)⇒(1)：図式(2)のもと、(ア)$P(0)$および(イ)$\forall k[P(k)\rightarrow P(k+1)]$を満たす任意の述語$P$をとり、$\forall n[P(n)]$を導く。そのために(ウ)$\forall m< n[P(m)]$なる任意の$n$をとり、$P(n)$を導くことで図式(2)の前件の成立を言う。$n=0$のときは(ア)から直ちに$P(n)$が従う。$n\neq0$のとき、$n=m+1$なる$m$がとれて、(ウ)から$P(m)$が成立するが、(イ)により$P(m+1)$すなわち$P(n)$も成立する。■
