2
$\begingroup$

For any first-order sentence $\phi$ let $$spec(\phi) = \{ n \in \mathbb{N} | \text { there exists model $m$ for $\phi$ where $|m| = n$ } \} $$

Let $$A^\Sigma = \{ \Sigma^r_{i=1} a_i | r \ge 1, a_1, ..., a_n \in A$$

Construct a such sentence $\psi $ that $spec(\psi) = spec(\phi)^\Sigma$.

My solution:

$$\psi = \bigvee_{n \in spec(\phi)^{\Sigma}} (\exists a_1 ... \exists a_n \forall a_{n+1} \bigwedge_{1 \le i,j \le n, j \neq i} \neg(a_i = a_j) \wedge \bigvee_{1 \le i \le n} (a_{n+1} = a_i) ) $$

There is no $\vee$ connector in the first order logic. But we can easily get it with $\Rightarrow$.

Is it correct?

$\endgroup$
1
+50
$\begingroup$

As @EricWofsey pointed out, your construction doesn't work because you're taking a possibly infinite disjunction, but first-order logic only has finite disjunctions.

Here's one way to go about solving the problem:

First, we can assume without loss of generality that $\varphi$ has no constant symbols. (If it has constant symbols $c_1,\dots,c_n,$ just replace $\varphi$ with the sentence $(\exists x_1)\dots(\exists x_n)\varphi(c_1/x_1,\dots,c_n/x_n),$ where the $x_i$ are variables that do not appear in $\varphi$ and where $c/x$ means to replace all occurrences of $c$ with $x.$ The resulting formula has the same spectrum as the original $\varphi,$ but has no constant symbols.)

Expand the language that $\varphi$ is written in by adding a new two-place relation symbol $R.$

Let $u$ be a variable that doesn't appear in the sentence $\varphi.$ For every formula $\chi$ in which the variable $u$ doesn't appear, we'll define a formula $\chi^*$ which has as its free variables all the free variables that appear in $\chi$ and possibly also $u.$ The definition of $\chi^*$ proceeds by induction, as follows:

  1. If $\chi$ is atomic, then $\chi^*$ is $\chi.$

  2. $(\lnot \chi)^*$ is $\lnot (\chi^*).$

  3. $(\chi_1 \lor \chi_2)^*$ is $\chi_1^* \lor \chi_2^*.$

  4. $(\chi_1 \land \chi_2)^*$ is $\chi_1^* \land \chi_2^*.$

  5. $(\exists y \,\chi)^*$ is $\exists y \,(R(u,y)\land(\chi^*)).$

  6. $(\forall y \,\chi)^*$ is $\forall y \,(R(u,y)\rightarrow (\chi^*)).$

Now define the sentence $\psi$ to be $$(\forall y)(\exists!u)R(u,y)\,\land\,(\forall u)\big((\exists yR(u,y))\rightarrow \varphi^*\big).$$ (As usual, $"\!\exists!u \,P(u)\!"$ is an abbreviation for $"\!\exists u \,(P(u) \land \forall v\,(P(v)\rightarrow v=u))\!",$ where $v$ is a variable that doesn't appear in $P.)$

Let $\mathscr{M}=\langle M, \dots\rangle$ be a finite model of $\psi,$ and let $\,C\,$ be the finite set $\,\{x \in M \mid \mathscr{M}\models (\exists y)R(x,y)\}.$ For each $c\in C,$ let $\mathscr{M}_c$ be the submodel of $\mathscr{M}$ with domain $M_c=\{y\in M \mid \mathscr{M}\models R(c,y) \}.$ (Each $M_c$ is non-empty, by the definition of $C.)$

The $M_c$ are pairwise disjoint, and $\bigcup_{c\in C}M_c=M,$ because $\mathscr{M}\models (\forall y)(\exists!u)\big(R(u,y)\big).$

Next observe that that the following is true by induction on $\chi\!:\;$ If $\chi$ is any formula with free variables among $x_1, \dots, x_n$ in which the variable $u$ does not appear, then, for any $c\in C$ and any $b_1,\dots,b_n\in M_c,$ we have

$$\mathscr{M}_c\models\chi(b_1,\dots, b_n) \;\text{ iff }\; \mathscr{M}\models\chi^*(b_1,\dots,b_n,u/c),$$ where $u/c$ means that $c$ is substituted for the free variable $u$ in $\chi^*.$

We know that $\mathscr{M}\models (\forall u)\big((\exists y\,R(u,y))\rightarrow \varphi^*\big),$ so, for every $c\in C,$ $\mathscr{M}\models \varphi^*(u/c),$ and it follows that each $\mathscr{M}_c$ is a model of $\varphi.$

So each $M_c$ has cardinality in $\operatorname{spec}(\varphi).$ Since the $M_c$ form a partition of $M,$ we can conclude that the cardinality of $M$ is a finite sum of members of $\operatorname{spec}(\varphi),$ as desired.

Conversely, if $a_1, \dots, a_n \in \operatorname{spec}(\varphi),$ we can let $\mathscr{M}_k=\langle M_k,\dots\rangle$ be a model of $\varphi$ of cardinality $a_k,$ for $1\le k \le n.$ Without loss of generality, we can assume that the $M_k$ are pairwise disjoint (by replacing each $\mathscr{M}_k$ by an isomorphic copy). Let $\mathscr{M}$ be the union of the models $\mathscr{M}_k,$ with the interpretation of relation and function symbols defined to extend the corresponding relations and functions on the $M_k.$ (If a relation or function is presented with arguments from more than one $M_k,$ define the relation or function on those arguments in any way you want — it doesn't matter. As for constant symbols, we eliminated all those in our language earlier precisely because there wouldn't be any way to define interpretations of any constant symbols in $\mathscr{M}$ in a way compatible with each $\mathscr{M}_k.)$

$\mathscr{M}$ is a model for the language of $\varphi;$ we still need to specify an interpretation for $R.$ For $1\le k \le n,$ pick $c_k\in M_k.$ Define $R(x,y)$ to be true iff $x$ is some $c_k$ and $y\in M_k.$

You can check that $\mathscr{M}$ is a model of $\psi,$ and $M$ has cardinality $a_1+\dots+a_n,$ so we're done.

$\endgroup$
0
$\begingroup$

This doesn't work because $\operatorname{spec}(\phi)^\Sigma$ may be an infinite set (indeed, it is whenever $\operatorname{spec}(\phi)$ contains a nonzero element), so you can't form a disjunction indexed by its elements. You're going to need to use the fact that this set is $\operatorname{spec}(\phi)^\Sigma$, rather than just some arbitrary subset of $\mathbb{N}$. Think about what sort of structure you could axiomatize that you could think of as a "disjoint union of models of $\phi$".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy