練習問題

任意の集合 \(A\) に対して、\(A\) の部分集合全体の集合を \(\operatorname{pow}(A)\) と表記する。\(A\) 自身も \(\operatorname{pow}(A)\) の要素である。空集合を \(\varnothing\) と表記する。

1. \(\operatorname{pow}(\left\{ 1, 2 \right\})\) の要素を示せ。

2. \(\operatorname{pow}(\left\{ \varnothing, \left\{ \varnothing \right\} \right\})\) の要素を示せ。

3. \(\operatorname{pow}(\left\{ 1, 2, \ldots, 8 \right\})\) の要素はいくつあるか？

集合に関する次の命題を集合理論の論理式 (第 8.3.2 項) で表せ。それぞれの解答では以前の解答を省略形として使って構わない。また、集合間の等価性を表す \(=\) は最初から使ってよい。

1. \(x = \varnothing\)
2. \(x = \left\{ y, z \right\}\)

3. \(x \subseteq y\quad\) (\(x\) は \(y\) の部分集合 ── \(y\) と等しい場合も含む)

ここまでの解答があれば、述語「\(x\) は \(y\) の真部分集合である」を集合理論の論理式で表せる。具体的は、\(x \neq y\) を \(\operatorname{\text{\footnotesize NOT}} (x = y)\) の省略形と定めれば、論理式 \(x \subseteq y \ \operatorname{\text{\footnotesize AND}} \ x \neq y\) は \(x \subset y\) を意味する集合理論の論理式である。

以降の解答では、この \(x \subset y\) も使ってよい。

4. \(x = y \cup z\)
5. \(x = y - z\)
6. \(x = \operatorname{pow} (y)\)
7. \(x = \bigcup\limits_{z \in y} z\)

最後の命題は「集合の集合 \(y\) に対して、\(y\) に属する全ての部分集合 \(z\) の和集合が \(x\) に等しい」を意味する。\(\bigcup\limits_{z \in y} z\) を単に \(\bigcup y\) と書く場合もある。

[集合に関する論理式と命題論理式の関係]

1. 命題論理式 \((P \ \operatorname{\text{\footnotesize AND}} \ \overline{\mathstrut Q}) \ \operatorname{\text{\footnotesize OR}}\ (P \ \operatorname{\text{\footnotesize AND}} \ Q)\) が \(P\) と同値だと示せ。

2. 任意の集合 \(A\), \(B\) に関する次の等式を証明せよ:

   \[ A = (A - B) \cup (A \cap B) \]

   ただし、\(\text{(a)}\) の結果と同値変形を使って任意の \(x\) に対する次の関係を示すアプローチで証明すること:

   \[ x \in A \ \ \longleftrightarrow \ \ x \in (A - B) \cup (A \cap B) \]

次の定理を証明せよ:

ただし、同値変形を使って次の関係を示すアプローチを使うこと:

ここで \(x\) は任意の要素である。命題論理式の同値公理 \(\text{(3.10)}\) を使ってよい。

集合の等価性に関する Deド Morganモルガン の法則を証明せよ:

ただし、命題「等式 \(\text{(4.9)}\) の左辺に \(x\) が属する」と命題「等式 \(\text{(4.9)}\) の右辺に \(x\) が属する」が同値だと示すアプローチで証明すること。命題論理式に対する De Morgan の法則 \(\text{(3.14)}\) を仮定してよい。

[冪集合の性質] \(A\), \(B\) を集合とする。

1. 次の等式を示せ:

   \[ \operatorname{pow}(A \cap B) = \operatorname{pow}(A) \cap \operatorname{pow}(B) \]

2. 次の関係を示せ:

   \[ (\operatorname{pow}(A) \cup \operatorname{pow}(B)) \subseteq \operatorname{pow}(A \cup B) \]

   等号は \(A\) と \(B\) の一方がもう一方の部分集合であるとき成り立つ。

部分集合テイクアウェイ (subset take-away) とは、有限集合 \(A\) を使って二人で遊ぶゲームである¹。プレイヤーは次のルールを守りながら \(A\) の非空部分集合を順に選択していく:

• \(A\) を選んではいけない。

• これまでに選ばれた部分集合を含む部分集合を選んではいけない。

先に部分集合を選べなくなったプレイヤーの負けとなる。

例えば \(A\) の要素数が \(1\) のとき、選択できる集合は存在しないので後攻のプレイヤーが必ず勝つ。\(A\) の要素数が \(2\) のとき両プレイヤーは \(2\) 個の \(1\) 要素部分集合を任意の順序で一つずつ選択するので、このときも後攻のプレイヤーが必ず勝つ。

