# Prove that any formula built up from $¬$ and $→$ in which no propositional variable occurs more than once cannot be a tautology.

Prove that any formula built up from $¬$ and $→$ in which no propositional variable occurs more than once cannot be a tautology.

If repeating propositional variable is allowed, then a tautology with a conditional would be easy; for $\psi\to\psi$ it will always be true regardless of $v(\psi)$. So if the question only concerns formulae built from $\to$ I can easily make up a truth assignment for, say, $\psi\to\theta$ such that it is false.

But the question concerns formulae built with both $\lnot$ and $\to$, and I cannot even think of a scenario where even repeating propositional variable would make any such formula a tautology. It seems natural to think that any such formula with no repeating propositional variable must be contingent, and cannot be a tautology.

For example, say, $\lnot(\psi\to\theta)$, if $v(\psi)$=F and $v(\theta)$=T, then the formula would be false. This would already serve as a counterexample to the opposite of the claim, i.e. 'that any formula built up from $¬$ and $→$ in which no propositional variable occurs more than once CAN be a tautology.'

In other words, the question seems too easy. I must have misunderstood the question somewhere. Could anyone please help?

• Well, while it seems 'too easy', you still need to prove it ... but you have the right idea: Just show how you can always make any such statement false. ... And I would use induction for that (structural induction!) :) Do you see how such a proof would go? – Bram28 Oct 30 '17 at 15:26
• Note that as part of the induction @Bram28 suggests, you also have to show that you can always make any such statement true ... – Henning Makholm Oct 30 '17 at 15:30
• @DanielMak: No, that doesn't work -- you can't disprove a statement of the form "such and such can hold" by using a counterexample. – Henning Makholm Oct 30 '17 at 15:32
• Yes, Henning is correct: since you have a $\neg$ to work with, the inductive proof is only going to work if you can show that you can make any such statement true as well as false, i.e. that any such statement is a contingency – Bram28 Oct 30 '17 at 15:32
• To state that a formula is not a tautology (ignore the cannot, they just mean is not) is to state that there exists an assignment of variables to make it false. Your task is to provide a proof that such an assignment exists. In this case, the proof is an algorithm which inputs a formula and outputs a variable assignment making the formula false. – DanielV Oct 30 '17 at 16:19

To prove this claim, you actually want to prove the following stronger claim:

Claim Any formula built up from $¬$ and $→$ in which no propositional variable occurs more than once is a contingent statement

(a statement $\phi$ is contingent iff there exists some valuation $v_1$ such that $v_1(\phi)=True$ as well as some valuation $v_2$ such that $v_2(\phi)=False$)

This we can prove by structural induction:

Base: Suppose $\phi$ is an atomic statement. Since we can set any atomic statement to True by some valuation, and to False by some other valuation, $\phi$ is contingent. Check!

Step: Take some $\phi$ that is built up from $¬$ and $→$ and in which no propositional variable occurs more than once. If $\phi$ is not an atomic statement, then there are only two options:

I. $\phi = \neg \psi$ for some $\psi$. Given that $\phi$ is built up from $¬$ and $→$ and in which no propositional variable occurs more than once, it follows that $\psi$ is also built up from $¬$ and $→$ and in which no propositional variable occurs more than once. We can therefore apply our inductive hypothesis that $\psi$ is a contingent statement. But, if $\psi$ is contingent, then clearly $\neg \psi$ is contingent as well, and hence $\phi$ is contingent.

II. $\phi = \phi_1 \rightarrow \phi_2$. Given that $\phi$ is built up from $¬$ and $→$ and in which no propositional variable occurs more than once, it follows that $\phi_1$ and $\phi_2$ are also built up from $¬$ and $→$ and in which no propositional variable occurs more than once. So we can apply our inductive hypothesis to $\phi_1$ and $\phi_2$, and conclude that they are both contingent. In particular, there is some valuation $v_1$ such that $v_1(\phi_1)=True$, some valuation $v_2$ such that $v_2(\phi_1)=False$, some valuation $v_3$ such that $v_3(\phi_2)=True$, some valuation $v_4$ such that $v_4(\phi_2)=False$.

Since no propositional variable occurs more than once in $\phi$, it follows that $\phi_1$ and $\phi_2$ do not share any variables. Hence, we can combine valuations $v_1$ and $v_3$ into one valuation $v_1 \cup v_3$, and it will be true that $$v_1 \cup v_3(\phi) = v_1 \cup v_3(\phi_1 \rightarrow \phi_2) = v_1 \cup v_3(\phi_1) \rightarrow v_1 \cup v_3(\phi_2) = True \rightarrow True = True$$

Likewise, $$v_1 \cup v_4(\phi) = v_1 \cup v_4(\phi_1 \rightarrow \phi_2) = v_1 \cup v_4(\phi_1) \rightarrow v_1 \cup v_4(\phi_2) = True \rightarrow False = False$$

Hence, $\phi$ is contingent.

This concludes the structural inductive proof of the Claim, and from this claim, your original statement to be proven immediately follows, for any statement that is a contingency is not a tautology.

• Thank you so so much! This is crystal clear. I didn't realise that you could assume the base case to have no overlapping variable so I was confused before I saw this. I was also stuck because at $\phi=\neg\psi$ I don't understand what would happen if $\psi$ is itself a negation; but then I realise because of the recursive definition we would have built the case for $\neg$ (ie $\psi$ being the most basic building block - a variable) such that even if $\psi$ is a $\neg$ it would have been fine. – Daniel Mak Nov 4 '17 at 16:07
• One clarifying question though; $v_1 \cup v_3(\phi_1 \rightarrow \phi_2)$ really just means we are applying both $v_1(\phi_1)=True$ and $v_3(\phi_2)=True$ to $(\phi_1 \rightarrow \phi_2)$, correct...? $v_3 \cup v_4(\phi_1)$ wouldn't make any sense because $v_3$ and $v_4$ are valuations for $\phi_2$? ie This is just what @Asaf Karagila said about the truth values of $\phi_1$ and $\phi_2$ being independent? – Daniel Mak Nov 4 '17 at 16:18
• @DanielMak $v_3 \cup v_4$ does indeed not make sense, because they are different valuations for $\phi_2$, meaning that you cannot combine them. You can combine any one of $v_1$ or $v_2$ with any one of $v_3$ or $v_4$, because the set of atomic propositions that $v_1$ and $v_2$ are defined for are those that occur in $\phi_1$, and that set is mutually exclusive from the set of atomic propositions that $v_3$ and $v_4$ are defined for, which are those that occur in $\phi_2$ (as such, you could indeed say that $\phi_1$ and $\phi_2$ are 'independent') – Bram28 Nov 4 '17 at 16:40
• "That set is mutually exclusive from the set of atomic propositions that $v_3$ and $v_4$ are defined for" because $\phi_1$ and $\phi_2$ do not have overlapping variable...of course! I get it now! Thank you so much @Bram28, you have been really patient with me, I really appreciate it. – Daniel Mak Nov 4 '17 at 17:31
• @DanielMak Yes, and now you see why the fact that there is only one instance of every atomic proposition is crucial to make this proof work, for that will imply that $\phi_1$ and $\phi_2$ share no such propositions. Glad I could help :) – Bram28 Nov 4 '17 at 17:31

First, to address your confusion, this is about negation and "strong negation". The negation of the statement "every googa is a plumbus" is "there is a googa which is not a plumbus". The "strong negation" would be "there is no googa which is a plumbus".

Here you made the switch from "every such and such sentence cannot be a tautology" to "every such and such sentence is a tautology". Of course, you contradicted the strong negation, the opposite if you will, but this is not a proof of the original statement.

Think of it this way, if $\varphi$ and $\psi$ are two propositions that have a disjoint set of propositional variables, then any assignment allows you to treat $\varphi$ and $\psi$ as a single propositional variable. Since their truth value is completely independent of one another.

This means that you can prove by induction on the structure of the proposition, that this is indeed the case.

• Thank you so much! So in 1st order logic terms, the statement is of the form $\forall xFx$, but I have only proved the strong negation $\exists x\lnot Fx$, whereas I actually need to prove $\forall x\lnot Fx$? And would you mind elaborating a bit more on treating $\varphi$ and $\psi$ as a single variable please? I am not sure what you mean by their truth values are independent of each other... – Daniel Mak Oct 31 '17 at 15:27
• What? No, that's entirely backwards... – Asaf Karagila Oct 31 '17 at 19:35

I'll give you part of the algorithm, and see if you can fill in the $\dots$ :

$$F(E) = \begin{cases} \text{if } E \text{ is of the form } \ulcorner A \to B \lrcorner & \text{return } G(A) \cup F(B) \\ \text{if } E \text{ is of the form } \ulcorner \lnot A \lrcorner & \text{return } \dots \\ \text{if } E \text{ is a propositional variable } \ulcorner A \lrcorner & \text{return } \{\ulcorner A \lrcorner \text{ as False}\} \\ \end{cases}$$

$$G(E) = \begin{cases} \text{if } E \text{ is of the form } \ulcorner A \to B \lrcorner & \text{return } \dots \\ \text{if } E \text{ is of the form } \ulcorner \lnot A \lrcorner & \text{return } \dots \\ \text{if } E \text{ is a propositional variable } \ulcorner A \lrcorner & \text{return } \{\ulcorner A \lrcorner \text{ as True}\} \\ \end{cases}$$

Fill in the dots as necessary so that the variable assignment $F(E)$ makes $E$ false.