数理論理学・集合論

命題変数 $p,q,r$ に真（$\mathrm{T}$）または偽（$\mathrm{F}$）を割り当てる $2^3=8$ 通りの割り当てのうち、論理式
$$(p\vee q)\to (q\leftrightarrow r)$$
を真にするものは何通りあるか。ただし、結合子 $\vee ,\to ,\leftrightarrow$ は通常の真理値表で解釈する（$A\to B$ は $A$ が真で $B$ が偽のときだけ偽、$A\leftrightarrow B$ は $A$ と $B$ の真理値が等しいときだけ真）。

広義単調増加な関数 $f:\mathbb{R}\to \mathbb{R}$（$x<y$ ならば $f(x)\leqq f(y)$ を満たす関数）全体の集合を $M$ とする。$\mathfrak{c}=2^{{\aleph }_0}$ を連続体の濃度とするとき、$M$ の濃度として正しいものを次から 1 つ選べ。

ア. ${\aleph }_0$

イ. $\mathfrak{c}$

ウ. $2^{\mathfrak{c}}$

$p_0=2,p_1=3,p_2=5,p_3=7,\dots$ を小さい順に並べた素数とする。$0$ 以上の整数からなる長さ $k+1$ の有限列 $(a_0,a_1,\dots ,a_k)$（$k\geqq 0$）を
$$┌(a_0,a_1,\dots ,a_k)┐=\prod _{i=0}^k{p}_i^{a_i+1}$$
で正の整数に符号化する。符号が $1440600$ である列を求め、成分を順に並べた組で答えよ。

$0$ 以上の整数全体を $\mathbb{N}=\{0,1,2,\dots \}$ とし、カントールの対関数 $J:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を
$$J(x,y)=\frac{(x+y)(x+y+1)}{2}+y$$
で定める。$J$ は全単射である。$J(x,y)=33$ を満たす $(x,y)\in \mathbb{N}\times \mathbb{N}$ を求め、組 $(x,y)$ で答えよ。

命題変数 $x_1,x_2,x_3$ だけを使う命題論理の論理式を考え、論理的に同値な論理式どうしを同一視する。
$$(x_1\wedge x_2\wedge x_3)\to \psi \text{と}\psi \to (x_1\vee x_2)$$
がともにトートロジーとなる論理式 $\psi$ の同値類の個数を求めよ。

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$ の集合を求めよ。ただし $=$ は台集合の元の等しさと解釈する。

$\omega$ を最小の無限順序数とし、$+$ と $\cdot$ は順序数の和と積とする。順序数
$$\alpha =(\omega \cdot 2+3)\cdot (\omega +2)$$
のカントール標準形を
$$\alpha ={\omega }^2\cdot a+\omega \cdot b+c(a,b,c\text{ は }0\text{ 以上の整数})$$
と表すとき、組 $(a,b,c)$ をこの順に求めよ。

$0$ 以上の整数全体を $\mathbb{N}=\{0,1,2,\dots \}$ とする。関数 $f:\mathbb{N}\to \mathbb{N}$ を、累積再帰
$$f(0)=1,f(n+1)=f(n)+f\left(\lfloor \frac{n}{2}\rfloor \right)(n\in \mathbb{N})$$
で定める。ここで $\lfloor t\rfloor$ は $t$ 以下の最大の整数である。$f(n)\ge 20$ となる最小の $n\in \mathbb{N}$ を求めよ。

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$ の部分集合として異なれば別のものと数える。

2 項関係記号 $E$ だけからなる言語の構造 $\mathcal{G}=(V,E^{\mathcal{G}})$ を、台集合 $V=\{1,2,3,4,5,6\}$、
$$E^{\mathcal{G}}=\{(a,b)\mid \{a,b\}\in \{\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{5,6\}\}\}$$
で定める（$E^{\mathcal{G}}$ は対称で、5 本の辺をもつ無向グラフを表す）。$\mathcal{G}$ の自己同型、すなわち全単射 $\sigma :V\to V$ であって、すべての $a,b\in V$ について $E(a,b)⟺E(\sigma (a),\sigma (b))$ を満たすものの個数を求めよ。

関係記号 $<$ を 1 つだけもつ一階述語論理の言語を考える（等号 $=$ は使ってよいとする）。正の整数 $n$ に対し、$L_n=(\{1,2,\dots ,n\},<)$ を、$<$ を通常の大小関係と解釈した有限線形順序とする。論理式 $\phi$ の量化子の深さ（量化子の入れ子の最大の深さ）を $\mathrm{qr}(\phi )$ と書き、構造 $\mathcal{A},\mathcal{B}$ が量化子の深さ $k$ 以下のすべての文で同じ真偽をとることを $\mathcal{A}{\equiv }_k\mathcal{B}$ と書く。

有限線形順序について、正の整数 $k$ に対して
$$L_m{\equiv }_k{L}_n⟺m=n\text{または}m,n\ge 2^k-1$$
が成り立つことを用いてよい。

$L_{12}\models \sigma$ かつ $L_{20}/\models \sigma$ となる文 $\sigma$（$L_{12}$ と $L_{20}$ を区別する文）の量化子の深さ $\mathrm{qr}(\sigma )$ の最小値を求めよ。

$\omega$ を最小の無限順序数（自然数全体 $\{0,1,2,\dots \}$ に通常の大小を入れた整列集合の順序型）とする。順序数の和 $\alpha +\beta$ は「$\alpha$ の後ろに $\beta$ を並べた整列集合の順序型」、積 $\alpha \cdot \beta$ は「$\alpha$ を $\beta$ 回（$\beta$ の順に）並べた整列集合の順序型」と定める。

次のア〜エの等式のうち、正しいものをすべて選べ。

ア. $2+\omega =\omega$

イ. $\omega +2=\omega$

ウ. $3\cdot \omega =\omega$

エ. $\omega \cdot 3=\omega$

命題変数 $x_1,x_2,x_3,x_4,x_5$ に関する命題論理の論理式
$$\phi =(x_1\vee x_2\vee x_3)\wedge \neg (x_1\wedge x_2)\wedge (x_4\to x_1)\wedge (x_5\to x_3)$$
を考える。$x_1,\dots ,x_5$ への真理値割り当て（全部で $2^5=32$ 通り）のうち、$\phi$ を真にするものの個数を求めよ。

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

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。$\mathbb{N}$ 上の関数を次の原始再帰で順に定める。

$(1)$ 符号関数 $\mathrm{sg}$：$\mathrm{sg}(0)=0,\mathrm{sg}(n+1)=1$

$(2)$ 打ち切り差 $x\dot{-}y$：$x\dot{-}0=x,x\dot{-}(y+1)=\mathrm{pd}(x\dot{-}y)$。ただし $\mathrm{pd}(0)=0,\mathrm{pd}(n+1)=n$ とする。

$(3)$ 関数 $r$：$r(0)=0,r(n+1)=(r(n)+1)\cdot \mathrm{sg}(2\dot{-}r(n))$

$(4)$ 関数 $f$：$f(0)=0,f(n+1)=f(n)+(n+1)\cdot \mathrm{sg}(r(n+1))$

このとき $f(30)$ の値を求めよ。

2 項関係記号 $E$ と 1 項関係記号 $P$ からなる一階の言語の構造 $\mathcal{M}=(A,E^{\mathcal{M}},P^{\mathcal{M}})$ を次で定める。
- 台集合 $A=\{0,1{\}}^3$（長さ $3$ の $0,1$ の列全体、$8$ 個の元）
- $E^{\mathcal{M}}(u,v)$ は「$u$ と $v$ がちょうど $1$ つの成分で異なる」ときに成り立つ
- $P^{\mathcal{M}}=\{(0,0,0),(1,1,1)\}$

$\mathcal{M}$ の自己同型（$A$ から $A$ への全単射 $\sigma$ で、すべての $u,v\in A$ について $E^{\mathcal{M}}(u,v)⟺E^{\mathcal{M}}(\sigma (u),\sigma (v))$ かつ $u\in P^{\mathcal{M}}⟺\sigma (u)\in P^{\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}})$ が異なれば別のものとして数える。

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、$p_i$ を $i$ 番目の素数とする（$p_0=2,p_1=3,p_2=5,\dots$）。有限列 $(a_0,a_1,\dots ,a_{k-1})\in {\mathbb{N}}^k$ のゲーデル数を
$$⟨a_0,a_1,\dots ,a_{k-1}⟩=\prod _{i=0}^{k-1}{p}_i^{a_i+1}$$
で定める（空列のゲーデル数は $1$ とする）。

関数 $F:\mathbb{N}\to \mathbb{N}$ を
$$F(0)=1,F(1)=1,F(n+2)=F(n+1)+2F(n)(n\in \mathbb{N})$$
で定め、その累積値関数（course-of-values function）$\overline{F}:\mathbb{N}\to \mathbb{N}$ を
$$\overline{F}(n)=⟨F(0),F(1),\dots ,F(n-1)⟩$$
で定める。自然数 $\overline{F}(5)$ の正の約数の個数を求めよ。

命題変数 $x_1,x_2,\dots ,x_{10}$ に関する命題論理の論理式
$$\phi =\underset{i=1}{\overset{10}{\bigwedge }}\left(\neg x_i\vee \neg x_{i+1}\right)$$
を考える。ただし添字は巡回的に読み、$x_{11}$ は $x_1$ を表すものとする（したがって $\phi$ は $10$ 個の節 $\neg x_1\vee \neg x_2,\neg x_2\vee \neg x_3,\dots ,\neg x_9\vee \neg x_{10},\neg x_{10}\vee \neg x_1$ の連言である）。

