Validity of Induction Proof - $\{ \land, \top, \bot \}$ is an incomplete set of connectives

83 Views Asked by At

I need to verify a proof of the fact that $\{ \land, \top, \bot \}$ is not complete.

I consider $\top$ and $\bot$ to be $0$-ary logical connectives that are constantly true or false. That is for any truth assignment $v,$ the connective $ \bot $ operates on the empty set to return $v(\bot) = F$

Proof: Let $C$ be the set of formulas generated from the propositional variables by the above connectives. Let $S$ be set of formulas $\alpha$ such that for every truth assignment $v$ involving its propositional variables, $ \overline{v}(\alpha)= F $ if $ v(X) = F $ for at least one variable $X$ in $\alpha$.

All the propositional symbols are in $S$. Suppose $\alpha, \beta$ are arbitrary formulas in $S$. It can be seen that $ (\alpha \land \beta), (\alpha \land \bot) $ and $ (\alpha \land \top) $ are all in $S$. Hence by induction on complexity, $S = C$.

Hence no formula in $C$ can model $(\lnot A)$ for a propositional symbol $A$.

$\mathscr Q.E.D.$

My issue is with the incorporation of $ \{ \top, \bot \}$ in the induction process. Is my method correct? Or should I first say that all the variables are in $S$. Then take $S' = S \cup \{ \top, \bot \} $ and use the induction argument on $S'$. I think the text I use, Enderton, fails to specify how these $0$-ary connectives act in the generation process of formulas. Any help would be appreciated. Thanks in advance.