Proof by induction of inadequacy of set of propositional connectives

Question

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.

Answer 1

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.

Answer 2

You must first show that the Basis step holds.

Whay does it mean ? That a formula built up with the § connective with only one propositional variable $p$ can never be a tautology.

This is because $p§p$ must be only $True-True$ or $False-False$, and both are mapped into $False$ by the truth-table.

Having proved this, you must use it in the Induction step that "reduce" the case $\alpha § \beta$ to the verification (via the truth-table) that the property hold for it, assuming that it holds for $\alpha$ and $\beta$ (being "shorter", the induction hypotheses applies to them).

Answer 3

Your set of terms T, I take it, is the smallest subset of the set of strings, S, generated from your propositional variables P, and the symbols §, (, and ) using the production

s,t in T => (s§t) is in T. (1)

That is, T is the smallest subset of S containing P and closed under (*).

Now if we have a valuation of v: P --> {T,F} which maps every element of P to F, then let TF be the subset of T on which v has value F, that is, let TF = {t in T | v(t) = F}. Now by our choice of v, P is contained in TF. Further if s,t are in TF then by the truth table definition of §, (s§t) is in TF. Hence TF contains P and is closed under (1). But your set of terms that I have called T is the smallest subset of S containing P and closed under (1). Hence TF = T and indeed T contains no tautologies.