(Solution verification and criticism) If wff $\phi$ has no repetition of sentence letters, then $\nvDash \phi$

Question

Edit: Here is attempt number 2. I've been much more terse, which I think flows much better. I've also changed the binary connective to disjunction to improve readability as well. By truth table $\lnot\phi \to \psi$ is equivalent to $\phi \lor \psi$, so it's justified.

L1: Iff $\nvDash \phi$, then there exists a PL-interpretation, $\mathscr{I}$, such that $V_\mathscr{I}(\phi)=0$. Iff $V_\mathscr{I}(\phi)=0$, then $V_\mathscr{I}(\lnot\phi)=1$. In other words, iff $\lnot \phi$ can be satisfied, which it can be iff there exists an $\mathscr{I}$ such that $V_\mathscr{I}(\phi)=0$, then it isn't a tautology.

Base case: Let wff $\phi$ be composed of a single sentence letter with an $\mathscr{I}$ such that $V_\mathscr{I}(\phi)=0$, thus, from L1, $\nvDash \phi$.

Induction hypothesis (IH): Let $\phi$ be composed of a finite number of sentence letters that don't appear more than once. Assume it holds that an $\mathscr{I}$ exists such that $V_\mathscr{I}(\phi)=0$.

Induction step:

• From the IH, $V_\mathscr{I}(\phi)=0$, so $V_\mathscr{I}(\lnot \phi)=1$, thus $\nvDash \phi$

• Let $\psi$ be composed of a single sentence letter that doesn't appear in $\phi$ with an $\mathscr{I}$ such that V$_\mathscr{I}(\psi)=0$. It follows that $V_\mathscr{I}(\phi \lor \psi)=0$, thus $\nvDash (\phi \lor \psi)$

---

I'm really trying to up my game when it comes to proofs. I'd greatly appreciate it if someone could check that my proof is correct, and, if so, offer ways to improve readability, style, structure, etc. Thanks in advance

---

Exercise 2.8$^1$: Show that if wff $\phi$ has no repetition of sentence letters (i.e., each sentence letter occurs at most once in $\phi$) then $\nvDash \phi.$

---

Definitions:

A. Language:

• Classic propositional logic (PL)

B. Primitive Vocabulary$^2$:

• Connectives: $\to$, $\lnot$
• Sentence letters: $P, Q, R\ldots,$ with or without numerical subscripts
• Parentheses: (, )

C. Definition of wff$\,^3$:

1. Every sentence letter is a PL-wff
2. If $\phi$ and $\psi$ are PL-wffs, then $(\phi \to \psi)$ and $\lnot \phi$ are also PL-wffs
3. Only strings that can be shown to be PL-wffs using (1) and (2) are PL-wffs

D. Definition of interpretation$^4$:

• A PL-interpretation is a function $\mathscr{I}$, that assigns to each sentence letter either $1$ or $0$.

E. Definition of valuation$^5$: For any PL-interpretation, $\mathscr{I}$, the PL-valuation for $\mathscr{I}$, $V_\mathscr{I}$, is defined as the function that assigns to each wff either $1$ or $0$, and which is such that, for any sentence letter $\alpha$ and any wffs $\phi$ and $\psi$:

1. $V_\mathscr{I}(\alpha)=\mathscr{I}(\alpha)$
2. $V_\mathscr{I}(\lnot \phi)=1$ iff $V_\mathscr{I}(\phi)=0$
3. $V_\mathscr{I}(\phi \to \psi)=1$ iff either $V_\mathscr{I}(\phi)=0$ or $V_\mathscr{I}(\psi)=1$

F. Definition of validity$^6$:

• A wff $\phi$ is PL-valid, $\vDash \phi$, iff for every PL-interpretation, $\mathscr{I}$, $V_\mathscr{I}(\phi)=1$

---

Proof

We will prove (2.8) via induction.

Base case:

Let wff $\phi$ be composed of a single sentence letter, $\alpha$. From (D) we can choose a PL-interpretation, $\mathscr{I}$, such that, $\mathscr{I}(\alpha)=1$ and we can choose an $\mathscr{I}$ such that $\mathscr{I}(\alpha)=0$. From (E1), $V_\mathscr{I}(\phi)=\mathscr{I}(\alpha)$, so there exists an $\mathscr{I}$ where $V_\mathscr{I}(\phi)=1$ and there exists an $\mathscr{I}$ where $V_\mathscr{I}(\phi)=0$. Thus, there exists a PL-interpretation such that $V_\mathscr{I}(\phi)\neq 1$, so, from (F), $\nvDash \phi$.

Induction hypothesis (IH):

Let $\phi$ and $\psi$ be wffs that don't share any sentence letters, $\alpha$, or contain any $\alpha$ that occur more than once. Assume it holds that a PL-interpretation, $\mathscr{I}$, exists such that $V_\mathscr{I}(\phi)=1$ and there exists an $\mathscr{I}$ where $V_\mathscr{I}(\phi)=0$, and there exists an $\mathscr{I}$ where $V_\mathscr{I}(\psi)=1$ and there exists an $\mathscr{I}$ where $V_\mathscr{I}(\psi)=0$, and thus there exists a PL-interpretation such that $V_\mathscr{I}(\phi)\neq 1$ and $V_\mathscr{I}(\psi)\neq 1$, so $\nvDash \phi$ and $\nvDash \psi$.

Induction step:

• From the (IH), choose a PL-interpretation such that $V_\mathscr{I}(\phi)=1$. From (E2), $V_\mathscr{I}(\lnot \phi)=0$, thus $\nvDash \lnot \phi$

• From the (IH), choose a PL-interpretation such that V$_\mathscr{I}(\phi)=1$ and $V_\mathscr{I}(\psi)=0$. From (E3), $V_\mathscr{I}(\phi \to \psi)=0$, thus $\nvDash \phi \to \psi$ ■

---

$\tiny\text{1. Sider, T., 2010. Logic for philosophy. Oxford: Oxford University Press, p.55}$$\tiny\text{2. Sider, T., 2010. Logic for philosophy. Oxford: Oxford University Press, p.25}$$\tiny\text{3. Sider, T., 2010. Logic for philosophy. Oxford: Oxford University Press, p.26}$$\tiny\text{4. Sider, T., 2010. Logic for philosophy. Oxford: Oxford University Press, p.29}$$\tiny\text{5. Sider, T., 2010. Logic for philosophy. Oxford: Oxford University Press, p.30}$$\tiny\text{6. Sider, T., 2010. Logic for philosophy. Oxford: Oxford University Press, p.34}$

Answer 1

As @Taroccoesbrocco noted in the comments, we need to prove a stronger conclusion: if the wff $\phi$ has no repetition of sentence letters then $\phi$ is neither a tautology nor a contradiction.

Proof. By induction on $\phi$.

1. $\phi=\alpha$ for some sentence letter $\alpha$. Pick interpretations $\mathscr{I}_1$ and $\mathscr{I}_0$ such that $\mathscr{I}_1(\alpha)=1$ and $\mathscr{I}_0(\alpha)=0$, and so $V_{\mathscr{I}_1}(\phi)=V_{\mathscr{I}_1}(\alpha)=\mathscr{I}_1(\alpha)=1$ and $V_{\mathscr{I}_0}(\phi)=V_{\mathscr{I}_0}(\alpha)=\mathscr{I}_0(\alpha)=0$ which follow that $\phi$ is neither a tautology nor a contradiction.
2. $\phi=\neg\psi$ for some $\mathrm{PL}$-$\mathrm{wff}$. By induction hypothesis that $\psi$ is neither a tautology nor a contradiction, there are some interpretations $\mathscr{I}_1$ and $\mathscr{I}_0$ such that $V_{\mathscr{I}_1}(\psi)=1$ and $V_{\mathscr{I}_0}(\psi)=0$, and so by Definition of valuation$^5$ we have $V_{\mathscr{I}_1}(\phi)=0$ and $V_{\mathscr{I}_0}(\psi)=1$ which follows that $\phi$ is neither a tautology nor a contradiction.
3. $\phi=\psi\to\theta$ for some $\mathrm{PL}$-$\mathrm{wff}$s $\psi,\theta$. By induction hypothesis that $\psi$ and $\theta$ are neither a tautologies nor contradictions, there is some interpretation $\mathscr{I}_1$ such that $V_{\mathscr{I}_1}(\psi)=1$, and there are some interpretations $\mathscr{J}_1$ and $\mathscr{J}_0$ such that $V_{\mathscr{J}_1}(\theta)=1$ and $V_{\mathscr{J}_0}(\theta)=0$.

(1) In one way, by Definition of valuation$^5$ we have $V_{\mathscr{J}_1}(\phi)=V_{\mathscr{J}_1}(\psi\to\theta)=1$ which follows that $\phi$ is not a contradiction.

(2) In another way we define ${\mathscr{I}_0}^*$ whose domain is the set of all sentence letters as follows:

$$ {\mathscr{I}_0}^*(\alpha)= \begin{cases} {\mathscr{I}_1}(\alpha)&\alpha\text{ occurs in }\psi,\\ {\mathscr{J}_0}(\alpha)&\text{otherwise.} \end{cases} $$ Since $\phi$ has no repetition of sentence letters, then ${\mathscr{I}_0}^*$ and ${\mathscr{I}_1}$ agree on sentence letters in $\psi$, and ${\mathscr{I}_0}^*$ and ${\mathscr{J}_0}$ agree on sentence letters in $\theta$. Then( by Exercise 2.7 on page 70 of your textbook) we have $V_{{\mathscr{I}_0}^*}(\psi)=1$ iff $V_{{\mathscr{I}_1}}(\psi)=1$ and $V_{{\mathscr{I}_0}^*}(\theta)=0$ iff $V_{{\mathscr{J}_0}}(\theta)=0$, and so $V_{{\mathscr{I}_0}^*}(\psi)=1$ and $V_{{\mathscr{I}_0}^*}(\theta)=0$. Therefore by Definition of valuation$^5$ we have $V_{{\mathscr{I}_0}^*}(\phi)=V_{{\mathscr{I}_0}^*}(\psi\to\theta)=0$ which follows that $\phi$ is not a tautology.

Remark. The assumption that $\phi$ has no repetition of sentence letters is used in the implication formula case.