My professor told me that any formula that is satisfiable by a reduct of a model is satisfiable by the model it is a reduct of, and vice versa (as long as the formula is interpretable on the reduct(?))This seems intuitively true to me, but I want to prove it and I don't know how. I think I should use proof by induction on formulas, but I am at a loss as to what to say besides something like "It's obviously true for atomic formulas, and it's also obviously true for more complex formulas built using the formula building operations". Any ideas?
1 Answer
See Reduct of a structure $\mathcal M$ : it is obtained omitting some of the operations and relations of that structure. The domain is not affected by the "reduction".
For the question :
that any formula that is satisfiable by a reduct of a model is satisfiable by the model it is a reduct of,
we have to consider that for an atomic $P(x)$ to be satisfiable in the "reduced" structure $\mathcal M^R$ means that there is an element $a$ in the "common" domain of the two structures such that $\mathcal M^R \vDash P(x)[a]$; but then also : $\mathcal M \vDash P(x)[a]$.
This is the basis case for the induction; the cases for the connectives are strightforward ...
For the $\exists$ quantifier, the argument is the same : if there is some $a \in |\mathcal M^R|$ such that $\mathcal M^R \vDash \varphi(x)[a]$, then obviously $\mathcal M \vDash \varphi(x)[a]$, because the two structures have the same domain.
-
-
$\begingroup$ Actually, I have one more question: why don't we have to specify that the formula P(x) needs to be interpretable on the reduct in order to be satisfied by it? This may be a species of a general question--can a structure satisfy a formula made of symbols which are not in the language of the structure? It sounds like it, but why? $\endgroup$– A LePellApr 30, 2015 at 15:02
-
$\begingroup$ @ALePell - correct : to say that the formula $\varphi(x)$ is satisfiable in the reduct of $\mathcal M$ implies that it must be interpretable in it. This amount to saying that the relations and functions in it must not be affected by the "reduction" process. You have to consider some easy example to grasp the concepts : let $\mathcal N = (\mathbb N, 0, +, \times)$ and consider its reduct $\mathcal N^R = (\mathbb N, 0, +)$. Clearly the formula : $x+y=z$ is interpretable in $\mathcal N^R$ while the formula $x+(y \times w)=z$ is not ... $\endgroup$ Apr 30, 2015 at 19:20