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

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}}$）の個数を求めよ。

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\}$ に固定し、関数 $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 項関係記号 $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$ だけからなる言語を考え、台集合を $M=\{1,2,3,4\}$ に固定する。$R$ の解釈 $R^{\mathcal{M}}\subseteq M\times M$ を 1 つ選ぶごとに構造 $\mathcal{M}=(M,R^{\mathcal{M}})$ が 1 つ定まる。文
$$\phi :\forall x\exists y(R(x,y)\wedge \forall z(R(x,z)\to z=y))\wedge \forall x\neg R(x,x)$$
について、$\mathcal{M}\models \phi$ となる $R^{\mathcal{M}}$ の個数を求めよ。ただし $=$ は台集合の元の等しさと解釈し、$R^{\mathcal{M}}$ は $M\times M$ の部分集合として異なれば別のものと数える。