最初の興味深いケースは \(A\) の要素数が \(3\) のときである。このとき、もし先攻のプレイヤーが \(1\) 要素部分集合を選んだなら、後攻のプレイヤーはそれ以外の要素からなる \(2\) 要素部分集合を選択する。先攻のプレイヤーが \(2\) 要素部分集合を選んだなら、後攻のプレイヤーはそれに含まれない要素だけからなる \(1\) 要素部分集合を選択する。こうすると両方の場合で、次の手で選択できる集合が \(2\) 要素集合を使ったゲームの初期状態と同じになり、その後は後攻のプレイヤーが必ず勝つ。よって \(A\) の要素数が \(3\) のときは後攻のプレイヤーに必勝戦略が存在する。

\(A\) の要素数が \(4\) のときも後攻のプレイヤーに必勝戦略が存在すると示せ²。

\(A\), \(B\), \(C\) を集合とする。次の等式を示せ:

第 4.1.5 項で触れた同値変形のアプローチを利用せよ。

\(2\) 個の集合の共通部分に対する和集合の分配律 (問題 4.4) は次の等式である:

等式 \(\text{(4.11)}\) と整列原理を使って、\(n\) 個の集合の共通部分に対する和集合の分配律 (次の等式) を示せ:

等式を任意の項数に一般化することは整列原理のよくある (しかし多くは退屈な) 応用の一つである。

演算子として \(\cup\), \(\cap\), \(-\) と補集合演算子だけを利用する式を考える。第 4.1.5 項で説明したように、そういった二つの式の等価性は対応する命題論理式の恒真性に帰着できる。同じアプローチを使うと、恒真でない集合論的等式に対する反例を生成できる。

例えば、次の恒真でない等式

に対する反例の一つに \(A = \left\{ 1 \right\}\), \(B = \left\{ 1 \right\}\), \(C = \varnothing\) がある: 左辺は \(\left\{ 1 \right\} - (\left\{ 1 \right\} \cup \varnothing) = \varnothing\) であり、右辺は \((\left\{ 1 \right\} - \left\{ 1 \right\}) \cup (\left\{ 1 \right\} - \varnothing) = \left\{ 1 \right\} \) なので等しくない。

二つの集合に関する式を結んだ恒真でない集合理論的等式が与えられたとき、対応する命題論理式を偽にする真理値割り当てを考えることで等式に対する反例を構築する方法を説明せよ。集合に関する任意の等式は \(1\) 要素集合を議論領域としたとき恒真なら、任意の議論領域でも恒真だと結論付けよ。

これまでに、集合の等価性が対応する命題論理式の同値性に等しいことを見た。例えば、同値変形を使った

の証明では、命題論理式 \((P \ \operatorname{\text{\footnotesize AND}} \ \overline{\mathstrut Q}) \ \operatorname{\text{\footnotesize OR}}\ (P \ \operatorname{\text{\footnotesize AND}} \ Q)\) と \(P\) の同値性が利用された。

集合に関する次の等式を同値変形で証明するとき、同値性が利用される二つの命題論理式を答えよ:

同値性が利用される二つの述語論理式だけを答えればよい。解答が同値であること、その同値性が上記の集合の等価性と等しいことを証明する必要はない。

これまでに、集合の等価性が対応する命題論理式の同値性に等しいことを見た。例えば、同値変形を使った

の証明では、命題論理式 \((P \ \operatorname{\text{\footnotesize AND}} \ \overline{\mathstrut Q}) \ \operatorname{\text{\footnotesize OR}}\ (P \ \operatorname{\text{\footnotesize AND}} \ Q)\) と \(P\) の同値性が利用された。

集合に関する次の等式を同値変形で証明するとき、同値性が利用される二つの命題論理式を答えよ:

同値性が利用される二つの述語論理式だけを答えればよい。解答が同値であること、その同値性が上記の集合の等価性と等しいことを証明する必要はない。

集合に関する等式

は、ある二つの命題論理式の同値性を使うと証明できる。

1. どんな同値性か？

2. その同値性を使って等式を示す方法を答えよ。

\(A\), \(B\), \(C\), \(D\) を任意の集合とする。デカルト積 \(A \times B\) と \(C \times D\) が共通要素を持たないとき、「\(A\) と \(C\) が共通要素を持たない」または「\(B\) と \(D\) が共通要素持たない」だと示せ。

