There is given spectrum for $\phi$. Find such $\psi$ with spectrum with special property.

Question

We have spectrum for $\phi$. It is set $X$. Now, we try to find such formula $\psi$ that its spectrum is $Y=\{n+m|n,m\in X\}$. It is allowed to extend sygnature.

Being honestly, I can't deal with it, however I managed to solve some simpler problems with finding formula for spectrum.

Since I can't start I state for me other problem:
Find $Y=\{2n|n\in X\}$.
I am not sure if I can correctly solve it. However, I try to defeat it.
Lets consider universum of models for $\phi$. Now, I extend this universum - each element will be matched wit its mirror reflection - whatever what does it mean - we get universum $A'$. More precisely, each element will be have exactly one twinbrother. Then, I add relation $twins(x,y)$ has brother. Where $x$ is old element and $y$ is new element (added to uniersum $A$).
Then $\psi = \phi\wedge \forall_{x\in A} \exists!_{y\in A'}R(x,y)$

Can anyone check my reasoning, especially I ask for help with base problem.

Answer 1

You're on the right track, but your sentence $\psi$ doesn't work. A model of $\psi$ is just a model $A$ of $\phi$ expanded by the binary relation $R$ in such a way that every element $x\in A$ is related to a unique $y\in A$. Since every model of $\phi$ can be expanded in this way (for example, just take $R(x,x)$ for every $x$), the spectrum of $\psi$ is the same as the spectrum of $\phi$.

You could try to fix this by requiring that every $x\in A$ is related to a unique $y\in A$ and $x\neq y$. But then it's exactly the finite models of $\phi$ with even cardinality that can be expanded to models of $\psi$, and the spectrum of $\psi$ is $\{n\mid n\in X\text{ and } n \text{ is even}\}\neq \{2n\mid n\in X\}$.

Instead, you want to realize the following picture: A model of $\psi$ should be a model $A$ of $\phi$, together with a bunch of elements, each one a twin of some element in $A$, but sitting outside $A$. So add a new unary relation symbol $P$ to the language, and try to write down a sentence expressing

1. $\{x\mid P(x)\}$ is a model of $\phi$.
2. $R$ is the graph of a bijection between $\{x\mid P(x)\}$ and $\{y\mid \lnot P(y)\}$.

If you don't see how to do point 1, a key word to look up is relativization.

Once you see how to do that, realizing the spectrum $\{x+y\mid x,y\in X\}$ is actually a bit easier. Rather than taking a model of $\phi$ and adding a twin for each of its elements, you just need to set two models of $\phi$ side by side...

Edit 1: Here's a solution to your problem, hidden behind a Spoiler tag, as you requested.

Let $\phi$ be a sentence with spectrum $X$. Let $P$ and $Q$ be new unary relation symbols. Then $(\forall x\, ((P(x)\lor Q(x)) \land \lnot (P(x)\land Q(x)))) \land \phi^P \land \phi^Q$ (where $\phi^P$ and $\phi^Q$ are the relativizations of $\phi$ to $P$ and $Q$, respectively) has spectrum $\{n+m\mid n,m\in X\}$. This sentence asserts that the predicates $P$ and $Q$ partition the universe, and each picks out a model of $\phi$.

Edit 2: You ask in the comments about relativization. The idea is simple: The relativization $\phi^P$ of a sentence $\phi$ to a unary predicate $P(x)$ is obtained by replacing the quantifiers so they only quantify over the interpretation of $P$. That is, we replace $\forall y\, \psi(y)$ by $\forall y\, (P(y)\rightarrow \psi(y))$, and we replace $\exists y\, \psi(y)$ by $\exists y\, (P(y) \land \psi(y))$. Then you can prove by induction that a structure $A$ satisfies $\phi^P$ and only if the substructure of $A$ with domain $P$ satisfies $\phi$. For this to be true in a language with function and constant symbols, you should also add the statements that $P$ is closed under all the function symbols and contains all the constants (so that $P$ picks out the domain of a substructure). The same idea works with the unary relation $P(x)$ replaced by any formula $\theta(x)$ in one free variable.