2
$\begingroup$

Let $\mathcal L$ be a language, $n$ a positive integer and $\phi=\phi(x_1,\dots,x_n)$ an $\mathcal L$-formula having $x_1,\dots,x_n$ as free variables.

Then for every $\mathcal L$-structure $\mathfrak A$ there is a set $\phi^{\mathfrak A}$ defined by $\phi$ as: $$\phi^{\mathfrak A}:=\{(a_1,\dots,a_n)\in |\mathfrak A|^n: \mathfrak A\vDash\phi[a_1,\dots,a_n]\}$$where $|\mathfrak A|$ denotes the domain of structure $\mathfrak A$.

Now let it be that for every $\mathcal L$-structure $\mathfrak A$ we have: $$\phi^{\mathfrak A}=\varnothing\text{ or }\phi^{\mathfrak A}=|\mathfrak A|^n$$

Can we conclude from this that one of the following statements must be true?

  • $\phi^{\mathfrak A}=\varnothing$ for every $\mathcal L$-structure $\mathfrak A$.
  • $\phi^{\mathfrak A}=|\mathfrak A|^n$ for every $\mathcal L$-structure $\mathfrak A$.
$\endgroup$
1
  • 1
    $\begingroup$ No. It basically only means that $\phi$ is independent of its variables but not necessarily of the models, e g. think about $\phi(x,y)=\exists z_1,z_2:z_1\ne z_2$, it is false in a model with one element but true in other models, independently of the values of $x,y$. $\endgroup$ – Berci Nov 23 '20 at 18:56
2
$\begingroup$

No, we cannot; let $\phi'$ be any $\mathcal{L}$-sentence (so $\phi'$ contains no free variables), and let $\phi$ be the $\mathcal{L}$-formula $\phi'\wedge\bigwedge_{i=1}^nx_i=x_i$. (Note that $\phi$ does indeed contain every $x_i$ as a free variable, albeit in a vacuous way.) Then if $\mathfrak{A}\models\phi'$ we have $\phi^\mathfrak{A}=|\mathfrak{A}|^n$, and if $\mathfrak{A}\models\neg\phi'$ we have $\phi^\mathfrak{A}=\emptyset$. Since every $\mathcal{L}$-sentence either holds or does not hold in an $\mathcal{L}$-structure, one of these two cases must apply. Thus, chosing $\phi'$ so that there are some structures in which it holds and some structures in which it does not provides a countexample.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you. It is easyer than I thought. $\endgroup$ – drhab Nov 23 '20 at 19:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.