Let L be a language without identity and with at least one constant.
Let σ = ∃x1 ··· xnϕ(x1,...,xn), where σ is a formula in predicate logic.
Let Σ = {ϕ(t1,...,tn)|tᵢ closed in L}, where ϕ is quantifier free.
I want to show that:
(i) ⊨ σ ⇔ each structure A is a model of at least one sentence in Σ. (Hint: for each A, look at the substructure generated by ∅.)
(ii) Consider Σ as a set of propositions. Show that for each valuation v (in the sense of propositional logic) there is a model A such that v(ϕ(t1,...,tn)) = the interpretation of ϕ(t1,...,tn) in A, for all ϕ(t1,...tn) ∈ Σ.
This question is pg.134 #16 of Logic and Structure by Van Dalen.
My attempt to answer:
For (i), I know that ⊨ σ iff every structure A is a model of ϕ(t1,...,tn) for some t1,...,tn in A's domain. But how do I show that this means each structure A is a model of at least one sentence in Σ? I followed the hint and constructed the substructure generated by ∅, which is just a structure with its domain consisting of the constants of A and terms involving the constants (definition of substructure generated by a set in this linked image). This substructure satisfy σ. I also know that ϕ(t1,...,tn) is true independent of what t1,...,tn are. I don’t know how these facts relate to L and how to continue from here.
For (ii), I'm thinking ϕ implies ϕ, so it is consistent and has a model but I feel this is wrong and I'm not sure where to correctly begin.
Help is appreciated.
(i) Given a model $A$, the substructure $A^0$ generated by $\emptyset$ is the set of (the $A$-interpretations of) all terms that only involve constant symbols (these are the 'closed terms' occuring in the definition of $\Sigma$).
For example, if the language contains $1$ as a constant symbol and $+$ as a binary operation symbol, then $((1+1)+1)+(1+1)$ is a closed term. In the usual model on $\Bbb N$, this term is interpreted as $5\in\Bbb N$.
By hypothesis, $A^0$ satisfies $\sigma$, so there are elements $t_i'\in A^0$ such that $\varphi(t_1',\dots,t_n')$ is true.
But the elements of $A^0$ all belong to some closed terms, i.e. there are closed terms $t_i$ that are interpreted exactly as $t_i'$. Note that the interpretation of constants and operations on $A^0$ is inherited from $A$, hence $$A\models\varphi(t_1,\dots,t_n)\,.$$
(ii) Here we introduce a propositional variable $P_\sigma$ for each $\sigma\in\Sigma$.
Let's assume that a valuation $v:\{P_\sigma:\sigma\in\Sigma\}\to\{\top,\bot\}$ is given.
We need a first order model $A$ such that $A\models\sigma\iff v(P_\sigma)=\top$.
The trick is that we can naturally define the constants and operations on the syntactic set $C$ of closed terms.
We still need to interpret the relation symbols on $C$ to obtain a model.
Since the language contains no $=$ sign, its quantifier-free formulas are built up by the relation symbols of the language and Boolean connectives.
One typically proceeds by formula induction on $\varphi$.
If $\varphi=R(t_1,\dots,t_n)$ with $t_i\in C$ and $R$ an $n$-ary relation symbol, then we can simply interpret $R$ in $C$ according to the given valuation $v$.
Can you continue with the Boolean connectives part of the formula induction?