1. 次の命題が偽だと示す反例を示し、それが反例である理由を簡単に説明せよ:

   偽の主張

   \(A\), \(B\), \(C\), \(D\) を集合とする。\(L\), \(R\) を次のように定める:

   \[ \begin{aligned} L ::= (A \cup B) \times (C \cup D) \\ R ::= (A \times C) \cup (B \times D) \end{aligned} \]

   このとき \(L = R\) である。

2. 上記の偽の主張に対する誤った証明を次に示す。どこが間違っているのか指摘せよ。

   誤った証明 \(L\), \(R\) は組の集合だから、全ての \(x\), \(y\) で \((x, y) \in L \ \ \longleftrightarrow \ \ (x, y)\in R \) が成り立つと示せれば十分である。これは同値変形で示せる:

   \[ \begin{aligned} & (x, y) \in R \\ & \quad \longleftrightarrow \ \ (x, y) \in (A \times C) \cup (B \times D) \\ & \quad \longleftrightarrow \ \ (x, y) \in A \times C \ \operatorname{\text{\footnotesize OR}}\ (x, y) \in B \times D \\ & \quad \longleftrightarrow \ \ (x \in A \ \operatorname{\text{\footnotesize AND}} \ y \in C) \ \operatorname{\text{\footnotesize OR}}\ (x \in B \ \operatorname{\text{\footnotesize AND}} \ y \in D) \\ & \quad \longleftrightarrow \ \ (x \in A \ \operatorname{\text{\footnotesize OR}}\ x \in B) \ \operatorname{\text{\footnotesize AND}} \ (y \in C \ \operatorname{\text{\footnotesize OR}}\ y \in D) \\ & \quad \longleftrightarrow \ \ x \in A \cup B \ \operatorname{\text{\footnotesize AND}} \ y \in C \cup D \\ & \quad \longleftrightarrow \ \ (x, y) \in L \end{aligned} \]

   ■

3. 証明を修正して \(R \subseteq L\) を示せ。

\(A\) から \(B\) への二項関係 \(R\) の逆 (inverse) \(R^{-1}\) は \(B\) から \(A\) への二項関係であり、次の規則で定義される:

言い換えれば、\(R\) を表す図の矢印を反転させると \(R^{-1}\) を表す図が得られる。

この問題では\(R\) の性質が \(R^{-1}\) の異なる性質に結び付くことを見る。例えば \(R\) が全域のとき \(R^{-1}\) は全射になる。次の表を埋めよ:

ヒント: \(R\) を表す図で \(A\) の要素から \(B\) の要素に向かう矢印を考える。

関数 \(f\colon \mathbb{R} \to \mathbb{R}\) であって全域かつ単射であるものの全単射でないものを示せ。

二項関係 \(R\colon A \to B\) の性質の中には、\(R\) を表す図に含まれる矢印だけから、つまり \(\operatorname{graph}(R)\) だけから決定するものが存在する。他の性質は \(\operatorname{graph}(R)\) だけでは分からず、始域 \(A\) や終域 \(B\) が分かって初めて決定する。\(R\) が次に示す性質を持つかどうかを判定するときに必要となる情報はどれかを答えよ:

1. \(\operatorname{graph}(R)\) のみ

2. \(\operatorname{graph}(R)\) と \(A\) のみ

3. \(\operatorname{graph}(R)\) と \(B\) のみ

4. \(\operatorname{graph}(R)\) と \(A\) と \(B\) の全て

性質:

1. \(R\) は全射

2. \(R\) は単射

3. \(R\) は全域

4. \(R\) は関数

次の式が定義する \(\mathbb{R}\) から \(\mathbb{R}\) への関数のそれぞれについて、「全単射である」「全射であるが単射ではない」「単射であるが全射でない」「全射でも単射でもない」のどれが成り立つか答えよ:

1. \(x \mapsto x + 2\)
2. \(x \mapsto 2x\)
3. \(x \mapsto x^{2}\)
4. \(x \mapsto x^{3}\)
5. \(x \mapsto \sin x\)
6. \(x \mapsto x \sin x\)
7. \(x \mapsto e^{x}\)

\(f\colon A \to B\) と \(g\colon B \to C\) を関数、\(h\) を \(f\) と \(g\) の合成とする。このとき任意の \(a \in A\) で \(h(a) ::= g(f(a))\) である。

1. \(f\) と \(g\) が全射なら \(h\) も全射だと示せ。

2. \(f\) と \(g\) が全単射なら \(h\) も全単射だと示せ。

3. \(f\) が全単射なら \(f^{-1}\) も全単射だと示せ。

