Here's a solution to a close relative of $3$, namely $$\{x+y+x^y: x,y\ge 2\}.$$
The idea is that $x^y$ counts the number of functions from a set with $y$ elements to a set with $x$ elements.
We start with the language consisting of three unary predicates $X,Y,F$ and a ternary relation $A$. Our axioms say:
$X,Y,F$ partition the domain, and $X$ and $Y$ each have at least two elements.
$A\subseteq F\times Y\times X$. Intuitively, elements of $F$ represent functions from $Y$ to $X$, and $A(f,x,y)$ means $f(x)=y$.
For all $f,y,x_1,x_2$, we have $A(f,y,x_1)\wedge A(f,y,x_2)\rightarrow x_1=x_2$; and similarly, each element of $F$ describes a total function from $Y$ to $X$.
Now a model of the theory so far amounts to a pair of sets $X,Y$ and some family of functions between them. We have to ensure that every function "appears in the $F$-part" - at least, as long as $X$ and $Y$ are finite (note that Lowenheim-Skolem implies that we can't do this for infinite $X$ and $Y$). We can do this via a cute trick:
Ensure that each constant function is "represented" in $F$, and then say that if $f$ is "represented" in $F$ and $g$ differs from $f$ in a single value then $g$ is "represented" in $F$ too.
Putting everything we have so far together we get a single sentence whose spectrum is the desired set. Now, do you see how to shift from "$x+y+x^y$" to the desired "$x^y$"? (HINT: let some elements of the structure "do double-duty.")
EDIT: note that the general strategy in the above was, "figure out a 'combinatorial story' that the set of numbers has, then tell it possibly with auxiliary sets, then if necessary 'fold in' those auxiliary sets appropriately." The same strategy, at least as I construe it, also describes Atticus' answer addressing your other question.
The approach I suggested in the update works. In order to remove the question from the unanswered list here are the details.
The equivalence of approach A and approach B for $L$-sentences means the following:
Let $M$ be any $L$-structure such that every element in the domain of $M$ has a name in $L$. Let $\alpha$ be any assignment. Let $\varphi$ be any $L$-sentence. Then $v_{M}(\varphi) = v_{M,\alpha}(\varphi)$
The proof can be easily carried out by induction on the degree (number of connectives and quantifiers) of $L$-sentences once the lemma in the update of the question is proven. Indeed, for atomic $L$-sentences it is straightforward from part 1 of the lemma. For the inductive steps, it is also straightforward for the connectives. If $\varphi$ is of the form $\exists x\,\phi$, then $v_{M}(\varphi) = \mathsf{T}$ iff $v_{M}(\phi[x/c])=\mathsf{T}$ for some constant $c\in L$ iff (induction hypothesis) $v_{M,\alpha}(\phi[x/c]) = \mathsf{T}$ for some constant $c\in L$ iff (by part 2 of the lemma for $s=c$ and $a=c^{M}$) $v_{M,\alpha_{u}^{x}}(\phi)=\mathsf{T}$ for some $u\in U_{M}$ iff $v_{M,\alpha}(\varphi)=\mathsf{T}$. And we are done.
The proof of the lemma can be carried out as follows:
For part 1, by term induction: If $t$ is the variable $x$, then $r$ is simply $x$ and $r^{M}[\alpha]=s^{M}[\alpha]=a=t^{M}[\alpha_{a}^{x}]$. If $t$ is the variable $y$ (different from $x$) then $r$ is just $y$ and $r^{M}[\alpha] = \alpha(y) = \alpha_{a}^{x}(y) = t^{M}[\alpha_{a}^{x}]$. The case when $t$ is a constant $c$ is clear. Finally, if $t$ has the form $ft_{1}\ldots t_{n}$ for some $n$-ary operation $f\in L$ and $L$-terms $t_{1},\ldots, t_{n}$ for which part 1 holds, then $r^{M}[\alpha] = f^{M}(t_{1}^{M}[\alpha_{a}^{x}],\ldots,t_{n}^{M}[\alpha_{a}^{x}]) = t^{M}[\alpha_{a}^{x}]$, as desired. By term induction, we are done.
For part 2, by formula induction: The case of atomic $L$-formulas is a straightforward application of part 1 of the lemma, which we have just proven. Handling the connectives is also straightforward. Regarding the quantifier $\exists$, we have two posibilities:
- $\phi$ is $\exists x\,\psi$. Then $\phi[x/s]$ is simply $\phi$ and $v_{M,\alpha}(\phi[x,s]) = v_{M,\alpha}(\phi) = v_{M,\alpha_{a}^{x}}(\phi)$ since $x$ is not free in $\phi$.
- $\phi$ is $\exists y\,\psi$, where $y$ is different from $x$, $y$ does not occurr in $s$ (if it does we can always rename $y$), and part 2 holds for $\psi$. Then $v_{M,\alpha}(\phi[x/s]) = v_{M,\alpha}(\exists y\,\psi[x/s])=\mathsf{T}$ iff $v_{M,\alpha_{b}^{y}}(\psi[x/s])=\mathsf{T}$ for some $b\in U_{M}$ iff (induction hypothesis and letting $\beta=\alpha_{b}^{y}$) $v_{M,\beta_{a}^{x}}(\psi)=\mathsf{T}$ for some $b\in U_{M}$ iff (by * and letting $\gamma=\alpha_{a}^{x}$) $v_{M,\gamma_{b}^{y}}(\psi)=\mathsf{T}$ iff $v_{M,\alpha_{a}^{x}}(\exists y\,\psi)=v_{M,\alpha_{a}^{x}}(\phi)=\mathsf{T}$, as desired. Formula induction concludes the proof.
The * explains the equivalence: it needs the hypothesis that $y$ is not in $s$ and is different from $x$ so we can have $a=s^{M}[\alpha] = s^{M}[\beta]$ and $\beta_{a}^{x} = \gamma_{b}^{y}$.
For completion, and my own understanding, I will add the third approach outlined in the comments above. Some references for this are: David Marker's Model Theory: An Introduction (2000) pages 9-11. Wilfrid Hodges' A Shorter Model Theory (1997) pages 11-13. And Elliot mendelson's Introduction to Mathematical Logic, 6th ed. (2015) pages 53-57.
Approach C:
Let $L$ be a language, and $M$ an $L$-structure, as stated at the beginning of the question. A variable context $\bar{x}$ is defined to be a finite set $\{x_{i_{1}},\ldots,x_{i_{m}}\}$ of variables of $L$. Therefore, we say that an $L$-term $t$ has context $\bar{x}$, and we write $t$ as $t[\bar{x}]$, when $\bar{x}$ is the set of variables occurring in $t$. Now, if $\bar{u}:\bar{x}\to U_{M}$ denotes an assignment of the context of $t$ (that is, $\bar{u}(x_{i_{j}}) = u_{i_{j}}\in U_{M}$, for $1\leq j\leq m$), then $t^{M}[\bar{u}]$ is defined to be the element of $U_{M}$ which is named by $t$ via the assignment $\bar{u}$. More precisely,
- If $t$ is the variable $x$, then $t^{M}[\bar{u}] = u$.
- If $t$ is the constant $c$, then $t^{M}[\bar{u}] = c^{M}$.
- If $t$ has the form $ft_{1}\ldots t_{n}$ for some $n$-ary operation $f$ and $L$-terms $t_{i}$, each having context $\bar{x}$, then $t^{M}[\bar{u}] = f^{M}(t_{1}^{M}[\bar{u}],\ldots,t_{n}^{M}[\bar{u}])$.
Note that if $t$ is variable-free (i.e., it has empty context), then $\bar{u}$ plays no role and we can simply write $t^{M}$.
Just as with terms, an $L-$formula $\varphi$ has context $\bar{x}$ if the set of variables occurring freely in $\varphi$ is $\bar{x}$. We write $\varphi$ as $\varphi[\bar{x}]$. Therefore, for an assignment $\bar{u}$ of $\bar{x}$ we can determine the truth or falsity of $\varphi[\bar{u}]$ in $M$. More precisely,
The valuation $V_{M}:\{\text{$L$-formulas}\}\to\{\mathsf{T},\mathsf{F}\}$ is defined as follows: let $\varphi$ have context $\bar{x}$ and assignment $\bar{u}$. If $\varphi$ is
- $t\dot{=}s$, then $V_{M}(\varphi[\bar{u}])=\mathsf{T}$ iff $t^{M}[\bar{u}] = s^{M}[\bar{u}]$, where $t,s$ are $L$-terms having context $\bar{x}$.
- $Rt_{1}\ldots t_{n}$, then $V_{M}(\varphi[\bar{u}]) = \mathsf{T}$ iff $(t^{M}_{1}[\bar{u}],\ldots,t_{n}^{M}[\bar{u}])\in R^{M}$, where $R$ is an $n$-ary predicate and each $t_{i}$ is an $L$-term having context $\bar{x}$.
- $\neg\phi$, then $V_{M}(\varphi[\bar{u}])=\mathsf{T}$ iff $V_{M}(\phi[\bar{u}])=\mathsf{F}$.
- $\phi\vee\psi$, then $V_{M}(\varphi[\bar{u}])=\mathsf{T}$ iff $V_{M}(\phi[\bar{u}])=\mathsf{T}$ or $V_{M}(\psi[\bar{u}])=\mathsf{T}$.
- $\exists y\,\phi$, then $V_{M}(\varphi[\bar{u}])=\mathsf{T}$ iff there is some $v\in U_{M}$ such that $V_{M}(\phi[\bar{v}])=\mathsf{T}$, where $\bar{v}$ is the assignment which sends $y\mapsto v$ and is otherwise the same as $\bar{u}$.
We define $M\vDash\varphi[\bar{u}]$ iff $V_{M}(\varphi[\bar{u}])=\mathsf{T}$. Clearly we may have defined $M\vDash\varphi[\bar{u}]$ directly by modifying the four clauses above in the obvious way.
It is straightforward to see that approaches B and C yield the same truth values for $L$-formulas, since approach C is nothing more than approach B particularized to the contexts of $L$-terms and $L$-formulas. That is, an assigment $\alpha$ is restricted to to the finite context of each $L$-term and $L$-formula. Therefore, when we ask about the truth value of an $L$-formula, we only need to think about assignments of the variables which actually appear in the $L$-formula, as Alex Kruckman points out in the comments.
Best Answer
Yes, $S$ is indeed complete. Here is an easy argument for showing this:
Lemma: Let $T$ be any first-order $L$-theory with only infinite models, and suppose $T$ is $\kappa$-categorical for some cardinal $\kappa\geqslant\max\{\aleph_0, |L|\}$. (This means that any two models of $T$ of size $\kappa$ are isomorphic.) Then $T$ is complete.
Proof: Suppose $T$ is not complete; then there is a sentence $\phi$ such that $T\not\vdash \phi$ and $T\not\vdash\neg\phi$. By the completeness theorem, there are thus $L$-structures $M$ and $M'$, each a model of $T$, such that $M\models\phi$ and $M\models\neg\phi$. By the hypothesis on $T$, $M$ and $M'$ are infinite. Thus, by the Lowenheim-Skolem theorem (in particular the "upwards" version if $|M|$, resp $|M'|$, is smaller than $\kappa$ and the "downwards" version if $|M|$, resp $|M'|$, is greater than $\kappa)$, we can find $L$-structures $N$ and $N'$ of size $\kappa$ that are elementarily equivalent to $M$ and $M'$. But this means $N\models T\cup\{\phi\}$ and $N'\models T\cup\{\neg\phi\}$; since isomorphic structures are elementarily equivalent, this contradicts that $T$ is $\kappa$-categorical. $\blacksquare$
[Note that we really do need both the assumption on $\kappa$ and the assumption that $T$ has only infinite models here. In the first case, let $T$ be your favorite incomplete theory with infinite models, and then let $(c_i)_{i\in\mathbb{R}}$ be a family of fresh constant symbols. Then $T\cup\{c_i\neq c_j:i\neq j\in\mathbb{R}\}$ is still incomplete, but it is $\aleph_0$-categorical since it has no countable models! In the second case, let $\phi$ be any countably categorical sentence with an infinite model (eg the conjunction of the theory of dense linear orders without endpoints), and let $\psi$ be a sentence in the same language with two non-isomorphic models of size $n$ for some $n\in\omega$. Then the theory $\{\exists^{=n}x(x=x)\to\psi\}\cup\{\exists^{> n}x(x=x)\to\phi\}$ is still countably categorical but is not complete.]
Okay, now note that your theory $S$ has only infinite models. Thus by the lemma we need only show that your theory $S$ is categorical in some sufficiently large cardinal $\kappa$. In fact, $S$ is categorical in any cardinal; indeed, if $M$ and $M'$ are models of $S$ with the same cardinality, let $f:M\to M'$ be any bijection such that $f(c^M)=c^{M'}$ for each constant symbol $c$ in the language. (This makes sense since $c^M$ is fixed as $c$ varies, by definition of $S$.) You can check that $f$ is a bijective $L$-embedding, hence an isomorphism, so we are done.