$\Sigma_{1}$-embedding in models of bounded theories

85 Views Asked by At

Let language L contains $ \leq $ and countable set of constants symbols $c_{1}, c_{2}, ... $. Is there a bounded theory T in language L, With the following property? For every model A of T, there is model B of T such that $B \preceq_{\Sigma_{1}} A $ and $ c_{i}$'s are cofinal in B. Bounded Theory means a Theory that can be axiomatized by bounded formulas. A quantifier free formula is a bounded formula and if $\varphi(x)$ is bounded, then so are $\exists x ( x\leq t \wedge \varphi (x))$ and $\forall x (x \leq t \to \varphi (x) )$, Where t is a term in language L.

1

There are 1 best solutions below

7
On

Edit: I assumed in the answer below that a "bounded theory" is axiomatized by a set of bounded sentences. But after reading the quote from Buss in your comment below, it's clear that this is not the intended definition. Rather, a bounded theory is axiomatized by a set of bounded formulas, and there's a convention in play that a formula with free variables should be interpreted as its universal closure.

So a bounded theory is one that's axiomaized by sentences of the form $\forall \overline{x}\, \psi(\overline{x})$, where $\psi$ is a bounded formula. In particular, any universal theory (like the theory of linear orders) is a bounded theory.

That means this is not an answer to the question. But I'll leave it here, since someone might find it interesting.


It's implicit in your question (since you say "cofinal") that you want $\leq$ to be a (partial) order on every model of $T$. But no consistent bounded theory implies that $\leq$ is a partial order. So this answer won't really answer your main question, but it shows you at least need to reformulate the question.

Indeed, let $M$ be a model of $T$. Let $M'$ be any structure containing $M$ such that the elements in $M'\setminus M$ are not $\leq$-related to any elements of $M$. In particular, you can make the relation $\leq$ fail to be reflexive or transitive or both on these new elements.

Now you can prove the following claim by induction: for any bounded formula $\varphi(\overline{x})$ and any $\overline{a}$ in $M$, $M\models\varphi(\overline{a})$ if and only if $M'\models\varphi(\overline{a})$. In particular $M'\models T$.

The quantifier-free case is easy. The quantifier cases are handled by the observation that $M$ contains all the terms with parameters in $M$, so any witness for a bounded quantifier has to come from $M$ (since no new element is $\leq$-related to any of these terms).