一階述語論理の構造と文の真偽

2 項関係記号 $D$ だけからなる言語の構造 $\mathcal{M}$ を、台集合 $M=\{1,2,3,4,5,6,7,8,9,10\}$ とし、$D$ を「割り切る」と解釈したものとする。すなわち $a,b\in M$ に対して $\mathcal{M}\models D(a,b)$ となるのは、$a$ が $b$ を割り切る（ある整数 $k$ で $b=ka$ となる）ときであり、そのときに限る。

自由変数 $x$ をもつ論理式
$$\phi (x):\forall y(D(x,y)\to y=x)$$
について、$\mathcal{M}\models \phi (a)$ となる $a\in M$ の集合を求めよ。ただし $=$ は台集合の元の等しさと解釈する。

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

1 項関数記号 $f$ と 1 項関係記号 $P$ からなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定し、関数 $f^{\mathcal{M}}:A\to A$ と部分集合 $P^{\mathcal{M}}\subseteq A$ の組を 1 つ定めるごとに構造 $\mathcal{M}=(A,f^{\mathcal{M}},P^{\mathcal{M}})$ が 1 つ定まるとする。次の 2 つの文
$${\phi }_1:\forall x(f(f(x))=x),{\phi }_2:\forall x(P(x)\to \neg P(f(x)))$$
をともにみたす構造 $\mathcal{M}$（すなわち $\mathcal{M}\models {\phi }_1\wedge {\phi }_2$ となる組 $(f^{\mathcal{M}},P^{\mathcal{M}})$）の個数を求めよ。ただし、同型な構造であっても $(f^{\mathcal{M}},P^{\mathcal{M}})$ が異なれば別のものとして数える。

