3
$\begingroup$

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\}$?

$\endgroup$
9
  • 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, 2015 at 22:21
  • $\begingroup$ @BrianO Nice, I did not think it would be that simple! $\endgroup$
    – Noah Schweber
    Nov 14, 2015 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, 2015 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, 2015 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, 2015 at 23:24

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .