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?


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.