何らかの集合 \(A\) 上の関係 \(R\) であって「全域かつ単射の関数であるが、全単射ではない」を満たすものを示せ。

1. \(A \mathrel{\text{\small surj}} B\) かつ \(B \mathrel{\text{\small surj}} C\) なら \(A \mathrel{\text{\small surj}} C\) だと示せ。

2. \(A \mathrel{\text{\small surj}} B \ \ \longleftrightarrow \ \ B \mathrel{\text{\small inj}} A\) である理由を説明せよ。

3. \(\text{(a)}\) と \(\text{(b)}\) の結果から、\(A \mathrel{\text{\small inj}} B\) かつ \(B \mathrel{\text{\small inj}} C\) なら \(A \mathrel{\text{\small inj}} C\) だと結論付けよ。

4. 定義 4.5.2 によると、\(A \mathrel{\text{\small inj}} B \) は全域かつ単射な関係の存在を意味する。\(A \mathrel{\text{\small inj}} B\) が「\(A\) から \(B\) への全域かつ単射な関数が存在する」と同値な理由を説明せよ。

二項関係 \(R\colon A \to B\) に関する五個の基礎的な性質を示す:

1. \(R\) は全射 \(\ \ \longleftrightarrow \ \ \) 「内 \(\geq 1\)」

2. \(R\) は単射 \(\ \ \longleftrightarrow \ \ \) 「内 \(\leq 1\)」

3. \(R\) は関数 \(\ \ \longleftrightarrow \ \ \) 「外 \(\leq 1\)」

4. \(R\) は全域 \(\ \ \longleftrightarrow \ \ \) 「外 \(\geq 1\)」

5. \(R\) は空 \(\ \ \ \ \ \hspace{1pt} \longleftrightarrow \ \ \) 「外 \(= 0\)」

\(R\) に関する命題を次にいくつか示す。それぞれについて、その命題が成り立つとき \(R\) が持つ上記の性質を全て答えよ。例えば、最初の命題が成り立つとき \(R\) は全域かつ全射である。変数 \(a\), \(a_{1}\), \(\ldots\) は \(A\) の任意の要素を表し、変数 \(b\), \(b_{1}\), \(\ldots\) は \(B\) の任意の要素を表す。

1. \(\forall a\, \forall b.\ \,a \mathrel{R} b\)
2. \(\operatorname{\text{\footnotesize NOT}} (\forall a\, \forall b.\ \,a \mathrel{R} b)\)
3. \(\forall a\, \forall b.\ \,\operatorname{\text{\footnotesize NOT}} (a \mathrel{R} b)\)
4. \(\forall a\, \exists b.\ \,a \mathrel{R} b\)
5. \(\forall b\, \exists a.\ \,a \mathrel{R} b\)

6. \(R\) は全単射である。

7. \(\forall a\, \exists b_{1}.\ \,a \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ (\forall b.\ \,a \mathrel{R} b \ \operatorname{\text{\footnotesize IMPLIES}}\ b = b_{1} )\)
8. \(\forall a, b.\ \,a \mathrel{R} b \ \operatorname{\text{\footnotesize OR}}\ a \neq b\)
9. \(\forall b_{1}, b_{2}, a.\ \,(a \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ a \mathrel{R} b_{2}) \ \operatorname{\text{\footnotesize IMPLIES}}\ b_{1} = b_{2}\)
10. \(\forall a_{1}, a_{2}, b.\ \,(a_{1} \mathrel{R} b \ \operatorname{\text{\footnotesize AND}} \ a_{2} \mathrel{R} b) \ \operatorname{\text{\footnotesize IMPLIES}}\ a_{1} = a_{2}\)
11. \(\forall a_{1}, a_{2}, b_{1}, b_{2}.\ \, (a_{1} \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ a_{2} \mathrel{R} b_{2} \ \operatorname{\text{\footnotesize AND}} \ a_{1} \neq a_{2}) \ \operatorname{\text{\footnotesize IMPLIES}}\ b_{1} \neq b_{2} \)
12. \(\forall a_{1}, a_{2}, b_{1}, b_{2}.\ \, (a_{1} \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ a_{2} \mathrel{R} b_{2} \ \operatorname{\text{\footnotesize AND}} \ b_{1} \neq b_{2}) \ \operatorname{\text{\footnotesize IMPLIES}}\ a_{1} \neq a_{2} \)

\(R\colon A \to B\) を二項関係とする。次に示す命題はどれも、本文中に登場した「矢印」の本数に関する性質 (「全射である」など) を \(R\) が持つことを意味する。どのような性質か答え、その理由を説明せよ。\(\text{Id}_{A}\), \(\text{Id}_{B}\) はそれぞれ \(A\), \(B\) 上の恒等関数を意味する。

