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

難易度 2大学院の講義の演習問題レベル大学院数学数理論理学・集合論

2 項関係記号 $R$ だけからなる一階の言語（等号を含む）を考える。台集合を $A = {1, 2, 3, 4}$ に固定し、 $R$ の解釈 $R^{M} \subseteq A \times A$ を 1 つ定めるごとに構造 $M = (A, R^{M})$ が 1 つ定まるものとする（同型な構造でも $R^{M}$ が異なれば別の構造として数える）。次の文 $φ$ を考える。
$φ : \forall x \neg R (x, x) \land \forall x \forall y (R (x, y) \to R (y, x)) \land \forall x \exists y R (x, y)$
$M ⊨ φ$ となる構造 $M$ （すなわち $R^{M}$ ）の個数を求めよ。

この問題で使うもの

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

ヒント

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

ヒント 1

$φ$ の 3 つの条件が $R$ についてどんな性質を表すかを読み取り、 $R$ をグラフとみなせないか考えよう。

ヒント 2

非反射的で対称的な関係は単純無向グラフと対応する。3 つ目の条件は「孤立点がない」ことになる。孤立点のないグラフは包除原理で数えられる。

ヒント 3

4 頂点上の単純グラフは $2^{6} = 64$ 個。指定した $k$ 個の頂点が孤立するグラフは $2^{(2 4 - k)}$ 個あるので、 $\sum_{k = 0}^{4} (- 1)^{k} (k 4) 2^{(2 4 - k)}$ を計算すればよい。

答えと解説

答えを見る

41

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

解説を読む

文の意味を読み替える. $φ$ の 3 つの連言肢はそれぞれ
- $\forall x \neg R (x, x)$ ： $R$ は非反射的（ループがない）
- $\forall x \forall y (R (x, y) \to R (y, x))$ ： $R$ は対称的
- $\forall x \exists y R (x, y)$ ：どの元 $x$ にも $R (x, y)$ となる $y$ がある

を意味する。非反射的かつ対称的な関係 $R \subseteq A \times A$ は、頂点集合 $A$ 上の単純無向グラフ（辺 ${a, b}$ があることと $R (a, b) \land R (b, a)$ が同値）と 1 対 1 に対応する。また非反射性から 3 つ目の条件の $y$ は $x$ と異なるので、3 つ目の条件は「孤立点（次数 0 の頂点）がない」ことと同値である。

よって求める個数は、ラベル付き 4 頂点 ${1, 2, 3, 4}$ 上の孤立点のない単純グラフの個数である。

包除原理で数える. 可能な辺は $(2 4) = 6$ 本なので、単純グラフは全部で $2^{6} = 64$ 個。頂点の部分集合 $S$ について「 $S$ の頂点がすべて孤立点」となるグラフは、残り $4 - ∣ S ∣$ 頂点の間の辺だけを自由に選べるので $2^{(2 4 - ∣ S ∣)}$ 個ある。包除原理より
$k = 0 \sum 4 (- 1)^{k} (k 4) 2^{(2 4 - k)} = (0 4) 2^{6} - (1 4) 2^{3} + (2 4) 2^{1} - (3 4) 2^{0} + (4 4) 2^{0}$
$= 64 - 32 + 12 - 4 + 1 = 41.$
（ $(2 1) = (2 0) = 0$ なので $k = 3, 4$ の項は $2^{0} = 1$ である。）

検算（辺の本数で分類）. 孤立点がないには辺が 2 本以上必要。
- 2 本：4 頂点すべてを覆うには 2 辺が互いに素（完全マッチング）で $3$ 個。
- 3 本： $(3 6) = 20$ 個のうち、ある 1 頂点が孤立するのは残り 3 頂点の三角形の場合で $4$ 個。よって $16$ 個。
- 4 本： $(4 6) = 15$ 個。孤立点があると辺は高々 3 本なので全部可。
- 5 本： $6$ 個、6 本： $1$ 個。

合計 $3 + 16 + 15 + 6 + 1 = 41$ となり一致する。

したがって答えは $41$ である。

別解

条件は、 $R$ が非反射的（ $\neg R (x, x)$ ）かつ対称で、すべての $x$ に対し $R (x, y)$ となる $y$ が存在する、というもの。したがって $R^{M}$ は頂点集合 $A = {1, 2, 3, 4}$ 上のラベル付き単純無向グラフ（辺は 2 元部分集合）で、孤立点をもたないものと 1 対 1 に対応する（非反射的なのでループなし、対称なので無向辺）。

孤立点のないグラフの個数を包除原理で数える。頂点 $i$ が孤立点である事象を $E_{i}$ とする。 $k$ 個の指定した頂点が孤立点であるとき、残り $4 - k$ 頂点の間の辺は自由なので $2^{(2 4 - k)}$ 通り。よって
$k = 0 \sum 4 (- 1)^{k} (k 4) 2^{(2 4 - k)} = 2^{6} - 4 \cdot 2^{3} + 6 \cdot 2^{1} - 4 \cdot 2^{0} + 1 \cdot 2^{0} = 64 - 32 + 12 - 4 + 1 = 41.$

検算として直接数える。辺の数で分類する。辺 2 本: 4 頂点すべてを覆うには互いに素な 2 辺で、完全マッチングの 3 通り。辺 3 本: $(3 6) = 20$ 通りのうち孤立点をもつのは三角形（4 頂点のうち 1 つが孤立）の 4 通りだけなので 16 通り。辺 4 本: $(4 6) = 15$ 通りで、4 本なら孤立点が生じるには残り 3 頂点に 4 辺必要だが最大 3 辺なので孤立点なし、15 通り。辺 5 本: 6 通り。辺 6 本: 1 通り。辺 0,1 本は不可。合計 $3 + 16 + 15 + 6 + 1 = 41$ 。一致する。

この問題の確認

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

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

確認の方法について

間違いを報告する

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