# Sentence Connectives in Formal Logic

*First published Tue May 4, 2010; substantive revision Tue Jun 25, 2024*

Natural language sentence-linking words (like “and”,
“or”) have traditionally had aspects of their use
simulated by corresponding connectives in various systems of formal
logic. (In fact we use the word “connective” more
generously, so that there don’t have to be two or more sentences
linked, allowing us to consider the analogues of words like
“not” and “necessarily” as connectives too.)
Among the questions this enterprise has raised are the following. (1)
Which such naturally occurring sentence connectives call for a
treatment of this kind? (Which of them should be counted as
‘logical constants’?) (2) Do the aspects of their use
which are simulated in that process exhaust what we might think of as
their *meanings*, or is there typically some mismatch here? Of
course this second question depends on the particular formal treatment
given, since different logics may disagree on the formal principles
accorded to their representatives—for example in the case of
“if”, but according to one famous line of thought
(developed by H. P. Grice) when we focus specifically on their
treatment in *classical* propositional logic, any such apparent
discrepancies can be explained away by appeal to pragmatic principles
regulating ordinary cooperative conversation, and do not reflect
differences of meaning (semantic differences).

Neither question (1) nor question (2) will be addressed here. Instead,
this entry focusses on the properties of—and relations
between—the formal representatives of these connectives.
Examples of such properties include truth-functionality and a
replacement property called congruentiality, and of such relations
what we call the *subconnective* relation—relating one
connective to another when (roughly speaking) every logical principle
holding for the first of a pair of connectives also holds for the
second. In fact, all of these concepts are subject to a further
relativity. For instance a connective is or is not congruential
*according to* a given logic, with a similar relativity in the
case of whether one connective is a subconnective of another. On the
other hand, as truth-functionality is defined below, a connective is
or is not truth-functional *with respect to* a class of
truth-value assignments—and various interesting further
relations give rise to a corresponding logic-relative version of this
concept depending on the different ways a class of truth-value
assignments is linked to a logic (which in turn depends on how we
think of a logic—as an ordinary consequence relation, for
example, or as a ‘multiple conclusion’ consequence
relation: see further note 1 below). For some other properties, the
further relativity is a bit different. For example, whether a given
connective is *uniquely characterized*—in the sense of
being governed by rules which when reduplicated to govern a new
connective render compounds formed from the same component sentences
using the original and the new connective completely
interchangeable—is relative not just to a logic but to a
particular proof system (set of rules systematizing the logic).

Section 1 introduces the idea of formal sentential languages as
(absolutely free) algebras, their primitive connectives having the
status of the fundamental operations of these algebras, and explains
the notion of a consequence relation on such a language. At a more
general level, Galois connections are also introduced, and a simple
observation made concerning what we call binary relational
connections, to be applied in later sections. Section 2 introduces the
fundamental idea of a valuation for a language (a bivalent truth-value
assignment to its formulas). Truth-functionality and a generalization
thereof called pseudo-truth-functionality (of a connective with
respect to a class of valuations) are explained, as well as the idea
of sequents and sequent-to-sequent rules. We then move to a more
general conception of sequents as originally conceived, allowing a set
of formulas to play the conclusion role rather than just a single
formula, as well as to the associated idea of generalized consequence
relations, emphasizing Carnap’s motivation for making this
generalization. That motivation can be summarised with reference to
one connective. We take negation as our example. Consider the
consequence relation determined by the class of all valuations on
which the usual negation truth-function is associated with the
negation connective. This can be regarded as the classical logic of
negation, at least if logics are identified with consequence
relations. Now, there are additional valuations consistent with this
consequence relation on which the negation truth-function is
*not* associated with the negation connective. (The terminology
of a valuation’s being consistent with a consequence relation is
adapted from Dana Scott. A precise definition appears in Section 2.)
But when we consider instead generalized consequence relations, the
analogous discrepancy does not arise. Section 2 includes a statement
of a result of D. Gabbay which isolates precisely the truth-functions
for which such discrepancies do not arise (roughly: generalizations of
the conjunction truth-function and various projection functions), as
well as of a result of W. Rautenberg showing that despite this
expressive weakness in the apparatus of consequence relations, they
are sufficiently discriminating—without the need to pass to
generalized consequence relations—to distinguish the logical
properties of any two truth-functions (of the same arity).

Section 3 picks up the theme of sequent-to-sequent rules, concentrating on semantic analysis in the style of J. W. Garson of such rules, and also on the existence and uniqueness of connectives satisfying given rules (a topic introduced by H. Hiż). These last two are seen to be connected with what we call cut-inductivity and id-inductivity of specifically sequent-calculus rules, via, in the former case, a proposal identifying the existence of a connective (with prescribed logical behaviour, given the perspective provided by a logic not explicitly providing such a connective) with conservative extension (of the given logic by rules for the new connective detailing that behaviour). This proposal was made by N. D. Belnap; some problems for conservative extension as a sufficient condition for granting the existence or intelligibility of a new connective with such-and-such logical properties are noted. Section 4 collects several cases of interest in which one might wonder about the existence of connectives with various such properties. For instance (this being Example 3 out of a total of seven) one might ask if it makes sense to have a 1-ary connective with the property that two applications of this connective are equivalent to a single application of (classical) negation. Section 5 assembles supplementary notes and references.

- 1. Preliminaries
- 2. Sequents and Valuations
- 3. Rules and Connectives
- 4. Selected Existence Questions
- 4.1 Conditions not Corresponding to Rules (Example 1)
- 4.2 Pollard-Style Nonconservativity (Example 2)
- 4.3 Negation by Iteration (Example 3)
- 4.4 Logical Subtraction (Example 4)
- 4.5 A Multiple Existence Question (Example 5)
- 4.6 An Example Related to Algebraizability (Example 6)
- 4.7 Two-Dimensional Isotopes of Boolean Connectives (Longer Example 7)
- 4.8 An Existence Question Related to Truth-Functions (Example 8)

- 5. Notes and Sources
- Bibliography
- Academic Tools
- Other Internet Resources
- Related Entries

## 1. Preliminaries

The connectives of the formal languages of propositional logic are
typically expected to exhibit salient features of the
sentence-connecting devices of natural languages, and especially such
devices as are regarded as items of logical vocabulary (*and*,
*or*), *not*, *if–then*,…), though it
will be no part of our concern to inquire as to what their
‘logicality’ consists in. This is an issue which arises
for expressions and constructions such as quantifiers, the identity
predicate, and so on, and not just for sentence connectives; for this
issue the entry “Logical Constants” by John MacFarlane
(2015) should be consulted. The formal languages concerned may be
taken to agree in constructing their formulas ultimately on the basis
of the same countably infinite supply of propositional
variables—or ‘sentence
letters’—\(p_1,
p_2,\ldots\), the first three of which we write for
convenience as \(p, q, r\). Where they differ
is in respect of their stock of primitive connectives. So for example,
we have the language \(\mathbf{L} =
(L, \wedge , \rightarrow , \neg , \bot)\) with (set of)
formulas \(L\) and connectives as indicated, of arities 2, 2, 1
and 0. (We have no qualms in the last two cases in speaking of
connectives, even when there are not two or more formulas to
‘connect’. Note that 0-ary or nullary connectives are
already formulas—sometimes called sentential constants—in
their own right.) As the notation suggests (with boldface capitals for
algebras and the corresponding italic capitals for their universes),
we are thinking—in the Polish tradition—of languages as
algebras, identifying the primitive connectives with the fundamental
operations of such algebras, and in particular, as absolutely free
algebras of their similarity types (in the present instance,
\(\langle 2,2,1,0\rangle)\) with the \(p_i\) as free
generators. This allows us to speak in the usual fashion of the
*main connective* of a given formula, the variables
*occurring in* and more generally the *subformulas of*
such and such a formula, and so on, without restricting ourselves to
construing the formulas as obtained specifically by concatenating
various symbols.

Alongside this ‘syntactic operation’ sense of
*connective*—explained above for the primitive
connectives and extended to derived connectives
presently—another use of the term is indispensable: to refer to
a connective with particular logical behaviour, as when people want to
compare the behaviour of intuitionistic and classical implication. In
due course we will see the notion of a consequence relation as one way
of specifying such behaviour. If \(\vdash\) is such a relation there is a
unique language in the above sense which is the language of \(\vdash\)
and we can think of this ‘logically loaded’ sense of
*connective* as applying to the ordered pair \(\langle\#,
\vdash \rangle\); thus in the case of intuitionistic implication this
would be \(\langle \rightarrow ,
\vdash_{IL}\rangle\), where
\(\vdash_{IL}\) is the consequence relation of
intuitionistic logic. (In fact it would be preferable to take
equivalence classes of such pairs under a relation of translational
equivalence but we will make no further explicit use of these ordered
pairs or any such equivalence classes, and keep this aspect of the
discussion relatively informal. Instead of saying \(\ldquo\langle\#,
\vdash \rangle\rdquo\), we will say things like \(\ldquo\#\) as it behaves
according to \(\vdash\rdquo\). It would be better still to use not
consequence relations—or the later introduced generalized
consequence relations—as the second coordinate of the
representatives \(\langle\#,\vdash \rangle\) but instead to insert here a
reference to a proof system—a set of sequent-to-sequent rules of
the kind introduced below, that is—since important differences
between logics fail to show up at the level which would individuate
them merely as consequence
relations.^{[1]})

The ‘languages as algebras’ perspective also allows us the convenience of defining matrix evaluations (see Section 5) as just homomorphisms from the algebra of formulas to the algebra of the matrix in question, of defining derived connectives and (sentential) contexts as term functions (formerly known as polynomial functions) and algebraic functions (now commonly called polynomial functions) respectively, and so on. This treatment would need some emendation were the discussion to embrace infinitary connectives, branching connectives, and various other exotic devices, but there will be enough to consider without touching on these.

For example, there is the issue raised by the use of the notation
above for the operations of \(\mathbf{L}\). Such a choice suggests
that \(\wedge , \rightarrow , \neg\) will represent conjunction, implication (or
the conditional) and negation—that is, be intended to capture
some aspect of the behaviour of *and*, *if–then*,
and *not*, respectively—and that \(\bot\) will be some kind
of falsity constant. (Similarly, while we are fixing notation, if we
had written \(\ldquo\vee\rdquo\), \(\ldquo\leftrightarrow\rdquo\), or
\(\ldquo\top\rdquo\), we would be arousing expectations of
disjunction, equivalence—or biconditionality—and a truth
constant, respectively.) We can think of this as a matter of the
inference patterns to be sanctioned by some proof system offered for
\(\mathbf{L}\), or as a matter of how the formulas of this
language are to be interpreted by assigning suitable semantic values
to them (truth-values being the simplest candidates here). We refer to
the former as a proof-theoretic or syntactical characterization of the
logic and the latter as a semantical characterization. The terminology
is somewhat unfortunate in that a perfectly respectable view in the
philosophy of logic (going back at least to Gentzen) has it that the
*meanings* of items of logical vocabulary, such as the
connectives of current concern, for a particular reasoner, are given
by a specification of the set of primitive *rules*, or a
favoured subset thereof, governing those items in a proof system
representing that reasoner’s (perhaps idealized) inferential
practices.^{[2]}
We take up some of those issues later, beginning with a reprise of
the semantical side of the story at the start of the following
section.

We need first some general preliminaries, and forgetting the intended
application(s) for a moment, let us define, given sets \(S\) and
\(T\), a pair of functions \((f, g)\) to be a
*Galois connection* between \(S\) and \(T\) when
\(f: \wp(S) \rightarrow \wp(T)\)
and \(g: \wp(T)\rightarrow \wp(S)\), and for
all \(S_0, S_1 \subseteq S,\) \(T_0, T_1 \subseteq T,\) we have
\(S_0 \subseteq g(f(S_0)),\) \(T_0 \subseteq f(g(T_0)),\) \(S_0
\subseteq S_1 \Rightarrow f(S_1) \subseteq f(S_0),\) and \(T_0
\subseteq T_1 \Rightarrow g(T_1) \subseteq g(T_0).\) It is well known
that the composition of \(g\) with \(f\) (respectively, \(f\) with
\(g)\) in such a case is a *closure operation* on \(S\)
(respectively, on \(T)\) in the sense of being a function (we do the
\(S\) case) \(C: \wp(S) \rightarrow \wp(S)\)
satisfying, for all subsets \(S_0, S_1\), of \(S\):

Further, where \(R \subseteq S \times T\), the
triple \(\langle R, S, T\rangle\), which we may
call a *binary relational connection* (between \(S\) and
\(T)\), induces a Galois connection \((f_R, g_R)\)
between \(S\) and \(T\) when we put, for all
\(S_0 \subseteq S, T_0\subseteq T\):

(\(\ldquo S\rdquo\) and \(\ldquo T\rdquo\) here are mnemonic for “Source” and “Target” respectively; note that we do not require \(S \cap T = \varnothing\), or even that \(S \ne T\).) Suppose we consider, not the sentential languages of our opening paragraph but rather first-order languages, and take \(S\) as the set of closed formulas of such a language and \(T\) as the set of models (interpretations, structures,…) for that language, then with \(R\) as the relation holding between a closed formula \(\phi\) and a structure \(\mathcal{M}\) when \(\mathcal{M} \vDash \phi , f_R (S_0)\) and \(g_R (T_0)\) are usually denoted by \(\Mod(S_0)\) and \(Th(T_0)\). (The labels are intended to suggest “class of all models of” and “theory of”, respectively.) In this case the derived closure operations \(Th\circ\Mod\) (mapping \(S_0\) to \(Th(\Mod(S_0)))\) and \(\Mod\circ Th\) (understood analogously) on \(S\) and \(T\) respectively deliver the set of first-order consequences of \(S_0\) and the set of all models verifying all the sentences verified by every \(\mathcal{M} \in T_0\). When there is only one such \(\mathcal{M}\) in the latter case, what is delivered is the class of structures elementarily equivalent to \(\mathcal{M}\). (Here we are thinking of classical first-order model theory.)

Returning to the former case: as this use of the term
‘consequences’ reminds us, a closure operation on the set
of formulas of some language is conventionally called a
*consequence operation*, and perhaps to use the notation
\(Cn(\cdot)\) rather than simply \(C(\cdot)\), though it
is often more convenient to talk in terms of the corresponding
consequence *relation*, holding between a set of formulas
\(\Gamma\) and an individual formula \(\phi\)—notated in some such way
as \(\ldquo\Gamma \Vdash \phi\rdquo\), \(\ldquo\Gamma \vdash \phi\rdquo\), etc.—when \(\phi \in Cn(\Gamma)\); when
the relation has been defined semantically it is not uncommon to press
\(\ldquo\vDash\rdquo\) into service in this role. (This will occur once
or twice below.) Certain shortcuts are usually taken with this
notation, so that one writes, for example \(\ldquo\Gamma , \Delta ,
\phi , \psi \vdash \chi\rdquo\) and \(\ldquo\vdash \phi\rdquo\) to
mean \(\ldquo\Gamma \cup \Delta \cup \{\phi ,\psi \} \vdash \chi\rdquo\) and \(\ldquo\varnothing \vdash \phi\rdquo\), respectively.
(For the moment, capital Greek letters range over sets of formulas.)
The conditions given earlier for \(C\)’s being a closure
operation can be recast as conditions definitive of a consequence
relation, conditions we do not give explicitly here. A consequence
relation \(\vdash\) on some language is *finitary* if whenever
\(\Gamma \vdash \phi\) then we have \(\Gamma_0 \vdash \phi\)
for some finite \(\Gamma_0 \subseteq \Gamma\); to be
*substitution-invariant* whenever \(\Gamma \vdash \phi\) then
\(s(\Gamma) \vdash s(\phi)\) where \(s\) is any
substitution, i.e., any endomorphism of the algebra of formulas (and
\(s(\Gamma)\) is \(\{s(\psi) \mid \psi \in \Gamma \})\);
and, finally, to be *congruential* when \(\phi \dashv \vdash \psi\) implies \(\chi(\phi) \dashv \vdash \chi(\psi)\), in which the
notation is to be understood as follows. \(\ldquo\phi \dashv \vdash \psi\rdquo\) abbreviates “\(\phi \vdash \psi\) and \(\psi \vdash \phi\rdquo\)
(and if we are decorating the turnstile \(\ldquo\vdash\rdquo\) with
superscripts or subscripts, these are written only on the \(\vdash\) and
not also on the \(\dashv\) part of the composite notation); \(\chi\) is some
formula constructed from propositional variables including at least
one, \(p_k\), say—to indicate which we
may sometimes write \(\chi = \chi(p_k)\)—and \(\chi(\phi)\), for a
formula \(\phi\), is the result of substituting \(\phi\) for all occurrences
of \(p_k\) in \(\chi\). (So \(\chi(\phi)\) is
\(s(\chi)\) for the unique substitution \(s\) for which
\(s(p_i) = p_i\) for \(i \ne k\) and
\(s(p_k) = \phi\).) The
\(\chi(\cdot)\) notation amounts to thinking of \(\chi\) as a (sentential)
*context*, and putting \(\phi\) into this context amounts to
producing the formula \(\chi(\phi)\); more generally, we can think of an
\(n\)-ary context as a formula containing \(n\)
distinguished propositional variables
\(p_{k_1},\ldots ,p_{k_n}\), say—and
perhaps additional variables
too.^{[3]}
If there are no additional variables, then the formula
\(\chi(p_{k_1},\ldots ,p_{k_n})\) can be thought
of as a derived or composite connective of the language under
consideration. Returning to the 1-ary case, when \(\phi \dashv \vdash \psi\) we describe \(\phi\) and \(\psi\) as *equivalent* according to
\(\vdash\), and, following Smiley (1962), when for all \(\chi(\cdot)\), the
formulas \(\chi(\phi)\) and \(\chi(\psi)\) are equivalent according to
\(\vdash\), we describe \(\phi\) and \(\psi\) as *synonymous* (according
to \(\vdash)\). Thus a congruential consequence relation is one for which
any equivalent formulas are synonymous.

The characterization of the (classical first-order) consequence relation given above was semantic, in that we described it in terms of the consequence operation \(Th\circ\Mod\) which invokes the structures for the language and what is true in them. A proof system for first-order logic provides a direct syntactic account of when \(\phi\) is a consequence of \(\Gamma\), in terms of derivability using rules (and perhaps axioms) sensitive only to the form of the formulas involved. We could discuss the properties of sentence connectives in terms of such quantified languages (in which open as well as closed sentences can be their arguments) but to avoid extraneous complications prefer the setting of the propositional languages with which we began. And, as in the discussion to this point, we will generally just say “connective”, rather than “sentence connective”.

Any binary relational connection \(\langle R, S,
T\rangle\), as above, will be said to have *conjunctive
combinations* on the left (right) if for any
\(s_0, s_1 \in S\) there
exists \(s_2 \in S\) such that for all
\(t \in T, R(s_2,
t)\) just in case \(R(s_0,
t)\) and \(R(s_1,
t)\) (respectively, for any \(t_0,
t_1 \in T\) there exists
\(t_2 \in T\) such that for all \(s \in S, R(s, t_2)\) just
in case \(R(s, t_0)\) and
\(R(s, t_1))\); we call
\(s_2\) (respectively, \(t_2)\) a
conjunctive combination of \(s_0\) and
\(s_1 (t_0\) and
\(t_1)\) in this case. Replacing the two
“and”s after the words “just in case” by
“or” gives the notion of *disjunctive combinations
on* the left and right of \(\langle R,
S, T\rangle\). Both notions admit of an obvious
generalization to the case in which \(\{s_0,
s_1\}\) is replaced by an arbitrary subset
\(S_0\) of \(S\), and similarly on the \(T\)
side. We write \(\prod_L S_0\) and
\(\sum_L S_0\) for conjunctive and
disjunctive combinations, respectively, in this case, and similarly on
the right (with an \(\ldquo R\rdquo\) subscript), when we know
either that such a combination is unique or that, while not unique,
what is being said would be correct however a representative
combination were chosen. The subscript is omitted when no confusion is
likely. If, as above \(S_0 = \{s_0, s_1\},\) instead of writing
\(\prod S_0\) (respectively, \(\sum S_0)\), we write \(s_0 \cdot s_1\)
(respectively, \(s_0 + s_1),\) and similarly on the right. To
illustrate these concepts, consider the connection \(\langle R, S,
T\rangle\) with \(S\) some non-empty set, \(T\) its power set, and
\(R\) the relation of membership \((\in)\). There are conjunctive
combinations and disjunctive combinations on the right, being
intersections and unions respectively, but there are in general
neither conjunctive nor disjunctive combinations on the left. Taking
the former case, a conjunctive combination of \(s_0\) and \(s_1\),
where these are distinct elements of \(S\), would be an element of
\(S\) belonging to precisely those subsets of \(S\) to which each of
\(s_0, s_1\), belongs—which is impossible since the unit set of
this element—as with any unit set—contains only one
element, and so not both of \(s_0, s_1\). By analogy with the above
definitions of conjunctive and disjunctive combinations we can also
consider the existence of negative objects on the left and right of a
relational connection, and note that again the set-theoretic example
just given presents is with negative objects on the right (for \(S_0
\subseteq S\), the corresponding negative object is \(S\backslash
S_0)\), but not on the left (“no negative individuals”, as
philosophers might put it, and the point would stand if we switched to
the case in which \(T\) comprised properties—rather than
sets—of individuals, reconstruing \(R\) accordingly). This
absence of combinations simultaneously on the left and right of a
relational connection is typical of non-degenerate cases, in that one
can easily verify that if a relational connection has disjunctive
combinations on the left and conjunctive combinations on the right, or
vice versa, then it satisfies the following (rather
strong) *crossover condition*:

for all \(s_0, s_1 \in S\), all \(t_0, t_1 \in T\), if \(R(s_0, t_0)\) and \(R(s_1, t_1)\), then either \(R(s_0, t_1)\) or \(R(s_1, t_0)\).

(To see this, assume the antecedent and consider the relation \(R\) as it relates \(s_0 + s_1\) and \(t_0 \cdot t_1\)—or, for the “vice versa”, \(s_0 \cdot s_1\) and \(t_0 + t_1\).)

## 2. Sequents and Valuations

Let us return to the propositional languages with which we began. A
*valuation* for such an \(\mathbf{L}\) is a function from
\(L\) to the two-element set \(\{\rT, \rF\}\) (of truth-values). As in the
case of first-order languages touched on above, we put the set of
formulas \(L\) in the source position (i.e. on the left) of our
relational connections \(\langle L, V, R\rangle\),
with the set \(V\) of all valuations for \(\mathbf{L}\) as
the target (on the right), and \(R\) (the “is true
on” relation) relates \(\phi \in L\) to \(v \in V\) just in case \(v(\phi) =\rT\). In view of the
one-to-correspondence between sets and characteristic functions, this
relational connection is just a mild variant of the \(\in\)-based
relational connection considered above, in particular sharing with it
the feature that it has conjunctive and disjunctive combinations on
the right but not the left, and the feature that no two elements from
the left bear the relation \(R\) to exactly the same elements on
the right, and no two elements on the right have have exactly the same
elements from the left bearing the relation \(R\) to them. To get
some interesting logic under way, some of these features needed to be
disturbed, though as we shall see, one of them—the existence of
conjunctive combinations on the right—will prove surprisingly
tenacious. If our interest lies in classical logic, we will be
especially keen to discard most of (the above) \(V\) and
concentrate only on Boolean valuations, in the sense to be explained
now. A function from \(\{\rT,
\rF\}^n\) to \(\{\rT, \rF\}\) is called an \(n\)-ary
*truth-function*, and we say that an \(n\)-ary
truth-function \(f\) *is associated with* the
\(n\)-ary connective \(\#\) of \(\mathbf{L}\) on the valuation
\(v\) (for \(L)\)—or alternatively, under these same
conditions, that \(\#\) is associated with \(f\) on
\(v\)—just in case for all
\(\phi_1 ,\ldots ,\phi_n \in L\):

We describe the connective \(\#\) as *truth-functional* with respect
to a class \(U\) of valuations when there is some \(f\) such
that for each \(v \in U, f\) is associated
with \(\#\) on \(v\), and as *pseudo-truth-functional* with
respect to \(U\) when \(U\) is a union of classes of
valuations with respect to each of which classes \(\#\) is
truth-functional.^{[4]}
A valuation \(v\) is \(\#\)-Boolean, speaking informally, when the
expected truth-function is associated with \(\#\) on \(v\). More
specifically, \(v\), assumed to be a valuation for a language
supporting the connectives to be mentioned here, is \(\wedge\)-Boolean when
the binary truth-function \(f_{\wedge}\) with
\(f_{\wedge}(x, y) = \rT\) iff \(x = y =\rT\) is associated with \(\wedge\) on \(v, \vee\)-Boolean
when a similar association holds for \(\vee\) and
\(f_{\vee}\) defined by \(f_{\vee}(x,
y) =\rF\) iff \(x = y =\rF\). We
assume that the idea is now clear without providing separate
definitions of \(\ldquo\rightarrow\)-Boolean”,
\(\ldquo\leftrightarrow\)-Boolean”, \(\ldquo\neg\)-Boolean”,
\(\ldquo\bot\)-Boolean”, etc. A Boolean valuation for
\(\mathbf{L}\) is just a valuation for \(\mathbf{L}\) which is
\(\#\)-Boolean for each primitive connective \(\#\) of \(\mathbf{L}\) for
which a notion of \(\#\)-Boolean valuation has been defined. (This is just
a way of registering an intended truth-functional interpretation for
the connectives \(\#\) in question.) Similarly we call any connective \(\#\) for
which a notion of \(\#\)-Boolean valuation has been defined, a Boolean
connective, even when discussing its behaviour according to a logic
not determined by a class of Boolean valuations. (This terminology
will be explained in due course.)

A set of truth-functions is *strongly functionally complete* if
every truth-function can be obtained by composition from functions in
the set, together with the projection functions, and *weakly
functionally complete* if every truth-function can be obtained
from functions in the set, together with the projection functions and
the operation of passing from an \((n+1)\)-ary function to an
\(n\)-ary function by dropping an inessential argument (an
argument on which the function does not depend, that is). This
terminology is transferred from truth-functions to Boolean connectives
via the conventional association of such connectives with
truth-functions described in the previous paragraph. Thus for example
each of the sets \(\{\wedge ,\neg \}, \{\rightarrow ,\neg \}\) is weakly functionally
complete, while \(\{\rightarrow ,\bot \}\) is strongly functionally complete.
This weak/strong distinction is not usually registered in the
literature, and functional completeness *simpliciter* is
understood as weak functional completeness. These notions also apply
in matrix semantics generally (see Section
5),
and there are analogous notions of expressive completeness tailored
to other areas; two distinct versions of expressive completeness in
the area of intuitionistic logic (the distinction being orthogonal to
the weak/strong distinction just drawn) are contrasted in Rousseau
(1968), for example. None of these matters will occupy us further
here.

It is often useful to take a more fine-grained look at the
truth-functions in play in the above discussion. Assuming the
identification of \(n\)-ary functions with certain \((n+1)\)-ary
relations and the latter with sets of ordered \((n+1)\)-tuples, we use
the term *determinant* for the elements of a
truth-function. Thus the four determinants of the truth-function
\(f_{\rightarrow}\) associated with \(\rightarrow\) on
\(\rightarrow\)-Boolean valuations are \(\langle\rT, \rT,
\rT\rangle,\) \(\langle\rT, \rF, \rF\rangle,\) \(\langle\rF, \rT,
\rT\rangle,\) and \(\langle\rF, \rF, \rT\rangle.\) Note that the final
entry is the ‘output’ value for the function
concerned. Such determinants will occupy us extensively below.

In saying that a consequence relation \(\vdash\) is *determined
by* a class \(V\) of valuations what is meant that \(\Gamma \vdash
\psi\) if and only if for all \(v \in V\), whenever \(v(\phi) =\rT\)
for each \(\phi \in \Gamma\), then \(v(\psi)=\rT\). When \(\vdash\)
has been described by means of some proof system (some collection of
rules), then the “only if” (“if”) direction of
this claim amounts to the claim that \(\vdash\) is *sound*
(respectively, *complete*) with respect to \(V\). Take the
language whose sole primitive connective is \(\wedge\) and the class
of \(\wedge\)-Boolean valuations. A simple proof system is provided by
the rules indicated in the obvious way by the following figures:

The rule on the left is usually called \(\wedge\)-Introduction while the
two on the right are collectively known as
\(\wedge\)-Elimination—thus \(\ldquo(\wedge\text{I})\rdquo\) and
\(\ldquo(\wedge\text{E})\rdquo\)—because they take us, respectively, to
and from a formula with \(\wedge\) as main connective, and they enable us
to define a consequence relation, \(\vdash_{\wedge}\) in purely
syntactic terms thus: \(\Gamma \vdash_{\wedge} \phi\) just in
case starting with formulas all of which lie in \(\Gamma\), successive
application of the above rules allows us to pass eventually to the
formula \(\phi\). And then one can show, not only that this is the
consequence relation determined by the class of \(\wedge\)-Boolean
valuations—so that if one began with that class and sought a
syntactic codification of the logic it gave rise to, one’s
search would be at an end—but further that the valuations
consistent with \(\vdash_{\wedge}\) are precisely the
\(\wedge\)-Boolean valuations. Here we call valuation \(v\)
*consistent with* \(\vdash\) when for no \(\Gamma , \psi\), for which
\(\Gamma \vdash \psi\), do we have \(v(\phi) =\rT\) for all \(\phi \in \Gamma\) while \(v(\psi) =\rF\); the “but
further” in the preceding sentence is explained by the fact that
every consequence relation \(\vdash\) is determined by the class
\(\text{Val}(\vdash)\) of all valuations consistent with \(\vdash\), which in the
case of \(\vdash_{\wedge}\) are precisely the \(\wedge\)-Boolean
valuations. (The general result just alluded to is a well-known
‘abstract completeness theorem’, and can be found on p.59
of Humberstone (2011). For the \(\vdash_{\wedge}\)-specific point,
see the discussion of Gabbay’s result on the
projection-conjunction truth-functions below on the precise extent of
the feature in question, which, for example, none of \(\vee , \rightarrow ,
\neg\) exhibits.) The significance of this is that if one started not
with the class of \(\wedge\)-Boolean valuations (or any other kind of
valuational semantics), but with the rules \((\wedge\text{I})\) and \((\wedge\text{E})\)
themselves, then that class of valuations would force itself on
one’s attention anyway as the only class of valuations,
preservation of truth on each of which coincided with derivability
using those rules. (We return to this theme below, in connection with
Carnap, by which time we will have traded in formula-to-formula rules
for sequent-to-sequent rules, allowing for the convenient
representation of inferences in which assumptions are discharged.)
Moreover, the rules have a considerable claim to the status of rules
in accordance with which one must reason if one is understanding \(\wedge\)
as “and”, as providing a codification of the way in which
conjunctive premisses and conclusions are reasoned from and to in
natural day-to-day reasoning.

Now, as Gerhard Gentzen observed, when we come to formulate similarly
compelling principles for introducing and eliminating the other
connectives, we find ourselves having to make reference to the
*discharging* of assumptions temporarily made for the sake of
argument. Such is the case for instance with formulating an
introduction rule for \(\rightarrow\) and with formulating an elimination rule
for \(\vee\). In the case of the former rule, for example, Gentzen took it
that the way to derive \(\phi \rightarrow \psi\) is to assume \(\phi\) and use
the various rules and other assumptions to derive \(\psi\), at which
point the rule (also called Conditional Proof) allows us to claim that
we have derived \(\phi \rightarrow \psi\) from the remaining assumptions,
without having to record this conclusion as depending on \(\phi\) (as
\(\psi\) itself did before the rule was applied). Thus to extend the
present approach, known as *natural deduction*, from \(\wedge\) to
these and other connectives, it is necessary to keep track not only of
what formulas we are dealing with at a given stage but also of the set
of initial formulas, or assumptions, on which that formula depends. We
want to say, in the case of the rule just described, that it entitles
us to pass from \(\psi\), as depending on \(\Gamma \cup \{\phi \}\), to \(\phi \rightarrow \psi\), as depending on \(\Gamma\). The ordered pair of a finite
set of formulas and an individual formula, \(\langle \Gamma , \phi \rangle\)
whose first entry records the set of formulas on which its second
entry depends, we write in the more suggestive notation \(\Gamma \succ \phi\), and call a *sequent*, or more explicitly, a
sequent of the logical framework Set-Fmla.
For the variant framework Set-Fmla\(_0\),
we
allow also the case in which there is no formula to the right of the
\(\ldquo\succ\rdquo\). Some principles for reasoning about sequents
which do not involve any specific connectives and were called by
Gentzen, *structural* rules (as opposed to *operational*
rules) are the following, which are respectively a zero-premiss, a
one-premiss and a two-premiss sequent-to-sequent rule:

As the notation makes clear, we use the same shortcuts in formulations
involving the regular turnstile \((\vdash)\) as for the current variant
\((\succ)\), despite the difference in role played by these two symbols:
the former is a metalinguistic predicate and the latter a device for
separating the two sides of a sequent. (\(\ldquo\succ\rdquo\),
arranging formulas into sequents, is, as Lemmon (1965) says of his
corresponding notation, the formal analogue of the word
“therefore”, which arranges sentences into arguments. The
former is, by contrast, for making comments about such
arguments—for example to the effect that they are valid. Of
course there is a little slack in the analogy for Set-Fmla,
since we allow the
case where there are no premisses.) Any collection \(\Sigma\) of sequents
which is closed under the structural rules above gives rise to a
corresponding (finitary) consequence relation: \(\Gamma \vdash_{\Sigma} \phi\) iff for some finite
\(\Gamma_0 \subseteq \Gamma\), we have \(\Gamma_0\succ \phi \in \Sigma\). We should also have a sequent-based analogue of
the notion of a valuation’s being consistent with a consequence
relation; accordingly we say that a sequent \(\Gamma \succ \phi\)
*holds on* the valuation \(v\) just in case we do not have
\(v(\psi) =\rT\) for each \(\psi \in \Gamma\) while also \(v(\phi) =\rF\). (When \(\Gamma\) is empty, the
sequent holds on \(v\) just in case \(v(\phi) =\rT\). It
would be uncouth to speak of a sequent as being true on a valuation,
however, just as one would not speak of the truth of an argument. Such
usages are on a par with, and closely allied to, the mistaken
conception of \(\succ\) as a kind of connective.)

We can now formulate the desired \(\rightarrow\)-introduction rule so that the assumption discharge feature is visible in what happens on the left of the sequent-separator as we move from premiss-sequent to conclusion-sequent. We write the elimination rule alongside in a similar notation; included also are the natural deduction rules for \(\vee\); the earlier rules for \(\wedge\) should be imagined as re-written along similar lines, with assumption-dependencies made explicit:

Along with the \(\wedge\) rules reformulated in the above sequent-to-sequent style, and the structural rule (Id)—(Weakening) and (Cut) being derivable—these rules render provable exactly those sequents in \(\{\wedge ,\vee ,\rightarrow \}\)-fragment of intuitionistic logic, while for the corresponding fragment of classical logic, one would need to add a further principle governing implication, such as the following subcontrariety rule:

\[(\text{Subc}_\rightarrow)\frac{\Gamma, \phi\rightarrow\psi\succ\chi\quad \Gamma, \phi\succ\chi}{\Gamma\succ\chi}\]
(Equivalently, in view of Weakening, one could give a formulation with
\(\ldquo\Delta\rdquo\) as a set-variable for the right sequent premiss,
and carry both \(\ldquo\Gamma\rdquo\) and \(\ldquo\Delta\rdquo\) down to
the conclusion-sequent, as in the formulation of \((\rightarrow\text{E})\) above.) In
the terminology of Dummett (1991) all of the rules we have seen are
*pure* (their schematic formulation involves mention only of a
single connective) and *simple* (each formulation mentions it
only once), this last rule is also *oblique*: a discharged
assumption has the connective in question as its main connective. One
can trade in this obliqueness for a loss of simplicity, changing the
\(\rightarrow\)-elimination rule from the familiar Modus Ponens
principle above to a version incorporating Peirce’s Law
\((\ldquo(p \rightarrow q) \rightarrow p \succ p\rdquo),\) due to
Kanger:^{[5]}

or sacrifice purity and have a zero-premiss rule \(\succ \phi \vee (\phi \rightarrow \psi)\), or again just leave the implicational rules as they are and rely on further rules (not given here) governing negation to make up the shortfall and render such classically but not intuitionistically acceptable \(\rightarrow\)-sequents—such as Peirce’s Law above—provable with their aid. (The same tensions would then arise for the \(\neg\) rules, if one regards obliqueness as undesirable, with “double negation elimination” principles abandoning simplicity, or “excluded middle” principles, abandoning purity. Note that by a ‘classically acceptable sequent’ here is meant a sequent holding on all Boolean valuations.) An alternative for capturing the classical logic of \(\rightarrow\) is to change from the logical framework Set-Fmla to Set-Set, in which finite (possibly empty) sets of formulas appear on the right of the \(\succ\), just as on the left. Then the above \(\rightarrow\)-Introduction rule can remain intact, but with a set variable to collect side-formulas on the right: from \(\Gamma , \phi \succ \psi , \Delta\) to \(\Gamma \succ \phi \rightarrow \psi , \Delta\). (Suitable modifications should also be made to the remaining rules in this case.) These ‘multiple-succedent’ sequents are more popularly associated with a different approach to logic from the natural deduction approach (though they have often appeared in this setting), namely the sequent calculus approach, in which instead of being inserted or removed from the right of the \(\succ\), by suitable introduction or elimination rules, together with the possible discharge of assumptions, the rules—again, ideally, pure and simple—always insert a connective, either to the left or the right, of the \(\ldquo\succ\rdquo\). The left insertion rules do the work of the elimination rules of the natural deduction approach, while the right insertion rules do the work of—indeed, are just—the natural deduction introduction rules. The left insertion rules, (\(\#\) Left) for \(\#\in \{\wedge ,\vee ,\rightarrow \}\) are then as follows for the classical case, with the right insertion rules (\(\#\) Right) being the natural deduction introduction rules as above, with a set-variable on the right of the \(\succ\) for the classical Set-Set case:

\[\begin{align} (\wedge\text{Left})&\frac{\Gamma, \phi\succ\Delta}{\Gamma, \phi\wedge\psi\succ\Delta}, \frac{\Gamma, \psi\succ\Delta}{\Gamma, \phi\wedge\psi\succ\Delta} \\[10pt] (\vee\text{Left})&\frac{\Gamma, \phi\succ\Delta\quad\Gamma', \psi\succ\Delta'}{\Gamma, \Gamma', \phi\vee\psi\succ\delta, \delta'} \\[10pt] (\rightarrow\text{Left})&\frac{\Gamma\succ\phi, \delta \quad\Gamma', \psi\succ\delta'}{\Gamma, \Gamma', \phi\rightarrow\psi\succ\Delta, \Delta'} \end{align}\]For formulations restricted to Set-Fmla\(_0\), and thus suitable for the intuitionistic sequent calculus, we require that \(\Delta\) in \((\wedge\) Left) contains at most one formula, and for \((\vee\) Left) and \((\rightarrow\) Left), that \(\Delta \cup \Delta'\) contains at most one formula. Indeed, one easily sees that using the structural rules mentioned earlier and the operational rules described here, there will always be exactly one formula, since proofs all begin with (Id) and no rule removes all formulas from the right-hand side (or ‘succedent’) in the transition from premiss sequents to conclusion sequent. This changes if we add the rules for negation, here giving both the left and the right insertion rules, initially for the Set-Set case:

\[ (\neg\text{Left})\frac{\Gamma\succ\phi, \Delta}{\Gamma, \neg\phi\succ\Delta} \qquad(\neg\text{Right})\frac{\Gamma, \phi\succ\Delta}{\Gamma\succ\neg\phi, \Delta}\]
A Set-Set sequent
\(\Gamma \succ \Delta\) holds on a valuation \(v\) if and only if
it is not the case that \(v\) verifies every formula in \(\Gamma\)
while falsifying every formula in \(\Delta;\) note that this coincides
with the definition of “holding on \(v\rdquo\) given for
Set-Fmla in the case
in which \(\Delta = \{\psi \}\) for some \(\psi\). Similarly, we have the
notion of a *generalized consequence relation* in which
suitably two-sided versions of the conditions definitive of
consequence relations are given, which can be found in Shoesmith and
Smiley (1978), Chapter 2, for example (under the name
‘multiple-conclusion consequence relation’). If \(\Vdash\) is
such a relation on a language \(\mathbf{L}\) then an
\(\mathbf{L}\)-valuation \(v\) is said to be *consistent
with* \(\Vdash\) when there do not exist \(\Gamma , \Delta\), with \(v(\phi)
=\rT\) for all \(\phi \in \Gamma\) and \(v(\psi) =\rF\)
for all \(\psi \in \Delta\). The
class of all such valuations is denoted, much as in the consequence
relation case, by \(\Val(\Vdash)\). Sometimes formulations appear below
with the phrase “(generalized) consequence relation”,
meaning that the claim being made or considered applies both in the
case of consequence relations and in the case of generalized
consequence relations.

One should distinguish sharply between *logical frameworks*,
that is, choices as to what kind of thing a sequent is (e.g., Set-Fmla
*vs.* Set-Set),
on the one hand,
and *approaches to logic*, that is, choices as to what kind of
sequent-to-sequent rules are to be used (e.g., natural deduction
*vs.* sequent calculus), on the other. Gentzen (1934) used
Set-Set for a
classical sequent calculus and Set-Fmla
for the intuitionistic case. (More accurately,
since he had finite sequences of formulas in mind rather than sets,
and in the latter case allowed empty but not multiple succedents, we
should really say something long the lines of Seq-Seq
and Seq-Fmla\(_0\),
respectively. Additional structural rules are then needed to allow
permutation of formulas in a sequence.) Rudolf Carnap (1943) had a
rather different reason for passing from Set-Fmla
to Set-Set,
one which is
semantically based rather than grounded in considerations of
proof-theoretic elegance.

Let us forget about \(\rightarrow\) and \(\neg\) and the rules governing them, and
consider the formulas constructed with the aid only of \(\wedge\) and \(\vee\).
On sequents of Set-Fmla
in this fragment, classical and intuitionistic
logic agree, and the consequence relation
concerned—\(\vdash_{\wedge ,\vee}\), we may call it—is
the consequence relation determined by the class of all \(\wedge\)- and
\(\vee\)-Boolean valuations. Carnap’s point is one anticipated
earlier with the remark that every \(v \in\)
\(\Val(\vdash_{\wedge})\) is \(\wedge\)-Boolean, which extends to the
case of \(\vdash_{\wedge ,\vee}\): all valuations in
\(\Val(\vdash_{\wedge ,\vee})\) are \(\wedge\)-Boolean, but they are not
all \(\vee\)-Boolean, for the simple reason that for any consequence
relation \(\vdash\), \(\Val(\vdash)\) is always closed under conjunctive
combinations, and it is easy to find \(\vee\)-Boolean \(u,
v\), with \(u \cdot v\) not
\(\vee\)-Boolean.^{[6]}
Indeed, in 4.8 below we shall see that there is no truth-function at
all associated with \(\vee\) on any \(u \cdot v\) with \(u
\ne v\), though here we will concentrate on illustrating this more
general result for the special case of the usual (inclusive)
disjunction truth-function to show how \(u \cdot v\)
can fail to be \(\vee\)-Boolean.

It is instructive see this particular case argued by an appeal to the
considerations of Section
1
as follows. Consider the binary relational connection between the set
of formulas in a language one of whose connectives is \(\vee\) and the
class of Boolean valuations, with the relation *is true on*. We
have disjunctive combinations on the left, with \(\phi + \psi\) as \(\phi \vee \psi\), since the
valuations on the right are all \(\vee\)-Boolean; therefore we cannot in
general have conjunctive combinations on the right, since the
crossover condition is not satisfied for this connection. The closure
claim applies quite generally, with \(\prod V \in
\Val(\vdash)\) whenever \(V \subseteq \Val(\vdash)\). This fact
appears in the philosophical literature in the fact that
supervaluations over classes of bivalent valuations deliver the same
consequence relation as the original valuations, which is accordingly
classical when the valuations are Boolean. (Supervaluations are
supposed to be non-bivalent, in verifying those formulas verified by
all the underlying valuations and falsifying those formulas false on
all the underlying valuations, with those in neither category being
neither true nor false on the supervaluation. But everything in this
definition after the words “verified by all the underlying
valuations” is mere rhetoric, since all that matters—for a
sequent’s holding on a valuation or a valuation’s being
consistent with a consequence relation—is truth-preservation;
setting it to one side, we can identify the supervaluation over
\(V\) with \(\prod V\). Likewise in the case of
‘subvaluations’—as in Hyde (2005)—where it is
\(\sum V\) that would be relevant.) A special case arises with
\(V = \varnothing\), for which \(\prod V\) is the unique
valuation \(v_{\rT}\) assigning \(\rT\) to every formula (of the
language in question, to which the claim of uniqueness is understood
as relativized).

One may wonder which truth-functions are like that associated (on
\(\wedge\)-Boolean valuations) with \(\wedge\) in this respect. More precisely,
let \(\vdash\) be the consequence relation determined by the class of
valuations on each of which an \(n\)-ary connective
\(\#_f\) is associated with the \(n\)-ary
truth-function \(f\). Our question is: for which choices of
\(f\) does \(\vdash\) enforce the interpretation of
\(\#_f\) as \(f\) in the sense that on every
\(v \in \Val(\vdash)\), \(\#_f\) is associated
with \(f\). This question was answered in Dov Gabbay (1978) and
(1981) (Chapter 1, Section 3) as follows. Say that \(f\) (as
above) is a *projection-conjunction* truth-function just in
case for some \(J \subseteq \{1,\ldots ,n\}\) we have, for
all \(x_1 ,\ldots ,x_n
(x_i \in \{\rT, \rF\})\):

\(f(x_1 ,\ldots ,x_n) = \rT\) if and only if for all \(j \in J, x_j = \rT\)

Then the truth-functions \(f\) for which every valuation
consistent with \(\vdash\) (as above) associates \(\#_f\)
with \(f\) are precisely the projection-conjunction
truth-functions. (Gabbay calls \(\#_f\), as it behaves
according to \(\vdash\), *strongly classical* in these cases,
though his own definition is not formulated in these terms.) By way of
example: when \(n = 1\), these are the identity and the
constant-true functions, while for \(n = 2\), they are the first
projection, second projection, constant true and (Boolean) conjunction
truth-functions. (The constant true cases arise by taking \(J\)
as \(\varnothing\).) The remaining 12 binary truth-functions thus exhibit the
behaviour we saw with the disjunction truth-function; the
corresponding connectives are what Gabbay calls *weakly*
classical: determined by a class of valuations over which the
connective is associated with a certain truth-function despite the
existence of further consistent valuation on which it is not so
associated. It is easy to see that the latter phenomenon does not
arise in the case of generalized consequence relations \(\Vdash\), since
we can easily write down unconditional conditions on such relations
which enforce the association with a particular truth-function on
valuations in \(\Val(\Vdash)\). This is best seen as proceeding
determinant by determinant. The unenforceable determinant in the case
of disjunction is \(\langle\rF, \rF, \rF\rangle\), dictating that when the
disjuncts have the values listed in the first two positions, the
disjunction has the value listed in the final position. This
determinant induces in a familiar way (e.g., Segerberg 1982,
§3.3) the following condition on \(\Vdash\): that for all \(\phi ,
\psi\), we have \(\phi \vee \psi \Vdash \phi , \psi\). Alternatively
put, in Set-Set, as
opposed to Set-Fmla,
there is a set of formulas holding on precisely the \(\vee\)-Boolean
valuations, namely that containing, for all formulas \(\phi , \psi\), the
sequents \(\phi \succ \phi \vee \psi\), and \(\psi \succ \phi \vee \psi\), and—the new case not already available in Set-Fmla—\(\phi \vee \psi \succ \phi , \psi\). In view of this, we can say that in Set-Set
though not in Set-Fmla,
the class of
\(\vee\)-Boolean valuations is *sequent-definable*, and the same
goes for connectives associated with all the other truth-functions not
meeting the projection-conjunction test (such as negation and material
implication). As the \(\vee\) example makes clear, by contrast with the
case of consequence relations, \(\Val(\Vdash)\), for a generalized
consequence relation \(\Vdash\), need not be closed under conjunctive
combinations.^{[7]}
Again, one can see this in the light of the considerations of Section
1,
thinking of the relational connection between Set-Set
sequents and
arbitrary valuations, with the relation being ‘holds on’.
This connection supplies disjunctive combinations on the left, with
\(\sigma + \sigma'\) being the least common weakening of \(\sigma\)
and
\(\sigma'\).^{[8]}
Thus it cannot also supply conjunctive combinations on the right,
since it does not satisfy the crossover condition.

This approximately Carnapian concern with sequent-definability—in particular the exclusion of unwanted non-Boolean valuations—can be taken to a higher level by moving from questions about sequents and the valuations they hold, to questions about rules and the valuations they preserve the property of holding on, as we shall see in Section 3, after making some further points about the apparatus of consequence relations, or logics in the framework Set-Fmla. The determinant-induced conditions on generalized consequence relations alluded to above can be converted into conditions on consequence relations in a straightforward way, illustrated here in the case of negation, with the condition

\[ \text{for all }\phi : \phi , \neg \phi \Vdash \varnothing \](induced by \(\langle\rT, \rF\rangle\)) becoming

\[ \text{for all }\phi , \psi ,: \phi , \neg \phi \vdash \psi \]and the condition

\[ \text{for all }\phi : \Vdash \phi , \neg \phi \]
(induced by \(\langle\rF, \rT\rangle\)) turning into the *conditional*
condition on consequence relations \(\Vdash\):

for all \(\Gamma , \phi , \psi\), if \(\Gamma , \phi \vdash \psi\) and \(\Gamma , \neg \phi \vdash \psi\) then \(\Gamma \vdash \psi \)

In a proof system in Set-Fmla
such conditional requirements emerge as
sequent-to-sequent rules, closure under which (along with containing
all the sequents corresponding to the unconditional requirements) will
suffice to secure completeness—in this case that any unprovable
sequent fails to hold on some \(\neg\)-Boolean valuation—without
the strong classicality property of having the provable sequents hold
*only* on such valuations. (The process just described
transforms the Set-Set
condition, \(\phi \vee \psi \succ \phi ,
\psi\) (all \(\phi , \psi\)), induced by the Set-Fmla
unenforceable \(\vee\)
determinant \(\langle\rF, \rF, \rF\rangle\), into the
*conditional* condition of closure under the rule \((\vee\text{E})\).) If
a generalized consequence relation \(\Vdash\) with a Boolean connective \(\#\)
in its language satisfies all the conditions induced by the
determinants of the associated truth-function we call \(\Vdash\) \(\#\)-*classical*. Similarly for a consequence relation which
satisfies the conditions on consequence
relations—*conditional* conditions
included—derived, as just described, from these
determinant-induced conditions on generalized consequence relations.
(These versions of \(\#\)-classicality can often be simplified on a
case-by-case basis. For example, the \(\wedge\)-classicality of a
consequence relation or generalized consequence relation—we use
the former notation here—is equivalent to its being the case
that for all \(\phi , \psi\), we have (1) \(\phi , \psi \vdash \phi \wedge \psi\), (2) \(\phi \wedge \psi \vdash \phi\), and (3) \(\phi \wedge \psi \vdash \psi\). Here we see a three-part condition, instead of
the four-part condition comprising the conditions induced by each of
the four determinants.)

Consideration of the determinant-induced conditions on generalized consequence relations allows us incidentally to observe, somewhat surprisingly, that consequence relations (and the Set-Fmla framework) manage to distinguish the logics of any two truth-functions of the same arity. More precisely, suppose that \(f\) and \(g\) are distinct \(n\)-ary truth-functions, \(\#\) is an \(n\)-ary connective, and \(V_f\) and \(V_g\) are the classes of valuations on which, respectively, \(f\) and \(g\) are associated with \(\#\); then the consequence relations determined by \(V_f\) and \(V_g\) are distinct. By way of illustration, suppose that \(n = 3\) and \(f\) and \(g\) differ on some determinant beginning with \(\rT, \rF, \rF\). (Thus we are considering the case in which the first component of a \(\#\)-compound is true on a given valuation and the second and third are false.) Without loss of generality, we can assume that \(\langle\rT, \rF, \rF, \rT\rangle \in f\) while \(\langle\rT, \rF,\rF, \rF\rangle \in g\). The conditions on a generalized consequence relation \(\Vdash\) induced by these determinants are respectively \(\phi \Vdash \psi , \chi\), \(\#(\phi , \psi , \chi)\) and \(\phi\), \(\#(\phi , \psi , \chi) \Vdash \psi , \chi\). Thus in particular, taking \(\phi\) as \(p\) and each of \(\psi , \chi\), as \(q\), for the generalized consequence relations \(\Vdash_f,\) say, determined by \(V_f\) and \(\Vdash_g\), determined by \(V_g\), we have:

\[p \Vdash_f q, \#(p, q, q)\quad\text{and}\quad p, \#(p, q, q)\Vdash_g q\]
Note that \(p\), \(\#(p, q, q)\nVdash_f q\), since otherwise it would
follow (by the ‘cut’ condition on generalized consequence
relations) from the first inset \(\Vdash\)-statement here that \(p \Vdash_f q\), which is not the case. Thus
in view of the second \(\Vdash\)-statement, \(\Vdash_f\)
and \(\Vdash_g\) differ on the sequent \(\sigma = p\), \(\#(p, q, q)\succ q\),
since \(\sigma \in \Vdash_g\) while \(\sigma \not\in \Vdash_f\). But \(\sigma\) is a sequent of
Set-Fmla, so the
*consequence relations*, \(\vdash_f\) and
\(\vdash_g\), say, determined respectively by
\(V_f\) and \(V_g\)
also differ (namely, on \(\sigma)\). We have worked through a simple
illustration of the general result claimed above, but this case is
sufficiently representative for the general proof to be
reconstructed.

Indeed the real moral is more general still. We did not need to use,
in our worked example, more than the fact that there was some
determinant respected by every valuation in
\(V_f\) with the opposite determinant
respected by every valuation in \(V_g\), where
\(V\) *respects* a determinant \(\langle x_1 ,\ldots ,x_n,x_{n+1}\rangle\)
for \(\#\) (with each \(x_i \in \{\rT, \rF\}\)) just in case for all formulas \(\phi_1 ,\ldots ,\phi_n\),
\(v(\phi_i) = x_i\) for \(i = 1,\ldots ,n\) implies \(v(\#(\phi_1 ,\ldots ,\phi_n)
= x_{n+1}\), and determinants are
*opposite* if they differ in precisely their final positions.
(Actually, inspection of the worked example shows that we also need
the classes playing the role of \(V_f\) and
\(V_g\) also to contain enough valuations to
assign different truth-values to any pair of distinct propositional
variables.) Take the 1-ary connective \(\Box\) of any familiar modal
logic (e.g., \(\mathbf{S5})\), for example. We expect it to
satisfy the determinant \(\langle\rF, \rF\rangle\), in the sense that the
appropriate consequence relation should satisfy the condition induced
by this determinant, since what is necessarily true is true—and
thus if \(\phi\) is false, \(\Box \phi\) should be false—while we do
not want any determinant of the form \(\langle\rT, x\rangle\) to be
satisfied. In this case we can describe \(\Box\) as *partially
determined* according to the consequence relation in question. On
the other hand, if a consequence relation \(\vdash\) (or a generalized
consequence relation \(\Vdash)\) satisfies, for each \(n\)-tuple of
truth-values, the condition induced by exactly one determinant for the
\(n\)-ary connective \(\#\), whose first \(n\) entries are as
given by that \(n\)-tuple (the final, \(n+1\)^{st},
entry being either a \(\rT\) or an \(\rF\)), then we say \(\#\) is *fully
determined* according to \(\vdash\) (or \(\Vdash)\). By the
determinant-induced conditions on a consequence relation here is meant
the conditions on a consequence relation derived as explained (or at
least illustrated) above from the directly determinant-induced
conditions on a generalized consequence relation. As one might expect,
this property of connectives relative to consequence relations has an
intimate relation with the similar property introduced at the start of
this section:

A connective \(\#\) in the language of a consequence relation \(\vdash\) is fully determined according to \(\vdash\) if and only if there is some class of valuations \(V\) such that \(\vdash\) is determined by \(V\) and \(\#\) is truth-functional with respect to \(V\).

Note that the two occurrences of the word ‘determined’
here mean quite different things. “Fully determined”, as
defined above, is a variation on Segerberg’s terminology in his
(1982) of ‘type-determined’, varied so as to lend itself
to other modifications—*partially determined*,
*completely undetermined*, *overdetermined*,…
(though this last will not be getting attention here)—while the
second occurrence of the word is the usual *sound and complete*
sense of “determined”. Turning to generalized consequence
relations, we find the connection to be more intimate still:

A connective \(\#\) in the language of a generalized consequence relation \(\Vdash\) is fully determined according to \(\Vdash\) if and only if \(\#\) is truth-functional with respect to \(\Val(\Vdash)\).

This implies the statement given for consequence relations (putting
\(\ldquo\Vdash\rdquo\) in place of \(\ldquo\vdash\rdquo\)) since a
generalized consequence relation, like a consequence relation, is
always determined by the class of all valuations consistent with it.
(But only the weaker statement above is available for consequence
relations, as such cases as that of \(\vee\) illustrates, since the
consequence relation determined by the class of \(\vee\)-Boolean
valuations—with respect to to which \(\vee\) is by definition
truth-functional—is also determined by other classes of
valuations, with respect to it is not.) Indeed another way of putting
the contrast between the consequence relations claim above and the
generalized consequence relations claim is that while for consequence
relations #‘s being fully determined according to \(\vdash\) is
equivalent to *some* class of valuations which determines
\(\vdash\) having \(\#\) truth-functional with respect to it, for generalized
consequence relations we can say that \(\#\)‘s being fully determined
according to \(\Vdash\) is equivalent to *every* class of
valuations which determines \(\Vdash\) having # truth-functional with
respect to it.

Along with truth-functionality, we also included a definition of pseudo-truth-functionality with respect to \(V\). A simple way of seeing the relation between these two concepts is in an \(\forall /\exists\) scope contrast (in which \(\ldquo f\rdquo\) ranges over truth-functions of the same arity as \(\#\)): \(\#\) is truth-functional with respect to \(V\) when

\(\exists f\forall v \in V[f\) is associated with \(\#\) on \(v\)],

whereas \(\#\) is pseudo-truth-functional with respect to \(V\) when

\(\forall v \in V\exists f[f\) is associated with \(\#\) on \(v\)].

It is natural to ask after a syntactical condition related to
pseudo-truth-functionality in the same way(s) as full determination is
related to truth-functionality. Say that an \(n\)-ary connective
\(\#\) is *left-extensional* in its \(i\)^{th} position
\((1 \le i \le n)\) or *right-extensional* in
its \(i\)^{th} position, according to a generalized
consequence relation \(\Vdash\), when the condition
(LE\(_i)\) or (RE\(_i)\) is satisfied,
respectively, for all formulas
\(\phi_1 ,\ldots ,\phi_n,\psi\) in the
language of \(\Vdash\) we have:

- (LE\(_i\))
- \(\phi_i, \psi, \#(\phi_1 ,\ldots ,\phi_n) \Vdash\#(\phi_1 ,\ldots ,\phi_{i-1},\psi ,\phi_{i+1},\ldots ,\phi_n)\)
- (RE\(_i\))
- \(\#(\phi_1 ,\ldots ,\phi_n) \Vdash \#(\phi_1 ,\ldots ,\phi_{i-1},\psi ,\phi_{i+1},\ldots ,\phi_n), \phi_i, \psi\)

\(\#\) is left-extensional (right-extensional) according to \(\Vdash\) if it
is left-extensional (respectively, right-extensional) in its
\(i\)^{th} position for each \(i\) \((1
\le i \le n)\), and finally \(\#\)
is *extensional* according to \(\Vdash\) when \(\#\) is both left- and
right-extensional according to \(\Vdash\). In 4.8 we encounter a failure
of of RE\(_2\) for\(\#= \vee\), relative to certain generalized
consequence relation considered there (which also violates
the RE\(_1\), as it happens). For \(n = 1\) we drop
the subscript, the above conditions reducing to (LE) and (RE):

- (LE)
- \(\phi, \psi, \#\phi\Vdash\#\psi\)
- (RE)
- \(\#\phi\Vdash\#\psi, \phi,\psi\)

Thus (LE) requires that each \(v \in \Val(\Vdash)\) “treats truths alike” when they are embedded under \(\#\), in the sense that when \(v(\phi) = v(\psi) =\rT\), then \(v(\#\phi) = v(\#\psi)\), while (RE) requires that falsehoods be treated alike in that \(v(\phi) = v(\psi) =\rF\) likewise implies that \(v(\#\phi) = v(\#\psi)\). (It may help to remark that for \(\leftrightarrow\)-classical \(\vdash\) together these amount to requiring that \(\phi \leftrightarrow \psi \vdash \#\phi \leftrightarrow \#\psi\). But we are trying to keep the discussion ‘pure’ so that definitions make sense even when the connective—here #—with the property being defined is the sole connective in the language.) The conditions (LE\(_i\)) already make sense as conditions on consequence relations (writing \(\vdash\) for \(\Vdash)\) since there is a single formula on the right, and we will speak of \(\#\) as left-extensional according to \(\vdash\) when they are all satisfied, while the conditions (RE\(_i\)) need to be converted into conditional conditions as above in the discussion of determinant-induced conditions. We will illustrate this only for the \(n = 1\) case, with (RE) becoming (RE\('\)), understood as demanding for all \(\Gamma , \phi , \psi , \chi\):

- (RE\('\))
- If \(\Gamma\), \(\#\psi \vdash \chi\) and \(\Gamma , \phi \vdash \chi\) and \(\Gamma , \psi \vdash \chi\), then \(\Gamma\), \(\#\phi \vdash \chi\)

Taking it that the intention is clear for the general case what (RE\('_i\)) should be as a condition on consequence relations, we say that \(\#\) is right-extensional according to \(\vdash\) when (RE\('_i\)) is satisfied for each \(i\) up to the arity of \(\#\), and that \(\#\) is extensional according to \(\vdash\) just in case \(\#\) is both left- and right-extensional according to \(\vdash\). Then paralleling the above results for truth-functionality are the following for pseudo-truth-functionality:

A connective \(\#\) in the language of a consequence relation \(\vdash\) is extensional according to \(\vdash\) if and only if there is some class of valuations \(V\) such that \(\vdash\) is determined by \(V\) and \(\#\) is pseudo-truth-functional with respect to \(V\).

A connective \(\#\) in the language of a generalized consequence relation \(\Vdash\) is extensional according to \(\Vdash\) if and only if \(\#\) is pseudo-truth-functional with respect to \(\Val(\Vdash)\).

Whether for consequence relations or for generalized consequence
relations, we have the following—in general,
irreversible—implications for the three properties of being
fully determined, being extensional, and being congruential (as
explained below) according to any given (generalized) consequence
relation:^{[9]}

fully determined\(\Rightarrow\)extensional\(\Rightarrow\)congruential.

where this last concept is defined by saying that \(\#\) is
*congruential* in the \(i^{\text{th}}\) position
according to a consequence relation or generalized consequence
relation \(\vdash\) or \(\Vdash\) (we state the condition only using the
\(\ldquo\vdash\rdquo\) notation) just in case for all formulas
\(\phi_1 ,\ldots ,\phi_n,\psi\):

and calling \(\#\) congruential according to \(\vdash\) when \(\#\) is congruential in each of its positions according to \(\vdash\). Clearly a consequence relation is congruential in the sense of Section 1—which of course also makes sense for generalized consequence relations—precisely when each primitive connective in its language is congruential in every position according to it. A similar lifting of properties of connectives—‘according to’ (generalized) consequence relations—can be made in the other cases too, for example calling a consequence relation fully determined when each of the primitive connectives of its language is fully determined according to it. Thus we may say that the consequence relation \(\vdash_{CL}\) of classical logic (with any given stock of primitive connectives—though we will not further decorate the notation to indicate a particular fragment) is fully determined and thus also extensional (and congruential), while the consequence relation \(\vdash_{IL}\) of intuitionistic logic is congruential but not extensional, since for example, \(\neg\), is not right-extensional according to \(\vdash_{IL}\). The consequence relation determined by the well-known three-element matrix of Łukasiewicz is not even congruential, since (again) \(\neg\) is not congruential according to this relation. There is a weaker property than extensionality as here defined (for the sake of the above connection with pseudo-truth-functionality) which properly implies left extensionality but not right extensionality and which, unlike left extensionality itself, implies congruentiality. We could define \(\#\), here taken for illustrative purposes again as 1-ary, to be weakly extensional according to a consequence relation \(\vdash\) when for all \(\Gamma , \phi , \psi\):

\(\Gamma , \phi \vdash \psi\) and \(\Gamma , \psi \vdash \phi\) imply \(\Gamma\), \(\#\phi \vdash \#\psi\).

Thus weak extensionality is congruentiality ‘with side
formulas’ (collected into \(\Gamma)\). The obvious adaptation of
this notion to generalized consequence relations would be to allow
side-formulas on the right too (replacing the
above\(\ldquo\vdash\rdquo\) by \(\ldquo\Vdash\rdquo\) and adding a set
variable \(\ldquo\Delta\rdquo\) to the right-hand sides, that is): this
turns out to be equivalent to extensionality for generalized
consequence relations as defined above in terms of
(LE\(_i\)) and (RE\(_i\))\(.\vdash_{IL}\) is weakly extensional in this sense, and
weak extensionality according to \(\vdash \supseteq \vdash_{IL}\) is a property of some theoretical
significance for the case in which the language of \(\vdash\) adds new
connectives in the spirit of the original intuitionistic
primitives.^{[10]}

Returning to the subject of extensionality, one area in which
extensional but not fully determined connectives arises is when one
takes hybrids of the latter. By the *hybrid* of disjunction and
conjunction, for example, understanding \(\vee\) and \(\wedge\) to have the
inferential powers conferred on them by a particular logic, is meant a
binary connective whose inferential powers are those shared \(\wedge\) and
\(\vee\). (See Rautenberg 1989 for this example, and Rautenberg 1991 and
references therein for more in this vein.) Note that the connectives
hybridized and the resulting hybrid are connectives in the
‘logically loaded’ sense of Section
1
above.

There are various ways of defining the hybridization process depending
on how much generality one wants, but the following minimally general
definition is the easiest to work with. Start with two (generalized)
consequence relations each on the same language, that language having
a single primitive connective, \(\#\), say. The hybrid connective is then \(\#\)
as it behaves according to the intersection of the (generalized)
consequence relations. This way of defining things requires us to
re-notate the connectives to be hybridized. Thus sticking with the
example just mentioned, we consider a copy of the pure \(\wedge\) fragment
of \(\vdash_{CL}\), called \(\vdash_{\wedge}\)
earlier in this section, but writing \(\#\) for \(\wedge\)—but let us
still call this consequence relation \(\vdash_{\wedge}\)—and
similarly with the \(\vee\) fragment. We are then interested in the
behaviour of \(\#\) according to \(\vdash_{\wedge} \cap \vdash_{\vee}\). (Where \(V_{\wedge}\) and
\(V_{\vee}\) are the classes of valuations on which \(\#\) is
associated respectively with the Boolean \(\wedge\) truth-function and with
the Boolean \(\vee\) truth-function, our intersective consequence relation
is that determined by \(V_{\wedge} \cup V_{\vee}\).) This behaviour includes the semilattice properties of idempotence, commutativity and associativity, for
example, since these are common to Boolean disjunction and
conjunction. This particular hybrid connective is partially
determined, since for example \(\phi , \psi \succ \phi \hash \psi\) (a sequent formulation of the condition induced
on consequence relations by \(\langle \rT, \rT,
\rT\rangle\)) belongs to \(\vdash_{\wedge} \cap \vdash_{\vee}\). This by itself does not show that
the hybrid is not *fully* determined, however, and to avoid
entanglement with some issues about rules, this point is best
illustrated in terms of the corresponding generalized consequence
relations and their intersection, the latter satisfying neither of the
conditions induced by the determinants beginning \(\rT, \rF\): for \(\langle\rT, \rF,
\rT\rangle\), the condition that \(\phi , \phi \hash \psi \Vdash \psi\)
(failing for \(\hash\) as \(\vee)\) or the determinant \(\langle \rT, \rF, \rF\rangle\), for
which the induced condition is \(\phi \Vdash \phi \hash
\psi , \psi\) (failing for \(\hash\) as \(\wedge)\). (Among issues about
non-zero-premiss sequent-to-sequent rules that call for care is the
fact that while for any such rule under which each of the intersected
consequence relations is closed, their intersection is likewise
closed, the converse is false: the hybrid consequence relation may be
closed under rules under which the originals are not. In the present
instance the rule: *from* \(\phi \succ \psi\) *to*
\(\psi \succ \phi\) is an example. Similarly for generalized
consequence relations the rule: *from* \(\Gamma \succ
\Delta\) *to* \(\Delta \succ \Gamma\) makes the same
point. This second version shows that the current example of
hybridization, as conducted
in Set-Set,
yields a symmetric generalized consequence
relation.^{[11]})

Let us note in view of the recent reference to \(\vdash_{\wedge} \cap \vdash_{\vee}\), there has been an interest in how one might form something like the union rather than the intersection of the two consequence relations involved here. Not quite the union, since that would not be a consequence relation, but something answering to the intuitive idea of a consequence relation embodying the combined logic of conjunction and disjunction. (This is the theme of Béziau and Coniglio (2010), further taken up in Humberstone (2015).) The situation is not exactly dual to that of hybrids, to which topic we return in the folowing paragraph, because the envisaged hybrid logic contains one connective with the common logical properties of (in the present instance) conjunction and disjunction, whereas the combined logic is based on the language with the two connectives. (The precise dual would be a consequence relation on a language with a single connective, roughly speaking giving that connective all the logical powers possessed by either disjunction or conjunction, and by a result of Wolfgang Rautenberg cited below, according to this consequence relation any formula follows from any other. Indeed, this particular instance of Rautenberg’s observation is already well known in the literature on \(\Tonk\), recalled in §3 below: any consequence relation in a language including a binary connective which satisfies, relative to that consequence relation, both an \(\vee\)-Introduction condition and also an \(\wedge\)-Elimination condition will be one of these trivial consequence relations.)

The hybrid of two fully determined connectives may even be completely
undetermined (satisfy no determinant-induced conditions at all, that
is). This will be the case, for example, if we hybridize not
conjunction and disjunction, but conjunction and negated conjunction
(sometimes called *nand*). By using negation in this way, we
prevent any overlap in the determinant-induced conditions which are
satisfied by the hybrid, though there still remain some non-trivial
properties (commutativity, for example) as well as
extensionality—the point of this mention of hybrids—since
any hybrid of fully determined connectives will still be extensional
(according to the intersection, that is). Of course, one can also
hybridize connectives which are not themselves fully, or even
partially determined—for example, one could investigate the
common properties of \(\Box\) and \(\Diamond\); according to the smallest
normal modal logic (commonly called \(\mathbf{K})\), though this
example would for its most natural development require us to go beyond
the simple account of hybrids given here, since it would have to
attend to the simultaneous presence of the Boolean connectives
alongside these modal operators. A better known modal example of
hybrids is that of the \(\Box\) operator in Łukasiewicz’s
Ł-modal logic (not that Łukasiewicz used this notation for
his necessity operator), which is a hybrid of 1-ary connectives for
the 1-place identity and constant-false truth-functions. (See Chapter
1 of Prior (1957) on this point; further references may be found in
Section
5.)

The hybrid of two connectives is a *subconnective* of each of
them in the sense that whatever sequents (of the logical framework in
play) are provable for it are provable for them. And
conversely—but for the moment the subconnective relation itself
will be the focus of attention. Intuitionistic negation is in this
sense a subconnective, indeed a *proper* subconnective (in the
sense that we do not have the converse) of classical negation. As with
hybrids, there are various options, of differing degrees of generality
in their application, for defining this relation. In the case of a
language with only a single primitive connective, \(\hash\), we can say
that \(\hash\) as it behaves according to (e.g.) the consequence relation
\(\vdash\) is a subconnective of \(\hash\) as it behaves according to
\(\vdash'\) just in case \(\vdash\,\subseteq\,\vdash'\). If we want to
allow different connectives of the same arity, say \(\hash\) and \(\hash'\),
then we can put this instead by saying that \(\sigma(\hash)\in\,\vdash\)
only if \(\sigma(\hash')\in\,\vdash'\), for all \(\sigma(\hash)\),
understanding the latter to denote a sequent with various occurrences
of \(\hash\) in its constituent formulas, with \(\sigma(\hash')\) the result
of replacing all such occurrences by \(\hash'\). This kind of formulation
lends itself to wider applicability since we can allow other
connectives in the formulas of \(\sigma(\hash)\), provided these are in
the language of \(\vdash'\). There is no reason to restrict attention
to primitive connectives in making such comparisons. For example, each
of \(\Box\) and \(\Box \Box\) is a subconnective of the other in
several well-known modal logics, as is shown in Zolin (2000), where
logics are developed axiomatically as sets of formulas (sequents of
the logical framework Fmla, as we would
say^{[12]}) so
the \(\ldquo\sigma(\hash)\rdquo\) would become \(\ldquo\phi(\hash)\rdquo\)
and the point is that in the logics concerned \(\phi(\Box)\) and
\(\phi(\Box \Box)\) are always equi-provable—though in the
interesting cases (e.g., those of \(\mathbf{K}, \mathbf{KT},
\mathbf{KTB})\), not provably equivalent. Note that this is an
intra-logical application of the subconnective idea (corresponding to
the case of \(\vdash\,=\,\vdash'\) above, for which
we *definitely* need to work with notationally distinguished
\(\hash\) and \(\hash')\). Zolin calls such mutual subconnectives
*analogous* (‘analogous modalities’). A
philosophically famous example of this phenomenon from bimodal (or
more specifically, doxastic-epistemic) logic was reported in Byrd
(1973).

Earlier in this section we saw that, where
\(V_f\) and \(V_g\)
are the classes of valuations for a language with an \(n\)-ary
connective \(\hash\) on which distinct truth-functions \(f\) and
\(g\) are associated with \(\hash\) respectively, the consequence
relations determined by \(V_f\) and
\(V_g\) were always distinct. In the present
terminology, this means that either \(\hash\) as it behaves according to the
first of these consequence relations is not a subconnective of \(\hash\) as it
behaves according to the second, or vice versa. This is obvious for
generalized consequence relations as one can read off the difference
from the unconditional conditions induced by the determinants of
\(f\) and \(g\), but we saw (in a worked example) that such
differences are also guaranteed to emerge at the relatively cruder
level of consequence relations. A stronger conclusion can be drawn
from Theorem 4 of Rautenberg (1981) (see also Rautenberg 1985,
p. 4), which will not be proved here, and for the statement of
which we need to explain that a *non-trivial* consequence
relation \(\vdash\) is one for which there exist formulas \(\phi , \psi\) in
the language of \(\vdash\) such that \(\phi \not\vdash \psi\); for some of the
matrix terminology here, see Section
5:

Let \(\mathbf{M}\) be any two-element matrix with one designated value. Then the consequence relation \(\vDash_{\mathbf{M}}\) determined by \(\mathbf{M}\) is not properly included in any non-trivial substitution-invariant consequence relation on the same language.

As one very special case of this maximality result, in which the algebra reduct of \(\mathbf{M}\) has only a single fundamental operation \((f\), as above, say), we get a stronger conclusion about the consequence relations \(\vdash_f\) and \(\vdash_g\) determined by \(V_f\) and \(V_g\) than our earlier conclusion that these consequence relations are distinct: we get the conclusion that neither is included in the other. Taking the \(\mathbf{A}\) and \(D\) of \(\mathbf{M} = (\mathbf{A}, D)\) as \((\{\rT, \rF\}, f)\) and \(\{\rT\}\), the consequence relation \(\vdash_f\) is what Rautenberg is calling \(\vDash_{\mathbf{M}}\), and if this were properly included in \(\vdash_g\) we should have a contradiction with the above result, since the latter consequence relation is certainly non-trivial and substitution-invariant. Thus informally speaking, even in the relatively undiscriminating framework Set-Fmla, the logic of one truth-function never subsumes that of another. Less informally: even in Set-Fmla, a fully determined connective is never a proper subconnective of another fully determined connective.

We conclude this section with two observations prompted by this
result. The first concerns whether anything was gained by our earlier
looking at the argument for the weaker result (understood in the light
of the above conventions) to the effect that, \(f \ne g\) implies
\(\vdash_{f} \;\ne\; \vdash_{g}\). The answer to this question is that
although the result is weaker, the proof yields something stronger:
any difference in determinants yields a difference in unconditional
determinant-induced conditions. Considered as sequents (with
propositional variables replacing the schematic letters in the induced
conditions) these have a very special form, and, transferring
Dummett’s terminology (seen earlier in this section) for rules,
across to sequents, we note that they are all included in the class of
*pure and simple* sequents: sequents in which there is only one
connective to occur and it occurs only once in the sequent. Suitably
abstracting from our earlier worked example, we can see that any
connectives satisfying the conditions induced by even one pair of
opposite determinants (whether or not any remaining
determinant-induced conditions are satisfied) are bound to differ on a
pair of pure and simple sequents. But the analogue of
Rautenberg’s result does not hold in this form: that the set of
pure and simple sequents satisfied by the one and the set satisfied by
the other are incomparable with respect to inclusion. For example,
consider the case of the 1-ary truth-functions Boolean negation and
the constant-false function. We can cite \(\# p \vdash q\) as an example of a pure and simple sequent which holds on
every valuation on which 1-ary \(\#\) is associated with the constant-false
function but not on every valuation on which it is associated with the
negation function. But an inspection of possible cases reveals that
there is no pure and simple sequent valid for the negation
interpretation of \(\#\) which is not also valid for the constant-false
interpretation. (Of course there are sequents doing this—e.g.,
\(p \succ \#\# p\) but, though pure, they are not
simple. And, yes, in Set-Set,
we can always find pure and simple witnesses to
the non-inclusion of the one logic in the other: the
determinant-induced conditions on generalized consequence relations
will serve in this capacity.)

For the second observation, we note a more linguistic reformulation of
Rautenberg’s result, for which we first need a brief digression
on defined connectives. A connective derived by composition from a set
of primitive connectives yields a defined connective in one of two
ways, depending on one’s views of definition. On one view,
isolating the derived connective is already giving a definition: one
has a formula \(\phi(p_1 ,\ldots ,p_n)\) in which exactly the exhibited
variables occur, which since it is constructed from these variables
via the primitive connectives constitutes a derived connective,
applying to formulas
\(\psi_1 ,\ldots ,\psi_n\) to yield the
formula \(\phi(\psi_1 ,\ldots ,\psi_n)\)
which results from substituting \(\psi_i\)
uniformly for
\(p_i\) in \(\phi(p_1 ,\ldots ,p_n)\). We can introduce a shorthand
to such substitution-instances, denoting \(\phi(\psi_1 ,\ldots ,\psi_n)\)
by \(\ldquo\#(\psi_1 ,\ldots ,\psi_n)\rdquo\),
for instance—as in calling the formula \(\neg(\psi_1 \wedge \neg \psi_2)\) by the name \(\ldquo\psi_1 \rightarrow \psi_2\rdquo\). (Of course this would only be a good idea if
there is nothing better to mean, or which is already meant, by
\(\rightarrow\)—as there would be in intuitionistic logic, for instance.)
That is the first view of
definition.^{[13]}
On the second view, rather than just being a metalinguistic
abbreviation, the defined connective is an addition to the object
language: we add (to continue with the example just given) a new
primitive connective \(\rightarrow\), along with a stipulation that compounds
of the form \(\psi_1 \rightarrow \psi_2\) are to be
synonymous with those of the corresponding form
\(\neg(\psi_1 \wedge \neg \psi_2)\). We need not
choose between these views here, but some formulations are sensitive
to which view is taken. In particular, if we have classical logic with
primitives \(\neg\) and \(\wedge\), we may still wish to consider its
implicational fragment—in Set-Fmla,
say, where this would be the restriction of
\(\vdash_{CL}\) to formulas constructed using only the
connective \(\rightarrow\). On the first view of definition, we cannot
literally do that, since to use \(\rightarrow\) is *ipso facto* to use
\(\neg\) and \(\wedge\), so what is meant is rather than the only occurrences
of \(\neg\) and \(\wedge\) are such as occur in subformulas of the form
\(\psi_1 \rightarrow \psi_2\) in virtue of these being
the formulas \(\neg(\psi_1 \wedge \neg \psi_2)\). On
the second view of definition, we have expanded the
language-as-algebra by adding a new fundamental operation \(\rightarrow\) and
can now consider the subalgebra generated by the propositional
variables of the reduct of this algebra obtained by discarding the
other fundamental operations.

Now let \(\phi_1\) and \(\phi_2\) be any two classically non-equivalent formulas in the same variables, \(p_1 ,\ldots ,p_n\) for definiteness, and consider the consequence relations \(\vdash_1\) and \(\vdash_2\), where \(\vdash_1\) is the restriction of \(\vdash_{CL}\) to formulas constructed using the \(n\)-ary connective \(\#\) defined thus:

\[\#(\psi_1 ,\ldots ,\psi_n) = \phi_1 (\psi_1 ,\ldots ,\psi_n)\]and \(\vdash_2\) is the analogous restriction of \(\vdash_{CL}\) this time to the \(\#\)-fragment with \(\#\) defined by:

\[\#(\psi_1 ,\ldots ,\psi_n) = \phi_2 (\psi_1 ,\ldots ,\psi_n)\]Since each of \(\phi_1\) and \(\phi_2\) fixes an \(n\)-ary truth-function of the variables involved, and these truth-functions are distinct (since \(\phi_1\) and \(\phi_2\) were to be non-equivalent) the above \(V_f /V_g\) application of Rautenberg’s result tells us that neither of \(\vdash_1, \vdash_2\), is included in the other. Concentrating on the connectives involved, we can put this by saying that in classical logic any two non-equivalent connectives are incomparable with respect to the subconnective relation (understood as relating the consequence relations on languages in which no further connectives appear). We close by observing that the analogous claim would be false for intuitionistic logic. A counterexample is provided by the connectives defined by \(\phi\mathbin{\#_1} \psi = \neg \phi \vee \neg \psi\) and \(\phi \mathbin{\#_2} \psi = \neg(\phi \wedge \psi)\). These are intuitionistically non-equivalent, in the sense of not always yielding \(\vdash_{IL}\)-equivalent compounds from the same components, while—by an argument not given here—for any intuitionistically provable sequent \(\sigma(\#_1)\) involving formulas constructed from the variables by means of \(\#_1\), the corresponding sequent \(\sigma(\#_2)\) is also intuitionistically provable (though not conversely). So, by contrast with what can happen in the classical setting, we have non-equivalent connectives one of which is a proper subconnective of the other—understanding this last phrase subject to the same parenthetical qualification as above.

## 3. Rules and Connectives

For this section the focus will be on rules governing the various connectives, beginning with a deferred topic from Section 2: the transfer of Carnap-inspired questions of the range of valuations on which the sequents provable in this or that logic hold to questions about the range of valuations on which the sequent-to-sequent rules preserve the property of holding. We will also revisit the sequent-calculus operational rules from early in Section 2 and look at some of their properties, as well as at some interesting variations on the structural rules which work alongside them. One topic—or pair of topics—raised by such investigations is the issue of the existence and uniqueness of connectives exhibiting prescribed logical behaviour (such as might be enshrined in various rules), an issue bearing on all approaches to logic and not just the sequent calculus approach. Finally we look at a pair of concepts applying to connectives as they behave in particular logics: the concept of a universally representative connective and the concept of a ‘special’ connective.

Beginning, then, with the preservation behaviour of rules (as in
Garson 1990 and 2001) it is necessary first to distinguish a
(sequent-to-sequent) rule’s having a local preservation
characteristic with respect to a class \(V\) of
valuations—that for each \(v \in V\), the rule
preserves the property of holding on \(v\)—from its having
a global preservation characteristic with respect to \(V\): if
the premiss-sequents hold on every \(v \in V\), then
the conclusion-sequent holds on every \(v \in V\).
For brevity, a sequent will be called \(V\)-*valid* when
it holds on each \(v \in V\). Then we distinguish the
local range of a rule \(\varrho\), denoted \(\mathit{Loc}(\varrho)\) from its
global range, \(\mathit{Glo}(\varrho)\), taking the definitions as relative
to a background language the class of all valuations for which we
denote by \(U\):

It is also natural to define the local and global range of a collection \(R\) of rules, by setting \(\textit{Loc}(R) =\bigcap_{\varrho \in R}\textit{Loc}(\varrho)\) and \(\mathit{Glo}(R) = \{V \subseteq U\) : each \(\varrho \in R\) preserves \(V\)-validity\(\}\).

Note that while the local range of a rule or set of rules is a set of
valuations, the global range is a set of sets of valuations. But in
some cases there is an especially simple relationship between the two,
namely that \(\mathit{Glo}(R) = \wp(\mathit{Loc}(R))\). This happens whenever \(R\)
comprises only zero-premiss rules, and, more interestingly, when the
rules in \(R\) are interderivable with a set of such rules, given
the structural rules (Id), (Weakening), and
(Cut),^{[14]}
as in the case of the natural deduction rules for conjunction
\(R = \{(\wedge\text{I}), (\wedge\text{E})\}\) or the corresponding sequent
calculus rules \(\{\wedge\text{Right}, \wedge\text{Left}\}\) where \(\mathit{Loc}(R)\)
comprises precisely the \(\wedge\)-Boolean valuations. Evidently, the
strong classicality phenomenon of Section
2
is making its presence felt here, and we should contrast the
situation with disjunction (in Set-Fmla).
For \(R = \{(\vee\text{I}), (\vee\text{E})\}\),
\(\mathit{Loc}(R)\) is the class of \(\vee\)-Boolean valuations, but
the same is the case if \((\vee\text{E})\)—the rule of current interest
since it has no zero-premiss equivalent—is replaced by another
which is far from interderivable with it (even given the structural
rules and \((\vee\text{I}))\):

Thus the local range is not very informative as to the precise
significance of such a rule as \((\vee\text{E}\) and it is natural if one thinks
of the rules as giving the meanings of the connectives they govern (a
perspective mentioned in Section
1)
and wants to distill this information into a semantics in terms of
valuations, to consider the global range. To do so we make use of the
partial order \(\le\) on the underlying set \(U\) of valuations (for
the language under consideration) defined by: \(u \le v\) if and only for all formulas \(\phi\), if \(u(\phi) =\rT\) then \(v(\phi) =
\rT\).^{[15]}
As Garson (2001) observes, the global range of the introduction and
elimination rules for \(\vee\) (and again we could equally well cite the
sequent calculus rules in this connection) is the set of all
\(V \subseteq U\) such that for all \(u \in V\) and all formulas \(\phi\) and \(\psi\), the following condition
is
satisfied:^{[16]}

\([\vee]_{Garson} u(\phi\vee\psi)=\rT\) iff for all formulas \(\chi\) such that \(u(\chi)=\rF\), there exists \(v\in V\) with \(u\leq v, v(\chi)=\rF\) and either \(v(\phi)\rT\) or \(v(\psi)=\rT\).

While we cannot go into the details of Garson’s program here, its aim should be noted: to arrive at the ‘natural semantics’ implicit in the rules governing a connective \(\#\) (here assumed \(n\)-ary) in the sense of a characterization of their global range as comprising those \(V\) of valuations satisfying a condition of the form: \(\forall u \in V, u(\#(\phi_1 ,\ldots ,\phi_n)) =\rT\) if and only if …, where the dots are replaced by something which would render this biconditional suitable as a clause in the inductive definition of truth on a valuation \(u \in V\). Garson worries about the use of \(\le\) on this score in what we are calling \([\vee]_{Garson}\) (and has various suggestions to offer), as well as about the explicit quantification over \(\chi\) which introduces an potential element of circularity or impredicativity (in particular because \(\chi\) need not have a lower complexity—be constructed with the aid of fewer primitive connectives, that is—than \(\phi \vee \psi\) itself); related concerns are aired in Woods (2013). One way of getting rid of the latter feature is to massage \([\vee]_{Garson}\) into the following equivalent form, which makes extensive use of conjunctive combinations of valuations, and uses the notation \(\mid\chi\mid\) which, for a formula \(\chi\), denotes the set of \(v\in V\) such that \(v(\chi) =\rT\):

\(u(\phi \vee \psi) =\rT\) iff \(\exists U_0, U_1 \subseteq V: U_0 \subseteq \mid\phi\mid, U_1 \subseteq \mid\psi\mid\), and \(u = \prod U_0 \cdot \prod U_1\).

In place of this last \(\ldquo\prod U_0 \cdot \prod U_1\rdquo\), we could equally well have
written \(\ldquo\prod(U_0 \cup U_1)\rdquo\), of course. The form as written is more
suggestive of the many variations on the semantic treatment of
disjunction in the literature—the Beth semantics for
intuitionistic logic, for instance, and the treatment of disjunction
for relevant (or ‘relevance’) and other substructural
logics to be found in Ono and Komori (1985), Orłowska (1985,
455), and Bell (1986), to cite only some papers from the
1980s.^{[17]}
We will not discuss other connectives from this perspective here, or
comment further on Garson’s program. See Garson (2001) for a
discussion of the global ranges of the usual sets of introduction and
elimination rules for \(\rightarrow , \neg\) and
\(\leftrightarrow\).^{[18]}
Garson’s approach to these matters has, it should be noted,
undergone further evolution since the publications cited in this
discussion: see Garson (2013).

The idea which has just re-surfaced in our discussion, apropos of
Garson, that the natural deduction introduction and elimination rules
together, or perhaps just the introduction rules alone
(Gentzen’s preferred
position),^{[19]}
somehow fix the meanings of the connectives they govern, often goes
hand in hand with considerations of the existence and the uniqueness
of a connective answering to the said rules, considerations first
raised by H. Hiż, according to Belnap (1962). Belnap was replying
to Prior (1960) in which the idea that any old set of rules could be
stipulated to fix the meaning of a proposed connective, was contested
with the aid of the subsequently much-discussed example \(\Tonk,\)
a supposed binary connective for which an
introduction rule allowed the passage from (arbitrary) \(\phi\) to
\(\phi \Tonk\psi\), as with \(\vee\)-introduction from the
first disjunct, and an elimination rule allowed the passage from \(\phi\Tonk\psi\) to \(\psi\), as with \(\wedge\)-elimination
to the second conjunct. (This was the point anticipated in §2
when the \(\Tonk\) problem was mentioned apropos of
the dual to hybridizing conjunction and disjunction.) Since this
allowed, by successively applying \((\Tonk\text{-I})\) and
then \((\Tonk\text{-E})\), any \(\psi\) to be derived from
any \(\phi\), Prior took this to show that no coherent meaning had been
conferred on \(\Tonk\) by the proposed rules, and
to refute the general thesis that the meaning of a connective can be
fixed by means of rules governing it. (Prior saw Popper and Kneale as
the targets of his argument, which does not touch Gentzen’s view
that the meaning is fixed by the totality of introduction rules for a
connective, coupled with the fact that these are the totality of such
rules. Since there is only the one way of introducing \(\Tonk\),
namely that provided by \((\Tonk\text{-I})\),
where the premiss is \(\phi\) the meaning of
\(\phi\Tonk\psi\) is simply that of \(\phi\) and
the *appropriate* elimination rule is not that given by Prior
but rather one licensing an elimination to the *first*
“tonkjunct”.) Belnap responded that what was wrong with
Prior’s \(\Tonk\) rules was that a proof
system antecedently endorsed for the connectives in use would be
non-conservatively extended by the enrichment of the language with
\(\Tonk\) in tandem with supplementing the proof
system with the \((\Tonk\text{-I})\) and then \((\Tonk\text{-E})\),
since they allow the derivation of the
sequent \(\phi \succ \psi\) even for \(\Tonk\)-free
\(\phi ,
\psi\).^{[20]}
Later in this section, we return to \(\Tonk\) and
examine its behaviour in a sequent calculus setting.

Of course, one expects the addition of new rules to make for the
provability of new sequents, but the extension should be
*conservative* in the sense that no new sequents exclusively
involving the *old* vocabulary become provable. Belnap’s
discussion suggests that the existence of a connective obeying certain
rules should be conceded by someone endorsing a particular proof
system if and only if the addition of that connective to the language
and those rules to the proof system yields a conservative extension.
(There are other things one might mean by the question of whether from
the perspective of a given logic, a connective with such-and-such
logical powers exists—most evidently, whether or not such a
connective is already definable in the logic. Showing that rules
ascribing the powers in question would extend the logic
non-conservatively would be one dramatic way of showing no such
connective to be definable, but since it could fail to be definable
while still being conservatively addable, the questions need to be
kept distinct.)

One snag for such a suggestion is that examples can be found involving
two connectives with associated sets of rules each of which sets of
rules yields a conservative extension of an initial proof system,
apparently requiring the answer “yes, there does exist such a
connective” in each case from the perspective of that original
system, while extending the initial proof system with both sets of
rules at once is non-conservative—undermining this double
endorsement.^{[21]}
We may conclude that while yielding a non-conservative extension of a
favoured proof system is sufficient to denying the existence or
intelligibility of a connective with such-and-such logical properties,
there may be other grounds for returning such a verdict. Boolean
negation comes under just such a critique in Chapter 5 of Priest
(2006), where such problems for Belnap’s account are raised and
references to the technical literature establishing the conservativity
of extending certain logics in the relevance tradition with suitable
principles governing this connection can also be found. (For an
earlier presentation of this point, see also Belnap and Dunn 1981, p.
344, and for a related discussion, Restall 1993, esp. §5.) It
should be noted also that the conservativity test raises issues of its
own, independently of the question of whether passing it is necessary
and sufficient (and what we have been querying is the sufficiency half
of this package) for acknowledging the existence of a connective. For
example, there are sentential connectives which conservatively extend
intuitionistic *propositional* logic in any of its conventional
presentations as a proof system, but non-conservatively extend
intuitionistic *predicate* logic. The best known is dual
intuitionistic implication (see López-Escobar
1985).^{[22]}
Returning to the conservative extension criterion of existence, let
us note that a related connective, dual intuitionistic negation, can
be added conservatively to intuitionistic predicate (and *a
fortiori* propositional logic) but already at the propositional
level produces violations of the *disjunction
property*—that \(\succ \phi \vee \psi\) should only be provable if at least one of
\(\succ \phi , \succ \psi\), is provable—which on
some accounts (e.g., Gabbay 1977 and 1981) renders it illegitimate
from an intuitionistic perspective. Finally, it should be observed
that an adherent of intuitionistic logic might be expected to take a
dim view of a proposed new connective with rules conservatively
extending that logic but not conserving synonymies, in the sense that
formulas in the original language which are synonymous according to
\(\vdash_{IL}\) are no longer so
according to the consequence relation associated with the extended
proof system. This happens in at least the most straightforward
extension of intuitionistic logic by what is called *strong
negation*.^{[23]}

The issue of uniqueness, as opposed to existence, of connectives (in
the logically loaded sense of the term, naturally) is best approached
by considering when a collection of rules governing a connective
*uniquely characterize* that connective in the sense that if
accompanied by corresponding rules governing a ‘duplicate’
version of that connective (of the same arity) result in the synonymy
of compounds formed from the appropriately many components and the
original connective with compounds formed from the duplicate
connective from the same components. In a congruential setting the
reference to synonymy can be replaced by one of equivalence, in the
sense of \(\dashv \vdash\)-equivalence in the consequence relation or
Set-Fmla framework,
with suitable variations for other frameworks. Without the assumption
of congruentiality one should perhaps distinguish unique
characterization to within synonymy from unique characterization to
within equivalence. And because the rules in question may not be pure,
but involve other connectives, it may be necessary to speak of \(\#\) being
uniquely characterized (by the given rules) *in terms of* the
other connectives involved, so that when the reduplicated system is
considered, \(\#\) is replaced by its duplicate, \(\#'\), say, while the
other connectives remain as they are. We will not be considering these
complications here. It is easy to see that the natural deduction rules
for the various connectives given in Section
2
as well as the sequent calculus rules all uniquely characterize the
connectives they govern. (Note that, since this includes the
introduction and elimination rules for \(\rightarrow\), which are shared by any
natural deduction system for intuitionistic logic, the rules may
uniquely characterize a connective which is not fully
determined—not amenable to a truth-functional interpretation.
The same applies in respect of negation, though we did not cover this
in our discussion of natural deduction.) This feature is sometimes
regarded as necessary for the connectives concerned to be regarded as
logical constants, although, as explained in Section
1,
we are not pursuing that issue here.

A related issue involving both uniqueness and existence does deserve
attention, however, arising over competition between logics, differing
on the rules governing a connective where the first logic has rules
which suffice to characterize uniquely a connective and the second has
all these and more governing that connective. The standard example of
this is provided by intuitionistic logic and classical logic in
respect of negation. The fact that the classical rules go beyond the
intuitionistic rules and yet the latter already suffice for unique
characterization means that there is no ‘live and let
live’ option available for the intuitionist, of recognising that
the intelligibility of two distinct negation connectives, classical
and intuitionistic, which can cohabit in the same proof system each
with their respect rules. This should be possible according to those
who think that any difference in the logical principles governing a
connective reflect a difference as to what is meant by the connective
(W. V. Quine’s view—see Section
5
below), since once a difference in meaning is acknowledged, the
previously ambiguous connective, \(\ldquo\neg\rdquo\), in the present
instance, should be replaceable by connectives registering the
disambiguation—\(\neg_i\) and \(\neg_c\),
say—and the intuitionistic and classical logician should be able
to use whichever they take a special interest in, with no further fear
of talking at cross-purposes in each other’s company. But of
course this is not a possibility, since the rules governing
\(\neg_i\) characterize it uniquely and those governing
\(\neg_c\) duplicate them—think of \(\neg_c\) as
\(\neg_i'\), in terms of the above
discussion—*and do more* (securing the provability of
\(\neg_c\neg_c p \succ p\), for
example). The result is that the two connectives form equivalent
compounds in the reduplicated system and all of the intuitionistically
unwanted properties of \(\neg_c\) spill over to infect
\(\neg_i\): we can now prove \(\neg_i \neg_i p \succ p\), and so on. The
conciliatory offer of a purportedly disambiguating notation along
these lines is one no advocate of intuitionistic logic can afford to
accept. (By imposing restrictions on some of the intuitionistic rules,
one can produce candidates for the title of ‘combined
classical-and-intuitionistic proof system’—as, for
example, in Fariñas del Cerro and Herzig (2001)—but,
especially on views according to which the rules of one’s logic
articulate the meanings of the connectives they govern, resistance to
any such restrictions is entirely understandable. Imagine an encounter
with aliens in which they told us that to explain what they meant by
some items of their vocabulary we had to be prepared to restrict the
principle that \(\psi\) followed from \(\phi\) *and* \(\psi\) for
certain choices of \(\psi\) involving translations of that vocabulary
into English.)

The above line of thought points in some interesting further
directions. For example, the intuitionistic natural deduction rules
governing \(\wedge\) (in Set-Fmla),
which are the same as the classical ones, are
themselves stronger than the following
rules:^{[24]}

We can take the intuitionistic (and classical) rules to differ from these in replacing the formula variable \(\chi\) with a set-of-formulas variable \(\Gamma\). The latter set is stronger in the sense that there are sequents provable with its rules (e.g., \(p, q \succ p \wedge q)\) which are not provable on the basis of the displayed rules (together with the standard structural rules, if desired). But clearly the displayed rules uniquely characterize \(\wedge\), since, once we reduplicate them for \(\wedge'\), we can take \(\chi\) in the second and third (collectively, \((\wedge\text{E})\)-style) rules to be \(\phi \wedge \psi\), to derive both \(\phi \wedge \psi \succ \phi\) and \(\phi \wedge \psi \succ \psi\), from which by the reduplicated version of the first (\(\ldquo(\wedge'\text{I})\rdquo\)) rule we derive \(\phi \wedge \psi \succ \phi \wedge' \psi\)—with a similar derivation for the converse sequent.

This example may seem far-fetched from the point of view of
motivation, but the dialectical upshot is clear—if the \(\neg\)
rules are objectionable in being stronger than needed for unique
characterization, the same holds for the intuitionistic \(\wedge\) rules;
in any case there are in fact variations on this theme is that have
been seriously proposed as weakenings of classical (or intuitionistic)
logic in the construction of quantum (or ortho-) logic, in which the
rule \((\vee\text{E})\) is subjected to restrictions blocking arbitrary sets of
side-formulas—the \(\Delta\) and \(\theta\) of our formulation of this
rule in Section
2—exactly
as with the \(\wedge\) rules inset above (which would be fully general in
the respect at issue if our chosen framework were what would naturally
be called Fmla-Fmla, a
framework occasionally used for logical
investigations).^{[25]}
One could explore the idea of a requirement that all rules should be
maximally general in respect of side formulas, to resist such
pressures to weaken the intuitionistic rules, though what this amounts
to depends on the logical framework, and it may be hard to hold the
line without succumbing to a similar pull in the direction of
generality which would take us over from Set-Fmla
to Set-Set.

The sensitivity to logical framework of issues of unique characterization is well illustrated with the case of modal logic. It is possible to fabricate special purpose logical frameworks which allow for the formulation of rules uniquely characterizing \(\Box\) in all normal modal logics (Blamey and Humberstone 1991), but without such exotic devices, unique characterization is limited to the case in which \(\Box\) is fully determined—among the normal modal logics, then, just to that for which \(\vdash \Box \phi\) for all \(\phi\), and that in which \(\phi \dashv \vdash \Box \phi\) for all \(\phi\). (Note 34 is relevant here. The \(\ldquo\vdash\rdquo\) just used stands for the local consequence relation concerned so we could equally well have written, \(\ldquo\vdash \phi \leftrightarrow \Box \phi\rdquo\). Even more exotic logical frameworks for modal logic – taking us further still from the idea of an argument with premisses and conclusion(s), that is – have been proposed than that just alluded to, several of which are described in Poggiolesi and Restall 2012 and in the literature cited in their bibliography.)

This same framework-sensitivity issue can be illustrated by considering substructural logics in multiset-based frameworks. Classical Linear Logic has two versions of the propositional constants (or 0-ary connectives) \(\bot\) and \(\top\), called (in the relevance tradition—see Avron 1988—rather than in the notation of the seminal paper Girard 1987) \(F\) and \(f\) in the former case and \(T\) and \(t\) in the latter, with the following Mset-Mset rules, the Greek letters now standing for finite multisets of formulas (and commas for multiset union):

\[\begin{align} &(F~\text{Left)}\quad \Gamma, F\succ\Delta & &(T~\text{Right)}\quad\Gamma\succ T, \Delta\\ &(t~\text{Left})\quad \frac{\Gamma \succ\Delta}{\Gamma, t\succ\Delta} & &(t~\text{Right)}\quad \succ t \\ &(f~\text{Left})\quad f\succ & &(f~\text{Right})\quad \frac{\Gamma\succ\Delta}{\Gamma\succ f, \Delta} \end{align}\]
If we were doing classical logic with multisets, we would need the
structural rules (Id), (Weakening) and (Cut) from Section
2,
set-variables now reinterpreted as multiset variables, and the
further rule of Contraction to allow double occurrences of formulas on
the left or right of the \(\succ\) to be replaced by single occurrences.
For linear logic we retain only (Id) and (Cut), disallowing weakenings
and contractions, which has the effect that there are now also two
versions of conjunction and of disjunction, multiplicative and
additive—into which distinction we cannot go further here,
except to say that for binary connectives it lines up with the
intensional/extensional distinction in the relevance
tradition.^{[26]}
A sequent calculus presentation of the favoured logic from this
tradition, \(\mathbf{R}\), can be obtained from that for Classical
Linear Logic (without two of its characteristic 1-ary connectives,
called exponentials, which are there to mark formulas for which
weakening and contraction are permitted) by allowing contraction
(while still banning
weakening).^{[27]}
We return to \(\mathbf{R}\) in Example 6 of Section
4;
it is for the sake of that return that the rules governing \(t\)
and \(T\) have been given here alongside those for \(f\) and
\(F\), the latter pair being of current interest. Notice that
even though there is only one rule for \(F\), namely a left
insertion rule (with no premiss sequents), this rule suffices to
characterize \(F\) uniquely, since in the combined language with
\(F'\) governed by a like rule we can prove—just by
appealing to the appropriate instance of the rule \(F \succ F'\) and \(F' \succ F\). The weaker
system of Intuitionistic Linear Logic is cast in the framework Mset-Fmla\(_0\)
disallowing the appearance of more than one formula on the right, and
this application of the left rule for \(F\) is available there,
as also in Mset-Fmla,
requiring exactly one formula on the right (since we have exactly one
formula—\(F\) or \(F'\)—there in the
present case). When we turn to \(f\), again we find that the
rules uniquely characterize this connective, since \((f \text{ Left})\)
provides the premiss for an application of \((f'\text{ Right})\)
with \(\Gamma\) consisting of (one occurrence of) \(f\) and \(\Delta\)
empty, yielding \(f \succ f'\), with the
converse proved similarly. (Note that while \(F \succ f\) is a special case of the (left) rule for \(F\), there
is no proof of the converse sequent. One cannot begin with \(f \succ\) and then weaken in an \(F\) on the right, since we do not
have
Weakening.^{[28]})
Again, these derivations go through in Mset-Fmla\(_0\),
but
this time we note that they do not go through in Mset-Fmla,
since the left
insertion rule has no applications in that framework. When attention
is restricted to Mset-Fmla,
there is no set of pure rules available which
uniquely characterize \(f\). The Mset-Mset
(or Mset-Fmla\(_0)\)
sequent calculus rules for \(\neg\), which can be taken to be those given
in Section
2
with the set-variables taken as multiset-variables (suitably
restricted for Mset-Fmla\(_0)\),
uniquely characterize \(\neg\), but
have no direct application in Mset-Fmla
or any other framework with a fixed multiset
cardinality on the right (or the left, for that matter). We can say in
this framework that the rules governing \(\neg\) uniquely characterize
this connective *in terms of* \(\rightarrow\) and \(f\)—on
the basis of which it would indeed be explicitly definable \((\neg \phi\) as \(\phi \rightarrow f)\), but since here \(f\) is not
uniquely characterized (even though \(\rightarrow\) is), this still leaves
\(\neg\) without its (perhaps) expected uniqueness, as is even more
evident in Fmla. These considerations continue
to apply in the presence of contraction (and \(\wedge/\vee)\) distribution,
accounting for the complaint sometimes made that relevant logic does
not operate with a uniquely characterized negation. The point here has
not been either to press or to reply to such complaints, but to note
their framework sensitivity: they do not arise for Mset-Mset
or Mset-Fmla\(_0\).

The existence and uniqueness questions for connectives turn out in the
case of sequent calculus rules to be intimately connected with the
structural rules (Id) and (Cut). Let us call the left and right
insertion rules governing an \(n\)-ary connective #—or
derivatively, the connective thereby
governed—*Id-inductive* if the provability of
\(\#(\phi_1 ,\ldots ,\phi_n) \succ \#(\phi_1 ,\ldots ,\phi_n)\) follows from
the provability of each \(\phi_{i} \succ \phi_{i} (i = 1,\ldots ,n)\) by
means of those rules (without assistance from other structural rules).
This means that no provable sequents are lost if the rule (Id) itself
is restricted to having applications \(\phi \succ \phi\) for \(\phi\) a
propositional variable. And let us say that the rules in question are
*Cut-inductive* if an application of the rule (Cut) with the
formula \(\#(\phi_1 ,\ldots ,\phi_n)\) as
cut-formula (i.e., as the \(\phi\) of our representation of the rule
(Cut) in Section
2
or the analogous rule in Set-Set
or the multiset based frameworks) can be
dispensed with if the premiss sequents for the application of the rule
have been derived by (\(\#\) Left) and (\(\#\) Right) and (Cut) is allowed with
the components \(\phi_1 ,\ldots ,\phi_n\)
as cut-formulas (but again, not allowing the use of other structural
rules).

All the connectives of the standard sequent calculi, including the cases of classical and intuitionistic linear logic, are inserted by rules which are both Id-inductive and Cut-inductive, as we illustrate here with the rules for \(\rightarrow\). For definiteness, think of these as the Left and Right rules of classical linear logic. To show Id-inductivity, we must show that \(\phi \rightarrow \psi \succ \phi \rightarrow \psi\) is provable using the \(\rightarrow\) rules, given (‘the inductive hypothesis’) that \(\phi \succ \phi\) and \(\psi \succ \psi\) are. (We write \(\phi\) and \(\psi\) rather than \(\phi_1\) and \(\phi_2\).) From the last two sequents, \((\rightarrow\) Left) delivers: \(\phi \rightarrow \psi , \phi \succ \psi\). From this an application of \((\rightarrow\) Right) gives the desired conclusion: \(\phi \rightarrow \psi \succ \phi \rightarrow \psi\).

For Cut-inductivity suppose (1) \(\Gamma , \Gamma', \phi \rightarrow \psi \succ \Delta , \Delta'\) has arisen by \((\rightarrow\) Left) from (1a) \(\Gamma \succ \phi , \Delta\) and (2a) \(\Gamma', \psi \succ \Delta'\), while (2) \(\Gamma'' \succ \phi \rightarrow \psi , \Delta''\) has arisen by \((\rightarrow\) Right) from (2a) \(\Gamma'', \phi \succ \psi , \Delta''\). We need to show that a cut on (1) and (2) with cut-formula \(\phi \rightarrow \psi\) can be avoided on the hypothesis that we can help ourselves to cuts with cut-formulas \(\phi , \psi\). From (1a) and (2a), cutting on \(\phi\), we get (3) \(\Gamma , \Gamma'' \succ \psi , \Delta''\). Then cutting on \(\psi\), (2b) and (3) deliver the desired conclusion: \(\Gamma , \Gamma', \Gamma'' \succ \Delta , \Delta', \Delta''\), without the need to use \(\phi \rightarrow \psi\) as a cut-formula with (1) and (2) as premisses.

Cut-inductivity is one aspect of a procedure which has traditionally
been a professional obsession of proof-theorists: the provision of
‘Cut Elimination’ theorems to the effect that this or that
sequent calculus with the rule (Cut) can have this rule removed
without the loss of any provable sequents. Obviously more is needed to
show this than the Cut-inductivity of the (pairs of) rules, since
there are also, *inter alia*, potential interactions with the
other structural (and operational) rules to be taken care of. Such
results are of interest because much follows from the subformula
property—any sequent provable has a proof in which the only
formulas to appear are subformulas of those in the sequent
concerned—which itself follows from the result since all the
remaining rules insert material rather than remove it in the course of
the
proof.^{[29]}
But from the perspective of the philosophy of logic, Cut-inductivity
and its somewhat less well-publicized companion, Id-inductivity,
should be considered on a par, as the following somewhat
impressionistic semantical remark (Girard, Taylor and Lafont 1989, p.
31) of Girard suggests, apropos of (Cut), in which \(C\)
represents the cut formula (and (Id) with \(C\) on the left and
right of the \(\ldquo\succ\rdquo\)):

The identity axiom says that \(C\) (on the left) is stronger than \(C\) (on the right); this rule [ = (Cut)] states the converse truth, i.e. \(C\) (on the right) is stronger than \(C\) (on the left).

The point of isolating Id- and Cut-inductivity here, however, has less to do with matters of truth (on which, and for further references to Girard on which, see further Hösli and Jäger 1994) than with uniqueness and existence—not that the semantical issues are unconnected with this, of course. The former link is perhaps already clear. At the last step of establishing Id-inductivity for \(\rightarrow\), above, we passed from \(\phi \rightarrow \psi , \phi \succ \psi\), obtained by \((\rightarrow\) Left), to \(\phi \rightarrow \psi \succ \phi \rightarrow \psi\), by \((\rightarrow\) Left): but this is just what the uniqueness proof in the reduplicated sequent calculus would do, except that the final step would be an application of \((\rightarrow'\) Right) and would establish \(\phi \rightarrow \psi \succ \phi \rightarrow' \psi\), with the converse proved by interchanging the rules used for \(\rightarrow\) and \(\rightarrow'\).

To see the connection between existence—or more specifically, the conservative extension side of the existence question—convert the natural deduction rules for \(\Tonk\) given earlier into sequent calculus rules (here for Set-Fmla):

\[ (\Tonk\text{ Left})\frac{\Gamma, \psi\succ\chi}{\Gamma, \phi\Tonk\psi\succ\chi}\qquad (\Tonk \text{ Right})\frac{\Gamma\succ\phi}{\Gamma\succ\phi\Tonk\psi} \]By applying the right insertion rule with premiss sequent (courtesy of (Id)) \(\phi \succ \phi\) and the left rule with premiss \(\psi \succ \psi\) we arrive at the point at which our natural deduction derivation started to go bad. We have:

\[\phi\succ\phi\Tonk\psi \quad\text{and}\quad \phi\Tonk\psi\succ\psi\]
and an appeal to (Cut) here, with \(\phi\Tonk\psi\) as cut-formula, amounts to bringing home the bad
news.^{[30]}
But of course this example simply makes vivid the fact that the \(\Tonk\)
rules in play are not Cut-inductive and there
is no Cut-free proof of the desired sequent (at least in general: take
\(\phi = p, \psi = q)\). This is hardly surprising
since the subformula property which Cut Elimination secures itself
guarantees that the rules for one connective conservatively extend the
subsystem comprising the rules for the remaining connectives. In the
present case, the point of the example was that there was no proof of,
for example, \(p \succ q\) which did not
detour—in violation of the subformula property—via
formulas involving Tonk.

We can look at what is roughly speaking a mirror-image of the \(\Tonk\)
example to reinforce the contrast between
Cut-inductivity and Id-inductivity and their respective links with
existence and uniqueness, and then sort out the “roughly
speaking” part of this description, which will show them as
providing, rather, special—one might say canonical—cases
of the satisfaction of the existence \(( =\) conservative extension) and
uniqueness conditions. We conduct the discussion in Set-Set
rather than Set-Fmla
to avoid a mass of
complications. The above \(\Tonk\) rules combine a
left insertion rule familiar from the sequent calculus treatment of
\(\wedge\) and a right insertion rule familiar from that of \(\vee\); their
reformulation for the change of framework just announced requires an
idle \(\Delta\) parameter on the right of the sequents in the premisses
and conclusions of the rules as schematically presented above
(replacing the \(\chi\) in the one case, accompanying the displayed
succedent formulas in the other). For our mirror image
example,^{[31]}
consider a binary connective Knot with rules
combining instead the left insertion rule for \(\vee\) with the right
insertion rule for \(\wedge\):

These rules are Cut-inductive, as the interested reader may confirm,
but not Id-inductive, since they do not uniquely characterize \(\Knot\).
To see this, note that both are derivable
rules for \(\wedge\) and also for \(\vee\), and of course we cannot prove \(\phi \vee \psi \succ \phi \wedge \psi\) in general. By contrast, neither
\(\wedge\) nor \(\vee\) satisfies *both* of the left and right rules for
\(\Tonk\). The upshot of the \(\Knot\)
rules is best visualised in terms of the
zero-premiss rules (sequent-schemata) with which they are
interderivable given the structural rules: \(\phi ,
\psi \succ \phi \Knot \psi\) (the right rule) and \(\phi \Knot\psi \succ \phi , \psi\) (the left
rule). An incidental point: since these are the sequent formulations
of conditions induced by the determinants \(\langle \rT,
\rT, \rT\rangle\) and \(\langle \rF, \rF, \rF\rangle\) one might think of them together as expressing
idempotence and therefore as being interchangeable with the simpler
pair \(\phi \succ \phi\Knot\phi\) and \(\phi\Knot\phi \succ \phi\). But while the latter
two can be derived from the earlier pair (just take \(\psi\) as \(\phi)\),
the converse derivation is not possible without further
principles—conspicuously, a sequent version of the
extensionality conditions on generalized consequence relations
mentioned in Section
2.
We could call binary \(\#\) for which \(\phi , \psi \Vdash \phi\hash\psi\)
and conversely, *strongly idempotent* according to the
generalized consequence relation \(\Vdash\). Then \(\wedge\) and \(\vee\) are not
the only Boolean candidates for a connective behaving as the \(\Knot\)
rules dictate—strongly idempotent
according to the generalized consequence relation
\(\Vdash_{CL}\) determined by the class of Boolean
valuations: we also have the binary projection to the first coordinate
\((\phi\hash\psi\) equivalent to \(\phi)\), to the second coordinate \((\phi\hash\psi\) equivalent to \(\psi)\), and venturing further afield, the Set-Fmla
hybrids of any two
of these connectives. Of these perhaps the most interesting is the
hybrid of the two projection connectives, since this—let us
write is as \(\ldquo\bullet\rdquo\)—can be used to define all other
hybrids explicitly from the connectives to be hybridized; for example
if we want the common properties (as explained in Section
2)
of \(\rightarrow\) and \(\vee\), we have them in the following compound of \(\phi\)
and \(\psi : (\phi \rightarrow \psi) \bullet(\phi \vee \psi)\).^{[32]}

If the treatment of \(\Knot\) were genuinely the
mirror image of that of \(\Tonk\), we would be able
to say that just as the \(\Knot\) rules are
Cut-inductive but not Id-inductive, so the \(\Tonk\)
rules are Id-inductive but not Cut-inductive.
(The twofold demand of Cut- and Id-inductivity is a promising
candidate for the notion of *harmony* as it applies to the
relation between right and left insertion rules in a sequent
calculus.^{[33]})
And while the failure of Cut-inductivity was indeed noted, nothing
was said on the subject of Id-inductivity for these rules. Spoiling
the intended duality, the situation is that the \(\Tonk\)
rules fail on this score too—though this
can be remedied by a simple variation. First, we should note that
Prior’s point could equally well have been made by combining the
\(\vee\) introduction rule from the *second* (rather than the to
first) disjunct with the \(\wedge\) elimination rule to the *first*
(rather than to the second) conjunct. Call the connective with these
rules \(\Tonk^*\)

This suffers from the same defects in respect of the analogy with
\(\Knot\), so, finally, let \(\Tonk^+\) be governed by the rules for
\(\Tonk\) and also the rules for \(\Tonk^*\). It is \(\Tonk^+\) that
has \(\Knot\) as its mirror image, since just as \(\Knot\) has the
full force of the \((\wedge\) Right) and \((\vee\) Left) rules,
\(\Tonk^+\) enjoys the full force of the \((\wedge\text{ Left})\) and
\((\vee\text{ Right})\) rules. (So here we arrive at the reason that
\(\Knot\) was originally described as only *roughly speaking* a
mirror image of \(\Tonk\).) And this time the rules are indeed
Id-inductive without being Cut-inductive. Indeed, Id-inductivity is
secured by two independent routes: by the interaction of the \(\Tonk\)
Left rule for \(\Tonk^+\) with the \(\Tonk^*\) Right rule to
\(\Tonk^+\), and then again by the interaction of \(\Tonk^+\)‘s
\(\Tonk^*\) Left rule with its \(\Tonk\) Right rule. (To give the
former in more detail, by way of example, the \(\Tonk\) Left rule for
\(\Tonk^+\) gives \(\phi\;\Tonk^+\; \psi \succ \psi\) from
(Id)-for-\(\psi\), from which applying the \(\Tonk^*\) Right rule for
\(\Tonk^+\) we obtain \(\phi\;\Tonk^+\; \psi \succ \phi\;\Tonk^+\;
\psi\).)

Let us sum up the lessons for the relations between existence and Cut-inductivity and between uniqueness and Id-inductivity that can be extracted from the foregoing discussion. Sequent calculus rules which are Id-inductive uniquely characterize the connective they govern, but not necessarily conversely: the \(\Tonk\) rules are not Id-inductive, but they do uniquely characterize \(\Tonk\), since they are already so strong that any sequent with at least one formula on the left and at least one on the right can be proved with their aid, and hence, in the reduplicated system with \(\Tonk'\), we can certainly prove \(\phi\Tonk\psi \succ \phi\;\Tonk'\; \psi\) and the converse sequent—without even using the \(\Tonk'\) rules! (This is the kind of thing we have in mind in calling this a non-canonical form of uniqueness.) On the ‘existence’ side: it is not clear to the author whether any Cut-inductive rules governing a connective guarantee that they are conservative over the (system consisting of the) rules governing other connective—since Cut Elimination may fail for other reasons; nor do the examples just considered settle the converse, as we see from the following tabular summary of our findings, in which (a “Yes” by) “unique” means the rules uniquely characterize the connective, and “conservative” means that we have a conservative extension of any system of sequent-calculus rules not involving the given connective; \(\Tonk^*\) is not listed separately since it patterns the same way as \(\Tonk\):

Id-inductive | Unique | Cut-inductive | Conservative | |

\(\Tonk\) | No | Yes | No | No |
---|---|---|---|---|

\(\Tonk\)\(^+\) | Yes | Yes | No | No |

\(\Knot\) | No | No | Yes | Yes |

That is enough on the subject of \(\Tonk\) and
variations. We will make one point about unique characterization and
then give some examples of non-conservative extension which will
involve introducing the important concepts of *special* and
*universally representative connectives*. Some further
‘existence’ examples are deferred to the following
section.

The above discussion has included such phrases as “the hybrid of
\(\wedge\) and \(\vee\rdquo\); the totality of principles governing such a
connective being those common to \(\wedge\) and \(\vee\), we obviously do not
have a connective uniquely characterized by those principles—in
which case is it legitimate to speak of *the* hybrid…? I
take this way of speaking to be as harmless as speaking of “the
\(\Box\) operator of \(\mathbf{S5}\rdquo\), where again the
logical principles involved are insufficient to characterize the
connective uniquely—in terms of the Boolean connectives or
otherwise—at least if we are in Fmla,
Set-Fmla or Set-Set,
and in the latter
cases, working with the so-called *local* (generalized)
consequence
relation.^{[34]}
(See Section
5
for the distinction between the local and the global consequence
relations determined by a class of models.) One could say that in the
monomodal, unreduplicated case, we have a single connective playing a
certain role and we can refer to it in that context as *the*
connective playing the role in question, while conceding, as we learn
from the reduplicated case, that this is a role that can be played
simultaneously (i.e. in a single logic) by several non-equivalent
connectives. This is the kind of situation Łukasiewicz had in
mind when, in his (1953), he likened certain pairs of connectives to
“twins who cannot be distinguished when met separately, but are
instantly recognised as two when seen together”.

We saw earlier that combining the intuitionistic and classical rules
in a single proof system did not work well, and another suggestion
that comes to mind is that we could perhaps extend intuitionistic
logic with a new connective, 1-ary \(\#\), say, which does what according
to the intuitionist, negation \((\neg)\) itself cannot do: serve as a
left inverse for \(\neg\) in the sense of rendering equivalent
\(\#\neg \phi\) and \(\phi\) for all
\(\phi\).^{[35]}
This again represents an offer the intuitionist cannot afford to
accept, assuming that any (the rules for any) proposed new connectives
should conserve synonymy, as suggested above. (The even stronger
demand that the consequence relation associated with the extended
proof systems should be congruential does not seem unreasonable.) The
reason is that \(\neg p\) and \(\neg \neg \neg p\) are
intuitionistically equivalent (and thus synonymous according to
\(\vdash_{IL})\) so the conservation of synonymy
requires that \(\#\neg p\) and \(\#\neg \neg \neg p\) should
be equivalent—since we have this ‘Law of Triple
Negation’ equivalence in intuitionistic logic—from which
the left inverse condition above delivers, taking \(\phi\) as
\(\neg p\) in the former case and as \(\neg \neg \neg p\) in
the latter, the equivalence of \(p\) with
\(\neg \neg p\)—a straightforwardly non-conservative
extension, then. (A similar argument shows that adding binary \(\#\) with
\(\phi\hash(\phi \leftrightarrow \psi)\) equivalent to \(\psi\)—a possibility
suggesting itself since, by contrast with the classical case, \(\leftrightarrow\)
itself cannot serve as \(\#\) here—is also non-conservative.) Nor,
incidentally, could the intuitionist acknowledge the existence of a
*right* inverse for negation, a \(\#\) with arbitrary \(\phi\)
equivalent to \(\neg\#\phi\), as this makes every formula equivalent to
a negated formula and hence to its own double negation. This argument,
which is well known (see, e.g., Koslow (1992), p. 97), does not even
require the ‘conservation of synonymies’ constraint.

These last non-existence proofs force our attention on the fact that
negated formulas are ‘special’ in intuitionistic logic in
that each such formula is equivalent to its own double negation while
this is not so for arbitrary formulas. Let us back up and give a clear
explanation of the notion of specialness as well as a contrasting
notion, in slightly more general terms; for definiteness only, we
tailor the account
to Set-Fmla. We also
begin with the contrasting notion. Say that an \(n\)-ary relation
\(R\) among the formulas of a language is *universally
representative* according to a consequence relation on that
language if for any formulas \(\phi_1 ,\ldots ,\phi_n\) of the
language, there are formulas \(\psi_1 ,\ldots ,\psi_n\), respectively
synonymous with \(\phi_1 ,\ldots ,\phi_n\) according to \(\vdash\),
with \(R(\psi_1 ,\ldots ,\psi_n)\). (If \(n = 1\), we speak instead of
a universally representative
*class* of formulas—a class of formulas such that every
formula is synonymous with some formula in the class; likewise in the
case of the notion *special*, defined below.) If \(\vdash\) is
congruential then we can replace “synonymous” in this
definition with “equivalent” (i.e. such that
\(\phi_{i} \dashv \vdash \psi_{i}\),
for \(i = 1,\ldots ,n)\). Say that \(R\) is
*special* according to \(\vdash\) if there is some Set-Fmla
sequent \(\sigma(p_1 ,\ldots ,p_n)\) constructed using not
necessarily just the variables exhibited, for which for any formulas
\(\psi_1 ,\ldots ,\psi_n\) with
\(R(\psi_1 ,\ldots ,\psi_n)\), we
have \(\sigma(\psi_1 ,\ldots ,\psi_n)
\in\, \vdash\), while we do not have, for all formulas
\(\phi_1 ,\ldots ,\phi_n\), \(\sigma(\phi_1 ,\ldots ,\phi_n)
\in\, \vdash\). For substitution-invariant \(\vdash\), this last
condition can be simplified to:
\(\sigma(p_1 ,\ldots ,p_n) \not\in\, \vdash\).^{[36]}
A consequence of these definitions is that no relation is both
universally representative and special according to any given \(\vdash\).
A simple example of a special relation—according to more or less
any ‘naturally occurring’ consequence relation with \(\vee\)
in its language is the relation \(R\) obtaining between \(\phi\) and
\(\psi\) just in case \(\psi\) is a disjunction of which \(\phi\) is a
disjunct. Here take \(\sigma(p, q)\) as \(p \succ q\) which is (e.g., in intuitionistic logic, though
classical logic or any of many others would do as well)
unprovable—i.e., not \(p \vdash_{IL} q\)—while \(\phi \vdash_{IL} \psi\) for
all \(\phi , \psi\) for which \(R(\phi , \psi)\). A more
interesting example is the relation of being (intuitionistically)
*head-linked*, i.e., that relation \(R\) such that for all
\(\phi , \psi , R(\phi , \psi)\) if and only if:

for some formulas \(\chi , \phi_0, \psi_0\), we have \(\phi \dashv \vdash_{IL} \phi_0 \rightarrow \chi\) and \(\psi \dashv \vdash_{IL} \psi_0 \rightarrow \chi\).

The analogous relation for classical logic would be universally representative (and thus not special), at least in any fragment which, as well as having \(\rightarrow\), has either \(\bot\) or \(\wedge\), since any \(\phi\) and \(\psi\) are here respectively equivalent to \((\phi \rightarrow \bot) \rightarrow \bot\) and \((\psi \rightarrow \bot) \rightarrow \bot\), where they are linked explicitly by having a common \(\chi\) at the head of the main implication. (Alternatively with \(\wedge\), replace \(\bot\) here by \(\phi \wedge \psi\).) But in the intuitionistic case the relation of being head-linked is special since, for example, with Peirce’s law \(\sigma(p,q) = (p \rightarrow q) \rightarrow p \succ p\), we have \(\sigma(p, q)\) intuitionistically unprovable but we have \(\sigma(\phi ,\psi) \in\, \vdash_{IL}\) for any head-linked \(\phi , \psi\).

Concentrating now on 1-ary relations between—i.e., classes
of—formulas, we transfer the above terminology to connectives by
saying that a connective is *universally representative* or
*special* according to a consequence relation if the class of
formulas with the given connective as main connective is itself a
universally representative class or a special class of formulas,
respectively, according to the consequence relation in question. While
every non-constant
connective^{[37]}
is universally representative according to
\(\vdash_{CL}\) our discussion of inverses for
intuitionistic \(\neg\) shows that \(\neg\) is special according to \(\vdash\),
since we can take \(\sigma(p)\) as \(\neg \neg p \succ p\) and every substitution instance of this IL-unprovable
sequent in which \(p\) is replaced by a negated formula is
IL-provable. Negation is therefore not universally representative in
intuitionistic logic. (This means that we could usefully speak, from
the perspective of \(\vdash_{IL}\), of negative
*propositions*, thinking of the equivalence class, with respect
to the relation of synonymy, of a formula as the proposition thereby
expressed, and meaning by this the equivalence classes of negated
formulas. Classically, the corresponding notion is not useful since
all propositions would count as negative, just as for both
\(\vdash_{CL}\) and \(\vdash_{IL}\), there
are no specifically conjunctive or disjunctive propositions.)

Although the properties of being special and being universally
representative according to a given logic are mutually exclusive, they
are not jointly exhaustive. For example, \(\bot\) is neither universally
representative nor special in minimal logic (according to the
consequence relation associated with the Johansson’s
*Minimalkalkül*, that is). Nor does the connective \(\Box\)
have either of these properties in the modal logic \(\mathbf{KD}\)
(sometimes just called \(\mathbf{D})\), though this example is far
from selected at random: in the sublogic \(\mathbf{K}, \Box\)
is special (since \(\Box \bot \rightarrow \phi\) is provable for all
\(\Box\)-formulas \(\phi\), though not for arbitrary \(\phi)\), and in the
extension \(\mathbf{KD4}\) it is special again (since \(\phi \rightarrow \Box \phi\) is provable for all \(\Box\)-formulas \(\phi\), though not
for all formulas).

## 4. Selected Existence Questions

### 4.1 Conditions not Corresponding to Rules (Example 1)

For conditions other than those corresponding to (closure under certain) rules we can also ask whether a connective satisfying the condition in question can safely—i.e. conservatively—be postulated to exist. One such condition is the following, here expressed as a condition on a consequence relation \(\vdash\) with a binary connective \(\hash\) in its language, all variables understood as universally quantified:

\(\Gamma \vdash \phi\hash\psi\) if and only if \(\Gamma \vdash \phi\) or \(\Gamma \vdash \psi\).

It is because of the “or” on the right that this
condition—more precisely, its ‘only if’
half—does not correspond to a sequent-to-sequent rule. Still we
can ask whether some Set-Fmla
proof system including the rule \((\vee\text{E})\) (or the
sequent calculus rule \((\vee\text{ Left})\)), e.g. for classical logic, has a
conservative extension to a proof system for a language with the
additional connective \(\#\), whose associated consequence relation
satisfies the above condition for this
\(\#\).^{[38]}
To see that the answer to this question is negative, note that the
binary relation R\(_{\vdash}\) defined in terms of the
\(\#\)-supporting extension \(\vdash :
R_{\vdash}(\phi ,\psi)\) iff \(\phi \vdash \psi\),
gives rise to a binary relational connection
\((R_{\vdash}, L, L)\) which provides
conjunctive (yes—*con*junctive) combinations on the left,
since \(\vdash\) is \(\vee\)-classical, \(\phi \cdot_L \psi\) here being \(\phi \vee \psi\), while the inset condition above
(take \(\Gamma = \{\chi \})\) secures disjunctive objects on the right,
with \(\phi +_R \psi\) being \(\phi\hash\psi\).
(\(\ldquo L\rdquo\) and \(\ldquo R\rdquo\) subscripts from
Section
1
restored here to prevent confusion, since the source and target
coincide.) Thus the crossover condition from Section
1
is satisfied, which says that if \(\phi_1 \vdash \psi_1\) and \(\phi_2 \vdash \psi_2\) then
either \(\phi_1 \vdash \psi_2\) or
\(\phi_2 \vdash \psi_1\). Taking \(\phi_1 = \psi_1 = \chi\) and \(\phi_2 = \psi_2 = \chi'\), we have the antecedent of this conditional (by (Id)),
so we conclude that for all formulas \(\chi , \chi'\), either \(\chi \vdash \chi'\) or \(\chi' \vdash \chi\), which includes
\(\#\)-free formulas of the original language (e.g., \(\chi = p,
\chi' = q)\) for which neither is a consequence of the
other by the original consequence relation, showing any proposed
extension along the above lines to be non-conservative.

### 4.2 Pollard-Style Nonconservativity (Example 2)

This is really a whole range of examples. As we required \((\vee\text{E})\) for
Example 1, here we require \((\rightarrow\text{I})\). Let us call a consequence
relation \(\vdash \rightarrow\)-*introductive* if \(\Gamma , \phi \vdash \psi\) always implies \(\Gamma \vdash \phi \rightarrow \psi\).^{[39]}
Now suppose \(\vdash \supseteq \vdash_{IL}\) and \(\vdash\)
is \(\rightarrow\)-introductive, and either (i) for some \(n\)-ary
connective \(\#\), \(\vdash\) satisfies the conditions induced (on consequence
relations) by the determinant \(\langle\)F,…, F,T\(\rangle(n\)
occurrences of “F”) for \(\#\), as well as some determinant
with F as its final entry, or (ii) \(\vdash\) satisfies the conditions
induced by the determinant \(\langle \rT,\ldots, \rT, \rF \rangle\)(\(n\)
occurrences of \(\ldquo\rT\rdquo\)) as well as some determinant with \(\rT\) as
final entry (for \(n\)-ary \(\#\)). Then it follows that \(\vdash \supseteq \vdash_{CL}\).

The implication from (i) to the conclusion that \(\vdash \supseteq \vdash_{CL}\) has been stressed in several
publications by S. Pollard (Pollard 2002, Pollard and Martin 1996);
there is a similar proof for the implication from (ii). Neither proof
is given here—only an illustration (of case (ii)). The
truth-function known as exclusive disjunction (or *xor*), which
differs from that associated on Boolean valuations with \(\vee\)
(“inclusive disjunction”) by having \(\langle \rT, \rT, \rF\rangle\)
instead of the determinant \(\langle \rT, \rT, \rT\rangle\), will serve as an
example, since as well as the determinant just mentioned, which has
T’s except for the final \(\rF\), we have a \(\rT\)-final determinant (e.g.)
\(\langle\rT, \rF, \rT\rangle\). The induced conditions on generalized consequence
relations for these two determinants are respectively:

For the following, we will take it that, as well as \(\rightarrow\), the connectives \(\vee , \neg , \top\) and \(\bot\) are available, though in fact the result just given requires is correct for any fragment with \(\rightarrow\) (with \(\vdash_{CL}\) understood as the restriction of the classical consequence relation to the fragment in question). Then we can write the induced conditions on our consequence relation \(\vdash\) as, respectively, rather than using a new schematic letter on the right for the first, and converting the second into conditional form:

\[\phi,\psi,\phi\hash\psi\vdash\bot \quad\text{and}\quad \phi\vdash\psi\vee(\phi\hash\psi).\]
Now making use of the hypothesis that \(\vdash\) is
\(\rightarrow\)-introductive—which does *not* follow from the fact
that \(\vdash_{IL}\) is \(\rightarrow\)-introductive and \(\vdash \supseteq \vdash_{IL}\)—the first condition now
allows for successive rewriting, first as

and then as

\[\phi\hash\psi\vdash\phi\rightarrow\lnot\psi.\]The fact that \(\vdash\) is an \(\rightarrow\)-introductive extension of \(\vdash_{IL}\) suffices for \(\vdash\) to be \(\vee\)-classical, and in particular for it to be ‘\(\vee\)-eliminative’ in the sense that whenever \(\Gamma \vdash \chi_1 \vee \chi_2\) and also \(\Gamma', \chi_1 \vdash \theta\) and \(\Gamma'', \chi_2 \vdash \theta\), we have \(\Gamma , \Gamma', \Gamma'' \vdash \theta\). Thus from the fact that \(\phi \vdash \psi \vee(\phi\hash\psi)\), inset on the right above, and that \(\phi\hash\psi \vdash \phi \rightarrow \neg \psi\), we may conclude that \(\phi \vdash \psi \vee(\phi \rightarrow \neg \psi)\). Not only does this fail—e.g., with the schematic letters replaced by distinct propositional variables—for \(\vdash_{IL}\), making the extension non-conservative, it takes us all the way to \(\vdash_{CL}\), as claimed in the general formulation ((i) and (ii)) of the result. To see this most easily in the present case, take \(\phi\) as \(\top\).

Does any of this mean that there is a problem in finding an
intuitionistic analogue of exclusive disjunction? Not at all. There
are many derived binary connectives all of which form compounds
equivalent in classical logic to the exclusive disjunction of \(\phi\)
with \(\psi\) and which are in the interesting cases not equivalent to
each other intuitionistically—for example, \(\phi \leftrightarrow \neg \psi\) and \(\neg(\phi \leftrightarrow \psi)\) and \((\phi \vee \psi) \wedge \neg(\phi \wedge \psi)\). As it happens, the third of these (which is
IL-equivalent to \((\phi \wedge \neg \psi) \vee(\neg \phi \wedge \psi))\) has an especially close relationship with
the truth-function of exclusive disjunction, like that between
intuitionistic \(\neg\) and the negation truth-function, which can be
explained in terms of the Kripke semantics for intuitionistic logic
(not explained in this entry) by saying that the compound in question
is true at a point just in case at every accessible point it is true
when evaluated by using the corresponding boolean function and the
truth-values of the components at that
point.^{[40]}
Note that the negation truth-function itself has its
determinant-induced conditions rules dangerous to the health of
intuitionistic logic under both (i) and (ii) of the result at the
start of this example: no single connective can conservatively form
from a formula a contrary of that formula (as \(\langle\rT, \rF\rangle\) demands) and also a subcontrary of
that formula (as \(\langle\rF, \rT\rangle\) demands). As it is often put,
standard intuitionistic negation \((\neg)\) forms the deductively weakest
contrary of a formula, while dual intuitionistic negation (mentioned
only in passing in this entry) forms its deductively strongest
subcontrary.^{[41]}

### 4.3 Negation by Iteration (Example 3)

Could there be a 1-ary connective \(\#\) two successive applications of
which amounted to a single application of (say) classical
negation?^{[42]}
If we work in Set-Set
an austere version of this question amounts to asking about the fate
of \(\#\) subjected, alongside the standard structural rules, to the
condition that for all \(\phi\):

should both be provable, to which it is natural to add immediately
that \(\#\) should be congruential according to the generalized consequence
relation associated with this proof system. Without the latter
addition, we could just think of \(\ldquo\#\#\rdquo\) as an
idiosyncratically long-winded way of writing \(\ldquo\neg\rdquo\). With
it, we are insisting that a single occurrence of “#” is
genuinely responsive to the content of what it applies to. It is not
hard to see that there is no (two-valued) truth-functional
interpretation available for \(\#\), not just in the weak sense that it
might be said that (for example) \(\Box\) in \(\mathbf{S4}\) does
not admit of such an interpretation—that this logic is
determined by (\(=\) both sound and complete with
respect to) no class of valuations over which \(\Box\) is
truth-functional—but in the stronger sense that the envisaged
logic of \(\#\) is not even *sound* with respect to such a class of
valuations, at least if that class is non-constant in the sense
defined at the end of note
20.^{[43]}
In the paper cited, this congruential logic of what is there and in
an earlier paper there referred to as demi-negation is discussed and
equipped with a Kripke-style semantics (essentially re-working an
earlier 4-valued matrix semantics) the upshot of which is that
classical propositional logic or any fragment thereof is
conservatively extended by the two zero-premiss rules inset
above—or alternatively, assuming \(\neg\) is in the fragment, by
the equivalence of \(\neg \phi\) and \(\#\#\phi\)—and a congruentiality
rule for \(\#\). Nevertheless it is hard to imagine, “from the
inside”, speaking a language with a connective for which this
provided a suitable formal treatment. The description suggested at p.
257 of Dalla Chiara, Giuntini, and Greechie (2004), a study in quantum
logic, of such a connective as expressing a kind of *tentative*
negation, seems wrong, since iterating tentative negation would not
produce (untentative) negation: If you tentatively negate the
tentative negation of \(\phi\) you would appear to be headed (however
tentatively) back in the direction of \(\phi\) rather than towards \(\neg \phi\). On the same page of Dalla Chiara *et al.* (2004),
Deutsch *et al.* (2000) are approvingly quoted as saying the
following—in which, since composition is more like
multiplication than addition, demi-negation is referred to as the
‘square root’ of negation:

Logicians are now entitled to propose a new logical operation \(\sqrt{\mathbf{not}}\). Why? Because a faithful physical model for it exists in nature.

I do not recall logicians having to seek the blessing of physicists
before pursuing this or that line of inquiry, or of the interest,
significance or legitimacy (“now entitled to propose…”,
no less) of such inquiries being dependent on empirical and
theoretical findings in physics, when what is under investigation is
most naturally taken to be an *a priori* matter: the coherence
of a connective with given inferential properties. This is not at all
to deny that the ‘quantum machines’ described in Deutsch
*et al.* (2000) (or Chiara, Giuntini, and Greechie 2004,
257–259) may help us get a feel for the connective in
question.^{[44]}

### 4.4 Logical Subtraction (Example 4)

Suppose one wants to say more about the weather than that it rained on
a particular Saturday. One wants to strengthen one’s commitments
so that they include not only rain on Saturday but also rain on the
following Sunday. With \(\wedge\) (assuming some background \(\wedge\)-classical
consequence relation) there is nothing easier. Abbreviating “It
rained on the Saturday in question” to \(\Sat\) and
“It rained on Sunday” to \(\Sun\), one can convert
one’s original statement into one making the stronger claim by
passing from \(\Sat\) to \(\Sat\wedge\Sun\). Now
suppose one wanted a similar device but working in the reverse
direction. One starts with a claim whose content is given by
\(\Sat\wedge\Sun\) and wants to modify this using a
connective which removes commitments in much the way that \(\wedge\) adds
them, and using this connective, often called *logical
subtraction* (though a case could be made for ‘logical
division’ in view of the usual association of conjunction with
multiplication), one wants to take away the commitment to rain on
Sunday, leaving only the original claim. That is, one would like a
connective added to the language of one’s favoured consequence
relation, in such a way that the added connective was governed by
rules making the extension conservative, but for which one had the
equivalence (writing \(\vdash)\) for the extended consequence
relation:

An early and plausible suggestion for the treatment of logical subtraction was made in Hudson (1975). According to this suggestion, no new connective is required, at least if we already have a reasonable implication connective at our disposal, because if we are to think of \(\phi - \psi\) as giving us the result of taking away the content of \(\psi\) from that of \(\phi\), then this should be the weakest statement which, together with \(\psi\), has \(\phi\) as a consequence. But this is just \(\psi \rightarrow \phi\), if the standard natural deduction rules for \(\rightarrow\) from Section 2 are accepted (as in intuitionistic and classical logic). Yet this does not give us the inset equivalence above. If we treat \((\Sat\wedge\Sun)-\Sun\) as \(\Sun\) \(\rightarrow\) (\(\Sat\wedge\Sun\)), then this is equivalent (in the logics just mentioned and many others) to \(\Sun\rightarrow\Sat\), whereas we wanted the stronger \(\Sat\) itself (stronger according to those logics, again).

The example above used an interpreted language with atomic sentences
\(\Sat\) and \(\Sun\). The inset equivalence presented
involving them would not be reasonable for all sentences. Modulating
back to the issue of a formal propositional logic involving the
envisaged new connective, such an equivalence would not be reasonable
for arbitrary \(\phi\) and \(\psi\) in place of them, since we would expect
the new connective to be congruential according to the desired
consequence relation, and any unrestricted such equivalence would then
deliver from \(\phi_1 \wedge \psi \dashv \vdash \phi_2 \wedge \psi\)—by “subtracting \(\psi\) from
both sides” (in view of congruentiality)—the conclusion
that \(\phi_1 \dashv \vdash \phi_2\), and it easy
to find counterexamples to such cancellation inferences for even quite
weak initial logics. Since the counterexamples arise for
\(\phi_1, \phi_2\), in the language unexpanded by
\(\ldquo-\rdquo\), the sense in which a generalized version of the
earlier equivalence would not be reasonable is that it would not be
conservative over the initial logic. Here we say no more about how to
constrain the equivalence in question, or, more generally, about
whether there really is any such logical subtraction connective as we
have been
envisaging.^{[45]}

### 4.5 A Multiple Existence Question (Example 5)

A much more straightforward example, this time considering several connectives at once. Suppose we ask whether one can conservatively add to intuitionistic logic three binary connectives \(\#_1\), \(\#_2\), \(\#_3\), satisfying for all \(\phi , \psi\):

\[ \phi\dashv\vdash(\phi\mathbin{\#_1}\psi) \rightarrow (\phi\mathbin{\#_3}\psi)\text{ and } \psi\dashv\vdash(\phi\mathbin{\#_2}\psi) \rightarrow (\phi\mathbin{\#_3}\psi). \]In classical logic we can take \(\phi\mathbin{\#_1}\psi\) and \(\phi\mathbin{\#_2} \psi\) as (equivalent to) \(\neg \phi\) and \(\neg \psi\) respectively, and \(\phi\mathbin{\#_3} \psi\) as \(\bot\). There are no three candidates playing the desired role in any conservative extension of intuitionistic logic, however, because the inset equivalences render arbitrary \(\phi\) and \(\psi\) head-linked in the sense of Section 3, with \(\phi\mathbin{\#_3} \psi\) as the head formula.

### 4.6 An Example Related to Algebraizability (Example 6)

The present example comes from the relevant logic \(\mathbf{R}\).
The sentential constants \(T\) and \(t\) whose sequent
calculus treatment we saw in Section
3
are treated in axiomatic developments of \(\mathbf{R}\) by means
of the axiom schemas \(\phi \rightarrow T\) for the former cases and
both \(t\) and \(t \rightarrow(\phi \rightarrow \phi)\), though
these last two can be replaced by \(\phi \leftrightarrow(t \rightarrow \phi)\). Here \(\leftrightarrow\) itself can be regarded as an abbreviation either
of \((\phi \rightarrow \psi) \wedge(\psi \rightarrow \phi)\), or as \((\phi \rightarrow \psi) \circ(\psi \rightarrow \phi)\),
where \(\wedge\) and \(\circ\) are the additive or ‘extensional’
(as the relevance tradition would have it) conjunction and the
multiplicative or ‘intensional’ conjunction (also called
*fusion*) respectively. While in linear logic neither
\(p \circ q\) nor \(p \wedge q\) provably
implies the other, in \(\mathbf{R}\), thanks to the presence of
contraction, the latter implies the
former.^{[46]}
A well-known further side effect of contraction is that \(\phi \circ \psi\) and \(\phi \wedge \psi\) are also equivalent whenever \(\phi\) is an
implicational formula and \(\psi\) is its converse, so the two
alternative readings of \(\phi \leftrightarrow \psi\) above are equivalent in
\(\mathbf{R}\). Now consider the possible existence of a new
nullary connective for \(\mathbf{R}\) in the ‘truth
constants’ family, \(\mathcal{T}\), subject to
the axiom schema:

This looks harmless enough, the principles governing \(t,
T\) and \(\mathcal{T}\) all holding for the
undifferentiated \(\top\) constant of classical and intuitionistic
logic, but here notationally distinguished so as not to prejudice
questions of the logical relations between
them.^{[47]}

But in \(\mathbf{R}\), this harmless appearance is deceptive. For
in this logic the connective \(\leftrightarrow\) is what we have called
*special*. After the well-known extension,
\(\mathbf{R}\)-Mingle or \(\mathbf{RM}\), of
\(\mathbf{R}\) by the Mingle schema \(\phi \rightarrow
(\phi \rightarrow \phi)\),^{[48]}
let us call a formula \(\phi\) for which this is already provable in
\(\mathbf{R}\) a *Mingler*. Since \(\mathbf{RM}\) is a
proper extension of \(\mathbf{R}\), not all formulas are Minglers
in \(\mathbf{R}\). But again thanks to contraction, all
\(\leftrightarrow\)-formulas are Minglers, rendering \(\leftrightarrow\) special in
\(\mathbf{R}\). Now we can see that the addition of \(\mathcal{T}\),
subject to the schema inset above, would
extend \(\mathbf{R}\) non-conservatively because now every formula
\(\phi\) would be equivalent to the corresponding \(\leftrightarrow\)-formula \(\mathcal{T} \leftrightarrow \phi\), so even for \(\mathcal{T}\)-free
\(\phi\) we should have the Mingle theorem
\(\phi \rightarrow(\phi \rightarrow \phi)\). Thus no devotee of
\(\mathbf{R}\) should be prepared to countenance the existence of
\(\mathcal{T}\) behaving as envisaged (or indeed any
pair \(\#_1\), \(\#_2\) of 1-ary connectives with \(\phi\)
provably equivalent to \(\#_1\phi \leftrightarrow\)
\(\#_2\phi)\).

The fact that the biconditional connective is special in
\(\mathbf{R}\) may appear to conflict with the fact, established
in Blok and Pigozzi (1989) that this logic is what the authors call
*algebraizable*. This term is applied to consequence relations
\(\vdash\) which are translationally equivalent to the quasi-equational
consequence relation \(\vDash_{\mathbf{K}}\) of a class
of algebras of the same similarity type as the language of \(\vdash\).
That is, for equations
\(e_1 ,\ldots ,e_n\), we
have
\(e_1 ,\ldots ,e_{n-1}\vDash_{\mathbf{K} } e_{n}\) just in case for any algebra
\(\mathbf{A} \in \mathbf{K}\) and any assignment of
elements of \(A\) to the variables in the
\(e_i\), if all of
\(e_1 ,\ldots ,e_{n-1}\)
come out true in \(\mathbf{A}\) on that assignment, so does
\(e_n\). The translational equivalence idea
means that there is a translation \(\tau\) from formulas of the
(sentential) language of \(\vdash\) to equations of the language of
\(\mathbf{K}\), and a translation \(\tau'\) back in the other
direction, which are mutually inverse in the sense that \(\phi \dashv \vdash \tau'(\tau(\phi))\) and \(e\)
⫤\(\vDash_{\mathbf{K}} \tau(\tau'(e))\) for all formulas \(\phi\) and equations
\(e\), and, for all formulas
\(\phi_1 ,\ldots ,\phi_n\) and equations
\(e_1 ,\ldots ,e_n\),
either of the following conditions is satisfied (from which it follows
that both are):

\(\phi_1 ,\ldots ,\phi_{n-1} \vdash \phi_{n}\) if and only if \(\tau(\phi_1),\ldots ,\tau(\phi_{n-1}) \vDash_{\mathbf{K}} \tau(\phi_n)\)

and

\(e_1 ,\ldots ,e_{n-1} \vDash_{\mathbf{K} } e_{n}\) if and only if \(\tau'(e_1),\ldots ,\tau'(e_{n-1}) \vdash \tau'(e_n)\).

This account of algebraizability has been oversimplified for
expository purposes in one respect: Blok and Pigozzi (1989) do not
require the translation of a formula (what we are calling \(\tau)\)
should yield a single equation, but allow a *set* of equations,
and similarly in the converse direction, \(\tau'(e)\) is
allowed to be a set of formulas. It follows from the present
definition, with the single equation/single formula restriction
removed, that the formulas in the latter set function collectively as
an equivalence-like compound satisfying some further congruence
conditions, which in the case of \(\vdash_{\mathbf{R}}\)
can be taken to be \(\leftrightarrow\). Accordingly, the fact that
\(\vdash_{\mathbf{R}}\)—explained
presently—is algebraizable, entails, in view of the \(\ldquo\phi \dashv \vdash \tau'(\tau(\phi))\rdquo\) condition, that,
loosely speaking, every formula is equivalent to an equivalence. But
does this not clash with our finding that \(\leftrightarrow\) is special in
\(\mathbf{R}\)?

Well, first, the consequence relation
\(\vdash_{\mathbf{R}}\) needs to be explained. Blok and
Pigozzi have in mind the least consequence relation for which \(\phi ,
\phi \rightarrow \psi \vdash \psi\) and \(\phi ,
\psi \vdash \phi \wedge \psi\) and
\(\vdash \phi\) for all \(\phi\) provable in the Fmla
logic \(\mathbf{R}\). (This third condition
can be restricted to all axioms of any axiomatization of \(R\)
with formula-to-formula rules corresponding to the first and second
conditions.) Now the loose summary just given to the effect that every
formula is equivalent to an equivalence makes a misleading double use
of the equivalence vocabulary for two different things: equivalence as
mutual consequence (\(\ldquo\dashv \vdash\rdquo\)) and equivalence as
the biconditional connective. Removing the conflation, it means that
for every \(\phi\) there exist \(\psi , \chi\), with \(\phi \dashv \vdash_{\mathbf{R}}\psi \leftrightarrow \chi\).^{[49]}
This is a very different matter from having
\(\vdash_{\mathbf{R}}\phi \leftrightarrow(\psi \leftrightarrow \chi)\).
The latter would indeed be equivalent to the provability in the
sequent calculus described for \(\mathbf{R}\) in Section
3
of \(\phi \succ \psi \leftrightarrow \chi\) and the converse sequent. But the
apparently matching \(\vdash_{\mathbf{R}}\)-statements
mean something very different, building in the structural features
(such as weakening) that the substructural sequent calculus was
designed to avoid. Note in particular that
\(\vdash_{\mathbf{R}}\) is not \(\rightarrow\)-introductive, in
the sense of Example 2 above.

### 4.7 Two-Dimensional Isotopes of Boolean Connectives (Longer Example 7)

Could there exist a connective \(\#'\) which, when appearing outside
of the scope of some specified range of operators – typically,
non-Boolean connectives – behaves just like a given Boolean
connective \(\#\), while behaving differently from # when occurring within
the scope of one of the operators in the range in question?
Understanding all of this as happening under the aegis of some
particular consequence relation, on which more will be said in the
following paragraph, the situation envisaged would be like this. A
\(\#'\)-compound would be equivalent to a #-compound of the same
components, each compound having the other as a consequence by the
relevant consequence relation, without being synonymous with that
compound (synonymy as explained in Section
1).
The remainder of this example assumes some familiarity with the basic
modal logic of “actually”. The semantics of this logic can
be presented, as in the first two pages of Davies and Humberstone
(1980), using models with a distinguished point (or world), with a
formula \(A\phi\) evaluated as true at any point in the model
just in case \(\phi\) is true at the distinguished point. The
*generally valid* formulas are then those true every point in
all such models, and the generally valid sequents are those for which
truth is preserved from left to right at each point in all such
models. The *real-world valid* formulas (sequents) are those
which are true (resp. truth-preserving) at the distinguished point in
all models.

Alternatively, the semantics can be reformulated so that the models
feature no such privileged point and truth (in a model) is relativized
to a pair of points, one of which plays the ‘real world’
role formerly played by the distinguished element, the other playing
the role of the world of at which the formula is being locally
evaluated, as in notes 4 and 16 of Davies and Humberstone (1980).
General validity is a matter of truth or its preservation relative to
arbitrary such pairs in all models, and *diagonal* validity (as
real-world validity is often suggestively called in this setting)
attends instead only to pairs whose first and second coordinates
coincide. On either style of presentation, the formulation in terms of
sequents gives a consequence relation in the obvious way, and for
present purposes the following terminology will be convenient.
Formulas will be said to be *diagonally equivalent* when each
is a consequence of the other by the consequence relation capturing
diagonal (or ‘real-world’) validity and to be
*unrestrictedly equivalent* when this holds instead for the
general consequence relation. (We avoid the phrase “generally
equivalent”, since it is hard not to hear this as meaning
“equivalent, for the most part”; this terminology is
adapted from the reference to general consequence on p. 15 of
Fusco 2015 as unrestricted consequence.) The current distinction
between diagonal and unrestricted equivalence provides a useful formal
modeling of Dummett’s well-known distinction between sameness of
assertive (or assertoric) content, on the one hand, and sameness of
ingredient sense on the
other.^{[50]}
The idea of applying such a contrast to the case of specific pairs of
connectives – as with the \(\#, \#'\) pairs from the start of
the preceding paragraph – appears, however, to be new with Fusco
(2015), to which we turn presently. The consequence relation in play
in the \(\#, \#'\) discussion above is taken as the diagonal
consequence relation (with the associated relation of weak
equivalence), according to which these connectives are
non-congruential, providing for mutual consequence without synonymy,
rather than the finer-grained general consequence relation (associated
with unrestricted equivalence). The latter consequence relation is
congruential, but at the cost of not directly reflecting the felt
*a priori* equivalence of \(A\phi\) with \(\phi\).

The aspect of Fusco (2015) of present concern is the treatment of disjunction, with special reference to the problems with which it is associated in deontic logic – such as Ross’s Paradox, and the representation of Free Choice permission. The issue is discussed further in Section 3 of Fusco (2018). (For general background, including these problems, see McNamara 2019; more detail on the specifically disjunction-related issues arising is provided in Aloni 2016.) Fusco (2015) argues, on grounds we do not go into here (since they involve several parts of an elaborate theory of deontic notions), that these problems of deontically embedded “or” in English (and corresponding vocabulary in other natural languages) are best treated rendering it formally by means of “\(\or\)”, with \(\phi \or \psi\) defined as:

\[\tag{1} (A(\phi \wedge \neg \psi) \rightarrow \phi) \wedge(A(\neg \phi \wedge \psi) \rightarrow \psi) \wedge (A(\phi \leftrightarrow \psi) \rightarrow(\phi \vee \psi))\]This is a suggested definition, at least for \(\phi , \psi\), constructed using just Boolean connectives, from a planned sequel to Fusco (2015) and (2019), spelling out in the object language a semantic characterization supplied in the first of those papers. An unrestrictedly equivalent definition (or more accurately, definiens) which some readers may prefer is the following:

\[\tag{2} (A(\phi \wedge \neg \psi) \wedge \phi) \vee(A(\neg \phi \wedge \psi) \wedge \psi) \vee (A(\phi \leftrightarrow \psi) \wedge(\phi \vee \psi))\]By contrast, instances of the following schema, giving the treatment of “whether \(\phi\) or \(\psi\rdquo\) in Lewis (1982) for Boolean \(\phi , \psi\) (though not in general, as explained in the last paragraph of note 51 below), would only be diagonally equivalent to the corresponding instances of the above pair:

\[\tag{3} (A\phi \wedge \phi) \vee (A\psi \wedge \psi)\]
So as to have concrete formulas to discuss, consider the instances of
these three schemata with distinct sentence letters \(p\) and
\(q\) taken as \(\phi\) and \(\psi\), respectively, and we will now use
(1)–(3) to refer to these concrete instances. The first pair are
unrestrictedly equivalent and all three are diagonally equivalent,
with (3) having (1) and (2) as general consequences though not
conversely.^{[51]}
All are diagonally equivalent to the Boolean disjunction \(p \vee q\), which we may put by saying that all are
two-dimensional *isotopes* of the one-dimensional, i.e.
\(A\)-free, formula \(p \vee q\), or, more
usefully, that their respective equivalence classes w.r.t. the
relation of unrestricted equivalence, stand in this
‘isotope’ relation. Similarly, we can speak of the (in the
above presentation, *derived*) connective \(\or\)
as a two-dimensional isotope of the Boolean \(\vee\),
thinking of the formula (2) as a context of the variables \(p,
q\). (On the other hand, what is referred to in note
51
as Groenendijk–Stokhof’s
“\(or\)” is not a two-dimensional
isotope of Boolean disjunction, \(p \or q,\) so understood, being
diagonally equivalent to a Boolean tautology, rather than to \(p \vee
q\).)

What is the point of considering such two-dimensional isotopes of
Boolean disjunction? Fusco’s idea is the following. Arguably,
people have thought that the correct treatment of inclusive
“or” in English is given by (Boolean) \(\ldquo\vee\rdquo\),
once they have learned to diagnose as pragmatic distraction any
apparent anomalies, because this simple connective with its
truth-functional semantics captures the way “or” behaves
when it appears unembedded (or only ‘Booleanly’ embedded).
The presumption has then been that any residual anomalies arising from
problematic embeddings will be eventually also then be explained away
pragmatically. But what if we had on our hands a two-dimensional
isotope of \(\vee\) that was specially hand-crafted to deal with these
anomalies, such as Fusco’s \(\or\)? The
unembedded behaviour of \(\vee\) and \(\or,\) in view
of the diagonal equivalence of compounds formed using the two
disjunctions, would be the same, so
\(\or\)-disjunction
would have all the benefits of
Boolean disjunction without the drawback of not faring very
satisfactorily when appearing in the scope of certain intensional
operators. On this matter of agreement in logical behaviour when
unembedded, consider, for example, the introduction and elimination
rules in a natural deduction system. What they introduce or eliminate
is the main connective of a formula, so they would not differ in their
intuitive acceptability in the case of “or” whether this
was rendered as Boolean disjunction \(\vee\) or as Fusco’s
two-dimensional \(\or\)
connective.^{[52]}
More generally, the conditions defining \(\vee\)-classicality (indeed
\(\#\)-classicality for any \(\#\)) of consequence relations or generalized
consequence relations pertain only to unembedded occurrences of \(\vee\)
(or more generally of \(\#\)). In the case of Fusco (2015), the obligation
operator \(O\) is interpreted by universal quantification over
suitably accessible points with the relata of this relation being the
worlds of local evaluation rather than the world taken as the actual
world, which remains the same, so while
\(p \or q\)
is a diagonal (though not a general) consequence of \(p,\) \(O(p \or
q)\) is not a diagonal consequence of
\(Op\).^{[53]}
Putting it very informally, this is because from the perspective of
some world of evaluation, \(w\), with \(w\) itself considered as
actual (since we are working the diagonal case), every world
deontically accessible to \(w\), qua world of evaluation, may be a
\(p\)-world, whereas at \(w\) if what is true is \(q\) but not \(p\),
then what is required for the truth at \(w\) of
\(O(p \or q)\) is that all the accessible
worlds be \(q\)-worlds, since in moving out to the \(w\)-accessible
worlds we are not changing the status of \(w\) as the world playing
the actual world role. (We are in the ‘middle disjunct’
case of (2) with this example.) This illustrates how Fusco has
arranged matters so that \(p \or q\) and \(p \vee q\) end up
exhibiting the same behaviour when unembedded but differing behaviour
when embedded – in the present instance, in the scope of the
obligation operator. The story with the permissibility operator,
written as may or \(M\) in Fusco (2015), and
not there treated as dual to \(O\), is more complicated, so the
interested reader is referred to that discussion for the details as
well as the motivation behind the choice of \(\or\) in this
setting. For present purposes, the main point to stress is the general
strategy of using the two-dimensional semantics to model differences
in ingredient sense compatible with a given assertoric content.

One may wonder how much room for manoeuvre is made available by this
general strategy, which, since we are concentrating on connectives
here, amounts to asking how many two-dimensional isotopes a given
Boolean connective has. A simpler case than that of the binary
connectives with which we have been preoccupied is that of the
one-place connectives. A ‘unarized’ version of the
*whether* featuring in (3) above arises by choosing the case in
which \(\psi\) is \(\neg \phi\). This can be written more simply as
\(A\phi \leftrightarrow \phi\), used (in effect) as the
definition of what was written as \(O\phi\) on p. 119 of
Humberstone (2002). (There is no intention, in using
\(\ldquo O\rdquo\) here, to evoke any deontic associations.) If
we took \(O\) as primitive, we could instead define \(A\) by
taking \(A\phi\) to abbreviate
\(O\phi \leftrightarrow \phi\) if we wanted. Either way, if an
epistemic operator \(K\) is treated in the same way semantically
as the deontic obligation operator above (though with its own
accessibility relation, of course, or even just using neighbourhood
semantics here, as in Lewis 1982, p. 202), then for purely
Boolean \(\phi , KO\phi\), alias
\(K(A\phi \leftrightarrow \phi)\) ends up
unrestrictedly equivalent to
\((A\phi \wedge K\phi) \vee(A\neg \phi \wedge K\neg \phi)\)
and thus not a bad approximation to something saying that our
cognitive subject knows whether (or not)
\(\phi\).^{[54]}

Our main concern here, though, is with formulas constructed just using
\(A\) and the Boolean connectives, and in particular, since we
are considering the 1-place case, with such formulas as can be
constructed with the aid of these devices and a single sentence
letter, \(p\), say. To see how many two-dimensional isotopes a
given 1-ary Boolean connective (equivalently, Boolean formula in just
one variable) might have, since there are only four such connectives
(or formulas), to within equivalence – and for these formulas
there is of course no contrast between diagonal and unrestricted
equivalence – we should ask how many equivalence classes w.r.t.
the relation of unrestricted equivalence there are of the one-variable
‘two-dimensional formulas’ (i.e., here, just
Boolean-with-\(A\) formulas). This question is easy to answer if
we bear the following things in mind: first, that every formula is
unrestrictedly equivalent to one in which \(A\) occurs, if at
all, then just immediately before a sentence letter, and secondly,
that w.r.t. the general consequence relation, the formulas \(p\)
and \(Ap\) are completely independent (by contrast with the
diagonal consequence relation, w.r.t. which they are equivalent). Thus
the (unrestricted) equivalence-classes of one-variable formulas
collectively manifest the same Boolean algebraic structure as do the
equivalence classes of purely Boolean two-variable formulas. So you
can take your favourite Hasse diagram of this 16-element Boolean
algebra^{[55]}
and, leaving all occurrences of \(p\) intact, replace every
occurrence of \(q\) with \(Ap\), and you now have a picture
of all the two-dimensional one-variable formulas (to within
unrestricted equivalence) and the logical relations among them. Each
of these 16 equivalence classes (or any of the formulas in such a
class) is a two-dimensional isotope of the Boolean equivalence class
(or any of its elements) we get by erasing all occurrences of
\(A\) in the formulas it contains. Thus the two-dimensional
formulas \(p, Ap\), and \(Op\) most recently
encountered, including the first as a degenerate case of a
two-dimensional formula for a streamlined account, are two-dimensional
isotopes of \(p, p\), and
\(p \leftrightarrow p\) (or \(\top)\), respectively. You
will find that each element of the 4-element Boolean algebra has four
distinct elements of the 16-element algebra mapped to it by this
erasure-of-\(A\) mapping. (This would usually be put by speaking
of the principal congruence generated by identifying
\(p\)’s equivalence class with \(Ap\)’s –
alias \(q\)’s – equivalence class: the smallest
congruence relation w.r.t. which these two elements of the algebra are
congruent.) For example, \(p\) (or its equivalence class) has, to
within unrestricted equivalence, the four two-dimensional isotopes
\(p \wedge Ap\), the logically strongest
isotope w.r.t. general consequence (lowest in the 16-element algebra)
and \(p \vee Ap\), the weakest isotope
(highest in the 16-element algebra), and between these two (and
mutually incomparable), \(p\) and \(Ap\).

Returning to the case of binary connectives or two-variable two-dimensional formulas, we could reason similarly. (The interested reader is left to work the general \(n\)-variable case.) \(2^{16} = 65,536\) is the number of equivalence classes of 4-variable formulas, the exponent 16 here being chosen as \(2^4\), the number of equivalence classes of 2-variable formulas. So if the variables are \(p, q, r, s\), when we collapse the former Boolean algebra into the latter by identifying \(r\) with \(p\) (thinking of \(r\) as \(Ap)\) and \(s\) with \(q\) (thinking of \(s\) as \(Aq)\) we are moving from 65,536 elements to 16, and a similarly equitable distribution renders each element of the 16-element algebra as the image of 65,536/16 elements of the larger algebra, which equals \(4096 (= 2^{12} = 2^{16}/ 2^4)\). There is a simpler route to this conclusion, and that is by consideration of such Stalnaker-inspired matrices as feature in Fusco’s discussion (see note 51). This is a 4-by-4 matrix since we have to take into account the local (‘world of evaluation’) truth-value and the actual truth-value of the first component (four possible combinations) of a binary compound and similarly for the second component, and reading down the diagonal gives the truth-table for the Boolean connective of which the original is a two-dimensional isotope. Thus in Fusco’s case, this descending diagonal reads \(\ldquo\rT, \rT, \rT, \rF\rdquo\), just like the descending vertical column of a familiar truth-table as conventionally displayed. The latter feature is retained however we label with \(\rT\)s and \(\rF\)s (or 1s and 0s if preferred) the non-diagonal cells, of which there are 12 (16 minus the four on the diagonal). Since each of these cells can be filled with either a \(\rT\) or an \(\rF\), so we are back calculating \(2^{12}\) and getting the answer 4096, whichever binary truth-function our original diagonal had displayed, including of course that associated with \(\vee\). Thus, if you like Fusco’s general strategy for responding to difficulties like those faced by what seemed to be Boolean disjunction behaving badly when deontically embedded, there is plenty of room to tweak the details of her proposed solution.

### 4.8 An Existence Question Related to Truth-Functions (Example 8)

Section 2 made use of the idea of a (bivalent) truth-function
\(f\)’s being *associated with* a connective \(\#\) on a
given valuation \(v\) (for the language under disussion), and
defined truth-functionality for a connective over a class of
valuations to consist in there being some truth-function associated
with \(\#\) over every valuation in the class. We also considered the
weaker notion of pseudo-truth-functionality when the
\(\forall\exists\)-version of that \(\exists\forall\)-condition was
satisfied: the truth-function in question may vary from valuation to
valuation in the class. If the class is a singleton, \(\{v\}\),
these two come to the same thing and we will simply say that the
connective is truth-functional on the valuation \(v\). These
truth-functionality conditions are all variations on the incarnation
of compositionality – the idea that the semantic value of a
compound should be determined on the basis of its components and the
way they are composed – as it applies especially to the case of
classical propositional logic. Bonnay and Westerståhl (2016)
suggest that ‘Carnap’s Problem’ for that logic, is
solved by appeal to such compositionality considerations, by building
in the requirement that the connectives be truth-functional on all
valuations under consideration.^{[56]}
Here we
illustrate this by considering the case of the ‘unwanted’
\(\vdash_{CL}\)-consistent but non-\(\vee\)-Boolean
valuations we saw arising in Section 2 as a result of taking
conjunctive combinations of Boolean valuations. For present purposes,
we need to show not just that the truth-function \(f_{\vee}\) from
near the start of Section 2 associated with the connective \(\vee\) on
Boolean valuations is not associated with \(\vee\) on some such
conjunctive combinations of \(\vdash_{CL}\)-consistent valuations, but
there is no truth-function at all associated with this connective on
such conjunctive combinations.

Accordingly, suppose that we have two \(\vdash_{CL}\)-consistent valuations \(u\) and \(v\) and that these are Boolean (in particular \(\vee\)-Boolean) valuations, making the following assignments to the sentence letters \(p, q: u(p) =\rT\), \(u(q) =\rF\), and \(v(p) =\rF\), \(v(q) =\rT\). Since \(u\) and \(v\) are \(\vee\)-Boolean, \(u(p \vee q) = v(p \vee q) =\rT\), so for their conjunctive combination \(u \cdot v\), from now on denoted more briefly by \(uv\), we have \(uv(p \vee q) =\rT\), even though we also have \(uv(p) =\rF\) (because \(v(p) =\rF\)) and \(uv(q) =\rF\) (since \(u(q) =\rF\)). Suppose that there is a truth-function \(f\) associated with \(\vee\) on \(uv, f\) must satisfy the condition that \(f(\rF, \rF) = \rT\). Since \(uv(p) =\rF\), the supposition just made tells us that

\[ uv(p \vee p) = f(uv(p), uv(p)) = f(\rF, \rF) = \rT \]even though \(uv(p) = \rF\). But now recall that \(p \vee p \vdash_{CL} p\): this gives us a ontradiction since the class of valuations consistent with any consequence relation is closed under taking conjunctive combinations, as \(uv\) is just such a combination we now see not to be consistent with \(\vdash_{CL}\), verifying in the present case the left-hand formula \((= p \vee p)\) while falsifying that on the right \((= p)\).

Since we considered a single valuation \((uv\) in the foregoing
discussion) consistent with the classical consequence and \(\vee\)’s
not being associated with a truth-function on that valuation, we have
seen that \(\vee\) is not even *pseudo*-truth-functional over the
class of \(\vdash_{CL}\)-consistent valuations. So the
discussion in Section 2 leads us to expect trouble on the
Extensionality front. To make the trouble visible, let us consider the
generalized consequence relation – let’s just call it
\(\Vdash\), for the discussion in this Example – determined, not by
the class of Boolean valuations but: by the class of all valuations
consistent with \(\vdash_{CL}\) (alias: the larger class
of all conjunctive combinations of Boolean valuations). Specifically,
to track the case considered in the preceding paragraph, with
(RE\(_2)\) for \(\#\) as \(\vee\):

Specifically, for the present case, take \(\phi_1, \phi_2, \psi\) as
\(p, q, p\), respectively, so that what we are considering is: \(p
\vee q \Vdash p \vee p, q, p\). The condition is violated by the
valuation \(uv\) (or \(u \cdot v)\) above, since \(uv(p \vee q) = \rT\)
whereas \(uv(p \vee p) = uv(q) = uv(p) = \rF\).^{[57]} Thus
the Set-Set
sequent \(p \vee q \succ p \vee p, q, p\) does not hold on the
valuation \(uv\). We already knew this for the result of deleting the
\(\ldquo p \vee p\rdquo\) from the r.h.s. (Section 2), refuting the
claim that \(uv\) is \(\vee\)-Boolean, whereas here we
have *weakened* the sequent, still failing to hold on \(uv\),
to establish the
*stronger* claim that there doesn’t exist any
truth-function \(f\) at all which is associated with \(\vee\) on
\(uv\).

## 5. Notes and Sources

Unless otherwise stated, page and (sub)section references in this
initial paragraph all pertain to Humberstone (2011), where several of
the topics touched on this entry are treated at greater length. For
example, the treatment of unique characterization in Section
3
of the present entry is largely based on §4.3 there. (Some
issues touched on here are, however, not treated there at all or are
addressed in greater detail here.) In connection with note
6
in the present entry, concerning Carnap’s observation that the
most familiar logical frameworks do not force a Boolean interpretation
on the connectives treated by the rules they make available,
references to some of the many discussions of this theme can be found
under ‘Strong vs. Weak Claim’ on p. 101. Apropos of
note
10
(on sentence-position extensionality) in the present entry, referring
the reader to this opening paragraph, see §3.2 and subsections
4.37–8. For the end of note
11
(the commutativity/symmetry distinction etc.), what is relevant is
subsection 3.34, “Operations vs. Relations” (though for
more on specifically the relational side of that contrast, see
Humberstone 2013, especially §4). In connection with note
17
(on ‘non-homophonic’ semantic treatments of disjunction),
see subsections 6.43–6.46 for a survey of some of these
treatments, and for note
21
(on separately conservative but jointly non-conservative extension by
new connectives with prescribed inferential properties), see
p.568*f*. For note
32
(on some of Rautenberg’s work on what we are calling hybrids of
connectives), see alternatively subsection 3.24. For note
41
(appended to a discussion of contrariety and subcontrariety), a more
detailed discussion can be found in subsection 8.11 and references
given there (especially in Remark 8.11.1). Expanding on note
45:
§5.2 goes into more detail on logical subtraction (Example
4.4
above); interesting work by Stephen Yablo on this topic, mentioned
there as then unpublished, subsequently appeared in Yablo (2014),
Chapters 8 and 9 being of particular relevance. Apropos of note
55:
for an example of a Hasse diagram of the 16-element Boolean algebra,
nodes labelled with representatives of the classical equivalence
classes of two-variable formulas, see Figure 2.\(13a\) on
p. 225. The bearing on logical theory of the topic of the
following paragraph of the present section, Galois connections, is
stressed in material on pp. 58*f*., 75 and 80 in
§1.1; the list of ‘Galois connection’ oriented
discussions of logical matters given in the bottom paragraph of
p. 101 should be supplemented by a reference to Bimbó and
Dunn (2008). Finally, to supplement the Urquhart reference given at
the end of the present section on head linkage as a special relation
in intuitionistic logic, see subsection 9.25. The remainder of the
present section gives further additional notes and sources on the
present entry working through in order.

The Galois connections described in the opening section are what are
sometimes called contravariant (as opposed to covariant) Galois
connections; they were introduced in somewhat different terminology by
Garrett Birkhoff (1967). Closure operations as defined in the opening
section are sometimes called closure operators. Note that the
definition given, although standard, is much less restrictive than the
notion of a specifically *topological* closure operation (in
particular, not requiring \(C(X \cup Y) = C(X) \cup C(Y)\) or
\(C(\varnothing) = \varnothing\)). Some authors discuss matters of
logical theory placing a particular emphasis on closure operations and
their systems of closed sets (sets \(X\) with \(C(X)
= X)\); see Pollard and Martin (1996) and references there
cited.

The phrase “logical frameworks” has been used in ways other than that introduced in Section 2, e.g., in Huet and Plotkin (1991). The use of \(\ldquo\succ\rdquo\) here as a sequent separator is occasioned by current HTML font limitations; its general use for that purpose is not recommended. Carnap’s observation about logic pursued in Set-Fmla not being capable of enforcing the intended truth-functional interpretation of various connectives (such as \(\vee , \neg\), and \(\rightarrow)\) has received extensive attention in the literature, as was mentioned in the first paragraph of this section. The term “congruential” used here is taken from Segerberg (1982); it is based on a related use of the term by D. Makinson (for modal logics in Fmla containing \(\Box \phi \leftrightarrow \Box \psi\) whenever they contain \(\phi \leftrightarrow \psi)\). In some quarters the term “self-extensional” is used for congruentiality, while in others the term “extensional”—used quite differently here—is used for this property.

The emphasis on (bivalent) valuations throughout our discussion may
suggest some limitation of scope: are we not excluding
‘many-valued logic’ (or better: matrix semantics)? And
what about Kripke style semantics in which truth is doubly relativized
not only to a model but to a point therein? No, there is no
limitation. Every (generalized) consequence relation is determined by
a class of valuations. The matrix assignments of values to formulas
are homomorphisms from the algebra \(\mathbf{L}\) of formulas to
the algebra \(\mathbf{A}\)—presumed to be of the same
similarity type of \(\mathbf{L}\)—of a matrix
\((\mathbf{A}, D)\), where \(D \subseteq A\);
\(D\) is called the set of designated elements of the matrix.
Thus the compositional semantics is done in terms of such
homomorphisms, any one of which, \(h\), say, gives rise to a
bivalent valuation \(v_h\) defined by setting
\(v_h (\phi) =\rT\) iff \(h(\phi)
\in D\), and a Set-Fmla
or Set-Set
sequent is valid in the matrix just in case it
holds—in the usual bivalent sense—on the valuation
\(v_h\) for every such homomorphism
\(h\), the (generalized) consequence relation determined by the
matrix is the (generalized) consequence relation determined by the
class of all such \(v_h\),
etc.^{[58]}
Similarly for classes of matrices, with the quantification now over
all \(v_h\) where \(h\) is a homomorphism
from the language to any matrix in the class. Likewise, in the
Kripke-semantical case, any model \(\mathcal{M}\) and
point \(x\) therein gives rise to the valuation
\(v^{\mathcal{M}}_{x}\)
defined by
\(v^{\mathcal{M}}_{x}(\phi) =\rT\) iff
\(\mathcal{M}\vDash_x \phi\), and the
(generalized) consequence relation determined by a class of models is
that determined by all such \(v^{\mathcal{M}}_{x}\)
with \(\mathcal{M}\)
in the class. (This is the so-called
*local* (generalized) consequence relation; for the global
variant, use valuations \(v^{\mathcal{M}}\)
with \(v^{\mathcal{M}}(\phi)
=\rT\) iff for all points
\(x\) in the model, \(\mathcal{M}\vDash_x \phi\).) There is
an obvious further adaptation of these definitions if one wants a
formulation in terms of determination by (“soundness and
completeness with respect to”) a class of frames rather than
models.

As well as Prior (1957) cited in Section 2 on the Ł-modal system, the following references are useful: Smiley (1961), Smiley (1962), Porte (1979), Font and Hájek (2002). The original paper is Łukasiewicz (1953).

The problem with a live-and-let-live attitude toward differences
between logics differing over the logical powers of a connective when
the weaker set of powers already suffice for unique characterization
\((\neg_i\) *vs.* \(\neg_c\) in Section
3)
was already pointed out in Popper (1948), and often re-surfaces in
subsequent literature e.g., Harris (1982), Hand (1993), Fariñas
del Cerro and Herzig (1996); see also the opening paragraph of the
present section. Uniquely characterized connectives are sometimes
spoken of as *implicitly defined*, but there are definite risks
involved in the latter usage—see Došen and
Schroeder-Heister (1985). The “implicit” in the title of
Caicedo (2004) does not carry quite the same risks, and refers to a
special case of unique characterization, essentially amounting to
unique characterization by zero-premiss rules in Fmla—i.e.,
by axioms. Similarly, the
“functionally dependent” connectives of Smiley (1962) are
those uniquely characterized by zero-premiss rules, taken in concert
with the standard structural rules, in Set-Fmla—though
Smiley’s definition is put in terms of consequence relations.
This class of connectives may well coincide with the class of
projection-conjunction connectives. It does not include disjunction or
implication, as treated in intuitionistic or classical logic, which
are uniquely characterized by rules essentially containing a
non-zero-premiss rule—though these would be uniquely
characterized by zero-premiss rules (together with the structural
rules) in Set-Set.
Makinson (2014) also addresses questions of existence and uniqueness
in connection with connectives, but his existence questions concern,
not the existence of a connective satisfying certain rules (or more
generally, certain conditions), but the existence of rules (or this or
that kind) satisfied by a given connective, where connectives are
individuated semantically (more specifically, by association with
bivalent truth-functions). The various notions of uniqueness
considered by Makinson do apply to connectives rather than rules, and
are defined in terms of the rules satisfied but the connectives
themselves are again individuated truth-functionally and so none ends
up amouting to unique characterization as understood here. See note 1,
p. 365, in Makinson (2014) for a discussion contrasting his
concerns with those found “in some proof-theoretic
studies”, and citing Došen and Schroeder-Heister (1988).
(In fact in the footnote, though not in the bibliography, the date is
given as 1998.)

Id-inductivity is called ‘regularity’ in Kaminski (1988); for Id-inductivity and Cut-inductivity and related concepts (under different names), see also Ciabattoni (2004) and Ciabattoni and Terui (2006).

A study of Popper’s generally under-appreciated work in logic is provided in Schroeder-Heister (1984). The faulty view that differences over logic amount to talking at cross purposes was defended in writings by W. V. Quine to which references may be found in Morton (1973), where this view is subjected to a somewhat milder version of the criticism in Section 3. A full discussion of substructural logics, also mentioned in Section 3, and related topics is provided in Restall (2000).

Aside from the papers by Prior, Belnap, Stevenson and Peacocke (and
Read 1988) mentioned in Section
3,
the \(\Tonk\) example is discussed in (at least)
the following places: Wagner (1981), Hart (1982), §4.12 in
Tennant (1978). Interest continues unabated, as witnessed by the
following publications from the period 2004–2006 alone: Hodes
(2004), Cook (2005), Tennant (2005), Bonnay and Simmenauer (2005),
Chapter 5 of Priest (2006) and Wansing (2006). Subsequent treatments
of interest include Avron (2010) and Rahmann (2012). Although \(\Tonk\)
is Prior’s best known example of
non-conservative extension, he also noted the non-conservative effect
of familiar logical principles concerning conjunction when added to a
purely implicational intermediate logic; references, details, and
further discussion can be found in Humberstone (2014). For the notion
– or perhaps better, notions – of *harmony* between
rules (especially in natural deduction), see the \(\Tonk\)
references just given, and also Chapter 23 of
Tennant (1987), Weir (1986), Dummett (1991) (*passim*), Milne
(1994) and (2002), and Read (2000), as well as the following more
recent investigations: Read (2010), Steinberger (2011), Francez and
Dyckhoff (2012), Hjortland (2012), Francez (2014), Milne (2015), Read
(2015), Schroeder-Heister (2015) and Dicher (2016). For general
background in proof-theoretic semantics informing these discussions,
two useful references are Schroeder-Heister (2014) and the
editor’s contribution (Chapter 1) to Wansing (2015). The subject
of harmony is also briefly touched on in Makinson (2014), esp.
p. 369.

Material of interest on the subjects of special and universally representative connectives can be found in Jankov (1969), Pahi (1971), de Jongh and Chagrova (1995), in addition to the references cited in Section 3. For the fact that the relation of head linkage is special in intuitionistic logic, see Urquhart (1974) — not that this terminology appears there.

## Bibliography

- Aloni, Maria, 2016, “Disjunction”,
*The Stanford Encyclopedia of Philosophy*(Winter 2016 Edition), Edward N. Zalta (ed.), URL \(= \lt\) https://plato.stanford.edu/archives/win2016/entries/disjunction/\(\gt\). - Avron, Arnon, 1988, “The Semantics and Proof Theory of
Linear Logic”,
*Theoretical Computer Science*, 57: 161–187. - Avron, Arnon, 2010, “Tonk—A Full Mathematical
Solution”, in A. Biletzki (ed.),
*Hues of Philosophy: Essays in Memory of Ruth Manor*, London: College Publications, pp. 17–42. - Beall, J.C., and Greg Restall, 2006,
*Logical Pluralism*, Oxford: Clarendon Press. - Bell, J.L., 1986, “A New Approach to Quantum Logic”,
*British Journal for the Philosophy of Science*, 37: 83–99. - Belnap, Nuel D., 1962, “Tonk, Plonk, and Plink”,
*Analysis*, 22: 130–134. - Belnap, Nuel D., and J.M. Dunn, 1981, “Entailment and the
Disjunctive Syllogism”, in
*Contemporary Philosophy: A New Survey*, Vol. 1, G. Fløistad (ed.), Martinus Nijhoff: The Hague, pp. 337–366. - Béziau, Jean-Yves, and Marcelo E. Coniglio, 2010, “To
Distribute or Not to Distribute?”,
*Logic Journal of the IGPL*, 19: 566–583. - Birkhoff, Garrett, 1967,
*Lattice Theory*, 3rd Edition, Providence, Rhode Island: American Mathematical Society. - Bimbó, Katalin and J. Michael Dunn, 2008,
*Generalized Galois Logics*, Stanford: CSLI Publications. - Blamey, Stephen, and Lloyd Humberstone, 1991, “A Perspective
on Modal Sequent Logic”,
*Publications of the Research Institute for Mathematical Sciences, Kyoto University*, 27: 763–782. - Blok, W.J., and D. Pigozzi, 1989, “Algebraizable
Logics”,
*Memoirs of the American Mathematical Society*, 77(396). - Bonnay, Denis, and B. Simmenauer, 2005, “Tonk Strikes
Back”,
*Australasian Journal of Logic*, 3: 33–44. - Bonnay, Denis, and Dag Westerståhl, 2016,
“Compositionality Solves Carnap’s Problem”,
*Erkenntnis*, 81:721–739. - Bonnay, Denis, and Dag Westerståhl, 2023,
“Carnap’s Problem for Modal Logic”,
*Review of Symbolic Logic*, 16:578-602. - Byrd, Michael, 1973, “Knowledge and True Belief in
Hintikka’s Epistemic Logic”,
*Journal of Philosophical Logic*, 2: 181–192. - Caicedo, Xavier, 2004, “Implicit Connectives of
Algebraizable Logics”,
*Studia Logica*, 78: 155–170. - Caicedo, Xavier, and Roberto Cignoli, 2001, “An Algebraic
Approach to Intuitionistic Connectives”,
*Journal of Symbolic Logic*, 66: 1620–1636. - Carnap, Rudolf, 1943/1961,
*Formalization of Logic*, reprinted in*Introduction to Semantics and Formalization of Logic*, Cambridge, Massachusetts: Harvard University Press. - Ciabattoni, A., 2004, “Automated Generation of Analytic
Calculi for Logics with Linearity”, in
*CSL 2004*, (Series: Lecture Notes in Computer Science, Volume 3210), J. Marczinkowski and A. Tarlecki (eds.), Berlin: Springer-Verlag, pp. 503–517. - Ciabattoni, A., and K. Terui, 2006, “Towards a Semantic
Characterization of Cut-Elimination”,
*Studia Logica*, 82: 95–119. - Cook, R.T., 2005, “What’s Wrong with Tonk?”,
*Journal of Philosophical Logic*, 34: 217–226. - Cross, C., and F. Roelofsen, 2018, “Questions”,
*Stanford Encyclopedia of Philosophy*(Spring 2018 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/spr2018/entries/questions/\(\gt\). - Dalla Chiara, Maria Luisa, R. Giuntini, and R. Greechie, 2004,
*Reasoning in Quantum Theory: Sharp and Unsharp Quantum Logics*, Dordrecht: Kluwer. - Davies, Martin, and Lloyd Humberstone, 1980, “Two Notions of
Necessity”,
*Philosophical Studies*, 38: 1–30. - De, Michael, and Hitoshi Omori, 2014, “More on Empirical
Negation”, in R. Goré, B. Kooi and A. Kurucz (eds.),
*Advances in Modal Logic, Vol. 10*, pp. 114–133. - de Jongh, D.H.J., and L.A. Chagrova, 1995, “The Decidability
of Dependency in Intuitionistic Propositional Logic”,
*Journal of Symbolic Logic*, 60: 498–504. - Deutsch, David, 1989, “Quantum Computational
Networks”,
*Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences*, 425: 73–90. - Deutsch, David, Artur Ekert, and Rossella Lupacchini, 2000,
“Machines, Logic and Quantum Physics”,
*Bulletin of Symbolic Logic*, 6: 265–283. - Dicher, Bogdan, 2016, “Weak Disharmony: Some Lessons for
Proof-Theoretic Semantics”,
*Review of Symbolic Logic*, 9: 583–602. - Došen, Kosta, and Peter Schroeder-Heister, 1985,
“Conservativeness and Uniqueness”,
*Theoria*, 51: 159–173. - –––, 1988, “Uniqueness, Definability and
Interpolation”,
*Journal of Symbolic Logic*, 53: 554–570. - Dummett, M.A., 1991,
*The Logical Basis of Metaphysics*, Cambridge, Massachusetts: Harvard University Press. - Dunn, J.M., and G.M. Hardegree, 2001,
*Algebraic Methods in Philosophical Logic*, Oxford: Clarendon Press. - Ertola Biraben, R.C., 2012, “On Some Extensions of
Intuitionistic Logic”,
*Bulletin of the Section of Logic*, 41: 17–22. - Ertola Biraben, R.C., and H. J. San Martín, 2011, “On
Some Compatible Operations on Heyting Algebras”,
*Studia Logica*, 98: 331–345. - Fariñas del Cerro, Luis, and Andreas Herzig, 1996,
“Combining Classical and Intuitionistic Logic”, in
*Frontiers of Combining Systems*, F. Baader and K. Schulz (eds.), Dordrecht: Kluwer, pp. 93–102. - Font, J.M., and P. Hájek, 2002, “On
Łukasiewicz’s Four-Valued Modal Logic”,
*Studia Logica*, 70: 157–182. - Francez, Nissim, 2014, “Harmony in Multiple-Conclusion
Natural-Deduction”,
*Logica Universalis*, 8: 215–259. - Francez, Nissim, and Roy Dyckhoff, 2012, “A Note on
Harmony”,
*Journal of Philosophical Logic*, 41: 613–628. - Fusco, Melissa, 2015, “Deontic Modality and The Semantics of
Choice”,
*Philosophers’ Imprint*15, Article No. 28. - –––, 2018, “Naturalizing Deontic Logic:
Indeterminacy, Diagonalization, and Self-Affirmation”,
*Philosophical Perspectives*, 32: 165–187. - Gabbay, D.M., 1977, “On Some New Intuitionistic
Propositional Connectives, I”,
*Studia Logica*, 36: 127–139. - –––, 1978, “What is a Classical
Connective?”,
*Zeitschr. für math. Logik und Grundlagen der Math.*, 24: 37–44. - –––, 1981,
*Semantical Investigations in Heyting’s Intuitionistic Logic*, Dordrecht: Reidel. - Garson, James W., 1990, “Categorical Semantics”, in
*Truth or Consequences: Essays in Honor of Nuel Belnap*, J.M. Dunn and A. Gupta (eds.), Dordrecht: Kluwer, pp. 155–175. - –––, 2001, “Natural Semantics: Why Natural
Deduction is Intuitionistic”,
*Theoria*, 67: 114–139. - –––, 2013,
*What Logics Mean: From Proof Theory to Model-Theoretic Semantics*, Cambridge: Cambridge University Press. - Gentzen, G., 1934, “Untersuchungen über das Logische
Schliessen”,
*Math. Zeitschrift*, 39: 176–210, 405–431; English translation in*The Collected Papers of Gerhard Genzen*, M. Szabo (ed.), Amsterdam: North-Holland, 1969. - Girard, Jean-Yves, 1987, “Linear Logic”,
*Theoretical Computer Science*, 50: 1–102. - Girard, Jean-Yves, with Paul Taylor and Yves Lafont, 1989,
*Proofs and Types*, Cambridge: Cambridge University Press. - Groenendijk, Jeroen, and Martin Stokhof, 1982, “Semantic
Analysis of \(Wh\)-Complements”,
*Linguistics and Philosophy*, 5: 175–233. - Hamblin, C.L., 1967, “One-Valued Logic”,
*Philosophical Quarterly*, 17: 38–45. - Hand, Michael, 1993, “Negations in Conflict”,
*Erkenntnis*, 38: 115–29. - Hart, W.D., 1982, “Prior and Belnap”,
*Theoria*, 48: 127–138. - Harris, J.H., 1982, “What’s so Logical about the
‘Logical’ Axioms?”,
*Studia Logica*, 41: 159–171. - Hodes, Harold, 2004, “On the Sense and Reference of a
Logical Constant”,
*Philosophical Quarterly*, 54: 134–165. - Horn, Laurence R., and Heinrich Wansing, 2022,
“Negation”,
*The Stanford Encyclopedia of Philosophy*(Winter 2022 Edition), Edward N. Zalta & Uri Nodelman (eds.), URL \(= \lt\)https://plato.stanford.edu/archives/win2022/entries/negation/\(\gt\). - Hjortland, Ole, 2012, “Harmony and the Context of
Deducibility”, in
*Insolubles and Consequences: Essays in Honour of Stephen Read*, Dutilh Novaes, C., and O. T. Hjorltand (eds.), London: College Publications, pp. 105–117. - Holliday, Wesley H., 2023, “A Fundamental Non-Classical
Logic”,
*Logics,*1:36–79. - Holliday, Wesley H., and Matthew Mandelkern, 2022,
“Compatibility, Compossibility, and Epistemic Modality”,
in M.
Degano, T. Roberts, G.
Sbardolini & M. Schouwstra (eds.),
*Proceedings of the 23rd Amsterdam Colloquium,*Institute for Logic, Language and Computation, UvA, Amsterdam. - Hösli, Brigitte, and Gerhard Jäger, 1994, “About
Some Symmetries of Negation”,
*Journal of Symbolic Logic*, 59: 473–485. - Hudson, James L., 1975, “Logical Subtraction”,
*Analysis*, 35: 130–135. - Huet, Gérard, and Gordon Plotkin (eds.), 1991,
*Logical Frameworks*, Cambridge: Cambridge University Press. - Humberstone, Lloyd, 1995, “Negation by Iteration”,
*Theoria*, 61: 1–24. - –––, 1998, “Many-Valued Logics,
Philosophical Issues in”,
*Routledge Encyclopedia of Philosophy, Vol. 6*, E. Craig (ed.), Routledge: London, pp. 84–91. - –––, 2000, “Parts and Partitions”,
*Theoria*, 66: 41–82. - –––, 2002, “The Modal Logic of Agreement
and Noncontingency”,
*Notre Dame Journal of Formal Logic*, 43: 95–127. - –––, 2011,
*The Connectives*, Cambridge MA: MIT Press. - –––, 2013, “Logical Relations”,
*Philosophical Perspectives*, 27: 176–230. - –––, 2014, “Prior’s OIC
Nonconservativity Example Revisited”,
*Journal of Applied Non-Classical Logics*, 24: 209–235. - –––, 2015, “Béziau on
*And*and \(Or\)”, in*The Road to Universal Logic: Festschrift for the 50th Birthday of Jean-Yves Béziau, Volume I*, A. Koslow and A. Buchsbaum (eds.), Heidelberg: Birkhäuser, pp. 283–307. - –––, 2016,
*Philosophical Applications of Modal Logic*, London: College Publications. - –––, 2019, “Supervenience, Dependence,
Disjunction”,
*Logic and Logical Philosophy*, 28: 3–135. - Hyde, Dominic, 1997, “From Heaps and Gaps to Heaps of
Gluts”,
*Mind*, 106: 641–60. - Jankov, V.A., 1969, “Conjunctively Indecomposable Formulas
in Propositional Calculi”,
*Math. USSR—Izvestija*, 3: 17–35. - Kaminski, M. 1988, “Nonstandard Connectives of
Intuitionistic Propositional Logic”,
*Notre Dame Journal of Formal Logic*, 29: 309–331. - Kalinowski, Georges, 1967, review of L. S. Rogowski, “Logika
kierunkowa a heglowska teza o sprzeczności zmiany”
[Directional logic and Hegel’s thesis on the contradiction of
change (1964)],
*Revue Philosophique de Louvain*, 86: 239–241. - Koslow, A., 1992,
*A Structuralist Theory of Logic*, Cambridge: Cambridge University Press. - Leblanc, Hugues, 1966, “Two Separation Theorems for Natural
Deduction”,
*Notre Dame Journal of Formal Logic*, 7: 159–180. - Lemmon, E.J., 1965,
*Beginning Logic*, London: Nelson. - Lewis, David, 1982 “‘Whether’ Report”, T.
Pauli (ed.),
*\(\langle 320311\rangle\): Philosophical Essays Dedicated to Lennart Aqvist on his Fiftieth Birthday*, T. Pauli (ed.), University of Uppsala, pp. 194–206. - López-Escobar, E.G.K., 1985, “On Intuitionistic
Sentential Connectives. I”,
*Revista Colombiana de Matemáticas*, 19: 117–130. - Łukasiewicz, Jan, 1953, “A System of Modal
Logic”,
*Journal of Computing Systems*, 1: 111–149. Reprinted in*Jan Łukasiewicz: Selected Works*, L. Borkowski (ed.), Amsterdam: North-Holland, 1970. - MacFarlane, John, 2015, “Logical Constants”,
*The Stanford Encyclopedia of Philosophy*(Summer 2015 Edition), Edward N. Zalta (ed.), URL \(= \lt\)https://plato.stanford.edu/archives/sum2015/entries/logical-constants/\(\gt\). - Makinson, David, 2014, “Intelim Rules for Classical
Connectives”, in
*David Makinson on Classical Methods for Non-Classical Problems*, S. O. Hansson (ed.), Dordrecht: Springer, pp. 359–385. - McNamara, Paul, 2019, “Deontic Logic”,
*The Stanford Encyclopedia of Philosophy*(Summer 2019 Edition), Edward N. Zalta (ed.), URL \(= \lt\) https://plato.stanford.edu/archives/sum2019/entries/logic-deontic/\(\gt\). - Meyer, Robert K., 1974, “Entailment is not Strict
Implication”,
*Australasian Journal of Philosophy*, 52: 211–231. - Milne, Peter, 1994, “Classical Harmony: Rules of Inference
and the Meaning of the Logical Constants”,
*Synthese*, 100: 49–94. - –––, 2002, “Harmony, Purity, Simplicity
and a ‘Seemingly Magical Fact’”,
*The Monist*, 85: 498–534. - –––, 2015, “Inversion Principles and Introduction Rules”, in Wansing (2015), pp. 189–224.
- Morton, Adam, 1973, “Denying the Doctrine and Changing the
Subject”,
*Journal of Philosophy*, 70: 503–510. - Niki, S., and Hitoshi Omori, 2022, “Another Combination of
Classical and Intuitionistic Conditionals”, in A. Indrzejczak
and M. Zawidzki (eds),
*10th International Conference on Non-Classical Logics: Theory and Applications*(NCL 2022), pp. 174–188. - Omori, Hitoshi, and Heinrich Wansing, 2018, “On
Contra-Classical Variants of Nelson Logic N4 and Its Classical
Extension”,
*Review of Symbolic Logic*, 11:805–820. - Ono, Hiroakira, and Yuichi Komori, 1985, “Logics without the
Contraction Rule”,
*Journal of Symbolic Logic*, 50: 169–201. - Orłowska, Ewa, 1985, “Semantics of Nondeterministic
Possible Worlds”,
*Bulletin of the Polish Academy of Sciences (Mathematics)*, 33: 453–458. - Pahi, B., 1971, “Full Models and Restricted Extensions of
Propositional Calculi”,
*Zeitschr. für math. Logik und Grundlagen der Math.*, 17: 5–10. - Paoli, F., 2019, “Bilattice Logics and Demi-Negation”,
in H. Omori, H. Wansing (eds.),
*New Essays on Belnap-Dunn Logic*, Basel: Springer, pp. 233–253. - Peacocke, Christopher, 1987, “Understanding Logical
Constants: A Realist’s Account”,
*Proceedings of the British Academy*, 73: 153–199. - Poggiolesi, Francesca, and Greg Restall, 2012, “Interpreting
and Applying Proof Theories for Modal Logic”, in
*New Waves in Philosophical Logic*, G. Restall and G. Russell (eds.), New York: Palgrave Macmillan, pp. 39–62. - Pollard, Stephen, 2002, “The Expressive Truth Conditions of
Two-Valued Logic”,
*Notre Dame Journal of Formal Logic*, 43: 221–230. - Pollard, Stephen, and Norman M. Martin, 1996, “Closed Bases
and Closure Logic”,
*The Monist*, 79: 117–127. - Popper, Karl, 1948, “On the Theory of Deduction”,
*Indagationes Math.*, 10: 44–54, 111–120. - Porte, Jean, 1979, “The \(\Omega\)-System and the Ł-System
of Modal Logic”,
*Notre Dame Journal of Formal Logic*, 20: 915–920. - Priest, Graham, 2006,
*Doubt Truth to Be a Liar*, Oxford: Oxford University Press. - Prior, A.N., 1957,
*Time and Modality*, Oxford: Clarendon Press. - –––, 1960, “The Runabout
Inference-Ticket”,
*Analysis*, 21: 38–39. Reprinted in*Papers in Logic and Ethics*, P.T. Geach and A. Kenny (eds.), London: Duckworth, 1976, pp. 85–87. - –––, 1964, “Conjunction and Contonktion
Revisited”,
*Analysis*, 24: 191–5. Reprinted in*Papers in Logic and Ethics*, P.T. Geach and A. Kenny (eds.), London: Duckworth, 1976, pp. 159–164. - Quine, W.V., 1951,
*Mathematical Logic*, Cambridge, Massachusetts: Harvard University Press. - Rabinowicz, W., and K. Segerberg, 1994, “Actual Truth,
Possible Knowledge”,
*Topoi*13: 101–115. - Rahman, Shahid, 2012, “Negation in the Logic of First Degree
Entailment and
*Tonk*: a Dialogical Study”, in*The Realism-Antirealism Debate in the Age of Alternative Logics*, S. Rahman, G. Primiero, and M. Marion (eds.), pp. 213–250, Berlin: Springer. - Rautenberg, Wolfgang, 1981, “2-Element Matrices”,
*Studia Logica*, 40: 315–353. - –––, 1985, “Consequence Relations of
2-Element Algebras”, in
*Foundations of Logic and Linguistics: Problems and their Solutions*, G. Dorn and P. Weingartner (eds.), New York: Plenum Press, pp. 3–23. - –––, 1989, “A Calculus for the Common
Rules of \(\wedge\) and \(\vee\)”,
*Studia Logica*, 48: 531–537. - –––, 1991, “Common Logic of 2-Valued
Semigroup Connectives”,
*Zeitschr. für math. Logik und Grundlagen der Math.*, 37: 187–192. - Read, Stephen, 1988,
*Relevant Logic*, Oxford: Basil Blackwell. - –––, 2000, “Harmony and Autonomy in
Classical Logic”,
*Journal of Philosophical Logic*, 29: 123–154. - –––, 2010, “General-Elimination Harmony
and the Meaning of the Logical Constants”,
*Journal of Philosophical Logic*, 39, 557–76. - –––, 2015, “General-Elimination Harmony and Higher-Level Rules”, in Wansing (2015), pp. 293–312.
- Restall, Greg, 1993, “How to be
*Really*Contraction Free”,*Studia Logica*, 52: 381–391. - –––, 1999, “Negation in Relevant
Logics”, in
*What is Negation?*, D.M. Gabbay and H. Wansing (eds.), Dordrecht: Kluwer, pp. 53–76. - –––, 2000,
*An Introduction to Substructural Logics*, London: Routledge. - Rousseau, G.F., 1968, “Sheffer Functions in Intuitionistic
Logic”,
*Zeitschr. für math. Logik und Grundlagen der Math.*, 14: 279–282. - Schroeder-Heister, Peter, 1984, “Popper’s Theory of
Deductive Inference and the Concept of a Logical Constant”,
*History and Philosophy of Logic*, 5: 79–110. - –––, 2014, “Proof-Theoretic Semantics
”,
*The Stanford Encyclopedia of Philosophy*(Summer 2014 Edition), Edward N. Zalta (ed.), URL \(= \lt\)https://plato.stanford.edu/archives/sum2014/entries/proof-theoretic-semantics/\(\gt\). - –––, 2015, “Harmony in Proof-Theoretic Semantics: A Reductive Analysis”, in Wansing (2015), pp. 329–358.
- Segerberg, Krister, 1982,
*Classical Propositional Operators*, Oxford: Clarendon. - Setlur, R.V., 1970, “The Product of Implication and
Counter-Implication Systems”,
*Notre Dame Journal of Formal Logic*, 11: 241–248. - Shoesmith, D. J., and T.J. Smiley, 1978,
*Multiple-Conclusion Logic*, Cambridge: Cambridge University Press. - Smiley, T.J., 1961, “On Łukasiewicz’s
Ł-modal System”,
*Notre Dame Journal of Formal Logic*, 2: 149–153. - –––, 1962, “The Independence of
Connectives”,
*Journal of Symbolic Logic*, 27: 426–436. - Stalnaker, Robert, 1978, “Assertion”, in P. Cole
(ed.),
*Syntax and Semantics 9: Pragmatics*, New York: New York Academic Press, pp. 315–332. - Steinberger, Florian, 2011, “What Harmony Could and Could
Not Be”,
*Australasian Journal of Philosophy*, 89: 617–639. - Stevenson, J.T., 1961, “Roundabout the Runabout
Inference-Ticket”,
*Analysis*, 21: 124–128. - Sundholm, Göran, 2001, “The Proof Theory of Stig
Kanger: A Personal Reflection”, in
*Collected Papers of Stig Kanger, With Essays on His Life and Work*, G. Holmström-Hintikka, S. Lindström, and R. Slivinski (eds.), Dordecht: Kluwer, Vol. II, pp. 31–42. - Tennant, Neil, 1978,
*Natural Logic*, Edinburgh: Edinburgh University Press. - –––, 1987,
*Anti-Realism and Logic*, Oxford: Clarendon Press. - –––, 2005, “Rule-Circularity and the
Justification of Deduction”,
*Philosophical Quarterly*, 55: 625–645. - Tong, Haotian, and Dag Westerståhl, 2023,
“Carnap’s Problem for Intuitionistic Propositional
Logic”,
*Logics*, 1: 163–181. - Troelstra, A.S., 1992,
*Lectures on Linear Logic*, (Series: CSLI Lecture Notes, Number 29), Stanford, California: CSLI Publications. - Turzyński, Konrad, 1990, “The Temporal Functors in the
Directional Logic of Rogowski: Some Results”,
*Bulletin of the Section of Logic*, 19: 30–32. - Urquhart, Alasdair, 1974, “Implicational Formulas in
Intuitionistic Logic”,
*Journal of Symbolic Logic*, 39: 661–664. - van Toor, Jonathan, 2022, “Pattern Connectives”,
*Journal of Logic and Computation*, 32: 1365–1374. - Wagner, Steven, 1981, “Tonk”,
*Notre Dame Journal of Formal Logic*, 22: 289–300. - Wansing, Heinrich, 2006, “Connectives Stranger than
Tonk”,
*Journal of Philosophical Logic*, 35: 653–660. - –––, 2015, (ed.),
*Dag Prawitz on Proofs and Meaning*, Basel: Springer. - Wansing, Heinrich, Grigory Olkhovikov, and Hitoshi Omori, 2021
“Questions to Michael Dunn”,
*Logical Investigations*27: 9–19. - Weir, Alan, 1986, “Classical Harmony”,
*Notre Dame Journal of Formal Logic*, 27: 459–482. - Williamson, Timothy, 2006a, “Indicative versus Subjunctive
Conditionals, Congruential versus Non-Hyperintensional
Contexts”,
*Philosophical Issues*, 16: 310–333. - –––, 2006b, “Conceptual Truth”,
*Aristotelian Society Supplementary Volume*, 80: 1–41. - –––, 2012, “Boghossian and Casalegno on
Understanding and Inference”,
*Dialectica*, 66: 237–247. - Woods, Jack, 2013, “Failures of Categoricity and
Compositionality for Intuitionistic Disjunction”,
*Thought*, 1: 281–291. - Yablo, Stephen, 2014,
*Aboutness*, Princeton: Princeton University Press. - Zolin, Evgeni E., 2000, “Embeddings of Propositional
Monomodal Logics”,
*Logic Journal of the IGPL*, 8: 861–882.

## Academic Tools

How to cite this entry. Preview the PDF version of this entry at the Friends of the SEP Society. Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). Enhanced bibliography for this entry at PhilPapers, with links to its database.

## Other Internet Resources

[Please contact the author with suggestions.]

### Acknowledgments

I am grateful to Thomas Hendrey for drawing my attention (in 2011) to
an error in the initial version of this entry, at a point in Section 2
after the formulation of the rules \((\wedge\)I) and \((\wedge\)E), where the
discussion included the following: “Typically \(\vdash\) will also
be determined by many further classes of valuations (meaning: other
than the class Val\((\vdash)\) of all valuations consistent with
\(\vdash)\), various subsets of Val\((\vdash)\), but not so, as just
remarked, in the present case.” By “the present
case” was meant the case of \(\vdash = \vdash_{\wedge}\).
As Hendrey pointed out, this consequence relation is determined by
numerous proper subsets of the set of all \(\wedge\)-Boolean valuations, so
the claim is false. In a moment of inattention I had confusingly
passed from the correct thought that the only valuations consistent
with \(\vdash_{\wedge}\) are the \(\wedge\)-Boolean ones to the faulty
conclusion that the only class of valuations determining
\(\vdash_{\wedge}\) is the class of all \(\wedge\)-Boolean valuations.
(Many counterexamples could be given to this latter claim but one
offered by Hendrey is particularly interesting: the class of all those
\(\wedge\)-Boolean valuations with the further property that they make at
most one sentence letter false.) The reference to subsets of
Val\((\vdash)\) was ill-conceived, since the point of contrast with,
e.g., \(\vdash_{\vee}\), taken as the consequence relation (on
the language with sole connective \(\vee)\) determined by the class of all
\(\vee\)-Boolean valuations is also determined by classes of valuations
which are *not* subsets of this class since we can include also
conjunctive combinations of \(\vee\)-Boolean valuations. By contrast,
\(\vdash_{\wedge}\) can only be determined by classes of
valuations all of which are \(\wedge\)-Boolean.