Proof explanation of invalidity implying a non-tautology

Question

In the PDF textbook, "A Friendly Introduction to Mathematical Logic 2nd Edition" by Christopher C. Leary and Lars Kristiansen, on page 54, exercise 6, I am asked to do the following:

Given that $\theta$ is some $\mathcal{L}\text{-formula}$ and $\theta_P$ is the propositional version of $\theta$, prove that :

if $\theta$ is not valid, then $\theta_P$ is not a tautology,

i.e.: prove

$$\not\vDash\theta\to\lnot(\forall v)(\bar v(\theta_P)=T)\\ \text{where $v$ is any truth assignment function, and}\\ \text{$\bar{v}$ is the extension of $v$ to any propositional formula.}$$

For clarity, I will provide some definitions given by the book.

$$v:{Var}_P\to\{T,F\}\\ \text{where ${Var}_P$ is the set of all propositional variables.}$$

$$\bar{v}(\phi)= \begin{cases} v(\phi) & \text{if $\phi$ is a propsitional variable} \\ F & \text{if $\phi=(\lnot\alpha)$ and $\bar{v}(\alpha)=T$} \\ F & \text{if $\phi=(\alpha\lor\beta)$ and $\bar{v}(\alpha)=\bar{v}(\beta)=F$}\\ T & \text{otherwise.} \end{cases} $$

$$\text{$\phi$ is a tautology} \iff (\forall v)(\bar{v}(\phi)=T) \\ \text{where $v$ is any truth assignment function.}$$

Looking at the in the exercise solutions in the back of the book on page 294, the solution goes as follows:

Let $\mathcal{L}$ be a first-order language, let $\phi$ be an $\mathcal{L}\text{-formula}$, and let $A_1, \ldots, A_n$ be the propositional variables that occur in the formula $\phi_P$.

Now, each variable in the list $A_1, \ldots, A_n$ corresponds to a subformula of $\phi$. For $i=1,\ldots,n$, let $\psi_i$ denote the subformula that corresponds to $A_i$. For any $\mathcal{L}\text{-structure } \mathfrak{U}$, we define the valuation $v_\mathfrak{U}$ by $$v_\mathfrak{U}(A_i)= \begin{cases} T & \text{if $\mathfrak{U}\vDash\psi_i$} \\ F & \text{otherwise.} \end{cases}$$ (Claim) $$\mathfrak{U}\not\vDash\phi\iff\bar{v}_\mathfrak{U}(\phi_P)=F\text{.}$$ Note that this claim is equivalent to $$\mathfrak{U}\vDash\phi\iff\bar{v}_\mathfrak{U}(\phi_P)=T\text{.}$$ We will now prove the claim by induction over the complexity of $\phi$.

Case: $\phi$ is an atomic formula. The claim follows straightforwardly from the definition of $v_\mathfrak{U}$.

Case: $\phi$ is of the form $(\forall x)(\alpha)$. The claim follows straightforwardly from the definition of $v_\mathfrak{U}$.

Case: $\phi$ is of the form $(\lnot\alpha)$. We have $$\mathfrak{U}\not\vDash(\lnot\alpha)\iff\mathfrak{U}\vDash\alpha\iff\bar{v}_\mathfrak{U}(\alpha_P)=T\iff\bar{v}_\mathfrak{U}((\lnot\alpha)_p)=F$$ The second equivalence follows by our induction hypothesis. Case: $\phi$ is of the form $(\alpha\lor\beta)$. $$\begin{align} \mathfrak{U}\not\vDash &\iff \mathfrak{U}\not\vDash\alpha\text{ and }\mathfrak{U}\not\vDash\beta \\ &\iff \bar{v}_\mathfrak{U}(\alpha_P)=F\text{ and }\bar{v}_\mathfrak{U}(\beta_P)=F && \text{(ind. hyp.)}\\ &\iff \bar{v}_\mathfrak{U}((\alpha\lor\beta)_P)=F \end{align} $$ This completes the proof of (Claim)

