Negation, material equivalence, and conditioned nonconjunction: completeness and duality.
Gerald J. Massey · Notre Dame Journal of Formal Logic · 1977
Object of paperThe object of this paper is threefold: to prove the functional incompleteness of {~, =} without appeal to a tedious analysis of cases; to give a proof simpler than the one in [2], p. 284 f., of the nonexistence of indigenous Sheffer connectives for {~, =}; and to furnish self-dual (in Church's sense) ternary Sheffer connectives for propositional logic.2 Functional incompleteness of{~, =} Lemma 1 Let A be a propositional wff containing no connectives other than ~ and =, and let A 1 be the wff that results when all occurrences of ~ in A are deleted.Then A is equivalent to A 1 or to ~Ar .Proof: Let signify (semantic) equivalence.Since B ~~B and since ~(B = C)#=>~J3 = CΦΦB = ~C, Lemma 1 follows from the substitutivity of equivalents by induction.Theorem 1 {~, =} is functionally incomplete.Proof: We call a truth-value a a fixed point for a wff B just in case the value of B is a when all its variables are assigned the value a, and we say that of is a fixed point for an ra-ary connective ® just in case a is a fixed point for Θ(/>i, . ..,/>").Notice that t is a fixed point for = and for any wff that contains no connectives other than =.Suppose that & is definable from {~, =}.Then by Lemma 1 there is a wff A(p, a) containing no connectives other than = such that p & q is equivalent to A(p, a) or to ~A(p, a).But since t is a fixed point for both p & q and A{p, a), p & q cannot be equivalent to ~A (p, q).So, p & qA(p, a).Therefore, p & ~q~A(p, q).So, ~(P 8ι~q) < ^Ά(p, q)ΦΦp &, q, which is a contradiction.So & is not definable from {~, =}.Theorem 1 follows.3 Indigenous Sheffer connectives An n-ary connective ® is said to be a