1. ## Fol 4

This is another exercise problem (Exercise 3 of Section 2.4) of Enderton's "A mathematical introduction to logic".

(a) Let $\displaystyle A$ be a structure and let $\displaystyle s:V \rightarrow |A|$. Define a truth assignment $\displaystyle v$ on the set of prime formulas by $\displaystyle v(\alpha)=T$ iff $\displaystyle \models_A \alpha[s]$. Show that for any formula (prime or not), $\displaystyle \bar{v}(\alpha) = T$ iff $\displaystyle \models_A \alpha[s]$.

(b) Conclude that if $\displaystyle \Gamma$ tautologically implies $\displaystyle \phi$, then $\displaystyle \Gamma$ logically implies $\displaystyle \phi$.

==============================
What I have tried so far is

For (a), if $\displaystyle \alpha$ is a prime formula, nothing needs to be done. If $\displaystyle \alpha$ is not a prime formula, two cases have to be considered, i.e., $\displaystyle \alpha = \neg \beta$ or $\displaystyle \alpha = (\beta \rightarrow \gamma)$, where $\displaystyle \beta$ and $\displaystyle \gamma$ are both atomic formulas.

For (b), if $\displaystyle \bar{v}(\psi) = T$ for every $\displaystyle \psi \in \Gamma$, then $\displaystyle \bar{v}(\phi)=T$ by assumption. Then I need to show if $\displaystyle \models_A \psi[s]$, then $\displaystyle \models_A \phi[s]$. I am stuck here.

Any help will be appreciated.

2. ## Re: Fol 4

Originally Posted by logics
(a) Let $\displaystyle A$ be a structure and let $\displaystyle s:V \rightarrow |A|$. Define a truth assignment $\displaystyle v$ on the set of prime formulas by $\displaystyle v(\alpha)=T$ iff $\displaystyle \models_A \alpha[s]$. Show that for any formula (prime or not), $\displaystyle \bar{v}(\alpha) = T$ iff $\displaystyle \models_A \alpha[s]$.
It seems that only quantifier-free formulas are considered here.

Originally Posted by logics
For (a), if $\displaystyle \alpha$ is a prime formula, nothing needs to be done. If $\displaystyle \alpha$ is not a prime formula, two cases have to be considered, i.e., $\displaystyle \alpha = \neg \beta$ or $\displaystyle \alpha = (\beta \rightarrow \gamma)$, where $\displaystyle \beta$ and $\displaystyle \gamma$ are both atomic formulas.
You cannot assume that $\displaystyle \beta$ and $\displaystyle \gamma$ are atomic formulas (does it mean the same as prime formulas?) in the induction step. E.g., $\displaystyle (\alpha\to \alpha)\to \alpha$ where $\displaystyle \alpha$ is a prime formula has the form $\displaystyle \beta\to\gamma$, but $\displaystyle \beta$ is not prime. I assume you can finish the definition and the proof that $\displaystyle \bar{v}(\alpha) = T$ iff $\displaystyle \models_A \alpha[s]$.

Originally Posted by logics
For (b), if $\displaystyle \bar{v}(\psi) = T$ for every $\displaystyle \psi \in \Gamma$, then $\displaystyle \bar{v}(\phi)=T$ by assumption.
I believe this holds for any truth assignment v. Call this fact (*).

Originally Posted by logics
Then I need to show if $\displaystyle \models_A \psi[s]$, then $\displaystyle \models_A \phi[s]$.
Suppose $\displaystyle \models_A\psi[s]$ for every $\displaystyle \psi$ in $\displaystyle \Gamma$. Let $\displaystyle v_{A,s}$ be the truth assignment constructed from $\displaystyle A$ and $\displaystyle s$ as described in (a). Then $\displaystyle \bar{v}_{A,s}(\psi)=T$ by (a), so by putting $\displaystyle v=v_{A,s}$ in (*) we have $\displaystyle \bar{v}_{A,s}(\phi)=T$, which again by (a) implies $\displaystyle \models_A\phi[s]$.