1. \(R \circ R^{-1} \subseteq \text{Id}_{B}\)
2. \(R^{-1} \circ R \subseteq \text{Id}_{A}\)
3. \(R^{-1} \circ R \supseteq \text{Id}_{A}\)
4. \(R \circ R^{-1} \supseteq \text{Id}_{B}\)

[訳注: \(\circ\) は二項関係の合成 (問題 4.29) を表す。二項関係の記号はそのグラフを表すと解釈する。]

\(f\colon A \to B\) と \(g\colon B \to C\) を関数とする。

1. 合成 \(g \circ f\) が全単射のとき、\(f\) は全域かつ単射で \(g\) は全射だと示せ。

2. 全域かつ単射の \(f\) と全単射の \(g\) であって \(g \circ f\) が全単射でないものが存在すると示せ。

\(A\), \(B\), \(C\) を非空集合、\(f\colon B \to C\) と \(g\colon A \to B\) を関数とする。\(h\colon A \to C\) を合成 \(f \circ g\) とする。つまり \(h\) は始域 \(A\) と終域 \(C\) を持ち、任意の \(x \in A\) で \(h(x) ::= f(g(x))\) が成り立つ。

1. \(h\) が全射で \(f\) が全域かつ単射なら、\(g\) は全射だと示せ。

   ヒント: 背理法を使う。

2. \(h\) が単射で \(f\) が全域だと仮定する。このとき \(g\) が単射だと示せ。さらに、\(f\) が全域でないとき \(g\) は単射になるとは限らないと示せ。

\(A\), \(B\), \(C\) を非空集合、\(f\colon B \to C\) と \(g\colon A \to B\) を関数とする。\(h\colon A \to C\) を合成 \(f \circ g\) とする。つまり任意の \(x \in A\) で \(h(x) ::= f(g(x))\) が成り立つ。次の命題が正しいなら証明し、正しくないなら反例を示せ:

1. \(h\) が全射なら、\(f\) は全射である。

2. \(h\) が全射なら、\(g\) は全射である。

3. \(h\) が単射なら、\(f\) は単射である。

4. \(h\) が単射で \(f\) が全域なら、\(g\) は単射である。

1. \(R\colon D \to D\) を集合 \(D\) 上の二項関係、変数 \(x\), \(y\) を \(D\) の任意の要素とする。「\(R\) が単射」を意味する命題を次から全て選べ。\(R(x) ::= \left\{ y \; | \; x \mathrel{R} y \right\}\) であり、\(R\) が関数あるいは全域関数とは限らない点に注意せよ。

   1. \(R(x) \cap R(y) = \varnothing\)
   2. \(R(x) = R(y) \ \ \longrightarrow \ \ x = y\)
   3. \(R(x) \cap R(y) = \varnothing \ \ \longrightarrow \ \ x \neq y\)
   4. \(x \neq y \ \ \longrightarrow \ \ R(x) \neq R(y)\)
   5. \(R(x) \cap R(y) \neq \varnothing \ \ \longrightarrow \ \ x \neq y\)
   6. \(R(x) \cap R(y) \neq \varnothing \ \ \longrightarrow \ \ x = y\)
   7. \(R^{-1}(R(x)) = \left\{x\right\}\)
   8. \(R^{-1}(R(x)) \subseteq \left\{x\right\}\)
   9. \(R^{-1}(R(x)) \supseteq \left\{x\right\}\)
   10. \(R(R^{-1}(x)) \subseteq \left\{x\right\}\)
   11. \(R(R^{-1}(x)) \supseteq \left\{x\right\}\)
   12. \(x \neq y \ \ \longrightarrow \ \ R(x) \cap R(y) = \varnothing\)

2. \(S\) から実数区間 \([0,1]\) への全域かつ単射な関係が存在しないような集合 \(S\) の例を示せ。

   [訳注: Cantor の定理 (定理 8.1.12) が必要になる。]

集合や関係に関する数学用語はプログラミングという実用的な世界から非常に遠いところにあると考えているかもしれない。しかし実際には、MySQL といったソフトウェアパッケージが実装するリレーショナルデータベース (relational database) と呼ばれるコンポーネントは集合や関係と密接に関連する。この問題では、集合と関係に関する演算子を使って大規模なデータセットを操作する方法を考える。MySQL などのシステムは数学の言葉に非常に良く似た高レベル命令を標準的なコンピューターハードウェアで効率良く実行できるので、プログラマーは高レベルな設計に集中しやすくなる。

基本的な機能を持ったウェブ検索エンジンを考えよう。このエンジンはウェブページに関する情報を格納し、クエリ (query, 問い合わせ) を処理することでユーザーが指定した条件を満たすページを見つける。重要な情報を高いレベルで形式化した例を次に示す:

• 集合 \(P\): 検索エンジンが知っているページ全体の集合

• \(P\) 上の二項関係 \(L\):

  \[ p_{1} \mathrel{L} p_{2} \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{ページ \(p_{1}\) がページ \(p_{2}\) へのリンクを持つ} \]

• 集合 \(E\): エンドーサー (endoser, 質の高いページを推薦した人物) 全体の集合

• \(E\) から \(P\) への二項関係 \(R\):

  \[ e \mathrel{R} p \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{エンドーサー \(e\) がページ \(p\) を推薦 (recommend) する} \]

• 集合 \(W\): ページに現れる単語 (word) 全体の集合

• \(P\) から \(W\) への二項関係 \(M\):

  \[ p \mathrel{M} w \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \text{ページ \(p\) に単語 \(w\) が現れる} \]

データセットに対するクエリを意味する数学的でない文章を次に示す。これらの文章を集合と関係に関する標準的な演算子を使った単一の式に変換するのがあなたの仕事である。解答の式は任意のデータセットに対して正しい答えを返す必要がある。解答で利用できるのは上で定義した集合と二項関係を表す記号、\(E\), \(W\) の固定された要素を表す記号、そして次の記号だけとする:

• 集合の和集合 \(\cup\)

• 集合の共通部分 \(\cap\)

• 二項関係の像 ── 例えば集合 \(A\) に対する \(R(A)\) や、特定の要素 \(a\) に対する \(R(a)\)

• 二項関係の逆

• そしてもう一つ: 二項関係の合成 ── 関数の合成の一般化であり、次のように定義される:

  \[ a \mathrel{(R\, \circ\, S)} c \ \ \overset{\text{def}}{\longleftrightarrow}\ \ \exists b \in B.\ (a \mathrel{S} b) \ \operatorname{\text{\footnotesize AND}} \ (b \mathrel{R} c) \]

  言い換えれば、\(a\) と \(c\) が \(R \circ S\) の関係を持つのは、\(a\) をスタートして \(S\) の矢印と \(R\) の矢印をたどって \(c\) に到達できるとき、かつそのときに限る³。

クエリを式に変換する例を一つ示す:

• クエリ: 単語 logic を含むページ全体の集合

• 式: \(M^{-1}(\text{``logic''})\)

次のクエリを式に変換せよ:

1. 単語 logic を含み、単語 predicate を含まないページ全体の集合

2. 単語 set を含み、Meyer によって推薦されたページ全体の集合

3. 単語 algebra を含むページを推薦したエンドーサー全体の集合

4. エンドーサー \(e\) が単語 \(w\) の含まれるページを推薦するとき、かつそのときに限って \(e\) を \(w\) を関係付ける二項関係

5. 内向きリンクもしくは外向きリンクを少なくとも一つ持つページ全体の集合

6. ページ \(p\) に対するリンクを持つページに単語 \(w\) が含まれるとき、かつそのときに限って \(w\) と \(p\) を関係付ける二項関係

7. エンドーサー \(e\) が推薦するページに対するリンクを持つページに単語 \(w\) が含まれるとき、かつそのときに限って \(w\) と \(e\) を関係付ける二項関係

8. ページ \(p_{1}\) からページ \(p_{2}\) までリンクをちょうど \(3\) 回たどることで到達できるとき、かつそのときに限って \(p_{1}\) と \(p_{2}\) を関係付ける二項関係

\(L_{n}\) を \(0\) 以上 \(9\) 以下の整数からなる長さ \(n\) の列であって和が \(9n/2\) より小さいもの全体の集合、\(G_{n}\) を \(0\) 以上 \(9\) 以下の整数からなる長さ \(n\) の列であって和が \(9n/2\) より大きいもの全体の集合とする。例えば \(\texttt{2134} \in L_{4}\) や \(\texttt{9786} \in G_{4}\) が成り立つ。

\(L_{n}\) から \(G_{n}\) への全単射を説明せよ。解答が全域・単射・全域・関数であることを注意深く示すこと。