$x_1,\dots ,x_{10}$ への真理値割り当て（全部で $2^{10}$ 通り）のうち、$\phi$ を真にするものの個数を求めよ。

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}}$ が集合として異なれば別に数える）。

定数記号 $0$、1 項関数記号 $S$、2 項関数記号 $+$ からなる一階の言語の項（変数を含まない閉項）を考える。項は次の規則で作られるものだけとする。
- $0$ は項である。
- $t$ が項ならば $St$ は項である。
- $s,t$ が項ならば $(s+t)$ は項である。

各項 $t$ のゲーデル数 $┌t┐$（正の整数）を、項の構成に関する帰納法で次のように定める。
$$┌0┐=1,┌St┐=2^{┌t┐},┌(s+t)┐=3^{┌s┐}\cdot 5^{┌t┐}.$$
ゲーデル数が $1000$ 以下である項の個数を求めよ（異なる項は異なる記号列として区別する）。

1 項関数記号 $f$ だけからなる一階の言語を考える。台集合 $A=\{1,2,\dots ,10\}$ 上の構造 $\mathcal{M}=(A,f^{\mathcal{M}})$ を、関数 $f^{\mathcal{M}}:A\to A$ の値が次の表で与えられるものとする。

$\mathcal{M}$ の自己同型、すなわち全単射 $\sigma :A\to A$ であって、すべての $x\in A$ について $\sigma (f^{\mathcal{M}}(x))=f^{\mathcal{M}}(\sigma (x))$ を満たすものは何個あるか。

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}}$ を満たすものの個数を求めよ。

命題変数 $x_1,x_2,x_3$ と結合子 $\wedge ,\vee$ だけを用いて作られる命題論理の論理式を考える。すなわち、各 $x_i$ は論理式であり、$\phi ,\psi$ が論理式ならば $(\phi \wedge \psi )$ と $(\phi \vee \psi )$ も論理式であり、これらの規則で作られるものだけを論理式とする（否定 $\neg$、含意 $\to$、定数 $\top ,\perp$ は用いない）。2 つの論理式は、$x_1,x_2,x_3$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。互いに同値でない論理式は最大で何個とれるか。すなわち、同値類の個数を求めよ。

自然数は $0$ を含むものとし、$\mathbb{N}=\{0,1,2,\dots \}$ とする。$p_i$ で $i$ 番目の素数を表す（$p_0=2,p_1=3,p_2=5,\dots$）。$n\ge 1$ と $i\in \mathbb{N}$ に対し、$(n{)}_i$ を「$p_i^e\mid n$ となる最大の $e\in \mathbb{N}$」と定め、$(0{)}_i=0$ とする。

長さ $k\ge 0$ の有限列 $(a_0,a_1,\dots ,a_{k-1})\in {\mathbb{N}}^k$ のゲーデル数を
$$┌a_0,\dots ,a_{k-1}┐=\prod _{i<k}{p}_i^{a_i+1}$$
と定める（空列のゲーデル数は $1$）。関数 $F:\mathbb{N}\to \mathbb{N}$ を、$n$ がある有限列 $(a_0,\dots ,a_{k-1})$ のゲーデル数であるとき $F(n)={\sum }_{i<k}{a}_i$、そうでないとき $F(n)=0$ と定める。

$F$ が原始再帰関数であることを証明せよ。

ただし、次の事実は用いてよい。
- $x+y$, $x\cdot y$, $x\dot{-}y$（$x\ge y$ なら $x-y$、そうでなければ $0$）、$x\mapsto p_x$、$(n,i)\mapsto (n{)}_i$ は原始再帰関数であり、述語 $x\mid y$ と $x<y$ は原始再帰的である。
- 原始再帰関数・原始再帰的述語の全体は、合成、原始再帰、論理結合子 $\neg ,\wedge ,\vee ,\to$、有界量化 $\forall i<m$, $\exists i<m$（$m$ は原始再帰関数の値）で閉じている。また、述語 $P$ が原始再帰的であることは、その特性関数 ${\chi }_P$（$P$ が成り立てば $1$、そうでなければ $0$）が原始再帰関数であることと定義する。
- 素因数分解の一意性。

$n\ge 2$ を整数とし、命題変数 $p_1,p_2,\dots ,p_n$ に対して論理式
$${\psi }_n=\underset{i=1}{\overset{n-1}{\bigwedge }}\neg (p_i\wedge p_{i+1})=\neg (p_1\wedge p_2)\wedge \neg (p_2\wedge p_3)\wedge \cdots \wedge \neg (p_{n-1}\wedge p_n)$$
を考える。真理値割り当て $v:\{p_1,\dots ,p_n\}\to \{\mathrm{T},\mathrm{F}\}$（全部で $2^n$ 個）のうち ${\psi }_n$ を真にするものの個数を $s_n$ とする。

フィボナッチ数を $F_1=F_2=1$, $F_{m+2}=F_{m+1}+F_m$ $(m\ge 1)$ で定めるとき、すべての整数 $n\ge 2$ について $s_n=F_{n+2}$ であることを証明せよ。

ZFC に一般連続体仮説 GCH（すべての無限基数 $\kappa$ に対して $2^{\kappa }={\kappa }^{+}$）を加えた体系で考える。${\omega }_n$ は $n$ 番目の無限始順序数で、$|{\omega }_n|={\aleph }_n$ とする（$n=0,1,2,\dots$）。集合 $X,Y$ に対して ${}^{X}Y$ は $X$ から $Y$ への写像全体の集合、$\mathcal{P}(X)$ は $X$ のべき集合を表す。次の 4 つの集合を考える。

• $A=\{S\subseteq {\omega }_3:S\text{ は高々可算}\}$（有限集合・空集合も含む）
• $B={}^{{\omega }_5}{\omega }_2$
• $C=\mathcal{P}({\omega }_1)\times {}^{{\omega }_1}{\omega }_4$
• $D=\{f:{\omega }_2\to {\omega }_2:f\text{ は全単射}\}$

それぞれの濃度は $|A|={\aleph }_a,|B|={\aleph }_b,|C|={\aleph }_c,|D|={\aleph }_d$（$a,b,c,d$ は $0$ 以上の整数）と表せる。組 $(a,b,c,d)$ を求めよ。

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}}$ が異なれば別のものとして数える。

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。カントールの対関数 $\pi :\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を
$$\pi (x,y)=\frac{(x+y)(x+y+1)}{2}+y$$
で定める。$\pi$ は全単射であるから、各 $n\in \mathbb{N}$ に対して $\pi (x,y)=n$ をみたす $(x,y)$ がただ 1 つ存在する。これを $x={\pi }_1(n)$, $y={\pi }_2(n)$ と書く（${\pi }_1,{\pi }_2$ は原始再帰関数である）。

関数 $g:\mathbb{N}\to \mathbb{N}$ を、累積再帰（course-of-values recursion）により
$$g(0)=0,g(n+1)=\pi (g({\pi }_2(n)),g({\pi }_1(n)))+1(n\in \mathbb{N})$$
で定める（${\pi }_1(n),{\pi }_2(n)\le n$ なので well-defined であり、$g$ は原始再帰関数である）。$g(2024)$ の値を求めよ。

命題変数 $x_1,x_2,x_3,x_4$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ を用いる）。2 つの論理式は、$x_1,\dots ,x_4$ へのすべての真理値割り当て（$2^4=16$ 通り）で同じ真理値をとるとき同値であるという。また、論理式 $\phi$ に現れる $x_3$ と $x_4$ を同時に入れ替えて得られる論理式を ${\phi }^{\sigma }$ と書く。

次の 4 つの条件をすべて満たす論理式 $\phi$ を考える。

(1) $(x_1\wedge x_2)\to \phi$ はトートロジーである。

(2) $\phi \to (x_1\vee x_2\vee x_3)$ はトートロジーである。

(3) $\phi$ と ${\phi }^{\sigma }$ は同値である。

(4) $\phi$ を真にする真理値割り当て（充足割り当て）はちょうど $8$ 個である。

このような論理式 $\phi$ は、同値なものを同一視すると何個あるか。

ZFC のもとで考える。$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）、$\mathbb{Q}$ は有理数全体、$\mathbb{R}$ は実数全体とし、$\mathfrak{c}=2^{{\aleph }_0}$ とおく（連続体仮説は仮定しない）。次の 11 個の集合を考える。

$(1)$ 有理数係数の 1 変数多項式全体 $\mathbb{Q}[x]$

$(2)$ 実数である代数的数全体

$(3)$ $\mathbb{N}$ の有限部分集合全体

$(4)$ 写像 $\mathbb{N}\to \mathbb{N}$ 全体 ${\mathbb{N}}^{\mathbb{N}}$

$(5)$ 全単射 $\mathbb{N}\to \mathbb{N}$ 全体

$(6)$ $\mathbb{R}$ の（通常の位相に関する）開集合全体

$(7)$ 連続関数 $\mathbb{R}\to \mathbb{R}$ 全体

$(8)$ $\mathbb{R}$ の高々可算な部分集合（有限集合・空集合を含む）全体

$(9)$ 関数 $\mathbb{R}\to \mathbb{R}$ 全体

$(10)$ $\mathbb{R}$ のルベーグ可測集合全体

$(11)$ $\mathbb{R}$ 上の同値関係全体

これらのうち、濃度が ${\aleph }_0$ であるものの個数、$\mathfrak{c}$ であるものの個数、$2^{\mathfrak{c}}$ であるものの個数を、この順に組で答えよ。

$\omega$ を最小の無限順序数とし、順序数の和・積は通常の（超限帰納法で定義される）順序数演算とする。積 $\alpha \cdot \beta$ は「$\alpha$ を $\beta$ 回並べたもの」を表す流儀とする（たとえば $\omega \cdot 2=\omega +\omega$、$2\cdot \omega =\omega$）。

順序数
$$\alpha =({\omega }^2+\omega \cdot 2+3)\cdot ({\omega }^2+4)$$
を考える。順序数 $\gamma$ であって、ある順序数 $\beta$ に対して $\beta +\gamma =\alpha$ が成り立つようなもの（$\gamma =0$ や $\gamma =\alpha$ も含む）の個数を求めよ。

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)$ が異なれば別のものとして数える。

この問題では自然数 $\mathbb{N}$ は $0$ を含むものとする。$p_0=2,p_1=3,p_2=5,p_3=7,p_4=11,p_5=13,\dots$ を小さい順に並べた素数とする（$p_i$ は $0$ 番目から数えて $i$ 番目の素数）。

正の整数 $c$ と $i\in \mathbb{N}$ に対し、$c$ を素因数分解したときの $p_i$ の指数を $e_i(c)$ とする（$p_i$ が $c$ を割り切らなければ $e_i(c)=0$）。さらに
$$(c{)}_i=\max (e_i(c)-1,0)$$
と定める。例えば $c=2^2\cdot 3^3$ のとき $e_0(c)=2,e_1(c)=3,e_2(c)=0$ なので $(c{)}_0=1,(c{)}_1=2,(c{)}_2=0$ である。

関数 $g:\mathbb{N}\times {\mathbb{Z}}_{>0}\to \mathbb{N}$ を、正の整数 $c$ に対して
$$g(0,c)=1,g(m,c)=(c{)}_{\lfloor m/2\rfloor }+(c{)}_{m-1}(m\ge 1)$$
で定める（右辺の 2 つの項はどちらも上で定めた $(c{)}_i$ の値の和であり、$g$ を再帰的に使うものではない）。さらに関数 $F:\mathbb{N}\to {\mathbb{Z}}_{>0}$ を
$$F(0)=1,F(n+1)=F(n)\cdot p_n^{g(n,F(n))+1}(n\in \mathbb{N})$$
で定める。例えば $F(1)=1\cdot p_0^{g(0,1)+1}=2^2$ である。

このとき、$F(6)$ を素因数分解したときの素数 $13$ の指数 $e_5(F(6))$ を求めよ。

命題変数 $x_1,x_2,\dots ,x_6$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ を用いる）。2 つの論理式は、$x_1,\dots ,x_6$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。次の 2 つの論理式を定める。
$$\phi =\underset{i=1}{\overset{5}{\bigwedge }}\left(x_i\vee x_{i+1}\right),\chi =\underset{i=1}{\overset{4}{\bigwedge }}\left(x_i\vee x_{i+1}\vee x_{i+2}\right).$$
$x_1,\dots ,x_6$ だけを用いた論理式 $\psi$ であって、$\phi \to \psi$ と $\psi \to \chi$ がともにトートロジー（恒真式）であるものを考える。このような $\psi$ の、同値関係による同値類の個数を求めよ。

$\omega$ を最小の無限順序数とし、順序数の和・積・べきは通常の（超限帰納法による）順序数演算とする。積 $\alpha \cdot \beta$ は「$\alpha$ を $\beta$ 回並べたもの」を表す流儀（たとえば $\omega \cdot 2=\omega +\omega$, $2\cdot \omega =\omega$）とする。順序数
$$\delta =(\omega \cdot 2+1{)}^3+({\omega }^2\cdot 3+\omega \cdot 5+2)\cdot (\omega \cdot 2+4)$$
をカントール標準形で
$$\delta ={\omega }^3\cdot c_3+{\omega }^2\cdot c_2+\omega \cdot c_1+c_0(c_0,c_1,c_2,c_3\text{は自然数})$$
と表したとき、組 $(c_3,c_2,c_1,c_0)$ をこの順に求めよ。

ZFC のもとで考える。$\mathbb{R}$ は実数全体、$\mathbb{N}=\{0,1,2,\dots \}$ は $0$ 以上の整数全体とし、連続体の濃度を $\mathfrak{c}=2^{{\aleph }_0}$ と書く（連続体仮説は仮定しない）。次の集合のうち、濃度がちょうど $\mathfrak{c}$ であるものをすべて選べ。

ア. $\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

イ. $\mathbb{R}$ のルベーグ可測な部分集合全体の集合

ウ. $\mathbb{N}$ から $\mathbb{N}$ への写像全体の集合

エ. 代数的数（有理数係数の $0$ でない多項式の根となる複素数）全体の集合

オ. $\mathbb{R}$ の（通常の位相に関する）開集合全体の集合

カ. $\mathbb{R}$ から $\mathbb{R}$ への全単射全体の集合

1 項関数記号 $f$ だけからなる一階の言語（等号を含む）の構造 $\mathcal{M}=(A,f^{\mathcal{M}})$ を、台集合 $A=\{1,2,\dots ,13\}$ と次の表で定める。

$\mathcal{M}$ の自己同型、すなわち全単射 $\sigma :A\to A$ で、すべての $a\in A$ に対して $\sigma (f^{\mathcal{M}}(a))=f^{\mathcal{M}}(\sigma (a))$ を満たすものの個数を求めよ。

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$ が部分集合として異なれば別のものとして数える。

ZFC 集合論の中で考える。$\mathbb{N}=\{0,1,2,\dots \}$ とし、実数全体 $\mathbb{R}$ の濃度を $\mathfrak{c}=2^{{\aleph }_0}$ とする。次のア〜キの集合のうち、濃度が $2^{\mathfrak{c}}$ であるものをすべて選べ。

ア: $\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

イ: $\mathbb{R}$ から $\mathbb{R}$ への関数全体の集合

ウ: $\mathbb{R}$ の可算部分集合（有限集合を含む）全体の集合

エ: $\mathbb{R}$ のルベーグ可測集合全体の集合

オ: $\mathbb{R}$ のボレル集合全体の集合

カ: $\mathbb{R}$ から $\mathbb{R}$ への単調増加関数（$x<y\Rightarrow f(x)\le f(y)$）全体の集合

キ: $\mathbb{N}$ 上の超フィルター全体の集合

$\omega$ を最小の無限順序数とし、順序数の和・積・べきは通常の（超限帰納法による）順序数演算とする。積 $\alpha \cdot \beta$ は「$\alpha$ を $\beta$ 回並べたもの」を表す流儀とし（たとえば $\omega \cdot 2=\omega +\omega$, $2\cdot \omega =\omega$）、${\alpha }^3=\alpha \cdot \alpha \cdot \alpha$ とする。 $$\alpha ={\omega }^2\cdot 2+\omega +3$$ とおく。${\alpha }^3$ のカントール標準形を $${\alpha }^3={\omega }^6\cdot a_6+{\omega }^5\cdot a_5+{\omega }^4\cdot a_4+{\omega }^3\cdot a_3+{\omega }^2\cdot a_2+\omega \cdot a_1+a_0(a_0,\dots ,a_6\text{は自然数})$$ と書くとき、組 $(a_6,a_5,a_4,a_3,a_2,a_1,a_0)$ を求めよ。

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。$\mathrm{rm}(x,y)$ を「$x$ を $y$ で割った余り」（$y\ge 1$）とし、ゲーデルの $\beta$ 関数を $$\beta (c,d,i)=\mathrm{rm}(c,1+(i+1)d)(c,d,i\in \mathbb{N})$$ で定める（$\beta$ は原始再帰関数である）。有限列 $(a_0,a_1,a_2)=(2,0,3)$ を、$s=\max \{3,a_0,a_1,a_2\}$ として $d=s!$ を用いて符号化する。すなわち $$\beta (c,d,0)=2,\beta (c,d,1)=0,\beta (c,d,2)=3$$ を満たす $c\in \mathbb{N}$ を考える。このような $c$ のうち最小のものを求めよ。

ZFC（選択公理を含む）の中で考え、$\mathfrak{c}=2^{{\aleph }_0}$ とおく。実数全体を $\mathbb{R}$、有理数全体を $\mathbb{Q}$、$0$ 以上の整数全体を $\mathbb{N}$ とする。集合が可算であるとは、有限または $\mathbb{N}$ と全単射をもつことをいう。

関数 $f:\mathbb{R}\to \mathbb{R}$ が単調非減少であるとは、すべての実数 $x,y$ について $x<y\Rightarrow f(x)\le f(y)$ が成り立つことをいう。単調非減少な関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合を $\mathcal{M}$ とする。$\mathcal{M}$ の濃度が $\mathfrak{c}$ であることを証明せよ。

ただし、次の事実は証明なしに用いてよい。
- $|\mathbb{R}|=|{\mathbb{R}}^2|=\mathfrak{c}$、$|\mathbb{Q}|={\aleph }_0$ であり、$\mathbb{Q}$ は $\mathbb{R}$ で稠密である。
- 基数の演算法則 $({\kappa }^{\lambda }{)}^{\mu }={\kappa }^{\lambda \cdot \mu }$ と ${\aleph }_0\cdot {\aleph }_0={\aleph }_0$。
- ベルンシュタインの定理（$|X|\le |Y|$ かつ $|Y|\le |X|$ なら $|X|=|Y|$）。
- 実数の連続性（上に有界な空でない部分集合は上限をもち、下に有界な空でない部分集合は下限をもつ）。

$\omega$ を最小の無限順序数とし、順序数の和は通常の（超限帰納法で定義される）順序数の和とする。次の $5$ つの順序数を考える。
$${\alpha }_1={\omega }^2+1,{\alpha }_2=\omega \cdot 2+1,{\alpha }_3={\omega }^2\cdot 2+\omega ,{\alpha }_4=\omega +3,{\alpha }_5=2$$
ただし $\omega \cdot 2=\omega +\omega$、${\omega }^2\cdot 2={\omega }^2+{\omega }^2$ である。$\{1,2,3,4,5\}$ の置換 $\sigma$ それぞれに対して
$$S_{\sigma }={\alpha }_{\sigma (1)}+{\alpha }_{\sigma (2)}+{\alpha }_{\sigma (3)}+{\alpha }_{\sigma (4)}+{\alpha }_{\sigma (5)}$$
とおく（順序数の和は結合的なので括弧は不要）。$120$ 個の置換 $\sigma$ をすべて動かすとき、$S_{\sigma }$ として現れる相異なる順序数の個数を求めよ。

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

2 項関係記号 $<$ だけからなる一階の言語（等号を含む）を考える。正の整数 $n$ に対し、$L_n=(\{1,2,\dots ,n\},<)$ を通常の大小関係による $n$ 元の線形順序とする。

論理式の量化子の深さ $\mathrm{qr}$ を、原子論理式では $0$、$\mathrm{qr}(\neg \phi )=\mathrm{qr}(\phi )$、$\mathrm{qr}(\phi \wedge \psi )=\mathrm{qr}(\phi \vee \psi )=\mathrm{qr}(\phi \to \psi )=\max (\mathrm{qr}(\phi ),\mathrm{qr}(\psi ))$、$\mathrm{qr}(\exists x\phi )=\mathrm{qr}(\forall x\phi )=\mathrm{qr}(\phi )+1$ で定める。

正の整数 $n$ に対し、$f(n)$ を「$L_n\models \sigma$ かつ $L_{n+1}/\models \sigma$ となる文（自由変数をもたない論理式）$\sigma$ の量化子の深さの最小値」と定める（$L_n$ と $L_{n+1}$ は同型でない有限構造なので、このような文は存在する）。

$$\sum _{n=1}^{100}f(n)$$
の値を求めよ。

選択公理を含む ZFC で考える。$\mathfrak{c}=2^{{\aleph }_0}$ を連続体の濃度とし、$\mathbb{N}=\{0,1,2,\dots \}$ とする。次の集合のうち、濃度が $2^{\mathfrak{c}}$ に等しいものをすべて選べ。

ア．$\mathbb{R}$ から $\mathbb{R}$ への連続関数全体の集合

イ．閉区間 $[0,1]$ 上で定義された実数値関数のうち、リーマン積分可能なもの全体の集合

ウ．$\mathbb{R}$ の部分集合のうち、ルベーグ可測なもの全体の集合

エ．$\mathbb{R}$ のボレル集合全体の集合

オ．$\mathbb{N}$ 上の超フィルター（ultrafilter）全体の集合

カ．複素数体 $\mathbb{C}$ の体としての自己同型全体の集合

キ．$\mathbb{R}$ から $\mathbb{R}$ への単調増加関数（$x<y\Rightarrow f(x)\le f(y)$ をみたす関数）全体の集合

ク．$\mathbb{N}$ から $\mathbb{N}$ への全単射全体の集合

ケ．$\mathbb{R}$ の可算無限部分集合全体の集合

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。カントールの対関数
$$J(x,y)=\frac{(x+y)(x+y+1)}{2}+y$$
は $\mathbb{N}\times \mathbb{N}$ から $\mathbb{N}$ への全単射であり、その逆写像の成分を $K,L:\mathbb{N}\to \mathbb{N}$（すなわち $J(K(n),L(n))=n$）とすると、$J,K,L$ はいずれも原始再帰関数である。$K(n)\le n,L(n)\le n$ に注意して、関数 $f:\mathbb{N}\to \mathbb{N}$ を累積再帰（course-of-values recursion）により
$$f(0)=1,f(n+1)=f(K(n))+f(L(n))(n\in \mathbb{N})$$
で定める（$f$ は原始再帰関数である）。$f(n)=9$ をみたす最小の $n\in \mathbb{N}$ を求めよ。

選択公理を含む集合論 ZFC の中で考える。$\mathbb{R}$ を実数全体の集合、$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、$\mathfrak{c}=2^{{\aleph }_0}$ を連続体の濃度とする。次のア〜クの集合のうち、濃度が $2^{\mathfrak{c}}$ であるものをすべて選べ。

ア　連続関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

イ　ルベーグ可測な $\mathbb{R}$ の部分集合全体の集合

ウ　単調非減少な関数 $f:\mathbb{R}\to \mathbb{R}$（$x\leqq y\Rightarrow f(x)\leqq f(y)$）全体の集合

エ　すべての $x,y\in \mathbb{R}$ に対して $f(x+y)=f(x)+f(y)$ を満たす関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

オ　$\mathbb{R}$ の可算な部分集合（有限集合を含む）全体の集合

カ　全単射 $\sigma :\mathbb{N}\to \mathbb{N}$ 全体の集合

キ　濃度がちょうど $\mathfrak{c}$ である $\mathbb{R}$ の部分集合全体の集合

ク　$\mathbb{R}$ の（通常の位相に関する）閉集合全体の集合

$\omega$ を最小の無限順序数とし、順序数の和は通常の（超限帰納法で定義される、一般には非可換な）順序数の和とする。また $\omega \cdot 2=\omega +\omega$、${\omega }^2\cdot 2={\omega }^2+{\omega }^2$ と書く。

次の 5 個の順序数
$${\alpha }_1=1,{\alpha }_2=\omega ,{\alpha }_3=\omega +2,{\alpha }_4={\omega }^2,{\alpha }_5={\omega }^2+1$$
を考える。$\{1,2,3,4,5\}$ の置換 $\pi$ 全体（$120$ 個）にわたって
$$S_{\pi }={\alpha }_{\pi (1)}+{\alpha }_{\pi (2)}+{\alpha }_{\pi (3)}+{\alpha }_{\pi (4)}+{\alpha }_{\pi (5)}$$
（左から順に足す）を考えるとき、$S_{\pi }$ がとりうる相異なる順序数の個数を求めよ。

ZFC（選択公理を含む集合論）で考える。$\mathbb{R}$ を実数全体、$\mathbb{N}=\{0,1,2,\dots \}$ とし、$\mathfrak{c}=2^{{\aleph }_0}$ を $\mathbb{R}$ の濃度とする。次の集合ア〜コのうち、濃度がちょうど $\mathfrak{c}$ であることが ZFC で証明できるものをすべて選べ（連続体仮説などの追加の仮定は用いない）。

ア．連続関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

イ．$\mathbb{R}$ のルベーグ可測な部分集合全体の集合

ウ．$\mathbb{R}$ のボレル集合全体の集合

エ．$\mathbb{N}$ 上の超フィルター（単項のものも含む）全体の集合

オ．加法的な関数、すなわちすべての $x,y\in \mathbb{R}$ で $f(x+y)=f(x)+f(y)$ を満たす関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

カ．単調非減少な関数 $f:\mathbb{R}\to \mathbb{R}$ 全体の集合

キ．実数列 $(a_n{)}_{n\in \mathbb{N}}$ 全体の集合 ${\mathbb{R}}^{\mathbb{N}}$

ク．体 $\mathbb{R}$ の自己同型写像全体の集合

ケ．$\mathbb{R}$ の可算無限部分集合全体の集合

コ．代数的数（有理数係数の $0$ でない多項式の根となる複素数）全体の集合

命題変数 $x_1,x_2,x_3,x_4$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ とし、定数 $\top ,\perp$ は用いない）。2 つの論理式は、$x_1,\dots ,x_4$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。

論理式 $\phi$ に対し、$\phi$ の中の $x_i$ をすべて $\neg x_i$（$i=1,2,3,4$）に同時に置き換えた論理式を ${\phi }^{\ast }$ とする。次の 2 条件をともに満たす論理式 $\phi$ を考える。

$(1)$ $\phi$ は、結合子 $\wedge ,\vee$ と命題変数 $x_1,\dots ,x_4$ だけを用いた（$\neg ,\to$ を用いない）ある論理式と同値である。

$(2)$ $\neg \phi$ と ${\phi }^{\ast }$ は同値である。

このような論理式 $\phi$ の同値類は何個あるか。

$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}}$ を満たすものをいう。コンパクト性定理は用いないこと。

2 項関係記号 $E$ だけからなる一階の言語（等号を含む）を考える。台集合 $A$ が空でない有限集合で、$E^{\mathcal{A}}$ が $A$ 上の同値関係であるような構造 $\mathcal{A}=(A,E^{\mathcal{A}})$ を、以下「有限同値構造」とよぶ。

論理式の量化子の深さ $\mathrm{qr}$ を次で定める。
- 原子論理式 $\phi$ に対して $\mathrm{qr}(\phi )=0$
- $\mathrm{qr}(\neg \phi )=\mathrm{qr}(\phi )$
- $\mathrm{qr}(\phi \wedge \psi )=\mathrm{qr}(\phi \vee \psi )=\mathrm{qr}(\phi \to \psi )=\max (\mathrm{qr}(\phi ),\mathrm{qr}(\psi ))$
- $\mathrm{qr}(\exists x\phi )=\mathrm{qr}(\forall x\phi )=\mathrm{qr}(\phi )+1$

2 つの構造 $\mathcal{A},\mathcal{B}$ が、$\mathrm{qr}\le 3$ のすべての閉論理式について真偽が一致するとき、$\mathcal{A}{\equiv }_3\mathcal{B}$ と書く。

すべての有限同値構造（台集合の大きさは任意）を ${\equiv }_3$ で分類したときの同値類の個数を求めよ。