A first order sentence such that the finite spectrum of that sentence is the following subsets of $\mathbb{N}^+$.

Question

I would like to find a language $\mathcal{L}$ and first order sentence $\phi$ of $\mathcal{L}$ so that its finite spectrum is

1. $\{p^n ~:~ n > 0, \text{ p is prime}\}$

2. $\{ p ~:~ p \text{ is prime}\}$

It seems like a large library of mathematical knowledge is needed to even begin consider such questions, and I have to admit mine are thin.

Answer 1

HINT: For the first problem consider finite fields.

The trick for the second problem is to construct a language and sentence for which the finite models look enough like initial segments of the positive integers, or something very similar. One especially elegant approach uses the something very similar idea. You’ll want a language $\{+,\times,\le,',2,a,b\}$. Then write down axioms that say that

• $\le$ is a linear order,
• $2$ is the smallest element,
• $b$ is the largest element,
• $x'$ is the immediate successor of $x$ if $x<b$,
• $a<b\land a'=b$,
• $b'=b$,
• $\forall x(x+2)=x''$,
• $\forall x\forall y\big(x+y'=(x+y)'\big)$,
• $\forall x(x\times 2=x+x)$, and
• $\forall x\forall y\big(x\times y'=(x\times y)+x\big)$.

Show that if $2\le n\in\Bbb Z^+$ there is (up to isomorphism) exactly one model of these axioms of cardinality $n$, and it’s $\{2,\ldots,n\}$ with the usual ordering and operations, with $a$ interpreted as $n$ and $b$ as $n+1$, and all of the integers greater than $n$ collapsed into the single entity $b$.

Note that an integer $n>1$ is composite iff it’s the product of two smaller integers greater than $1$, so the compositeness (and hence the primality) of $a$ can be expressed in this language.

Answer 2

For the first problem consider the theory of fields in the language $\{+,-,\cdot,0,1\}$. It is well known fact that finite fields have $p^n$ elements.

For the second problem, consider the language $\{+,-,\cdot,0,1,<\}$ and the theory $T$ containing the theory of fields with additional axioms:

1. formulas saying that $<$ is irreflexive and transitive (i.e. strict order);

2. $\forall x\,(x+1\neq 0\Rightarrow x<x+1)$.

If $M$ is a finite model of $T$, then $M$ is a field with $p^n$ elements, for some prime $p$. If $M\neq \mathbb F_p$, then $M$ containes an element $a\notin \mathbb F_p$, so $a+i\neq 0$ holds, hence by the axiom 2. $a<a+1<a+2<\ldots <a+p-1<a+p=a$, which contradicts the axiom 1. Therefore $M=\mathbb F_p$, i.e. has $p$ elements.

On the other hand, you can order elements of $\mathbb F_p$ as: $0<1<2<\ldots<p-1$. This shows that $\mathbb F_p$ is a model of $T$.

Answer 3

Both sets and their complements are spectra. Consider the language $\mathcal{L}$ (which contains only predicates and equality) and the $\mathcal{L}$-sentence $A'$ I define in this answer (you will also find how the predicates I use next are defined).

Now, for 1. let $B$ be the $\mathcal{L}$-sentence saying that a prime power is the largest element in our domain: $$\exists z\,\exists v\,((\neg\exists w\, Rzw)\wedge(\neg\exists x\,\exists y\,(Rxv\wedge Ryv\wedge Qxyv))\wedge(\neg Ov)\wedge\forall x\,((\neg Ox\wedge\exists y\,Qxyz)\Rightarrow\exists w\,Qvwx)).$$

The set of prime powers is the spectrum of $A'\wedge B$, and its complement is the spectrum of $A'\wedge\neg B$.

Now, for 2. let $B$ be the $\mathcal{L}$-sentence saying that a prime number is the largest element in our domanin: $$\exists z\,((\neg\exists w\, Rzw)\wedge(\neg\exists x\,\exists y\,(Rxz\wedge Ryz\wedge Qxyz))\wedge(\neg Oz)).$$

The set of prime numbers is the spectrum of $A'\wedge B$, and its complement, the set of composite numbers, is the spectrum of $A'\wedge\neg B$.