\(A\) を \(5\) 個の集合 \(\left\{ a \right\}\), \(\left\{ a, b \right\}\), \(\left\{ b, d\right\}\), \(\left\{ a, e \right\}\), \(\left\{ e, f \right\}\) だけを含む集合、\(B\) を \(3\) 個の集合 \(\left\{ a, b\right\}\), \(\left\{ b, c, d \right\}\), \(\left\{ e, f\right\}\) だけを含む集合とする。「部分集合である」を意味する \(A\) から \(B\) への二項関係 \(R\) を次の規則で定義する:

1. 次の図に矢印を書き加え、二項関係 \(R\) を表す図を完成させよ。

   \[ \def\arraystretch{1.2}\begin{array}{ccc} A & \qquad \text{矢印} \qquad & B \\ \hline && \\ \left\{ a \right\} & & \\ & & \left\{ a, b \right\} \\ \left\{ b, c \right\} & & \\ & & \left\{ b, c, d \right\} \\ \left\{ b, d \right\} & & \\ & & \left\{ e, f \right\} \\ \left\{ a, e \right\} & & \\ & & \\ \left\{ e, f \right\} & & \end{array} \]

2. 二項関係 \(R\) が満たす特徴に丸を付けよ:

   \[ \text{関数} \qquad \text{全域} \qquad \text{単射} \qquad \text{全射} \qquad \text{全単射} \]

3. 二項関係 \(R^{-1}\) が満たす特徴に丸を付けよ:

   \[ \text{関数} \qquad \text{全域} \qquad \text{単射} \qquad \text{全射} \qquad \text{全単射} \]

1. 二項関係 \(R\colon A \to B\) に関する五個の命題を次に示す。その次にある述語論理式の中には、五個の命題のいずれかと同値なものが存在する。それぞれの命題と同値な述語論理式の番号を答えよ。変数 \(a\), \(a_{1}\), \(\ldots\) は始域 \(A\) の要素を表し、変数 \(b\), \(b_{1}\), \(\ldots\) は終域 \(B\) の要素を表すとする。それぞれの命題に対応する述語論理式が一つとは限らない。

   1. \(R\) は全射である。

   2. \(R\) は単射である。

   3. \(R\) は関数である。

   4. \(R\) は全域である。

   5. \(R\) は恒等関係である。

   1. \(\forall b\, \exists a.\ a \mathrel{R} b\)
   2. \(\forall a\, \exists b.\ a \mathrel{R} b\)
   3. \(\forall a.\ a \mathrel{R} a\)
   4. \(\forall a, b.\ a \mathrel{R} b \ \operatorname{\text{\footnotesize IFF}}\ a = b\)
   5. \(\forall a, b.\ a \mathrel{R} b \ \operatorname{\text{\footnotesize OR}}\ a \neq b\)
   6. \(\forall b_{1}, b_{2}, a.\ (a \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ a \mathrel{R} b_{2}) \ \operatorname{\text{\footnotesize IMPLIES}}\ b_{1} = b_{2}\)
   7. \(\forall a_{1}, a_{2}, b.\ (a_{1} \mathrel{R} b \ \operatorname{\text{\footnotesize AND}} \ a_{2} \mathrel{R} b) \ \operatorname{\text{\footnotesize IMPLIES}}\ a_{1} = a_{2}\)
   8. \(\forall a_{1}, a_{2}, b_{1}, b_{2}.\ (a_{1} \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ a_{2} \mathrel{R} b_{2} \ \operatorname{\text{\footnotesize AND}} \ a_{1} \neq a_{2}) \ \operatorname{\text{\footnotesize IMPLIES}}\ b_{1} \neq b_{2}\)
   9. \(\forall a_{1}, a_{2}, b_{1}, b_{2}.\ (a_{1} \mathrel{R} b_{1} \ \operatorname{\text{\footnotesize AND}} \ a_{2} \mathrel{R} b_{2} \ \operatorname{\text{\footnotesize AND}} \ b_{1} \neq b_{2}) \ \operatorname{\text{\footnotesize IMPLIES}}\ a_{1} \neq a_{2}\)

2. 全射・単射・全域・関数のいずれか三つの性質を満たし、かつ全単射でない二項関係 \(R\) の例を示せ。どの三つの性質を満たすのか解答に記すこと。

\(D\) を非空集合、\(f\colon D \to D\) を全域関数とする。次に示す命題において、\(x\), \(y\) は \(D\) の要素、\(g\) は \(D\) から \(D\) への関数とする。「\(f\) は単射である」と同値な命題を全て答えよ。

