The Sheffer stroke (https://en.wikipedia.org/wiki/Sheffer_stroke) is functionally complete: any truth-functional connective (such as $\wedge, \vee, \rightarrow$, . . .) can be represented purely in terms of the stroke.

My question is about a version of the Sheffer stroke for a certain subclass of formulas:

Say that a (propositional) sentence $\varphi$ is essentially positive if it is satisfied by the assignment making every propositional variable "true." It is a good exercise to show that all such sentences can be expressed using only the connectives "$\wedge$" and "$\implies$"; see e.g. A formula $\phi$ is logically equivalent to a another formula which contains only propositional variables and the connectives $\wedge$ and $\to$. Moreover, any sentence expressible just using "$\wedge$" and "$\implies$" is essentially positive.

My question is: can we make do with a single connective? Specifically:

Is there a single truth-functional such that the sentences expressible using that functional as a connective are exactly the essentially positive formulas?

It's pretty easy to see that there isn't such an operation which is binary, just by enumerating the possibilities, but there isn't an obvious reason why the simplest such functional couldn't be 15-ary, say.

More generally,

Suppose I have a finite collection of truth-functional connectives $\{C_i: i\in I\}$. When is there a single truth-functional connective $C$ such that the sentences expressible using $C$ are exactly those expressible using $\{C_i: i\in I\}$?

  • 2
    $\begingroup$ Re your first question, this ternary connective should do the trick: $$\triangleleft(A,B,C) := (A\Rightarrow(B\land C)).$$ In terms of this, we can define $A\Rightarrow B := \triangleleft(A,A,B)$ and then $A\land B := \triangleleft(A\Rightarrow A,A,B)$. Clearly, $\triangleleft$ and $\Rightarrow, \land$ are inter-expressible, so the sentences that each set generates are the same, i.e. the essentially positive ones. // I have to think more about the more general case. $\endgroup$ – BrianO Nov 14 '15 at 22:21
  • $\begingroup$ @BrianO Nice, I did not think it would be that simple! $\endgroup$ – Noah Schweber Nov 14 '15 at 22:33
  • $\begingroup$ @BrianO: although it is not so hard in retrospect, that would make a reasonable answer to the question $\endgroup$ – Carl Mummert Nov 14 '15 at 22:56
  • $\begingroup$ @CarlMummert OK I'll take you up on that, merci. It's a reasonable half-answer, anyway. $\endgroup$ – BrianO Nov 14 '15 at 23:05
  • $\begingroup$ Re the general question, for infinite $I$, perhaps there are two cases to consider: (1) the set of sentences $S$ expressible using the $C_i$ can be finitely generated, i.e. for some finite set of connectives $\{C'_j\mid j\in J\}$, not necessarily among the $C_i$, $S$ is the sentences expressible using the $C'_j$, and (2) $S$ is not finitely generated. In case (2), of course there's no such connective $C$; showing that the case isn't vacuous may just be a cardinality argument. I'm considering the question in between other things, so.. take what I just said with a brick of salt. $\endgroup$ – BrianO Nov 14 '15 at 23:24

Your first question has a simple answer — this ternary connective does the trick: $$\triangleright(A,B,C):=(A\Rightarrow(B\land C)).$$

In terms of this connective, we can define $$A\Rightarrow B:=\triangleright(A,A,B)$$ and then $$A\land B:=\triangleright(A\Rightarrow A,A,B). $$

Clearly, $\{\triangleright\}$ and $\{\Rightarrow,\land\}$ are inter-expressible, so the (truth functions corresponding to the) sentences that each set generates are the same, i.e. the essentially positive ones.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.