Now, assume that the first-order formula $\theta$ is not valid. By the definition of validity, there exists a structure $\mathfrak{U}$ such that $\mathfrak{U}\not\vDash\theta$. By (Claim) there exists a valuation $v$ such that $\bar{v}(\theta_P)=F$. Thus, by the definition of a tautology, $\theta_P$ is not a tautology. Hence, if $\theta_P$ is a tautology, then $\theta$ is valid.

The problem I'm having with this proof is the definition of $v_\mathfrak{U}$. Previously, the author states on page 52,

Notice that if $\beta_P$ is a tautology, then $\beta$ is valid, but the converse of this statement fails. For example, if $\beta$ is $$[(\forall x)(\theta)\land(\forall x)(\theta\to p)]\to(\forall x)(p),$$ then $\beta$ is valid, but $\beta_P$ would be $[A\land B]\to C$, which is certainly not a tautology.

The author builds $v_\mathfrak{U}$ such that if $\mathfrak{U}\vDash\phi$, then $\bar{v}_\mathfrak{U}(\phi_P)=T$, but just because $\phi$ is valid does not mean it is a tautology (as the author admits above). When I interpret $v_\mathfrak{U}$ within the proof, I see it as building a connection between the truth-hood of of $\phi$ within the $\mathcal{L}\text{-structure } \mathfrak{U}$ and the tautologous-ness of $\phi_P$ in propositional logic. Assuming my understanding is correct, this would imply a contradiction within (Claim) which conflicts with the author's statement I quoted above.

In short, this proof given by the author for exercise 6 is speciously incorrect because I believe the author appears to erroneously define function $v_\mathfrak{U}$. I can't see what I'm doing wrong or what I'm not seeing. Can someone explain this proof to me and debunk my misunderstanding?

Answer 1

Firstly, we have to convince ourselves that there are valid formulas $\theta$ whose "propositional reduct" $\theta_P$ is not a tautology.

Consider for simplicity the valid formula : $\forall x (x=x)$ as $\theta$. We have that $\theta_P$ is $A_1$, which clearly is not a tautology.

Thus, it is not true that :

$\theta \text { is valid iff } \theta_P \text { is a tautology.}$

But we want to prove the other part :

$\text { if } \theta_P \text { is a tautology, then } \theta \text { is valid,}$

and we do this by contraposition, i.e. showing that :

$\text { if } \theta \text { is not valid, then } \theta_P \text { is not a tautology.}$

The proof relies on the Lemma :

Let $\phi$ a formula and $\mathfrak U$ a structure; then we have a valuation $v_{\mathfrak U}$ such that $\phi$ is FALSE in $\mathfrak U$ iff (please, note the "iff") $\overline {v}_{\mathfrak U}(\phi_P)=\text{F}$.

Thus, if $\theta$ is not valid, we have an interpretation $\mathfrak U$ such that : $\mathfrak U \nvDash \theta$.

Then we manufacture the valuation $v_{\mathfrak U}$ such that $v_{\mathfrak U}(A_i)$ from $\psi_i$ as above, and the Lemma says that $\overline {v}(\theta_P)=\text{F}$.

So, we have found a valuation such that $\theta_P$ is FALSE, and this is enough to conclude that :

$\theta_P$ is not a tautology.

---

The Claim does not requires the validity of $\theta$ : it relies on the costruction of $v$ for every $\mathfrak U$, and vice versa.

Consider $\forall x \forall y(x=y)$ which is not valid. We have that $\theta_P$ is $A_1$ and clearly we can have $v$ such that $v(A_1)=\text{T}$.

Then we need to manufacture the corresponding $\mathfrak U$ such that $\mathfrak U \vDash \psi_1$, where $\psi_1$ is $\forall x \forall y(x=y)$.

It is enough to consider a domain $U = \{ a \}$.

But we can have also a different $v'$ such that : $v'(A_1)=\text{F}$.

In this case, it is enough to consider a domain $U' = \{ a, b \}$ and we have that : $\mathfrak U' \nvDash \forall x \forall y(x=y)$.