2 項関係記号 $E$ だけからなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定し、$E$ の解釈 $E^{\mathcal{M}}\subseteq A\times A$ を 1 つ定めるごとに構造 $\mathcal{M}=(A,E^{\mathcal{M}})$ が 1 つ定まるとする。次の 3 つの文の連言を $\sigma ={\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3$ とおく。
$${\sigma }_1:\forall x\neg E(x,x)$$
$${\sigma }_2:\forall x\forall y(E(x,y)\to E(y,x))$$
$${\sigma }_3:\forall x\exists y\exists z(y\ne z\wedge E(x,y)\wedge E(x,z)\wedge \forall w(E(x,w)\to (w=y\vee w=z)\left)\right)$$
$\mathcal{M}\models \sigma$ となる $E^{\mathcal{M}}\subseteq A\times A$ の個数を求めよ（同型な構造も、$E^{\mathcal{M}}$ が集合として異なれば別に数える）。

2 項関係記号 $R$ だけからなる一階の言語（等号を含む）を考える。台集合 $A=\{1,2,\dots ,30\}$ 上の構造 $\mathcal{M}=(A,R^{\mathcal{M}})$ を $$R^{\mathcal{M}}=\{(a,b)\in A\times A:a\text{が}b\text{を割り切る}\}$$ で定める。$\mathcal{M}$ の自己同型、すなわち全単射 $\sigma :A\to A$ で、すべての $a,b\in A$ について $(a,b)\in R^{\mathcal{M}}⟺(\sigma (a),\sigma (b))\in R^{\mathcal{M}}$ を満たすものの個数を求めよ。

2 項関数記号 $\cdot$ だけからなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4\}$ に固定する。写像 ${\cdot }^{\mathcal{M}}:A\times A\to A$ を 1 つ定めるごとに構造 $\mathcal{M}=(A,{\cdot }^{\mathcal{M}})$ が 1 つ定まる。全部で $4^{16}$ 個の構造がある。等号は $A$ 上の相等として解釈する。次の 4 つの文を考える。
$${\sigma }_1:\forall x(x\cdot x=x),{\sigma }_2:\forall x\forall y(x\cdot y=y\cdot x),$$
$${\sigma }_3:\forall x\forall y\forall z((x\cdot y)\cdot z=x\cdot (y\cdot z)),{\sigma }_4:\neg \exists e\forall y(e\cdot y=y).$$
これらの構造のうち、${\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3\wedge {\sigma }_4$ を満たすものの個数を求めよ。ここで、同型な構造でも ${\cdot }^{\mathcal{M}}$ が異なれば別のものとして数える。

1 項関数記号 $f$ と 1 項関係記号 $P$ からなる等号付きの一階の言語を考える。台集合を $A=\{1,2,3,4,5,6\}$ に固定する。写像 $g:A\to A$ と部分集合 $S\subseteq A$ を 1 つずつ選ぶごとに、$f$ を $g$、$P$ を $S$ と解釈し、等号は $A$ 上の本当の等号と解釈して、構造 $\mathcal{M}=(A,g,S)$ が 1 つ定まる。

次の文を $\phi$ とする。
$$\phi :\forall x(f(f(x))=x)\wedge \forall x(f(x)=x\to P(x))\wedge \forall x(P(x)\wedge P(f(x))\to f(x)=x)$$

組 $(g,S)$ のうち、$\mathcal{M}=(A,g,S)$ が $\phi$ のモデルとなる（$\mathcal{M}\models \phi$ となる）ものの個数を求めよ。ただし、同型な構造でも $(g,S)$ が異なれば別のものとして数える。

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

2 項関係記号 $R$ だけからなる一階の言語（等号を含む）を考える。台集合 $D=\{1,2,\dots ,100\}$ 上の構造 $\mathcal{D}=(D,R^{\mathcal{D}})$ を、$a,b\in D$ に対して
$$R^{\mathcal{D}}(a,b)⟺a\text{ は }b\text{ を割り切る}$$
で定める。$\mathcal{D}$ の自己同型とは、全単射 $\sigma :D\to D$ であって、すべての $a,b\in D$ について $R^{\mathcal{D}}(a,b)⟺R^{\mathcal{D}}(\sigma (a),\sigma (b))$ を満たすもののことである。$\mathcal{D}$ の自己同型の個数（自己同型群 $\mathrm{Aut}(\mathcal{D})$ の位数）を求めよ。

$L=\{f\}$ を 1 変数関数記号 $f$ だけからなる一階の言語とし（等号は論理記号として常に真の等号と解釈する）、$L$ の文
$$\sigma :\forall x(f(f(f(x)))=f(x))$$
を考える。正の整数 $n$ に対して $[n]=\{1,2,\dots ,n\}$ とおき、$[n]$ を台集合とする $L$ 構造（$f$ の解釈 $f^{\mathcal{M}}:[n]\to [n]$ によって決まる。解釈が異なる構造は別のものとして数える）のうち、$\sigma$ のモデルであるものの個数を $a_n$ とする。

また、正の整数 $k$ に対し
$$I_k=\sum _{j=0}^{\lfloor k/2\rfloor }\frac{k!}{2^{j}j!(k-2j)!}$$
とおく。すべての正の整数 $n$ について
$$a_n=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)I_k{k}^{n-k}$$
が成り立つことを証明せよ。

$L$ を等号付きの一階の言語とする。$L$ は関係記号・関数記号・定数記号をいくつ含んでもよい（無限個でもよく、その濃度は任意とする）。$L$ 構造の台集合は空でないものとする。$L$ 構造 $\mathcal{A},\mathcal{B}$ が初等同値である（$\mathcal{A}\equiv \mathcal{B}$）とは、すべての $L$ 文 $\phi$ について $\mathcal{A}\models \phi ⟺\mathcal{B}\models \phi$ が成り立つことをいう。

$\mathcal{A}$ の台集合が有限集合であり、$\mathcal{A}\equiv \mathcal{B}$ であるとき、$\mathcal{A}$ と $\mathcal{B}$ は同型であることを証明せよ。

ただし、同型写像とは、台集合の間の全単射 $\sigma :A\to B$ で、各関係記号 $R$（$k$ 項）について $R^{\mathcal{A}}(a_1,\dots ,a_k)⟺R^{\mathcal{B}}(\sigma a_1,\dots ,\sigma a_k)$、各関数記号 $f$（$k$ 項）について $\sigma (f^{\mathcal{A}}(a_1,\dots ,a_k))=f^{\mathcal{B}}(\sigma a_1,\dots ,\sigma a_k)$、各定数記号 $c$ について $\sigma (c^{\mathcal{A}})=c^{\mathcal{B}}$ を満たすものをいう。コンパクト性定理は用いないこと。