素数集合在(ℕ, +)中一阶可定义性的证明方法咨询

嘿，这个问题确实有点绕，毕竟咱们常用的“自同构不变性”路子在这里直接失效——没错，(ℕ, +)只有恒等自同构，任何集合都是自同构不变的，所以靠这个方法根本没法证明不可定义。不过别慌，咱们可以换个角度，从Presburger算术（也就是(ℕ, +)的一阶理论）的可定义集合性质入手。

首先得明确一个关键结论：Presburger算术里能一阶定义的集合，全都是半线性集合——简单说，就是有限个算术 progression（形如{ a + k·b | k ∈ ℕ, a,b ∈ ℕ }）的并集。比如偶数集合是{0 + 2k | k∈ℕ}，就是个典型的半线性集合；再比如“x是3或5的倍数”，就是两个算术 progression 的并。

那素数集合呢？它显然不是半线性集合。为什么？咱们反推一下：如果素数集合是半线性的，那它就得是有限个算术 progression 的并。但根据数论里的结论，没有任何无穷的算术 progression 全是素数（除了单个素数的平凡情况，但素数是无穷多的），而且素数集合也没法拆成有限个这样的progression——毕竟任意一个算术 progression a + kb，当k足够大时，总能找到其中的合数（比如当k=a时，a + a·b = a(b+1)，就是合数，只要a>1）。

所以反过来想，既然素数集合不符合Presburger算术可定义集合的特征，那它自然没法在(ℕ, +)中一阶定义。

另外还有个思路可以辅助理解：假设存在一个一阶公式φ(x)能定义素数，那我们可以用紧致性定理构造一个非标准自然数模型M。在M里，会存在一个非标准的“素数”c——但在非标准模型中，这类非标准数的性质和标准素数完全矛盾，再结合前面半线性集合的结论，就足以坐实它的不可定义性。

备注：内容来源于stack exchange，提问作者zaq