-
set of connectives
How do we show that the set of connectives $\displaystyle \{ \to \}$ is not complete?
I'm not sure how to prove it is or it is not complete. But I know how to test for adequacy. And I know the set of standard connectives is adequate $\displaystyle \{\neg, \wedge, \vee, \to, \leftrightarrow \}$, so a set of connectives is adequate if we can express all the standard connectives in terms of this set. There is a test for adequacy of connctives. But if prove that the set is not adequate, how do we know if it failed completeness?
-
Re: set of connectives
Implication is true if both arguments are true, so by induction any function built from -> returns true when all arguments are true. Therefore, negation is not expressible.
For a characterization of completeness, see Post's theorem.