2
$\begingroup$

Let $T$ be a theory in a first order language $\tau$. Let $T_\forall$ be set of all formulas $\varphi$ of the form $\forall x \psi$, where $\psi$ is quantifier-free, such that $T\vDash \varphi$. Then for all $\tau$-structures $\mathcal{A}$, $\mathcal{A} \vDash T_\forall$ iff there exists a $\tau$-structure $\mathcal{M}$ such that $\mathcal{A} \subseteq \mathcal{M}$ and $\mathcal{M} \vDash T$.

Maybe it is an easy problem, but I don't know how to deal with it. I can't seem to be able to construct a model $\mathcal{M}$ starting with $\mathcal{A}$.

Can anyone maybe give me some tips?

| cite | improve this question | | | | |
$\endgroup$
4
$\begingroup$

First, as written this is not true: you need $T_\forall$ to contain formulas with any number of universal quantifiers at the start (and no other quantifiers), not just a single universal quantifier. (Maybe you meant this implicitly, with the $x$ in $\forall x\psi$ actually standing for a tuple of variables.) Given the corrected statement, here is what you can do.

Typically the main tool to construct a model like this is compactness. In this case, to express that $\mathcal{M}$ contains $\mathcal{A}$ as a substructure you'll need to extend the language, and then you want to show that $T$ together with axioms saying that $\mathcal{A}$ is a substructure is finitely satisfiable.

A more detailed sketch of the proof is hidden below.

Add a constant symbol to $\tau$ for each element of $\mathcal{A}$. Let $S$ be the theory consisting of all quantifier-free sentences over this enlarged language that are true in $\mathcal{A}$. Note that a model of $S$ is exactly a $\tau$-structure that contains a substructure isomorphic to $\mathcal{A}$. So, we just have to show that $S\cup T$ has a model. But for any finite $S_0\subset S$, taking the conjunction of its elements and replacing its constants for elements of $\mathcal{A}$ with variables, we get a single quantifier-free formula $\psi$ over $\tau$ such that $\forall x_1\dots\forall x_n\neg\psi\not\in T_\forall$ (since $\mathcal{A}\models T_\forall$). Thus $T\not\models \forall x_1\dots\forall x_n\neg\psi$ and so $T\cup S_0$ is consistent.

| cite | improve this answer | | | | |
$\endgroup$

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.