First order logic sentence s with spec(s) = X

187 Views Asked by At

I am told that given a first order language $L$ and a sentence $s$, the spectrum of $s$ is defined as $spec(s) = (n \in N: \exists M\models s \space\wedge\space |U(M)|=n)$ meaning the spectrum of a sentence s is a set of numbers {$n$} such that models entailing s have a universe of size n (where n is a natural number).

I have been asked to find sentences such that $spec(s)=X$ for:

  1. $X=N$

  2. $X=(n\in N : n$ is even$)$

  3. $X=(n\in N : n$ is a power of $2)$

where $N$ is the set of natural numbers.

For 1. I have $s=\forall x(x=x)$

For 2. I have $s=\forall x \exists y(x\neq y \wedge f(x)=y\wedge f(f(x))=x)$

I am not sure what to do for the 3rd problem. I know that a power set of a set of n elements has a cardinality = $2^n$, and I know that a finite Boolean algebra has an underlying universe of cardinality = $2^n$, but I don't know how to form a sentence to express these facts.