1. \(\forall x, y.\ x = y \ \operatorname{\text{\footnotesize OR}}\ f(x) \neq f(y)\)
2. \(\forall x, y.\ x = y \ \operatorname{\text{\footnotesize IMPLIES}}\ f(x) = f(y)\)
3. \(\forall x, y.\ x \neq y \ \operatorname{\text{\footnotesize IMPLIES}}\ f(x) \neq f(y)\)
4. \(\forall x, y.\ f(x) = f(y) \ \operatorname{\text{\footnotesize IMPLIES}}\ x = y\)
5. \(\operatorname{\text{\footnotesize NOT}} (\exists x, y.\ x \neq y \ \operatorname{\text{\footnotesize AND}} \ f(x) = f(y))\)
6. \(\operatorname{\text{\footnotesize NOT}} (\exists y\, \forall x.\ f(x) \neq y)\)
7. \(\exists g\, \forall x.\ g(f(x)) = x\)
8. \(\exists g\, \forall x.\ f(g(x)) = x\)

関係 \(R\colon A \to B\) が全域かつ単射 (「外 \(\geq 1\)」かつ「内 \(\leq 1\)」) なら次の関係が成り立つと示せ:

ここで \(\text{Id}_{A}\) は \(A\) 上の恒等関数を表す。[「矢印」を使った簡単な議論で構わない。]

\(R\colon A \to B\) を二項関係とする。

1. 「\(R\) が関数」と「\(R \circ R^{-1} \subseteq \text{Id}_{B}\)」が同値だと示せ。

次の命題と同値な論理式を示せ。解答は \(\text{(a)}\) で登場した論理式と同様に \(R^{-1} \circ R\), \(R \circ R^{-1}\), \(\text{Id}_{A}\), \(\text{Id}_{B}\) からなる必要がある。解答が命題と同値であることの証明は必要ない。

2. \(R\) は全域である。

3. \(R\) は全射である。

4. \(R\) は単射である。

\(R\colon A \to B\) と \(S\colon B \to C\) を二項関係とする。\(S \circ R\) が全単射で \(|A| = 2\) だと仮定する。

この条件を満たす \(R\), \(S\) であって、\(R\) と \(S\) がどちらも関数でない例を示せ。その \(R\) と \(S\) が満たす性質は全域・単射・全射・関数のどれかを答えよ。

ヒント: \(|B| = 4\) とする。

\(\left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega}\) は \(\texttt{1}\), \(\texttt{2}\), \(\texttt{3}\) だけからなる無限列全体の集合を意味する。同様に、\(\left\{ \texttt{4}, \texttt{5} \right\}^{\omega}\) は \(\texttt{4}\) と \(\texttt{5}\) だけからなる無限列全体の集合を意味する。例えば、次の関係が成り立つ:

1. 単射関数 \(f\colon \left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega} \to \left\{ \texttt{4}, \texttt{5} \right\}^{\omega}\) の例を示せ。

2. 全単射 \(g\colon (\left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega} \times \left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega}) \to \left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega} \) の例を示せ。

3. \(\left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega} \times \left\{ \texttt{1}, \texttt{2}, \texttt{3} \right\}^{\omega}\) と \(\left\{ \texttt{4}, \texttt{5} \right\}^{\omega}\) の間に全単射が存在する理由を説明せよ。全単射を明示的に定義する必要はない。

\(A\) を有限集合、\(f\colon A \to B\) を全域関数とする。次の命題に含まれる \(\star\) を \(\leq\), \(=\), \(\geq\) のいずれかに置き換えることを考える。置き換えた後の命題を可能な限り強い真の命題にしたいとき、どの記号に置き換えるべきかそれぞれ答えよ:

1. \(|f(A)| \star |B|\)

2. \(f\) が全射のとき \(|A| \star |B|\)

3. \(f\) が全射のとき \(|f(A)| \star |B|\)

4. \(f\) が単射のとき \(|f(A)| \star |A|\)

5. \(f\) が全単射のとき \(|A| \star |B|\)

\(A = \left\{ a_{0}, a_{1}, \ldots, a_{n-1} \right\}\) を \(n\) 要素集合、\(B = \left\{ b_{0}, b_{1}, \ldots, b_{m-1} \right\}\) を \(m\) 要素集合とする。\(A \times B\) から \(0\) 以上 \(mn - 1\) 以下の非負整数全体の集合への単純な全単射の存在を示すことで、\(|A \times B| = mn\) を証明せよ。

\(R\colon A \to B\) を二項関係とする。矢印の個数を数えるアプローチを使って、次の命題 (補題 4.5.3 の \(\text{1.}\) の一般化) を証明せよ: