[Math] Proof by induction of inadequacy of set of propositional connectives

logic

So we have to show that given a particular set of propositional connectives that the set is not adequate. I am comfortable with what a set being adequate means but I can't get my head around why the proof by induction works and is sufficient. This is a question and solution which is given in my notes:

"Q) Prove that the connective § with truth table shown below is not adequate.

$$\begin{array}{cc|c}
p & q & p§q \\ \hline
T& T& F\\
T& F& F\\
F& T& T\\
F& F & F\\
\end{array}$$

A) We prove by induction on complexity of terms, that for any term built
up from a set L of propositional variables using § only – let us denote the set of
such terms by Term§(L) – and for any valuation v, if v(p) = F for every p ∈ L,
then v(s) = F for every s ∈ Term§(L). That will be enough since then there
will be no term in Term§(L) which is a tautology.

Base case (s a propositional variable): this is our hypothesis.

Induction step (just one): Suppose that s = t§u where, by induction, we
may assume that v(t) = F = v(u). Then, consulting the truth table for §, we
see that v(s) = F, as required."

I understand why the result shows that the set is not adequate as it shows that there is no term that can be built from the connectives that make a tautology, however I don't understand the assumption that:

"If v(p) = F for every p ∈ L, then v(s) = F for every s ∈ Term§(L)"

How can we just make this assumption? What about the valuations where v(p) = T? Don't they need to be accounted for? Struggling with the whole idea with the proof on complexity on terms so thanks for reading.

Best Answer

  1. I think you agree that in order to show that § is inadequate, it is enough to show that there is no way to express a tautology with just §.

  2. A tautology is a term $t$ whose value $v(t)$ is true for every assignment of values to the variables of $t$.

  3. If there is any assignment of values to $t$'s variables that results in $t$ having a false value, then $t$ is not a tautology.

  4. In particular, if assigning false values to all the variables of $t$ results in $t$ having a false value also, then $t$ is not a tautology. (This is the crucial point that seems to be giving you trouble.)

  5. But it is the case that if $t$ is made of only §, then assigning false values to all its variables results in $t$ also having a false value. (This is the step that is justified by the induction proof.)

  6. Therefore, any term $t$ made of only § is not a tautology.

  7. Therefore, § is not adequate.

Is this clearer now?

You said you don't understand how to go from step 3 to step 4.

Consider this silly example, which follows the same pattern:

  1. A paradise is a country where every inhabitant is happy.
  2. Gaston, who lives in France, is not happy.
  3. Therefore, France is not a paradise.

“But,” you say, “why don't we have to consider Pierre? Pierre also lives in France!”

Pierre doesn't matter. France is only a paradise if every person in France is happy. To show that France is not a paradise, we only have to find one person in France who is not happy.

  1. A tautology is a term for which every assignment of values to its variables results in its having a true value.
  2. Assigning all false values to the variables of the term $t$ results in $t$ having a false value.
  3. Therefore, $t$ is not a tautology.

“But,” you say, “why don't we have to consider other assignments of values to the variables of $t$? Those are assignments too!”

Those assignments don't matter. $t$ is only a tautology if every assignment results in $t$ having a true value. To show that $t$ is not a tautology, we only have to find one assignment that results in $t$ having a false value.

Related Question