数理論理学・集合論の問題

難易度 3大学院入試の専門科目の標準レベル大学院数学数理論理学・集合論

2 項関係記号 $R$ だけをもつ等号付きの一階の言語を考える。台集合を $A = {1, 2, 3, 4, 5}$ に固定する。部分集合 $S \subseteq A \times A$ を 1 つ選ぶごとに、 $R$ を $S$ と解釈し、等号を $A$ 上の通常の等しさと解釈した構造 $M_{S} = (A, S)$ が定まる。次の 4 つの文を考える。
$σ_{1} : \forall x \forall y (\neg (x = y) \to (R (x, y) \lor R (y, x)))$
$σ_{2} : \forall x \forall y (R (x, y) \to \neg R (y, x))$
$σ_{3} : \forall x \exists y R (x, y)$
$σ_{4} : \forall x \exists y R (y, x)$
$M_{S} ⊨ σ_{1} \land σ_{2} \land σ_{3} \land σ_{4}$ となる部分集合 $S \subseteq A \times A$ は何個あるか。ただし、同型な構造であっても、 $S$ が部分集合として異なれば別のものとして数える。

この問題で使うもの

有限の台集合上のモデルの個数（説明と入口の問題）
一階述語論理の構造と文の真偽（説明と入口の問題）
一般の包除原理（説明と入口の問題）

この問題を解けるようになるまで（12 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

まず $σ_{1} \land σ_{2}$ を満たす $S$ がどんな関係かを考える。 $σ_{2}$ で $x = y$ とおくと何がわかるか。

ヒント 2

$σ_{1} \land σ_{2}$ を満たす $S$ は $A$ 上のトーナメント（ $2^{10}$ 個）と対応する。 $σ_{3}$ は「出次数 $0$ の頂点がない」、 $σ_{4}$ は「入次数 $0$ の頂点がない」ことを表すので、包除原理で数える。

ヒント 3

トーナメントでは出次数 $0$ の頂点は高々 1 個。頂点 $v$ の出次数が $0$ のものは $2^{6}$ 個、出次数 $0$ の頂点 $v$ と入次数 $0$ の頂点 $u$ を両方もつものは $2^{3}$ 個ある。

答えと解説

答えを見る

544

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

以下、 $S$ に $(x, y)$ が属することを有向辺 $x \to y$ とみて、 $S$ を $A$ 上の有向グラフと考える。

$σ_{1} \land σ_{2}$ の言い換え

$σ_{2}$ で $x = y$ とおくと $R (x, x) \to \neg R (x, x)$ 、つまり $\neg R (x, x)$ がすべての $x$ で成り立つ。よって $S$ はループ $(x, x)$ を含まない。異なる $x, y$ については、 $σ_{1}$ より $(x, y)$ と $(y, x)$ の少なくとも一方が $S$ に属し、 $σ_{2}$ より両方は属さない。したがって $σ_{1} \land σ_{2}$ を満たす $S$ は、 $A$ 上のトーナメント（異なる 2 頂点の各組に、どちらか一方向の有向辺をちょうど 1 本引いた有向グラフ）と 1 対 1 に対応する。頂点の組は $(2 5) = 10$ 組で、各組で向きを 2 通り選べるので、その個数は $2^{10} = 1024$ である。

$σ_{3}, σ_{4}$ の意味

$σ_{3}$ は「すべての頂点から出る辺がある」、すなわち出次数 $0$ の頂点（シンク）がないことを表す。 $σ_{4}$ は「すべての頂点に入る辺がある」、すなわち入次数 $0$ の頂点（ソース）がないことを表す。

包除原理

トーナメントのうち、シンクをもつものの集合を $P$ 、ソースをもつものの集合を $Q$ とする。求める個数は $1024 - ∣ P ∣ - ∣ Q ∣ + ∣ P \cap Q ∣$ である。

トーナメントではシンクは高々 1 個である（異なるシンク $u, v$ があると、 $u, v$ の間の辺がどちら向きでも一方の出次数が正になり矛盾）。同様にソースも高々 1 個である。

頂点 $v$ がシンクであるトーナメント： $v$ に関わる 4 本の辺はすべて $v$ に入る向きに決まり、残りの $(2 4) = 6$ 本の向きは自由なので $2^{6} = 64$ 個。シンクは高々 1 個なので、 $v$ ごとの集合は互いに交わらず、 $∣ P ∣ = 5 \cdot 64 = 320$ 。
同様に $∣ Q ∣ = 320$ 。
シンク $v$ とソース $u$ を両方もつもの： $v$ の出次数は $0$ 、 $u$ の出次数は $4$ なので $u \neq = v$ 。 $u, v$ に関わる辺は $4 + 4 - 1 = 7$ 本で、その向きはすべて決まる（ $u, v$ の間の辺は $u \to v$ ）。残り $10 - 7 = 3$ 本の向きは自由なので $2^{3} = 8$ 個。順序対 $(u, v)$ の選び方は $5 \cdot 4 = 20$ 通りで、これらも互いに交わらないので $∣ P \cap Q ∣ = 20 \cdot 8 = 160$ 。

よって、シンクもソースももたないトーナメントの個数は
$1024 - 320 - 320 + 160 = 544.$

（確認：頂点が 4 個のときに同じ計算をすると $2^{6} - 4 \cdot 2^{3} - 4 \cdot 2^{3} + 12 \cdot 2^{1} = 24$ となる。4 頂点でシンクもソースもないトーナメントは得点列が $(1, 1, 2, 2)$ のものに限られ、その個数 $24$ と一致する。）

以上より、求める個数は $544$ である。

別解

$σ_{1}$ は相異なる $x, y$ について $R (x, y)$ か $R (y, x)$ の少なくとも一方が成り立つこと。 $σ_{2}$ で $x = y$ とすると $R (x, x) \to \neg R (x, x)$ なので $R (x, x)$ は偽（反射的な辺なし）、また $x \neq = y$ では両方向は同時に成り立たない。よって $S$ は $A$ 上の（ラベル付き）トーナメントと同じ。個数は $2^{(2 5)} = 2^{10} = 1024$ 。

$σ_{3}$ : どの点も出次数 $\geq 1$ （出次数 0 の点＝沈点がない）。 $σ_{4}$ : どの点も入次数 $\geq 1$ （入次数 0 の点＝源点がない）。

包除原理:
- 沈点をもつもの: 沈点は高々 1 つで、その点の選び方 5 通り、残り 4 点のトーナメント $2^{6} = 64$ 通り → $5 \cdot 64 = 320$ 。
- 源点をもつもの: 同様に $320$ 。
- 沈点と源点の両方をもつもの: 沈点 5 通り、源点 4 通り、残り 3 点のトーナメント $2^{3} = 8$ 通り → $5 \cdot 4 \cdot 8 = 160$ 。

求める個数 $= 1024 - 320 - 320 + 160 = 544$ 。

検算: 3 点の場合の同じ方法で $2^{3} - 3 \cdot 2 - 3 \cdot 2 + 3 \cdot 2 \cdot 1 = 8 - 6 - 6 + 6 = 2$ （巡回的な 2 つ）となり、正しい。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる