NKU 第三次作业

题1

令 $L$ 为一阶语言，$\varphi$ 为 $L$ 语句，则可定义 $\varphi$ 的谱 (spectrum) ：即 $\varphi$ 的有限（集）模型的基数构成的集合. 表示为 $\mathrm{Sp}(\varphi) = \left\lbrace |A|: A\models \varphi, A \text{ is finite} \right\rbrace$.

例如：令 $L$ 为 $L_=$ ，则 $\mathrm{Sp}(\exists x(x=x))=\omega\backslash \left\lbrace 0 \right\rbrace$ ，$\mathrm{Sp}(\exists^{\geqslant 4}) = \left\lbrace n\in \omega | n \geqslant 4 \right\rbrace$ ，$\mathrm{Sp}(\exists^{=4}) = \left\lbrace 4 \right\rbrace$.

令 $\mathrm{Rs}_L = \mathrm{Cs}_L = \varnothing$ ，$\mathrm{Fs}_L = \left\lbrace f \right\rbrace,\nu_L(f)=1$ ，有
$$ \varphi = \forall x (f(f(x)) = x)\land (\neg f(x) = x) $$
求 $\mathrm{Sp}(\varphi)$ .

首先，取 $x\in A$ ，则有

\[ f(x)\ne x, f(f(x)) = x \]

令 $y = f(x)$ ，容易知道 $f(y)\ne y$ 且 $f(f(y)) = y$ ，且 $x\ne y$ ，因此对于每个 $x\in A$ ，均有一个对应的 $y = f(x)$ . 因此必须成对出现.

则对于任意自然数 $n$ ，总可以构造出如下的全域 $A$ ：

\[ A = \left\lbrace x_1,x_2,\cdots,x_n ,y_1,\cdots,y_n \right\rbrace \]

其中 $y_i = f(x_i)$ . 那么此时 $|A| = 2n$ ，因此全体偶数均在谱中. 从而 $\mathrm{Sp}(\varphi) = \left\lbrace 2n: n\in \omega \backslash \left\lbrace 0 \right\rbrace \right\rbrace$ . $\square$

选做题

给出一个一阶语言 $L$ 和一个 $L$ 语句的 $\varphi$ 的例子，使得满足：
$$ \mathrm{Sp}(\varphi) = \left\lbrace k^2|k=1,2,\cdots \right\rbrace $$

考虑一个一阶语言 $L$ 的 signature 为：

\[ (<,\cdot,+,1) \]

其中 $<$ 即为自然数的小于关系，$+,\cdot$ 分别为三元加法关系和三元乘法关系， $1$ 为常量.

$+xyz$ 即表示 $x+y=z$ ；
$\cdot xyz$ 即表示 $x\cdot y=z$ .

考虑以下语句的合取：

存在一个最大的平方数：$$ \exists x [(\neg \exists y (x<y))\land (\exists z (z\cdot z = x) )] $$
对于任意的两个数，它们要么一个是另一个的后继，要么存在某个数在它们中间，要么相等：$$ \forall x\forall y[(x=y)\lor(+x1y) \lor (+y1x)\lor (\exists z((x<z\land z<y)\lor (y<z\land z<x)))] $$

那么此时，两个语句的合取记为 $\psi$ . 首先第一个语句已经保证存在一个最大的平方数，其次.

对于其模型 $A$ ，$1\in A$ ，若仅有 $1$ ，$|A|=1$ 为平方数，随后可利用归纳法证明：有且仅有如下形式的集合 $A$ 为模型：

\[ A = \left\lbrace 1,2 ,\cdots,n^2 \right\rbrace,n\in \mathbb{N} \]

若最大的元素不为平方数，那么就和第一个语句矛盾，如果出现 $1<k< n^2$ 且 $k\notin A$ 的情况，则与第二个情形矛盾，故语句 $\psi$ 满足题意. $\square$

NKU 第三次作业

评论