If $X$ is a spectrum then $X^2$ is a spectrum

Question

Suppose that $X$ is a spectrum, say of a sentence $\varphi$. Let $$X^{2}:=\{n^2:n\in X\}.$$ See this related question. However, I am looking for a direct argument.

I thought about using two equivalence relations $R$ and $S$ ("rows" and "columns"), each having at least one equivalence class, rows and columns having equal cardinality, and intersecting in exactly one point. But I don't know how to add $\varphi$ appropriately to this in order to obtain a sentence whose spectrum is $X^2$.

---

Edit: I think the way to add $\varphi$ is by saying that $\varphi$ holds in a structure whose domain is a row or a column in the square. In other words, to relativize $\varphi$ to that row or column. But how do I do this formally?

Answer 1

The language must contain an additional unary predicate in order to be able to express that there is a one-to-one correspondence between the elements of a row and the elements of a column. See the comments by Atticus Stonestrom and this.

The additional predicate $P$ intuitively means our domain has a diagonal, i.e. its elements are arranged in a square matrix. Therefore, $Px$ means $x$ is in the diagonal. Finally, we want the diagonal to be the domain of a model of the sentence $\varphi$, whose spectrum is $X$. More formally:

The sentence $\varphi$ whose spectrum if the set $X$ is expressed in some language $\mathcal{L}$ (with identity). Consider two new binary predicates $R$ and $S$ and a new unary predicate $P$. Consider the langugage $\mathcal{K}=\mathcal{L}\cup\{R,S,P\}$ and the $\mathcal{K}$-sentence $\psi$ to be the conjunction of the following clauses:

1. $\forall x\, Rxx$, $\forall x\, Sxx$
2. $\forall x\,\forall y\, (Rxy\Leftrightarrow Ryx)$, $\forall x\,\forall y\, (Sxy\Leftrightarrow Syx)$
3. $\forall x\,\forall y\,\forall z\, ((Rxy\wedge Ryz)\Rightarrow Rxz)$, $\forall x\,\forall y\,\forall z\, ((Sxy\wedge Syz)\Rightarrow Sxz)$ $R$ and $S$ are equivalence relations partitioning the elements of our universe into rows and columns
4. $\exists x\,\exists y\,Rxy$, $\exists x\,\exists y\,Sxy$ Each equivelence relation has at least one equivalence class.
5. $\forall x\,\forall y\,\exists z\,\forall t\,((Rxt\wedge Syt)\Leftrightarrow (z=t))$ Each row intersects each column in exactly one element.
6. $\forall x\,\exists y\,\exists z\,(Py\wedge Pz\wedge Rxy\wedge Sxz)$ Our universe has a diagonal, i.e. its elements are arranged in a square matrix.
7. $\varphi^{P}$ The relativization of $\varphi$ to $P$ (see this for a definition). That is, the diagonal is the domain of a model of $\varphi$.

Then $\mathrm{Spectrum}(\psi)=X^{2}$, as desired.

I agree with Atticus Stonestrom that it is cleaner to modify one of the two approaches described here. In the comments above Atticus describes the modification necessary for his approach. Regarding mine, we add a new binary predicate $R$, and $Q$ can be taken as $\neg P$ in 1. 2. and 3. so that 1. becomes simply $\varphi^P$. Then we add to the conjunction the sentences expressing that $R$ is the graph of a one-to-one correspondence between $P$ and $\neg P$. The sentence thus obtained has spectrum $X^2$.

More formally, Consider the language $J=L\cup\{P,R,H\}$, where the $\varphi$ is an $\mathcal{L}$-sentence whose spectrum is $X$, the unary predicate $P$ and the ternary predicate $H$ are as in the linked question on the previous paragraph, and $R$ is a new binary predicate.

Then, the $\mathcal{J}$-sentence $\psi$ will be the conjunction of the following clauses:

1. $\varphi^{P}$
2. $\forall x\,\forall y\,((Px\wedge (\neg Py))\Rightarrow\exists z\,\forall t\,(Hxyt\Leftrightarrow (z=t)))$
3. $\forall z\,((\exists x\,\exists y\,\forall t\,((Pt\Leftrightarrow (x=t))\wedge((\neg Pt)\Leftrightarrow (y=t))))\wedge Hxyz)$
4. $\forall x\,(Px\Rightarrow\exists y\,((\neg Py)\wedge Rxy\wedge\forall t\,(Rxt\Rightarrow (y=t))))$
5. $\forall y\,((\neg Py)\Rightarrow\exists x\,(Px\wedge Rxy\wedge\forall t\,(Rty\Rightarrow (x=t))))$.

$\mathrm{Spectrum}(\psi)=X^{2}$, as desired.

Answer 2

We may directly use $\sigma, \tau$ in $J$ from @Atticus_Stonestrom's answer to express there is a bijection from $\{x:P(x)\}$ and $\{y: Q(y)\}$, i.e. we add the sentences:

$$\forall x, P(x)\rightarrow \pi(\sigma(x))=x$$ $$\forall y, Q(y)\rightarrow \sigma(\pi(y))=y$$