Relational Syllogisms with Numerical Quantifiers and Beyond

Abstract

In the first half of this paper, we present a fragment of relational syllogisms named RELSYLL consisting of quantified statements with a special set of numerical quantifiers, and introduce a number of concepts that are useful for the later sections, including indirect reduction, quantifier transformations and equivalence of syllogisms. After determining the valid and invalid syllogisms in RELSYLL, we then introduce two Derivation Methods which can be used to derive valid relational syllogisms based on known valid simple syllogisms. We also show that the two Methods are sound and complete for RELSYLL. In the second half of this paper, we discuss ways to extend the Derivation Methods, including the use of more valid syllogisms and the use of existential assumptions. In this way, we are able to derive more relational syllogisms that contain other types of non-classical quantifiers, including “only” and proportional quantifiers. Finally, we state and prove a proposition concerning the relationship between the two Methods.

1 Introduction

Syllogisms constitute an important topic in classical logic and in some modern disciplines such as natural language reasoning and cognitive psychology. Among the various types of syllogisms that have been studied, relational syllogisms are a challenging topic because they contain $n$-ary predicates (where $n > 1$) in the premises and/or conclusion which make the sentence structure more complicated (e.g. with object, oblique argument and relative clause), as opposed to simple syllogisms, whose premises and conclusion contain only unary predicates. Given the difficulty, it is not surprising that the studies on relational syllogisms have been focused on those with the classical quantifiers, and there are few studies of relational syllogisms with other quantifiers, such as numerical and proportional quantifiers.

This paper introduces two new Derivation Methods for deriving relational syllogisms. Under the new Methods, we do not derive relational syllogisms directly from axioms and/or inference rules as was done in Ivanov and Vakarelov (2012), Keene (1969), Moss (2010, 2011), Pratt-Hartmann (2013), Pratt-Hartmann and Moss (2009), to name just a few. Instead, we use known valid simple syllogisms as a starting point and derive valid relational syllogisms by applying certain validity-preserving operations on these simple syllogisms. In this way, we can guarantee that the Methods are sound, i.e. the relational syllogisms derived by applying the Methods are valid provided that the simple syllogisms we start with are valid.

Given the great variety of relational syllogisms in terms of the format as well as the types of quantifiers and predicates that they may contain, it is hard to determine the completeness of the Methods, i.e. whether all valid relational syllogisms can be derived by the Methods. For this reason, we will only prove the completeness of the Methods for a fragment of relational syllogisms consisting of quantified statements with the numerical quantifiers studied by Murphree (1991, 1993, 1997, 1998), which is named RELSYLL. This fragment is restrictive in terms of the format of the premises and conclusion in each syllogism, just like the classical syllogisms. However, we will discuss how the Methods can be used to derive a much larger set of valid relational syllogisms, while leaving the discussion of the completeness of the Methods for this larger set, or a subset of it, to future studies.

The paper is organized as follows. In the first half of the paper, we will first introduce some basic notions and notation for predicates, quantifiers, individual terms, syllogisms and the fragment RELSYLL, as well as a number of concepts that are useful for the later sections, including indirect reduction, quantifier transformations and equivalence of syllogisms. After determining the valid and invalid relational syllogisms in RELSYLL, we will then describe the Derivation Methods in detail. We will also prove that the Methods are sound and complete for RELSYLL. In the second half of the paper, we will discuss how we can extend the Methods, including the use of more valid syllogisms and the use of existential assumptions, so as to derive more relational syllogisms that contain other types of non-classical quantifiers. Finally, we will state and prove a proposition concerning the relationship between the two Methods before concluding the paper.

2 Basic Notions and Notation

2.1 Predicates and Quantifiers

In this paper, we will adopt a notation for quantified statements that is based on the Generalized Quantifier Theory (GQT) as presented in, say Keenan and Westerståhl (2011) and Peters and Westerståhl (2006), among many others. Under GQT, a quantifier is seen as a second-order predicate with ordinary (first-order) predicate(s) as its argument(s), and a quantified statement is made up of a quantifier plus its argument(s). Quantifiers can be classified according to the number and type of argument(s) required. A type $\langle 1\rangle$ quantifier, represented generically as $Q$ in this paper, requires one unary predicate, while a type $\langle 1 ,1\rangle$ quantifier, commonly called “determiner” in the GQT literature and so represented generically as $D$ in this paper, requires two unary predicates as its argument(s).

In this paper, we will use small-case letters in the beginning of the alphabet list, i.e. $a$, $b$, $c$, ...to represent unary predicates, and $A$, $E$, $I$ and $O$ to represent the four classical quantifiers “every”, “no”, “some” and “not every”, respectively. These are type $\langle 1 ,1\rangle$ quantifiers as they require two unary predicates as arguments, which will be called the first and the second arguments. Moreover, a type $\langle 1 ,1\rangle$ quantifier plus a unary predicate in its first argument position can also be seen as a type $\langle 1\rangle$ quantifier because this structure requires only one unary predicate to make up a quantified statement. Hence, the quantified statement $Aab$, meaning “Every $a$ is a $b$”, can be seen as made up of a type $\langle 1 ,1\rangle$ quantifier $A$ plus two unary predicates $a$ and $b$. It can also be seen as made up of a type $\langle 1\rangle$ quantifier $Aa$ plus one unary predicate $b$.

When a quantified statement contains a binary predicate, which will be represented by the small-case letter $r$ in this paper, the situation is a bit more complicated. In the GQT literature, type $\langle 1\rangle$ quantifiers can be seen as “arity reducers” which, when combined with an $n$-ary predicate, will reduce that predicate to an $n - 1$-ary predicate¹. In this paper, we stipulate that when a binary predicate $r$ combines with a type $\langle 1\rangle$ quantifier $Q$, $r$ always appear on the right of $Q$, i.e. we always have $Qr$ and never $rQ$. Hence, when the type $\langle 1\rangle$ quantifier $Ia$ combines with the binary predicate $r$, we have $Iar$, which is a unary predicate, and the quantified statement $Ab(Iar)$ can be seen as made up of a type $\langle 1,1\rangle$ quantifier $A$ plus two unary predicates $b$ and $Iar$.

We also stipulate that $Qr$ should be interpreted in a way such that $Q$ acts as the “subject” of $r$ semantically. Formally, we have $\texttt {Qr} = \{\texttt {y}: \texttt {Q}(\{\texttt {x}: (\texttt {x}, \texttt {y}) \in \texttt {r}\}) = 1\}$². Hence, $Aar$ means “that which every $a$ $r$ it”. A statement with an “object” (as well as a “subject”) of $r$ like “Some $b$ is such that every $a$ $r$ it” will be represented under this notation by $Ib(Aar)$, while a statement with a headless relative clause like “All that every $a$ $r$ is a $b$” is represented by $A(Aar)b$. Moreover, a statement with both a headless relative clause and an object of a binary predicate like “All that every $a$ $r_1$ is such that some $b$ $r_2$ it” can be represented by $A(Aar_1)(Ibr_2)$.

In case we wish to express a unary predicate in which $Q$ acts as the “object” of $r$ semantically, we may use the converse³ of $r$, represented by $r^{-1}$. Formally, we have $\texttt {Qr}^{-1} = \{\texttt {y}: \texttt {Q}(\{\texttt {x}: (\texttt {x}, \texttt {y}) \in \texttt {r}^{-1}\}) = 1\} = \{\texttt {x}: \texttt {Q}(\{\texttt {y}: (\texttt {x}, \texttt {y}) \in \texttt {r}\}) = 1\}$. If $r$ is interpreted as a transitive verb, then $r^{-1}$ can be interpreted as the passive form meaning “be $r$-ed by”. Hence, $Aar^{-1}$ means “that which every $a$ is $r$-ed by it”, or equivalently, “that which $r$ every $a$”, where “every $a$” acts as the “object” of $r$, and $Ib(Aar^{-1})$ means “Some $b$ (is such that it) $r$ every $a$”. Of course, since $r^{-1}$ is an arbitrary variable for binary predicates, we may as well write it as $r$, provided that we interpret it properly. Hence, the sentence “Some boy loves every girl”, which is equivalent to “Some boy is such that every girl is loved by him”, can be represented by $Ib(Aar)$, provided that we interpret $b$, $a$ and $r$ as “boy”, “girl” and “be loved by”, respectively.

Apart from transitive verbs, binary predicates can also be used to represent other parts of speech that require two arguments, including some relational nouns such as “parent of”, comparative adjectives such as “taller than” and prepositions such as “in front of”, etc. The concept of converse is also applicable to these parts of speech. Hence, if $r$ is interpreted as the aforesaid relational noun, comparative adjective and preposition, then $r^{-1}$ can be interpreted as “child of”, “shorter than” and “behind”, respectively, and so a quantified statement with a binary predicate can be used to represent a great variety of natural language sentences instead of just those with transitive verbs.

We next introduce the notation for the numerical quantifiers discussed in this paper. These are the type $\langle 1,1\rangle$ quantifiers studied by Murphree (1991, 1993, 1997, 1998). Under Murphree’s system, there are four types of numerical quantifiers, meaning “at least all but $n$”, “at most $n$”, “at least $n$” and “at most all but $n$”⁴, where $n$ is an appropriate non-negative integer⁵. The interpretation of these quantifiers is given below:

$$\begin{aligned}&\hbox {``At least all but }n \ a \hbox { are } b\hbox {''} \hbox { is true iff }\, |\texttt {a} - \texttt {b}| \le n. \end{aligned}$$

(1)

$$\begin{aligned}&\hbox {``At most }n \ a \hbox { are } b\hbox {''} \hbox { is true iff } |\texttt {a} \cap \texttt {b}| \le n. \end{aligned}$$

(2)

$$\begin{aligned}&\hbox {``At least }n \ a \hbox { are } b\hbox {''} \hbox { is true iff } |\texttt {a} \cap \texttt {b}| \ge n. \end{aligned}$$

(3)

$$\begin{aligned}&\hbox {``At most all but }n \ a \hbox { are } b\hbox {''} \hbox { is true iff } |\texttt {a} - \texttt {b}| \ge n. \end{aligned}$$

(4)

From the above interpretation, one can easily see that these four types of numerical quantifiers are in fact extensions of the four classical quantifiers in that “every” = “at least all but $0$”, “no” = “at most $0$”, “some” = “at least $1$” and “not every” = “at most all but $1$”. Following Murphree’s practice, we will represent the four types of numerical quantifiers as $nA$, $nE$, $nI$ and $nO$. As for the four classical quantifiers, of course they can be represented as $0A$, $0E$, $1I$ and $1O$. But for flexibility, in this paper they will usually be represented simply as $A$, $E$, $I$ and $O$, as no confusion will arise if they are represented in this simpler way. Hence, a statement like “Every $d$ is such that at least all but $n$ $a$ $r$ it” is represented in this paper by $Ad(nAar)$.

2.2 Individual Terms

In this paper, we will use letters at the end of the alphabet list, i.e. $u$, $v$, $w$, $x$, ...to represent individual terms. Under GQT, individual terms can be lifted to type $\langle 1\rangle$ quantifiers (they are sometimes called “Montagovian individuals” in the GQT literature). To highlight this point, we will use capital letters $U$, $V$, $W$, $X$, ...to represent type-lifted individual terms⁶. As type $\langle 1\rangle$ quantifiers, individual terms can appear in any position of a quantified statement where a general type $\langle 1\rangle$ quantifier can appear. Hence, $Xa$, meaning “$x$ is an $a$”, can be seen as made up of a type $\langle 1\rangle$ quantifier $X$ plus a unary predicate $a$, while $X(Iar)$, meaning “$x$ is such that some $a$ $r$ it”, is just a slightly more complicated quantified statement made up of a type $\langle 1\rangle$ quantifier $X$ plus a unary predicate $Iar$.

According to Zimmermann (1993), an individual term is scopeless. This special property enables it to interchange with another type $\langle 1\rangle$ quantifier in a quantified statement with a binary predicate, provided that the binary predicate is changed to its converse. For example, the statement $Aa(Xr^{-1})$, which means “Every $a$ $r$ $x$”, can be rewritten as $X(Aar)$, which means “$x$ is such that every $a$ $r$ it”.

Moreover, an individual term can also interchange with the negation operator $\lnot$. Hence, $\lnot Xa$, which means “It is not the case that $x$ is an $a$”, can be rewritten as $X\lnot a$, which means “$x$ is not an $a$”. However, an individual term cannot interchange with a type $\langle 1,1\rangle$ quantifier. For example, in $E(Xr^{-1})b$ and $A(Xr^{-1})b$, $X$ cannot interchange with $E$ or $A$⁷.

Note that interchange of type $\langle 1\rangle$ quantifiers is not generally allowed if the quantifiers involved do not include individual terms. For example, the statement $Aa(Ibr^{-1})$, which means “Every $a$ $r$ some $b$” cannot be rewritten as $Ib(Aar)$, which means “Some $b$ is such that every $a$ $r$ it”, because the two statements have different meanings. Moreover, interchange of a type $\langle 1\rangle$ quantifier with $\lnot$ is also not generally allowed if the quantifier that $\lnot$ operates on is not an individual term. For example, $\lnot Aab$, which means “It is not the case that every $a$ is a $b$”, cannot be rewritten as $Aa\lnot b$, which means “Every $a$ is not a $b$”, because the two statements have different meanings.

2.3 Syllogisms

Classical syllogisms do not include all possible inferences that involve the classical quantifiers, but only a fragment of these inferences. This fragment is restrictive in terms of the format of the premises and conclusion in each syllogism, and can be characterized by the so-called “Figures” and “Moods” in classical logic. Table 1 provides the format of the four Figures.

Table 1 The four figures of classical syllogisms

The above table shows that each syllogism must consist of exactly three quantified statements: two premises (those on the left of $\vdash$)⁸ and one conclusion (that one on the right of $\vdash$). In the above table, $D_1$, $D_2$ and $D_3$ represent type $\langle 1,1\rangle$ quantifiers (some or all of which can be identical), while $a$, $b$ and $c$ represent three unary predicates which are called “minor term”, “major term” and “middle term”, respectively, in classical logic. The above table shows that in each syllogism, each of $a$, $b$ and $c$ must appear exactly twice, with c appearing only in the premises.

By instantiating $D_1$, $D_2$ and $D_3$ in Table 1 with the classical quantifiers, we then obtain a particular Mood. For example, by letting $D_1 = A$, $D_2 = A$ and $D_3 = A$ in Figure 1, we obtain the following syllogism, which is one of the 256 Moods in classical syllogisms and is named $AAA$-1:

$$\begin{aligned} Acb,\, Aac\, \vdash \, Aab \end{aligned}$$

(5)

The remaining Moods are named in an analogous way.

Murphree’s system inherits the basic features of classical syllogisms, including the traditional concepts of Figures and Moods. But since Murphree’s system uses numerical quantifiers, the names of Mood under this system also contain numbers. For example, the following is a Figure-1 Mood under Murphree’s system (where $n$ and $m$ represent appropriate non-negative integers), which can be named $nAmA(n + m)A\hbox {-}1$:

$$\begin{aligned} nAcb,\, mAac\, \vdash \, (n + m)Aab \end{aligned}$$

(6)

2.4 The Fragment RELSYLL

In this subsection, we present a fragment of relational syllogisms called RELSYLL that satisfy the following format: two of the quantified statements in the syllogism have the forms $D_4d(D_1ar)$ and $D_5d(D_2cr)$ while the remaining quantified statement has the form $D_3ac$ or $D_3ca$, where $D_1$, $D_2$, $D_3$ are the numerical quantifiers introduced above, $D_4, D_5 \in \{A, I\}$⁹, $a$, $c$, $d$ are unary predicates, and $r$ is a binary predicate. An example of relational syllogisms in RELSYLL is given below:

$$\begin{aligned} Ad(nAcr),\, mAac\, \vdash \, Ad((n + m)Aar) \end{aligned}$$

(7)

In the above, if we ignore the part $Ad$, hereinafter called the “front part”, in the first premise and the conclusion, then the remaining parts have the form $nAcr,\,$ $mAac\, \vdash \, (n + m)Aar$, which is identical to the simple syllogism given in (6) after renaming of the predicates. Thus, we can say that (7) is based on the simple syllogism $nAmA(n + m)A$-1. The relational syllogism (7) differs from the simple syllogism given in (6) in that we have a binary predicate $r$ instead of the unary predicate $b$, as well as the front part $Ad$ in the first premise and the conclusion. The syllogism in (7) will be named $nAmA(n + m)A\hbox {-}1\, AXA$ in this paper¹⁰, with $AXA$ representing the front part structure of the syllogism, where the $A$ in the first and third positions represent the front part $Ad$ in the first premise and the conclusion of (7), and the $X$ in the second position means that the second premise of (7) has no front part. In a similar fashion, the following relational syllogism will be named $nEmA(n + m)E\hbox {-}2\, AIX$:

$$\begin{aligned} Ad(nEbr),\, Id(mAar)\, \vdash \, (n + m)Eab \end{aligned}$$

(8)

Since we have stipulated that the binary predicate $r$, if it exists in a quantified statement of a syllogism, must appear in the final position of the quantified statement, this has greatly restricted the possible types of relational syllogisms in RELSYLL. For example, if the binary predicate $r$ appears in the first and second premises, then the relational syllogism must be one based on a Figure-2 simple syllogism (like the one given in (8) above), because it is only in Figure 2 that the predicates appearing in the final position of the first and second premises are identical. Moreover, if the binary predicate $r$ appears in the conclusion and one of the premises, then the relational syllogism must be one based on a Figure-1 or Figure-3 simple syllogism and $r$ must appear in the first premise, because in both Figures 1 and 3, it is the first premise that shares the same predicate as the conclusion. Therefore, RELSYLL does not include relational syllogisms of the forms $D_1D_2D_3\hbox {-}1\, XD_4D_5$ and $D_1D_2D_3\hbox {-}3\, XD_4D_5$. Furthermore, RELSYLL does not include relational syllogisms that are based on Figure-4 simple syllogisms, because in Figure 4, unlike the other three Figures, the predicates appearing in the final positions of the three quantified statements are all different. For this reason, in what follows we will only consider relational syllogisms that are based on Figure-1, 2 or 3 simple syllogisms.

In summary, RELSYLL includes only relational syllogisms of the following forms: $D_1D_2D_3\hbox {-}1\, D_4XD_5$, $D_1D_2D_3\hbox {-}2\, D_4D_5X$, $D_1D_2D_3\hbox {-}3\, D_4XD_5$, where $D_1$, $D_2$, $D_3$ are the numerical quantifiers studied in this paper and $D_4, D_5 \in \{A, I\}$.

2.5 Equivalence of Syllogisms

In this subsection, we introduce the notion of “equivalence of syllogisms”, which is borrowed from Richman (2004). The definition of this notion is based on two types of transformations of syllogisms. The first type is called “indirect reduction”, under which the conclusion and one of the premises of a syllogism are negated and interchanged. Thus, if we represent a syllogism schematically as $p_1,\, p_2\, \vdash \, p_3$, then it can be transformed under indirect reduction to either $p_1,\, \lnot p_3\, \vdash \, \lnot p_2$ or $\lnot p_3,\, p_2\, \vdash \, \lnot p_1$.

Indirect reduction will result in syllogisms consisting of quantifiers with the negation symbol $\lnot$. To get rid of this symbol and to obtain syllogisms that conform to the prescribed format, we need a second type of transformations that rewrite the quantifiers in the syllogisms, and are thus called “quantifier transformations” in this paper. These transformations are based on the notions of “outer negation” and “inner negation” of quantifiers in GQT. According to Keenan and Westerståhl (2011) and Peters and Westerståhl (2006), a type $\langle 1,1\rangle$ quantifier $D$ has two types of negation: an outer negation, denoted $\lnot D$, such that $\lnot Dab$ is true iff $Dab$ is false; and an inner negation, denoted $D^*$, such that $D^*ab$ is true iff $Da\lnot b$ is true. By definitions (1)–(4), we can easily find that

$$\begin{aligned} \lnot nA = (n + 1)O;\, \lnot (n + 1)O = nA;\, \lnot nE = (n + 1)I;\, \lnot (n + 1)I = nE \end{aligned}$$

(9)

and

$$\begin{aligned} nA^* = nE;\, nE^* = nA;\, nI^* = nO;\, nO^* = nI \end{aligned}$$

(10)

Note that the above facts are also applicable to classical quantifiers if we view them as special cases of numerical quantifiers, e.g. $A$ can be seen as equivalent to $0A$, etc.

For illustration, consider the relational syllogism $nAmA(n + m)A\hbox {-}1\, AXA$ given in (7) above. Applying indirect reduction to (7), we may obtain

$$\begin{aligned} Ad(nAcr),\, \lnot Ad((n + m)Aar)\, \vdash \, \lnot mAac \end{aligned}$$

(11)

To get rid of the $\lnot$ symbol, we use (9) to rewrite $\lnot A$ and $\lnot mA$ above and obtain

$$\begin{aligned} Ad(nAcr),\, Od((n + m)Aar)\, \vdash \, (m + 1)Oac \end{aligned}$$

(12)

The second premise above does not conform to the format of RELSYLL. But using (10), we have $Od((n + m)Aar) = Id(\lnot (n + m)Aar)$, and using (9) again, we have $Id(\lnot (n + m)Aar) = Id((n + m + 1)Oar)$, and so (12) can be transformed to

$$\begin{aligned} Ad(nAcr),\, Id((n + m + 1)Oar)\, \vdash \, (m + 1)Oac \end{aligned}$$

(13)

The above conforms to the prescribed format of RELSYLL and can easily be recognized as of the Mood $nA(n + m + 1)O(m + 1)O\hbox {-}2\, AIX$, by renaming predicates if necessary.

The above example also shows that by using (9) and (10), one can always transform a quantified statement with $E$ or $O$ as the front part quantifier to one with $A$ or $I$ as the front part quantifier. For example, $Od((n + m)Aar)$ can be transformed to $Id((n + m + 1)Oar)$, as shown above. That is why we can impose the restriction $D_4, D_5 \in \{A, I\}$ at the beginning of the previous subsection.

We say that a syllogism $\alpha$ is equivalent to another syllogism $\beta$ if $\alpha$ can be transformed to $\beta$ by $n$ applications of indirect reduction plus quantifier transformations, where $n$ is any non-negative integer and one application of indirect reduction plus quantifier transformations means doing an indirect reduction and then some quantifier transformation(s).

We now show that the relation defined above is indeed an equivalence relation. It is reflexive because any syllogism $\alpha$ can be transformed to itself by $0$ application of indirect reduction plus quantifier transformations. It is symmetric because if $\alpha$ can be transformed by $n$ applications of indirect reduction plus quantifier transformations via $\beta _1$, $\ldots$ $\beta _{n-1}$ to $\beta _n$, then $\beta _n$ can be transformed by applying $n$ indirect reduction plus quantifier transformations via $\beta _{n-1}$, $\ldots$ $\beta _1$ back to $\alpha$. For example, if we transform $\alpha : Acb,\, Aac\, \vdash \, Aab$ first to $\beta _1: Acb,\, Oab\, \vdash \, Oac$, and then to $\beta _2: Aac,\, Oab\, \vdash \, Ocb$ by two applications of indirect reduction plus quantifier transformations, then it can easily be seen that $\beta _2$ can be transformed first to $\beta _1$ and then back to $\alpha$, by applying two indirect reduction plus quantifier transformations. It is also transitive because if $\alpha$ can be transformed to $\beta$ by $n$ applications of indirect reduction plus quantifier transformations and $\beta$ can be transformed to $\gamma$ by $m$ applications of indirect reduction plus quantifier transformations, then $\alpha$ can be transformed to $\gamma$ by $n + m$ applications of indirect reduction plus quantifier transformations.

This equivalence relation partitions the set of a specific type of syllogisms into equivalence classes. For example, $\{AAA\hbox {-}1, AOO\hbox {-}2, OAO\hbox {-}3\}$ is an equivalence class in classical logic under this equivalence relation. Note that each Figure-1 classical syllogism is equivalent to one Figure-2 and one Figure-3 syllogisms, while each Figure-4 classical syllogism is either equivalent to two other Figure-4 syllogisms or just to itself. The first fact can be proved by applying indirect reduction to the Figure-1 syllogism $\alpha : D_1cb,\, D_2ac\, \vdash \, D_3ab$ and obtain $\beta _1: D_1cb,\, \lnot D_3ab\, \vdash \, \lnot D_2ac$ or $\beta _2: \lnot D_3ab,\, D_2ac\, \vdash \, \lnot D_1cb$. By renaming variables, one can then recognize that $\beta _1$ and $\beta _2$ are Figure-2 and Figure-3 syllogisms, respectively. To prove the second fact, if we apply indirect reduction to the Figure-4 syllogism $\gamma : D_1bc,\, D_2ca\, \vdash \, D_3ab$, we obtain $\delta _1: D_1bc,\, \lnot D_3ab\, \vdash \, \lnot D_2ca$ or $\delta _2: \lnot D_3ab,\, D_2ca\, \vdash \, \lnot D_1bc$. By renaming variables, one can then recognize that $\delta _1$ and $\delta _2$ are both Figure-4 syllogisms. For some Figure-4 syllogism such as $AAO\hbox {-}4$, indirect reduction (plus renaming of variables) will yield the same syllogism. Thus, $\{AAO\hbox {-}4\}$ is a single-member equivalence class.

To facilitate discussion of relational syllogisms below, we will next state and prove two propositions concerning equivalence between relational syllogisms in RELSYLL. Here is the first proposition (in what follows, we will represent the outer negation of a generic type $\langle 1,1\rangle$ quantifier $D$ by $\lnot D$. It is to be understood that when $D$ is instantiated as a specific quantifier, such as $A$, then $\lnot D$ is instantiated as one to which quantifier transformation is applied, such as $O$).

Proposition 1

Let $D_1$, $D_2$, $D_3$ be the numerical quantifiers studied in this paper. Then the following are equivalence classes:

$$\begin{aligned} \begin{array}{lll} \{D_1D_2D_3\hbox {-}1\, AXA, &{} D_1\lnot D_3\lnot D_2\hbox {-}2\, AIX, &{} \lnot D_3D_2\lnot D_1\hbox {-}3\, IXI\} \\ \{D_1D_2D_3\hbox {-}1\, IXI, &{} D_1\lnot D_3\lnot D_2\hbox {-}2\, IAX, &{} \lnot D_3D_2\lnot D_1\hbox {-}3\, AXA\} \\ \{D_1D_2D_3\hbox {-}1\, AXI, &{} D_1\lnot D_3\lnot D_2\hbox {-}2\, AAX, &{} \lnot D_3D_2\lnot D_1\hbox {-}3\, AXI\} \\ \{D_1D_2D_3\hbox {-}1\, IXA, &{} D_1\lnot D_3\lnot D_2\hbox {-}2\, IIX, &{} \lnot D_3D_2\lnot D_1\hbox {-}3\, IXA\} \end{array} \end{aligned}$$

Proof

Here we only prove the first equivalence class. The proofs for the remaining ones are similar. Consider the syllogism $D_1D_2D_3\hbox {-}1\, AXA$, which can be written out in full as

$$\begin{aligned} Ad(D_1cr),\, D_2ac\, \vdash \, Ad(D_3ar) \end{aligned}$$

(14)

Applying indirect reduction to the above and then using (9), we obtain either one of the following:

$$\begin{aligned}&Ad(D_1cr),\, Od(D_3ar)\, \vdash \, \lnot D_2ac \end{aligned}$$

(15)

$$\begin{aligned}&Od(D_3ar),\, D_2ac\, \vdash \, Od(D_1cr) \end{aligned}$$

(16)

By (10), the above two can be rewritten as

$$\begin{aligned}&Ad(D_1cr),\, Id(\lnot D_3ar)\, \vdash \, \lnot D_2ac \end{aligned}$$

(17)

$$\begin{aligned}&Id(\lnot D_3ar),\, D_2ac\, \vdash \, Id(\lnot D_1cr) \end{aligned}$$

(18)

The above two are $D_1\lnot D_3\lnot D_2\hbox {-}2\, AIX$ and $\lnot D_3D_2\lnot D_1\hbox {-}3\, IXI$, respectively. If we apply indirect reduction plus quantifier transformations to (17) above, we will then obtain either (14) or (18). Doing the same to (18) above will obtain either (14) or (17). Thus, one can see that by applying indirect reduction plus quantifier transformations to any member of the set {(14), (17), (18)}, one will always obtain another member of this set and so this set constitutes an equivalence class. $\square$

Syllogisms belonging to the same equivalence class are not only related to each other in terms of their transformability under indirect reduction plus quantifier transformations, but are also related in terms of their validity. This is the content of the second proposition.

Proposition 2

A syllogism is valid iff any one of its equivalent forms is also valid.

Proof

• (a) Let $\alpha : p_1,\, p_2\, \vdash \, p_3$ be a syllogism. Its equivalent forms include $\beta : p_1,\, \lnot p_3\, \vdash \, \lnot p_2$ and $\gamma : \lnot p_3,\, p_2\, \vdash \, \lnot p_1$. Suppose first that $\alpha$ is valid. This means that in any model $M$ under which $p_1$ and $p_2$ are both true, $p_3$ must also be true. We now show that $\beta$ is also valid. Consider any model $M$ under which $p_1$ and $\lnot p_3$ are both true. To show that $\lnot p_2$ must also be true under $M$, we assume by way of contradiction that $\lnot p_2$ is false, i.e. $p_2$ is true. Then, we would have $p_1$, $p_2$ and $\lnot p_3$ all true. But by the preceding fact, since $p_1$ and $p_2$ are both true, then $p_3$ must also be true under $M$. Then we have $p_3$ and $\lnot p_3$ both true under $M$, a contradiction. We have thus shown that $\beta$ is valid. In a similar fashion, one can also show that $\gamma$ is valid.

• (b) Next suppose that $\alpha$ is invalid. Then there must exist a counterexample for $\alpha$, i.e. a model $M$ under which $p_1$ and $p_2$ are both true and $p_3$ is false, or in other words, $p_1$, $p_2$ and $\lnot p_3$ are all true. But then $M$ is also a counterexample for $\beta$ and $\gamma$, and so $\beta$ and $\gamma$ are also invalid. $\square$

The above proposition shows that two equivalent syllogisms are both valid or both invalid. This fact will be made use of below to simplify some proofs. Moreover, the above proposition is applicable to all types of syllogisms, be they simple or relational.

3 Determination of Valid and Invalid Syllogisms

3.1 Classical Syllogisms and Murphree’s Numerical Syllogisms

In this section, we will determine the valid and invalid syllogisms in RELSYLL. This is based on the corresponding results of simple numerical syllogisms, which is in turn based on the corresponding results of classical syllogisms.

According to Peterson (2000), for each of the $256$ classical syllogisms, one can decide whether it is valid by consulting the Laws of Distribution developed by ancient and medieval logicians, or by using a validity checking method based on Venn diagrams. As a result, we can list out all the $15$ valid classical syllogisms as follows: $AAA\hbox {-}1$, $AII\hbox {-}1$, $EAE\hbox {-}1$, $EIO\hbox {-}1$, $AEE\hbox {-}2$, $AOO\hbox {-}2$, $EAE\hbox {-}2$, $EIO\hbox {-}2$, $AII\hbox {-}3$, $EIO\hbox {-}3$, $IAI\hbox {-}3$, $OAO\hbox {-}3$, $AEE\hbox {-}4$, $EIO\hbox {-}4$, $IAI\hbox {-}4$. According to Pagnan (2012), among the remaining $241$ classical syllogisms, some are valid under “existential import”, i.e. under suitable assumptions of the existence of some of the predicates. For example, $AAI\hbox {-}1$ is valid under the assumption that $\texttt {a} \not = \emptyset$. For simplicity, we will not consider existential import in this section and will thus consider the above $15$ classical syllogisms as valid and the remaining ones as invalid.

Murphree (1991, 1993, 1997, 1998) extended the above results to simple syllogisms with the numerical quantifiers introduced above. According to him, a valid classical syllogism $\alpha$ remains valid if the classical quantifiers in $\alpha$ are replaced by the corresponding numerical quantifiers, i.e. $A$ replaced by $nA$, etc., provided that the numeral associated with the quantifier in the conclusion satisfies the following “Rules of Deviation”: (1) if the quantifier in the conclusion is a global quantifier (i.e. quantifier in the form $nA$ or $nE$), then the numeral associated with that quantifier must be no less than the sum of the numerals associated with the quantifiers in the premises; (2) if the quantifier in the conclusion is a local quantifier (i.e. quantifier in the form $nI$ or $nO$), then the numeral associated with that quantifier must be no greater than the numeral associated with the local quantifier in one premise minus the numeral associated with the global quantifier in another premise. Murphree’s conclusion can be proved by a special schematic method developed by him.

For example, since $AAA\hbox {-}1$ and $EIO\hbox {-}1$ are valid classical syllogisms whose conclusions contain a global quantifier (i.e. $A$) and a local quantifier (i.e. $O$), respectively, according to Murphree (1991, 1993, 1997, 1998), $nAmA(n + m)A\hbox {-}1$ and $nE(n + m + 1)I(m + 1)O\hbox {-}1$ are also valid.

In the above examples, we have provided the strongest conclusion for a valid numerical syllogism. But weaker conclusions are also admissible. For example, $nAmA(n + m + k)A\hbox {-}1$, where $k \ge 0$, is also a valid syllogism. Note that the adoption of $n + m + k$ does not violate Rule (1) above and the conclusion of $nAmA(n + m + k)A\hbox {-}1$ is entailed by that of $nAmA(n + m)A\hbox {-}1$ (because if $|\texttt {a} - \texttt {b}| \le n + m$, then it must be the case that $|\texttt {a} - \texttt {b}| \le n + m + k$). Similarly, $nE(n + m + 1)I(m + 1 - l)O\hbox {-}1$, where $0 \le l \le m$, is also a valid syllogism. Note that the adoption of $m + 1 - l$ does not violate Rule (2) above and the conclusion of $nE(n + m + 1)I(m + 1 - l)O\hbox {-}1$ is entailed by that of $nE(n + m + 1)I(m + 1)O\hbox {-}1$ (because if $|\texttt {a} - \texttt {b}| \ge m + 1$, then it must be the case that $|\texttt {a} - \texttt {b}| \ge m + 1 - l$).

All other numerical syllogisms under Murphree’s system are invalid. They are invalid either because they are based on invalid classical syllogisms, such as $nAmA(n + m)E\hbox {-}1$, or because they are associated with the wrong numerals and so violating Rule 1 or 2 above even though they are based on valid classical syllogisms, such as $nAmA(n + m - 1)A\hbox {-}1$. The invalidity of any such syllogism can be proved by a counterexample, i.e. a model under which the premises are true but the conclusion is false. The “Appendix” to this paper provides counterexamples for some of the invalid numerical syllogisms.

3.2 RELSYLL

In this subsection, we will prove a number of propositions that will characterize the valid and invalid relational syllogisms in RELSYLL. The first proposition establishes the validity of a subset of RELSYLL.

Proposition 3

Let $D_1D_2D_3\hbox {-}i$ be a valid simple syllogism where $D_1$, $D_2$, $D_3$ are the numerical quantifiers studied in this paper and $i \in \{1, 2, 3\}$. If $i = 1$ or $3$, then $D_1D_2D_3\hbox {-}i\, AXA$ and $D_1D_2D_3\hbox {-}i\, IXI$ are both valid. If $i = 2$, then $D_1D_2D_3\hbox {-}i\, AIX$ and $D_1D_2D_3\hbox {-}i\, IAX$ are both valid.

Proof

• (a) First let $D_1D_2D_3\hbox {-}1$ be a valid Figure-1 simple syllogism. Then in any model such that $D_1cb$ and $D_2ac$ are both true, $D_3ab$ must also be true. This fact can be represented by

  $$\begin{aligned} D_1cb,\, D_2ac\, \models \, D_3ab \end{aligned}$$

  (19)

Since $b$ is an arbitrary unary predicate, the above relation must still hold if $b$ is replaced by another unary predicate $Xr^{-1}$, where $X$ is an arbitrary individual variable and $r$ is any binary predicate. Thus, we must have the following:

$$\begin{aligned} D_1c(Xr^{-1}),\, D_2ac\, \models \, D_3a(Xr^{-1}) \end{aligned}$$

(20)

Since $X$ is an individual term, it can interchange with a type $\langle 1\rangle$ quantifier in the quantified statement and so the following must also hold:

$$\begin{aligned} X(D_1cr),\, D_2ac\, \models \, X(D_3ar) \end{aligned}$$

(21)

Since $X$ is an arbitrary variable, the above means that for any individual $\texttt {x}$ in a model, if $\texttt {x}$ is a member of $\texttt {D}_1\texttt {cr}$ and the statement $D_2ac$ is true in that model, then $\texttt {x}$ is also a member of $\texttt {D}_3\texttt {ar}$ in that model.

We next prove that $D_1D_2D_3\hbox {-}1\, AXA$ and $D_1D_2D_3\hbox {-}1\, IXI$ are valid by showing the validity of the following:

$$\begin{aligned}&Ad(D_1cr),\, D_2ac\, \models \, Ad(D_3ar) \end{aligned}$$

(22)

$$\begin{aligned}&Id(D_1cr),\, D_2ac\, \models \, Id(D_3ar) \end{aligned}$$

(23)

First suppose $M$ is a model in which $Ad(D_1cr)$ and $D_2ac$ are both true. Now $Ad(D_1cr)$ means that for every individual $\texttt {x}$ in $M$, if $\texttt {x}$ is a member of $\texttt {d}$, then $\texttt {x}$ is also a member of $\texttt {D}_1\texttt {cr}$. But then by the discussion after (21), $\texttt {x}$ is also a member of $\texttt {D}_3\texttt {ar}$ in $M$. This shows that for every individual $\texttt {x}$ in $M$, if $\texttt {x}$ is a member of $\texttt {d}$, then $\texttt {x}$ is also a member of $\texttt {D}_3\texttt {ar}$, which is what the statement $Ad(D_3ar)$ means. We have thus proved that (22) is valid. Next suppose $M$ is a model in which $Id(D_1cr)$ and $D_2ac$ are both true. Now $Id(D_1cr)$ means that there is an individual $\texttt {x}$ in $M$ such that $\texttt {x}$ is both a member of $\texttt {d}$ and a member of $\texttt {D}_1\texttt {cr}$. Again, by the discussion after (21), $\texttt {x}$ is also a member of $\texttt {D}_3\texttt {ar}$ in $M$. This shows that there exists an individual $\texttt {x}$ in $M$ such that $\texttt {x}$ is both a member of $\texttt {d}$ and a member of $\texttt {D}_3\texttt {ar}$, which is what the statement $Id(D_3ar)$ means. We have thus proved that (23) is valid.

• (b) Next let $D_1D_2D_3\hbox {-}2$ be a valid Figure-2 simple syllogism. Now since $D_1D_2D_3\hbox {-}2$ is equivalent to $D_1\lnot D_3\lnot D_2\hbox {-}1$, by Proposition 2, $D_1\lnot D_3\lnot D_2\hbox {-}1$ must be a valid Figure-1 simple syllogism, and so by (a) above, $D_1\lnot D_3\lnot D_2\hbox {-}1\,$ $AXA$ must be valid. By Proposition 1, $D_1\lnot D_3\lnot D_2\hbox {-}1\, AXA$ is equivalent to $D_1D_2D_3\hbox {-}2\,$ $AIX$, and so by Proposition 2 again, $D_1D_2D_3\hbox {-}2\, AIX$ must be valid. In a similar fashion, we can also prove that $D_1D_2D_3\hbox {-}2\, IAX$ is valid. Finally, let $D_1D_2D_3\hbox {-}3$ be a valid Figure-3 simple syllogism. Using an argument similar to the above, one can prove that $D_1D_2D_3\hbox {-}3\, AXA$ and $D_1D_2D_3\hbox {-}3\, IXI$ are both valid. $\square$

Based on the above proposition, we can now list a set of representative valid syllogisms in RELSYLL in Table 2. These valid relational syllogisms are closely related to the valid classical syllogisms listed in the previous subsection. Discarding the Figure-4 syllogisms in that list (because RELSYLL does not include relational syllogisms based on Figure-4 simple syllogisms), there are 12 classical syllogisms left in that list. Each of these corresponds to a valid numerical syllogism studied by Murphree, which in turn corresponds to two valid syllogisms in RELSYLL according to Proposition 3. This accounts for the 24 syllogisms listed in Table 2.

Table 2 Valid syllogisms in RELSYLL

For convenience, the syllogisms listed in Table 2 are grouped into eight cells, each constituting an equivalence class. Note that each cell represents an infinite number of valid syllogisms, not only because $n$ and $m$ can be substituted by an infinite number of appropriate non-negative integers, but also because from each cell one can deduce an infinite number of valid syllogisms with weaker conclusions. For example, from $nAmA(n + m)A\hbox {-}1\, AXA$ one can deduce that $nAmA(n + m + k)A\hbox {-}1\, AXA$, where $k > 0$, is also a valid relational syllogism.

Here is an exemplification of $1A3I2I\hbox {-}1\, AXA$, with $a$, $c$, $d$, $r$ interpreted as “foreign employee in this school”, “teacher in this school”, “student”, “be liked by”, respectively:

Every student likes all but at most one teacher in this school¹¹. At least three foreign employees in this school are teachers. Therefore, every student likes at least two foreign employees in this school.

As pointed out above, apart from being interpreted as transitive verbs, binary predicates can also be interpreted as other parts of speech, such as relational nouns. For illustration, here is another exemplification of $1A3I2I\hbox {-}1\, AXA$, with $a$, $c$, $d$, $r$ interpreted as “singer”, “movie star”, “youngster”, “idol of” (whose converse is assumed to be “fan of” here), respectively:

Every youngster is a fan of all but at most one movie star. At least three singers are movie stars. Therefore, every youngster is a fan of at least two singers.

We next show that all other relational syllogisms in RELSYLL are invalid syllogisms, which can be classified into two types. The first type consists of those that are based on invalid simple syllogisms. The invalidity of these syllogisms is summarized in the following proposition.

Proposition 4

Let $D_1D_2D_3\hbox {-}i$ be an invalid simple syllogism where $D_1$, $D_2$, $D_3$ are the numerical quantifiers studied in this paper and $i \in \{1, 2, 3\}$. If $i = 1$ or $3$, then $D_1D_2D_3\hbox {-}i\, AXA$, $D_1D_2D_3\hbox {-}i\, IXI$, $D_1D_2D_3\hbox {-}i\, AXI$, $D_1D_2D_3\hbox {-}i\, IXA$ are all invalid. If $i = 2$, then $D_1D_2D_3\hbox {-}i\, AAX$,$D_1D_2D_3\hbox {-}i\, IIX$, $D_1D_2D_3\hbox {-}i \, AIX$, $D_1D_2D_3\hbox {-}i\, IAX$ are all invalid.

Proof

We will only prove the invalidity of $D_1D_2D_3\hbox {-}1\, AXA$ and $D_1D_2D_3\hbox {-}2\, AIX$. The proofs of the other cases are similar.

• (a) Let $D_1D_2D_3\hbox {-}1$ be an invalid Figure-1 simple syllogism with the form $D_1cb, D_2ac\, \vdash \, D_3ab$. Since it is invalid, it must have a counterexample, i.e. there must be $\texttt {a}$, $\texttt {b}$ and $\texttt {c}$ such that $D_1cb$ and $D_2ac$ are true while $D_3ab$ is false. Let $\texttt {u}$ be an individual in the domain and $\texttt {r} = \texttt {b} \times \{\texttt {u}\}$. This implies that $\texttt {Ur}^{-1} = \texttt {b}$¹², and so $D_1c(Ur^{-1})$ is true and $D_3a(Ur^{-1})$ is false. Since $U$ is an individual term, it follows that we have $U(D_1cr)$ true and $U(D_3ar)$ false. Now let $\texttt {d} = \{\texttt {u}\}$. It then follows that $Ad(D_1cr)$ is true and $Ad(D_3ar)$ is false. This means that if we set $\texttt {a}$, $\texttt {c}$, $\texttt {d}$ and $\texttt {r}$ as mentioned above, then $Ad(D_1cr)$ and $D_2ac$ are true while $Ad(D_3ar)$ is false. We have thus found a counterexample for the invalid syllogism $D_1D_2D_3\hbox {-}1\, AXA$.

• (b) Let $D_1D_2D_3\hbox {-}2$ be an invalid Figure-2 simple syllogism with the form $D_1bc, D_2ac\, \vdash \, D_3ab$. Since it is invalid, it must have a counterexample, i.e. there must be $\texttt {a}$, $\texttt {b}$ and $\texttt {c}$ such that $D_1bc$ and $D_2ac$ are true while $D_3ab$ is false. Let $\texttt {u}$ be an individual in the domain and $\texttt {r} = \texttt {c} \times \{\texttt {u}\}$. This implies that $\texttt {Ur}^{-1} = \texttt {c}$, and so $D_1b(Ur^{-1})$ and $D_2a(Ur^{-1})$ are both true. Since $U$ is an individual term, it follows that we have $U(D_1br)$ and $U(D_2ar)$ both true. Now let $\texttt {d} = \{\texttt {u}\}$. It then follows that $Ad(D_1br)$ and $Id(D_2ar)$ are both true. This means that if we set $\texttt {a}$, $\texttt {b}$, $\texttt {d}$ and $\texttt {r}$ as mentioned above, then $Ad(D_1br)$ and $Id(D_2ar)$ are true while $D_3ab$ is false. We have thus found a counterexample for the invalid syllogism $D_1D_2D_3\hbox {-}2\, AIX$. $\square$

For illustration, suppose we want to construct a counterexample for the invalid syllogism $2A1A2A\hbox {-}1\, AXA$. By consulting “Appendix 1”, we can find the following counterexample for the invalid simple syllogism $2A1A2A\hbox {-}1$: $\texttt {a} = \{\texttt {u}_1, \texttt {u}_2, \texttt {v}_1\}$, $\texttt {b} = \emptyset$, $\texttt {c} = \{\texttt {u}_1, \texttt {u}_2\}$. Following the above proof, we can set $\texttt {a} = \{\texttt {u}_1, \texttt {u}_2, \texttt {v}_1\}$, $\texttt {c} = \{\texttt {u}_1, \texttt {u}_2\}$, $\texttt {d} = \{\texttt {u}\}$ and $\texttt {r} = \emptyset$. Then under this model, $\texttt {Ur}^{-1} = \emptyset$, and we have $Ad(2Acr)$ true (because $U(2Acr)$ is true), $1Aac$ true, and $Ad(2Aar)$ false (because $U(2Aar)$ is false).

The second type of invalid relational syllogisms consists of those that are based on valid simple syllogisms but with incorrect front parts. The invalidity of these syllogisms is summarized in the following proposition.

Proposition 5

Let $D_1D_2D_3\hbox {-}i$ be a valid simple syllogism where $D_1$, $D_2$, $D_3$ are the numerical quantifiers studied in this paper and $i \in \{1, 2, 3\}$. If $i = 1$ or $3$, then $D_1D_2D_3\hbox {-}i\, AXI$ and $D_1D_2D_3\hbox {-}i\, IXA$ are invalid. If $i = 2$, then $D_1D_2D_3\hbox {-}i\, AAX$ and $D_1D_2D_3\hbox {-}i\, IIX$ are invalid.

Proof

• (a) First let $D_1D_2D_3\hbox {-}1$ be a valid Figure-1 simple syllogism. Since there are only four such syllogisms, namely $nAmA(n + m)A\hbox {-}1$, $nA(n + m + 1)I(m + 1)I\hbox {-}1$, $nEmA(n + m)E\hbox {-}1$ and $nE(n + m + 1)I(m + 1)O\hbox {-}1$, we can prove that $D_1D_2D_3\hbox {-}1\, AXI$ and $D_1D_2D_3\hbox {-}1\, IXA$ are invalid just by considering these four syllogisms. For $D_1D_2D_3\hbox {-}1\, AXI$, since among the above four syllogisms, $D_2$ is either $mA$ or $(n + m + 1)I$, we can set $\texttt {d} = \texttt {r} = \emptyset$ and $\texttt {a} = \texttt {c} = \{\texttt {u}_1, \ldots \texttt {u}_k\}$, where $k = m$ or $n + m + 1$ as the case may be. Then it is clear that $Ad(D_1cr)$ and $D_2ac$ are both true and $Id(D_3ar)$ is false. The above is thus a counterexample for the invalid syllogism $D_1D_2D_3\hbox {-}1\, AXI$. For $D_1D_2D_3\hbox {-}1\, IXA$, we have to divide the above four syllogisms into two groups and consider them separately.

  • (i) First consider $nAmA(n + m)A\hbox {-}1$ and $nEmA(n + m)E\hbox {-}1$. Set $\texttt {a} = \{\texttt {u}_1, \ldots \texttt {u}_{n+m+1}\}$, $\texttt {c} = \{\texttt {u}_1, \ldots \texttt {u}_{n+1}\}$, $\texttt {d} = \{\texttt {u}, \texttt {v}\}$, $\texttt {r} = \{(\texttt {u}_1, \texttt {u}), \ldots (\texttt {u}_{n+m+1}, \texttt {u})\}$. Then under this model, $\texttt {Ur}^{-1} = \{\texttt {u}_1, \ldots \texttt {u}_{n+m+1}\}$, $\texttt {Vr}^{-1} = \emptyset$, and we have $Id(nAcr)$ true (because $U(nAcr)$ is true), $mAac$ true, and $Ad((n + m)Aar)$ false (because $V((n + m)Aar$) is false), showing that $nAmA(n + m)A\hbox {-}1\, IXA$ is invalid. Moreover, under this model, we also have $Id(nEcr)$ true (because $V(nEcr)$ is true), $mAac$ true, and $Ad((n + m)Ear)$ false (because $U((n + m)Ear)$ is false), showing that $nEmA(n + m)E\hbox {-}1\, IXA$ is invalid.

  • (ii) Next consider $nA(n + m + 1)I(m + 1)I\hbox {-}1$ and $nE(n + m + 1)I(m + 1)O\hbox {-}1$. Set $\texttt {a} = \texttt {c} = \{\texttt {u}_1, \ldots \texttt {u}_{n+m+1}\}$, $\texttt {d} = \{\texttt {u}, \texttt {v}\}$, $\texttt {r} = \{(\texttt {u}_1, \texttt {u}), \ldots (\texttt {u}_{n+m+1}, \texttt {u})\}$. Then under this model, $\texttt {Ur}^{-1} = \{\texttt {u}_1, \ldots \texttt {u}_{n+m+1}\}$, $\texttt {Vr}^{-1} = \emptyset$, and we have $Id(nAcr)$ true (because $U(nAcr)$ is true), $(n + m + 1)Iac$ true, and $Ad((m + 1)Iar)$ false (because $V((m + 1)Iar)$ is false), showing that $nA(n + m + 1)I(m + 1)I\hbox {-}1\, IXA$ is invalid. Moreover, under this model, we also have $Id(nEcr)$ true (because $V(nEcr)$ is true), $(n + m + 1)Iac$ true, and $Ad((m + 1)Oar)$ false (because $U((m + 1)Oar)$ is false), showing that $nE(n + m + 1)I(m + 1)O\hbox {-}1\, IXA$ is invalid.

  • (b) Next let $D_1D_2D_3\hbox {-}2$ be a valid Figure-2 simple syllogism. Now since $D_1D_2D_3\hbox {-}2$ is equivalent to $D_1\lnot D_3\lnot D_2\hbox {-}1$, by Proposition 2, $D_1\lnot D_3\lnot D_2\hbox {-}1$ must be a valid Figure-1 simple syllogism, and so by (a) above, $D_1\lnot D_3\lnot D_2\hbox {-}1\,$ $AXI$ must be invalid. By Proposition 1, $D_1\lnot D_3\lnot D_2\hbox {-}1\, AXI$ is equivalent to $D_1D_2D_3\hbox {-}2\, AAX$, and so by Proposition 2 again, $D_1D_2D_3\hbox {-}2\, AAX$ must be invalid. In a similar fashion, we can also prove that $D_1D_2D_3\hbox {-}2\, IIX$ is invalid. Finally, let $D_1D_2D_3\hbox {-}3$ be a valid Figure-3 simple syllogism. Using an argument similar to the above, one can prove that $D_1D_2D_3\hbox {-}3\, AXI$ and $D_1D_2D_3\hbox {-}3\, IXA$ are both invalid. $\square$

4 Derivation Methods

4.1 Description of the Methods

In this section, we introduce two Derivation Methods (called Methods 1 and 2) that can be used to derive the valid relational syllogisms in RELSYLL. We first provide a description of the Methods. Both Methods consist of the following steps: (i) substitution into a valid simple numerical syllogism; (ii) interchange of an individual variable with a type $\langle 1\rangle$ quantifier; (iii) derivation of an immediate inference (i.e. an inference with only one premise); (iv) substitution into a valid classical syllogism; and (v) premise replacement.

The general idea of the Derivation Methods is as follows: we first make substitution into a valid simple syllogism $\alpha$ so that it contains a binary predicate and derive from it an immediate inference $\beta$. We then choose another valid simple syllogism $\gamma$ such that one of its premises / conclusion contains the same quantifier in the conclusion / premise of $\beta$, and make substitution into $\gamma$ so that one premise / conclusion of $\gamma$ is identical to the conclusion / premise of $\beta$. The end result is a relational syllogism that “combines” the two simple syllogisms $\alpha$ and $\gamma$.

Here are the specific steps under Method 1. Step (i): choose a valid simple numerical syllogism $D_1D_2D_3\hbox {-}1$ or $D_1D_2D_3\hbox {-}3$ (where there are two identical predicates $b$ in the second argument position of one premise and the conclusion) with the form:

$$\begin{aligned} D_1cb,\, D_2ac\, (\hbox {or}\, D_2ca)\, \vdash \, D_3ab \end{aligned}$$

(24)

and substitute $b = Xr^{-1}$, where $X$ is an arbitrary individual variable, into the above to obtain

$$\begin{aligned} D_1c(Xr^{-1}),\, D_2ac\, (\hbox {or}\, D_2ca)\, \vdash \, D_3a(Xr^{-1}) \end{aligned}$$

(25)

Step (ii), interchange X with the type $\langle 1\rangle$ quantifiers in the first premise and conclusion:

$$\begin{aligned} X(D_1cr),\, D_2ac\, (\hbox {or}\, D_2ca)\, \vdash \, X(D_3ar) \end{aligned}$$

(26)

Step (iii): from (26), derive the following immediate inference:

$$\begin{aligned} D_2ac\, (\hbox {or}\, D_2ca)\, \vdash \, A(D_1cr)(D_3ar) \end{aligned}$$

(27)

Step (iv): choose the classical syllogism $AAA\hbox {-}1$ or $AII\hbox {-}1$ (where the first premise contains the same quantifier as that in the conclusion of (27), namely $A$) with the form:

$$\begin{aligned} Aef,\, D_4de\, \vdash \, D_5df \end{aligned}$$

(28)

and substitute $e = D_1cr$ and $f = D_3ar$ into the above (this substitution is to make the first premise below identical to the conclusion of (27)) to obtain

$$\begin{aligned} A(D_1cr)(D_3ar),\, D_4d(D_1cr)\, \vdash \, D_5d(D_3ar) \end{aligned}$$

(29)

Step (v): replace the first premise of (29) by the premise of (27)) (which derives the former) to obtain¹³

$$\begin{aligned} D_4d(D_1cr),\, D_2ac\, (\hbox {or}\, D_2ca)\, \vdash \, D_5d(D_3ar) \end{aligned}$$

(30)

Note that the above relational syllogism has the form $D_1D_2D_3\hbox {-}1\, D_4XD_5$ or $D_1D_2D_3\hbox {-}3\, D_4XD_5$. Since $D_4$ and $D_5$ are either both $A$ or both $I$, $D_4XD_5$ is either equal to $AXA$ or $IXI$. Moreover, since $D_1D_2D_3\hbox {-}1$ and $D_1D_2D_3\hbox {-}3$ are valid simple numerical syllogisms, according to Proposition 3, the above is a valid relational syllogism in RELSYLL.

Here are the specific steps under Method 2. Step (i): choose a valid simple numerical syllogism $D_1D_2D_3\hbox {-}2$ (where there are two identical predicates $c$ in the second argument position of the two premises) with the form:

$$\begin{aligned} D_1bc,\, D_2ac\, \vdash \, D_3ab \end{aligned}$$

(31)

and substitute $c = Xr^{-1}$, where $X$ is an individual variable not used in the previous derivation, into the above to obtain

$$\begin{aligned} D_1b(Xr^{-1}),\, D_2a(Xr^{-1})\, \vdash \, D_3ab \end{aligned}$$

(32)

Step (ii), interchange $X$ with the type $\langle 1\rangle$ quantifiers in the two premises:

$$\begin{aligned} X(D_1br),\, X(D_2ar)\, \vdash \, D_3ab \end{aligned}$$

(33)

Step (iii): from (33), derive the following immediate inference:

$$\begin{aligned} I(D_1br)(D_2ar)\, \vdash \, D_3ab \end{aligned}$$

(34)

Step (iv): choose the classical syllogism $IAI\hbox {-}3$ or $AII\hbox {-}3$ (where the conclusion contains the same quantifier as that in the premise of (34), namely $I$) with the form:

$$\begin{aligned} D_4de,\, D_5df\, \vdash \, Ife \end{aligned}$$

(35)

and substitute $e = D_2ar$ and $f = D_1br$ into the above (this substitution is to make the conclusion below identical to the premise of (34)) to obtain

$$\begin{aligned} D_4d(D_2ar),\, D_5d(D_1br)\, \vdash \, I(D_1br)(D_2ar) \end{aligned}$$

(36)

Step (v): replace the premise of (34) by the premises of (36) (which derives the former) to obtain

$$\begin{aligned} D_5d(D_1br),\, D_4d(D_2ar)\, \vdash \, D_3ab \end{aligned}$$

(37)

Note that the above relational syllogism has the form $D_1D_2D_3\hbox {-}2\, D_5D_4X$. Since among $D_5$ and $D_4$, one is $A$ and the other is $I$, $D_5D_4X$ is either equal to $AIX$ or $IAX$. Moreover, since $D_1D_2D_3\hbox {-}2$ is a valid simple numerical syllogism, according to Proposition 3, the above is a valid relational syllogism in RELSYLL.

4.2 Soundness and Completeness of the Methods

In this subsection, we will show that Methods 1 and 2 introduced above are sound and complete for RELSYLL. In the previous subsection, we have already shown that the final outputs of the two Methods are always valid relational syllogisms in RELSYLL. What we have to ensure is that each step in the two Methods are legitimate moves.

Steps (i) and (iv) of the two Methods involve substitutions into valid simple syllogisms. These are obviously legitimate as substitution into a valid syllogism will always yield a valid syllogism. Step (ii) involves interchange of $X$ with a type $\langle 1\rangle$ quantifier. As we have pointed out in Sect. 2.2, this is a legitimate move since $X$ is scopeless. Step (v) involves premise replacement which transforms the inference $\varSigma ,\, p_2\, \vdash \, p_3$ to the inference $\varSigma ,\, p_1\, \vdash \, p_3$, given that $p_1\, \vdash \, p_2$, where $\varSigma$ represents a (possibly empty) set of statements and $p_1$ can be a conjunction of more than one statement. This transformation is legitimate because by replacing a premise $p_2$ in a valid inference with another premise that derives $p_2$, the inference remains valid.

We next consider Step (iii), which involves the derivation of immediate inferences. Under Method 1, this Step derives (27) from (26). The legitimacy of this Step can be proved by applying the semantic version of the Deduction Theorem in Propositional Logic, which states that

$$\begin{aligned} p_1,\, \varSigma \, \models \, p_2 \,\,\,\hbox {iff}\,\,\, \varSigma \models p_1 \rightarrow p_2 \end{aligned}$$

(38)

and the close relation between implications and universal statements, which can be summarized as follows:

$$\begin{aligned} \forall x[Xa \rightarrow Xb] \,\,\,\hbox {is true iff }A ab \hbox { is true} \end{aligned}$$

(39)

The above is in fact the truth condition for the universal quantifier $A$. Intuitively, the above states that if the implication “If $x$ is $a$, then $x$ is $b$” is true for all $x$, then the universal statement “Every $a$ is $b$” is also true, and vice versa.

Based on the above, we can formulate the following lemma.

Lemma 1

Let $a$, $b$ be unary predicates, $X$ be an arbitrary individual variable and $\varSigma$ be a set of statements. If $Xa,\, \varSigma \, \models \, Xb$, then we have $\varSigma \, \models \, Aab$.

Proof

Suppose $Xa,\, \varSigma \, \models \, Xb$. Then by (38), we have $\varSigma \, \models \, Xa \rightarrow Xb$. Since $X$ is an arbitrary variable, the implication $Xa \rightarrow Xb$ means that for any individual $\texttt {x}$ in a model, if $\texttt {x}$ belongs to $\texttt {a}$, then $\texttt {x}$ also belongs to $\texttt {b}$, which is what $\forall x[Xa \rightarrow Xb]$ means. Thus, by (39), we have in every model such that $\varSigma$ is true, $Aab$ is also true. This means that $\varSigma \, \models \, Aab$. $\square$

We now show that if the inference in (26) is valid, then the immediate inference in (27) is also valid. So suppose (26) is valid, which means that in every model, if $X(D_1cr)$ and $D_2ac$ (or $D_2ca$) are both true, then $X(D_3ar)$ is also true. But then the assumptions of Lemma 1 are satisfied (note that $X$ is arbitrary in (26)), and so we can invoke that lemma to conclude that in every model such that $D_2ac$ (or $D_2ca$) is true, $A(D_1cr)(D_3ar)$ is also true, i.e. (27) is valid.

Under Method 2, Step (iii) derives (34) from (33). The legitimacy of this Step can be proved by applying the “Exposition” rule in Medieval Logic (as studied in Parsons (2014)). In what follows, we will make use of the semantic version of this rule, which can be stated as follows: let $a$, $b$ be unary predicates, $X$ be an individual variable not used in the previous derivation and $\varSigma$ be a set of statements. Then

$$\begin{aligned} \varSigma ,\, Iab\, \models \, \varSigma \wedge Xa \wedge Xb \end{aligned}$$

(40)

The above rule is in fact a statement of the meaning of the existential quantifier $I$, because if in a model all members of $\varSigma$ and $Iab$, meaning “Some $a$ is $b$”, are true, then there exists an $X$, which may be different from any individual variable used in the previous derivation, such that all members of $\varSigma$ as well as $Xa$ and $Xb$ are true.

Based on the above rule, we can formulate the following lemma.

Lemma 2

Let $a$, $b$ be unary predicates, $X$ be an individual variable not used in the previous derivation, $p$ be a statement and $\varSigma$ be a set of statements. If $\varSigma ,\, Xa,\, Xb\, \models \, p$, then we have $\varSigma ,\, Iab\, \models \, p$.

Proof

By (40), we have $\varSigma ,\, Iab\, \models \, \varSigma \wedge Xa \wedge Xb$ for an $X$ not used in the previous derivation, which means that in every model where all members of $\varSigma$ and $Iab$ are true, all members of $\varSigma$ as well as $Xa$ and $Xb$ are true. Now suppose $\varSigma ,\, Xa,\, Xb\, \models \, p$, which means that in every model such that all members of $\varSigma$ as well as $Xa$ and $Xb$ are true, $p$ is also true. Combining the above, we then have in every model where all members of $\varSigma$ and $Iab$ are true, $p$ is also true. This means $\varSigma ,\, Iab\, \models \, p$. $\square$

We now show that if the inference in (33) is valid, then the immediate inference in (34) is also valid. So suppose (33) is valid, which means that in every model, if $X(D_1br)$ and $X(D_2ar)$ are both true, then $D_3ab$ is also true. But then the assumptions of Lemma 2 are satisfied (note that $X$ is not used in the previous derivation in (33)), and so we can invoke that lemma to conclude that in every model such that $I(D_1br)(D_2ar)$ is true, $D_3ab$ is also true, i.e. (34) is valid. Summarizing the above, we have proved that Methods 1 and 2 are sound.

To prove that Methods 1 and 2 are complete for RELSYLL, we have to show that every valid relational syllogism in RELSYLL is derivable by using one of these Methods. But it is clear that every valid relational syllogism in RELSYLL listed in Table 2 takes the form of either (30) (if it is based on a Figure-1 or Figure-3 simple syllogism) or (37) (if it is based on a Figure-2 simple syllogism), and so is derivable by using these Methods.

Specifically, valid relational syllogisms based on $D_1D_2D_3\hbox {-}1$ or $D_1D_2D_3\hbox {-}3$ simple syllogisms can be derived by using Method 1 and choosing $D_1D_2D_3\hbox {-}1$ or $D_1D_2D_3\hbox {-}3$ in Step (i). To derive relational syllogisms with the desired front part $AXA$ or $IXI$, one chooses $AAA\hbox {-}1$ or $AII\hbox {-}1$, respectively in Step (iv). On the other hand, valid relational syllogisms based on $D_1D_2D_3\hbox {-}2$ simple syllogisms can be derived by using Method 2 and choosing $D_1D_2D_3\hbox {-}2$ in Step (i). To derive relational syllogisms with the desired front part $AIX$ or $IAX$, one chooses $IAI\hbox {-}3$ or $AII\hbox {-}3$, respectively in Step (iv).

5 Extensions of the Derivation Methods

5.1 Use of More Valid Syllogisms

In the previous section, we have introduced two Derivation Methods which are sound and complete for the fragment RELSYLL. While the relational syllogisms in RELSYLL are restrictive in terms of their format, the general idea of the Derivation Methods is applicable to a much larger set of relational syllogisms than RELSYLL. In this section, we discuss some possible ways to extend the Derivation Methods.

One way is to extend the choice of syllogisms in Steps (i) and (iv) of the Methods to valid syllogisms other than those prescribed in Sect. 4.1. In this way, we can then derive more relational syllogisms, although these syllogisms may no longer conform to the format of RELSYLL prescribed in Sect. 2. Of course, the chosen syllogisms must tie in with the remaining Steps of the two Methods. To be more specific, the valid syllogisms chosen for Step (i) of Methods 1 and 2 must be such that there are two identical predicates in the second argument position of one premise and the conclusion and such that there are two identical predicates in the second argument position of the two premises, respectively; whereas the valid syllogisms chosen for Step (iv) of Methods 1 and 2 must be such that at least one premise contains the same quantifier as that in the conclusion of the immediate inference derived in Step (iii) and such that the conclusion contains the same quantifier as that in the premise of the immediate inference derived in Step (iii), respectively.

We also allow use of indirect reduction and/or quantifier transformations to transform the valid syllogisms chosen in Steps (i) and (iv) and the immediate inference obtained in Step (iii) so that these conform to the stipulations given above. Apart from these, the targets of substitutions in Steps (i) and (iv) as well as the target of premise replacement in Step (v) may also have to be adjusted to ensure that these Steps will yield the desired effects. Obviously, the aforesaid extensions and adjustments will not affect the soundness of the Methods, and we are able to derive valid relational syllogisms by using the Methods provided that the simple syllogisms that we choose in Steps (i) and (iv) are valid.

We now illustrate the use of the modified Methods by two examples. In the first example, we choose the ${\ddot{A}}OO\hbox {-}1$ syllogism proposed by Dekker (2015)¹⁴ in Step (i) and the classical $EAE\hbox {-}2$ syllogism in Step (iv) of Method 1. ${\ddot{A}}OO\hbox {-}1$ is a valid syllogism containing the non-classical quantifier ${\ddot{A}}$, meaning “only”, with the truth condition: ${\ddot{A}}ab$ is true iff $Aba$ is true for all $a, b$. This syllogism has the following form:

$$\begin{aligned} {\ddot{A}}cb,\, Oac\, \vdash \, Oab \end{aligned}$$

(41)

In Step (i), we substitute $b = Xr^{-1}$ into the above to obtain

$$\begin{aligned} {\ddot{A}}c(Xr^{-1}),\, Oac\, \vdash \, Oa(Xr^{-1}) \end{aligned}$$

(42)

In Step (ii), we interchange $X$ with the type $\langle 1\rangle$ quantifiers in the first premise and conclusion above:

$$\begin{aligned} X({\ddot{A}}cr),\, Oac\, \vdash \, X(Oar) \end{aligned}$$

(43)

In Step (iii), we derive the following immediate inference from (43):

$$\begin{aligned} Oac\, \vdash \, A({\ddot{A}}cr)(Oar) \end{aligned}$$

(44)

In Step (iv), we choose $EAE\hbox {-}2$ whose second premise contains the quantifier $A$:

$$\begin{aligned} Ede,\, Afe\, \vdash \, Efd \end{aligned}$$

(45)

To make the second premise below identical to the conclusion of (44), we substitute $e = Oar$ and $f = {\ddot{A}}cr$ into the above to obtain

$$\begin{aligned} Ed(Oar),\, A({\ddot{A}}cr)(Oar)\, \vdash \, E({\ddot{A}}cr)d \end{aligned}$$

(46)

Finally, in Step (v), we replace the second premise of (46) by the premise of (44) to obtain

$$\begin{aligned} Ed(Oar),\, Oac\, \vdash \, E({\ddot{A}}cr)d \end{aligned}$$

(47)

The above is a valid relational syllogism containing the non-classical quantifier ${\ddot{A}}$. Here is an exemplification of the above syllogism, with $a$, $c$, $d$, $r$ interpreted as “smoker”, “boy”, “girl”, “be hated by”, respectively:

No girl does not hate all the smokers. Not every smoker is a boy. Therefore, no one that only hates boys is a girl.

In the second example, we choose the classical $AEE\hbox {-}2$ syllogism in Step (i) of Method 2 and the numerical syllogism $2E3I1O\hbox {-}4$ in Step (iv). The classical $AEE\hbox {-}2$ syllogism has the following form:

$$\begin{aligned} Abc,\, Eac\, \vdash \, Eab \end{aligned}$$

(48)

In Step (i), we substitute $c = Xr^{-1}$ into the above to obtain

$$\begin{aligned} Ab(Xr^{-1}),\, Ea(Xr^{-1})\, \vdash \, Eab \end{aligned}$$

(49)

In Step (ii), we interchange $X$ with the type $\langle 1\rangle$ quantifiers in the two premises above:

$$\begin{aligned} X(Abr),\, X(Ear)\, \vdash \, Eab \end{aligned}$$

(50)

In Step (iii), we derive the following immediate inference from (50):

$$\begin{aligned} I(Abr)(Ear)\, \vdash \, Eab \end{aligned}$$

(51)

In Step (iv), we choose the numerical syllogism $2E3I1O\hbox {-}4$ with the form

$$\begin{aligned} 2Eed,\, 3Idf\, \vdash \, 1Ofe \end{aligned}$$

(52)

While this schema does not have the desired form for Step (iv) of Method 2, i.e. the conclusion of this schema does not contain the same quantifier as that in the premise of (51), we can either rewrite the quantifier in the premise of (51) or rewrite the quantifier in the conclusion of (52). Here we opt to rewrite (52) and obtain

$$\begin{aligned} 2Eed,\, 3Idf\, \vdash \, 1If\lnot e \end{aligned}$$

(53)

To make the conclusion below identical to the premise of (51) (recall that $1I = I$), we substitute $f = Abr$ and $e = \lnot Ear$ into the above to obtain

$$\begin{aligned} 2E(\lnot Ear)d,\, 3Id(Abr)\, \vdash \, 1I(Abr)(Ear) \end{aligned}$$

(54)

Finally, in Step (v), we replace the premise of (51) by the premises of (54) to obtain

$$\begin{aligned} 2E(\lnot Ear)d,\, 3Id(Abr)\, \vdash \, Eab \end{aligned}$$

(55)

The above is a valid relational syllogism that contains numerical quantifiers but does not belong to RELSYLL. Here is an exemplification of the above syllogism, with $a$, $b$, $d$, $r$ interpreted as “boy”, “smoker”, “girl”, “be hated by”, respectively¹⁵:

At most two who hate at least one boy is a girl. At least three girls hate all smokers. Therefore, no boy is a smoker.

5.2 Use of Existential Assumptions

In classical logic, there are some syllogisms whose validity depends on certain existential assumptions. For example, $AAI\hbox {-}1$ is valid under the assumption that $\texttt {a} \not = \emptyset$. Existential assumptions also enable us to extend the choice of valid syllogisms in Step (iv) of the two Methods. Under Method 1 (Method 2), the immediate inference derived in Step (iii) of the two Methods is such that its conclusion (premise) must contain a classical quantifier. This has restricted the subsequent choice of syllogism in Step (iv). By introducing existential assumptions, we can relax this restriction. In this paper, existential assumptions will be treated as special additional premises in syllogisms and placed on the far left of $\vdash$. But they do not have the same status as normal premises. When transforming a syllogism to its equivalent form, we do not consider negating the existential assumption (if any) of the given syllogism and interchanging it with the negated conclusion.

There are two types of existential assumptions that we can use. The first type consists of those asserting the existence of members of a unary predicate, like “There is at least one $a$”, which will be represented by $Iaa$. Such an assumption allows us to make the following inference (in what follows, $\ge _p$ and $<_p$ where $p$ is a fraction such that $0< p < 1$ are proportional quantifiers)¹⁶:

$$\begin{aligned} Iaa,\, Aab\, \vdash \, \ge _p\!\!ab \end{aligned}$$

(56)

or

$$\begin{aligned} Iaa,\, <_p\!\!ab\, \vdash \, Oab \end{aligned}$$

(57)

Note that the above two are equivalent inferences in the sense that if one is valid the other is also valid and vice versa. Thus, by introducing an existential assumption of the first type, we can derive an inference involving a proportional quantifier by using (56) under Method 1 or (57) under Method 2, and the valid syllogism chosen for Step (iv) can then be one involving a proportional quantifier.

For illustration, suppose we choose $EAE\hbox {-}2$ in Step (i) of Method 2. Following the initial steps of Method 2, we can derive the following immediate inference:

$$\begin{aligned} I(Ebr)(Aar)\, \vdash \, Eab \end{aligned}$$

(58)

which can be rewritten as

$$\begin{aligned} O(Ebr)(Oar)\, \vdash \, Eab \end{aligned}$$

(59)

But by (57), we have

$$\begin{aligned} I(Ebr)(Ebr),\, <_{\frac{1}{2}}\!\!(Ebr)(Oar)\, \vdash \, O(Ebr)(Oar) \end{aligned}$$

(60)

Given (60), we can derive the following by applying premise replacement to (59):

$$\begin{aligned} I(Ebr)(Ebr),\, <_{\frac{1}{2}}\!\!(Ebr)(Oar)\, \vdash \, Eab \end{aligned}$$

(61)

The above is our new output of Step (iii) (instead of (59)).

Then in Step (iv), we can choose a valid syllogism whose conclusion contains the quantifier $<_{\frac{1}{2}}$. Suppose we choose the following syllogism containing proportional quantifiers (the following is one of the “rules of inference” proposed by Johnson (1994):

$$\begin{aligned} Iee,\, >_{\frac{1}{2}}\!\!ed,\, Edf\, \vdash \, <_{\frac{1}{2}}\!\!ef \end{aligned}$$

(62)

Then by following Steps (iv) and (v) of Method 2, we can finally derive the following valid relational syllogism:

$$\begin{aligned} I(Ebr)(Ebr),\, >_{\frac{1}{2}}\!\!(Ebr)d,\, Ed(Oar)\, \vdash \, Eab \end{aligned}$$

(63)

Here is an exemplification of the above syllogism, with $a$, $b$, $d$, $r$ interpreted as “boy”, “smoker”, “girl”, “be liked by”, respectively:

There exists someone who likes no smokers. More than half of those who like no smokers are girls. No girl does not like every boy. Therefore, no boy is a smoker.

The second type of existential assumptions consists of those asserting the minimum number of members of a unary predicate, like “There are at least $n + 1$ $a$”, which will be represented by $(n + 1)Iaa$. Such an assumption allows us to make the following inference:

$$\begin{aligned} (n + 1)Iaa,\, Aab\, \vdash \, (n + 1)Iab \end{aligned}$$

(64)

or

$$\begin{aligned} (n + 1)Iaa,\, nEab\, \vdash \, Oab \end{aligned}$$

(65)

Again the above two are equivalent inferences. Thus, by introducing an existential assumption of the second type, we can derive an inference involving a numerical quantifier by using (64) under Method 1 or (65) under Method 2, and the valid syllogism chosen for Step (iv) can then be one involving a numerical quantifier.

For illustration, suppose we choose $AAA\hbox {-}1$ in Step (i) of Method 1. Following the initial steps of Method 1, we can derive the immediate inference

$$\begin{aligned} Aac\, \vdash \, A(Acr)(Aar) \end{aligned}$$

(66)

But by (64), we have

$$\begin{aligned} 3I(Acr)(Acr),\, A(Acr)(Aar)\, \vdash \, 3I(Acr)(Aar) \end{aligned}$$

(67)

Given (66) we can derive the following by applying premise replacement to (67):

$$\begin{aligned} 3I(Acr)(Acr),\, Aac\, \vdash \, 3I(Acr)(Aar) \end{aligned}$$

(68)

The above is our new output of Step (iii) (instead of (66)).

Then in Step (iv), we can choose a valid syllogism such that one of the premises contains the quantifier $3I$. Suppose we now choose the numerical syllogism $2E3I1O\hbox {-}4$ given in (52) above. Then by following Steps (iv) and (v) of Method 1, we can finally derive the following valid relational syllogism:

$$\begin{aligned} 3I(Acr)(Acr),\, 2Ee(Acr),\, Aac\, \vdash \, 1O(Aar)e \end{aligned}$$

(69)

Here is an exemplification of the above syllogism, with $a$, $c$, $e$, $r$ interpreted as “boy”, “smoker”, “girl”, “be hated by”, respectively:

There are at least three who hate all smokers. At most two girls hate all smokers. All boys are smokers. Therefore, at least one who hates all boys is not a girl¹⁷.

The use of existential assumptions as described above will not affect the soundness of the Methods. What it adds to the Methods is only that it enables us to derive a new inference in Step (iii) by applying (56) or (64) under Method 1, and (57) or (65) under Method 2. But (56) and (64) (as well as their equivalent forms (57) and (65)) are obviously valid inferences.

5.3 Relationship Between the Two Methods

In the previous two subsections, we have discussed modifications to the two Derivation Methods. While we have concluded that the modifications will not affect the soundness of the Methods, we have not discussed the completeness of the modified Methods for the larger set of valid relational syllogisms. In view of the great variety of possible relational syllogisms that may contain various types of quantifiers and predicates, it is not a trivial task to determine a suitable fragment of syllogisms for which the modified Methods are complete, and this task will be left for future studies.

However, the Methods possess a nice property which is summarized and proved in the following proposition.

Proposition 6

Let $\alpha$ be a relational syllogism that can be transformed to an equivalent relational syllogism $\beta$ by one application of indirect reduction plus quantifier transformations. If $\alpha$ can be derived by Method 1, then $\beta$ can be derived by either Method 2 or Method 1. If $\alpha$ can be derived by Method 2, then $\beta$ can be derived by Method 1.

Proof

• (a) Suppose $\alpha$ can be derived by Method 1. Then it is derived by the following steps. First we choose a valid simple syllogism where there are two identical predicates in the second argument position of one premise and the conclusion with the form

  $$\begin{aligned} D_1ab,\, D_2cd\, \vdash \, D_3eb \end{aligned}$$

  (70)

  from which we derive an immediate inference

  $$\begin{aligned} D_2cd\, \vdash \, A(D_1ar)(D_3er) \end{aligned}$$

  (71)

If we now introduce an existential assumption, then by (56) or (64) above, we have

$$\begin{aligned} \varSigma ,\, A(D_1ar)(D_3er)\, \vdash \, D_6(D_1ar)(D_3er) \end{aligned}$$

(72)

where $\varSigma$ represents the set of existential assumptions and $D_6$ is a proportional / numerical quantifier. By applying premise replacement to (72), we can then derive a new inference

$$\begin{aligned} \varSigma ,\, D_2cd\, \vdash \, D_6(D_1ar)(D_3er) \end{aligned}$$

(73)

Whether we introduce an existential assumption or not, the output of Step (iii) can be represented uniformly by (73), where $\varSigma = \emptyset$ and $D_6 = A$ if there is no existential assumption. We next choose another valid simple syllogism one of whose premises contains the quantifier $D_6$ with the form

$$\begin{aligned} D_6fg,\, D_4hi\, \vdash \, D_5jk \end{aligned}$$

(74)

from which we derive

$$\begin{aligned} \alpha : \varSigma ,\, D_2cd,\, D_4h'i'\, \vdash \, D_5j'k' \end{aligned}$$

(75)

by substituting

$$\begin{aligned} f = D_1ar,\,\,\, g = D_3er \end{aligned}$$

(76)

into (74) and then applying premise replacement, where $h'$, $i'$, $j'$, $k'$ are the effects of the substitution (76) on the predicates $h$, $i$, $j$, $k$.

Now there are two possible $\beta$s that can be transformed from $\alpha$ by one application of indirect reduction plus quantifier transformations:

$$\begin{aligned}&\beta _1: \varSigma ,\, \lnot D_5j'k',\, D_4h'i'\, \vdash \, \lnot D_2cd \end{aligned}$$

(77)

$$\begin{aligned}&\beta _2: \varSigma ,\, D_2cd,\, \lnot D_5j'k'\, \vdash \, \lnot D_4h'i' \end{aligned}$$

(78)

We now show that $\beta _1$ can be derived by Method 2 whereas $\beta _2$ can be derived by Method 1. Consider $\beta _1$ first. By one application of indirect reduction plus quantifier transformations to (70), we obtain

$$\begin{aligned} D_1ab,\, \lnot D_3eb\, \vdash \, \lnot D_2cd \end{aligned}$$

(79)

which is a valid syllogism and has the desired form for Step (i) of Method 2 (there are two identical predicates, namely $b$, in the second argument position of the two premises). By following the initial Steps of Method 2, from the above we can derive the following immediate inference:

$$\begin{aligned} I(D_1ar)(\lnot D_3er)\, \vdash \, \lnot D_2cd \end{aligned}$$

(80)

which can be rewritten as the following:

$$\begin{aligned} O(D_1ar)(D_3er)\, \vdash \, \lnot D_2cd \end{aligned}$$

(81)

If we now introduce the existential assumption in $\varSigma$ above, then we will obtain the following which is equivalent to (72) above:

$$\begin{aligned} \varSigma ,\, \lnot D_6(D_1ar)(D_3er)\, \vdash \, O(D_1ar)(D_3er) \end{aligned}$$

(82)

By applying premise replacement to (81), we can then derive a new inference

$$\begin{aligned} \varSigma ,\, \lnot D_6(D_1ar)(D_3er)\, \vdash \, \lnot D_2cd \end{aligned}$$

(83)

Again, the output of Step (iii) can be represented uniformly by (83), where $\varSigma = \emptyset$ and $\lnot D_6 = O$ if there is no existential assumption. Then in Step (iv), we choose

$$\begin{aligned} \lnot D_5jk,\, D_4hi\, \vdash \, \lnot D_6fg \end{aligned}$$

(84)

which is a valid syllogism equivalent to (74) and has the desired form for Step (iv) of Method 2 (the conclusion contains the quantifier $\lnot D_6$). Next, by using the same substitution given in (76) above, we can derive

$$\begin{aligned} \lnot D_5j'k',\, D_4h'i'\, \vdash \, \lnot D_6(D_1ar)(D_3er) \end{aligned}$$

(85)

Finally, by applying premise replacement to (83), we obtain $\beta _1$ given in (77).

To derive $\beta _2$, we just follow the same steps as deriving $\alpha$ above until we obtain (73) at the end of Step (iii). Then in Step (iv), we choose

$$\begin{aligned} D_6fg,\, \lnot D_5jk\, \vdash \, \lnot D_4hi \end{aligned}$$

(86)

which is also a valid syllogism equivalent to (74). It can be easily seen that by using the same substitution given in (76) above and then completing Step (v), we can finally derive $\beta _2$ given in (78). Thus, we have shown that if $\alpha$ can be derived by Method 1, then $\beta$ can be derived by either Method 2 or Method 1.

• (b) Suppose $\alpha$ can be derived by Method 2. Then it is derived by the following steps. First we choose a valid simple syllogism where there are two identical predicates in the second argument position of the two premises with the form

  $$\begin{aligned} D_1ab,\, D_2cb\, \vdash \, D_3ed \end{aligned}$$

  (87)

from which we derive an immediate inference

$$\begin{aligned} I(D_1ar)(D_2cr)\, \vdash \, D_3ed \end{aligned}$$

(88)

which can be rewritten as

$$\begin{aligned} O(D_1ar)(\lnot D_2cr)\, \vdash \, D_3ed \end{aligned}$$

(89)

If we now introduce an existential assumption, then by (57) or (65) above, we have

$$\begin{aligned} \varSigma ,\, D_6(D_1ar)(\lnot D_2cr)\, \vdash \, O(D_1ar)(\lnot D_2cr) \end{aligned}$$

(90)

where $\varSigma$ represents the set of existential assumption and $D_6$ is a proportional / numerical quantifier. By applying premise replacement to (89), we can then derive a new inference

$$\begin{aligned} \varSigma ,\, D_6(D_1ar)(\lnot D_2cr)\, \vdash \, D_3ed \end{aligned}$$

(91)

Whether we introduce an existential assumption or not, the output of Step (iii) can be represented uniformly by (91), where $\varSigma = \emptyset$ and $D_6 = O$ if there is no existential assumption. We next choose another valid simple syllogism whose conclusion contains the quantifier $D_6$ with the form

$$\begin{aligned} D_4fg,\, D_5hi\, \vdash \, D_6jk \end{aligned}$$

(92)

from which we derive

$$\begin{aligned} \alpha : \varSigma ,\, D_4f'g',\, D_5h'i'\, \vdash \, D_3ed \end{aligned}$$

(93)

by substituting

$$\begin{aligned} j = D_1ar,\,\,\, k = \lnot D_2cr \end{aligned}$$

(94)

into (92) and then applying premise replacement, where $f'$, $g'$, $h'$, $i'$ are the effects of the substitution (94) on the predicates $f$, $g$, $h$, $i$.

Now there are two possible $\beta$s that can be transformed from $\alpha$ by one application of indirect reduction plus quantifier transformations:

$$\begin{aligned}&\beta _1: \varSigma ,\, \lnot D_3ed,\, D_5h'i'\, \vdash \, \lnot D_4f'g' \end{aligned}$$

(95)

$$\begin{aligned}&\beta _2: \varSigma ,\, D_4f'g',\, \lnot D_3ed\, \vdash \, \lnot D_5h'i' \end{aligned}$$

(96)

We now show that both $\beta _1$ and $\beta _2$ can be derived by Method 1. Consider $\beta _1$ first. By one application of indirect reduction plus quantifier transformations to (87), we obtain

$$\begin{aligned} D_1ab,\, \lnot D_3ed\, \vdash \, \lnot D_2cb \end{aligned}$$

(97)

which is a valid syllogism and has the desired form for Step (i) of Method 1 (there are two identical predicates, namely $b$, in the second argument position of one premise and the conclusion). By following the initial Steps of Method 1, from the above we can derive the following immediate inference:

$$\begin{aligned} \lnot D_3ed\, \vdash \, A(D_1ar)(\lnot D_2cr) \end{aligned}$$

(98)

If we now introduce the existential assumption in $\varSigma$ above, then we will obtain the following which is equivalent to (90) above:

$$\begin{aligned} \varSigma ,\, A(D_1ar)(\lnot D_2cr)\, \vdash \, \lnot D_6(D_1ar)(\lnot D_2cr) \end{aligned}$$

(99)

By applying premise replacement to (99), we can then derive a new inference

$$\begin{aligned} \varSigma ,\, \lnot D_3ed\, \vdash \, \lnot D_6(D_1ar)(\lnot D_2cr) \end{aligned}$$

(100)

Again, the output of Step (iii) can be represented uniformly by (100), where $\varSigma = \emptyset$ and $\lnot D_6 = A$ if there is no existential assumption. Then in Step (iv), we choose

$$\begin{aligned} \lnot D_6jk,\, D_5hi\, \vdash \, \lnot D_4fg \end{aligned}$$

(101)

which is a valid syllogism equivalent to (92) and has the desired form for Step (iv) of Method 1 (at least one premise contains the quantifier $\lnot D_6$). Next, by using the same substitution given in (94) above, we can derive

$$\begin{aligned} \lnot D_6(D_1ar)(\lnot D_2cr),\, D_5h'i'\, \vdash \, \lnot D_4f'g' \end{aligned}$$

(102)

Finally, by applying premise replacement to (102), we obtain $\beta _1$ given in (95).

To derive $\beta _2$, we just follow the same steps as deriving $\beta _1$ above until we obtain (100) at the end of Step (iii). Then in Step (iv), we choose

$$\begin{aligned} D_4fg,\, \lnot D_6jk\, \vdash \, \lnot D_5hi \end{aligned}$$

(103)

which is also a valid syllogism equivalent to (92). It can be easily seen that by using the same substitution given in (94) above and then completing Step (v), we can finally derive $\beta _2$ given in (96). Thus, we have shown that if $\alpha$ can be derived by applying Method 2, then $\beta$ can be derived by applying Method 1. $\square$

From the above proposition, we know that if a relational syllogism is (un)provable by the two Derivation Methods, then all relational syllogisms that are equivalent to it are also (un)provable by the Methods. This can thus save us some efforts in determining the provability of relational syllogisms by the Methods.

6 Conclusion

In this paper, we have presented a fragment of relational syllogisms called RELSYLL consisting of quantified statements with the numerical quantifiers studied by Murphree (1991, 1993, 1997, 1998). Instead of deriving relational syllogisms directly from axioms and/or inference rules, we have introduced two Derivation Methods to derive the valid syllogisms. We have also shown that the two Methods are sound and complete for RELSYLL.

While RELSYLL and the Derivation Methods are quite restrictive in terms of the format of the derivable relational syllogisms and the types of valid simple syllogisms that can be used in the Methods, we have discussed some possible ways to extend the Derivation Methods, including the use of more valid syllogisms and existential assumptions. We have also shown how to use the extended Methods to derive valid relational syllogisms containing “only” and proportional quantifiers.

In fact, the extended Methods can be applied to derive an even larger set of relational syllogisms containing other non-classical quantifiers. One such type of quantifiers consists of the vague quantifiers studied by, say Khayata et al. (2002) and Peterson (2000), among many others. By using valid simple syllogisms with vague quantifiers identified by these scholars, we can then derive valid relational syllogisms containing these quantifiers. For example, the following is the $APT\hbox {-}1$ syllogism proposed by Peterson (2000), where $P$ and $T$ are vague quantifiers meaning “almost all” and “most”, respectively (note that the validity of the following syllogism relies on existential import):

$$\begin{aligned} Idd,\, Afe,\, Pdf\, \vdash \, Tde \end{aligned}$$

(104)

One can check that by using the classical syllogism $AAA\hbox {-}1$ in Step (i) of Method 1 and the above syllogism in Step (iv), one can derive the following relational syllogism with vague quantifiers:

$$\begin{aligned} Idd,\, Aac,\, Pd(Acr)\, \vdash \, Td(Aar) \end{aligned}$$

(105)

Thus, the extended Methods have a wide scope of applications.

While we have shown that the extended Methods remain sound, we have not discussed the completeness of the extended Methods for a larger set of valid relational syllogisms. But we have proved a special property of the two Methods which may save the efforts in determining the provability of relational syllogisms by the Methods. Therefore, the extended Methods enable us to discover an extended set of valid relational syllogisms, whereas the determination of the completeness of the extended Methods for this extended set, or a subset of it, will have to be left for future studies.

Before closing this paper, we would like to point to a possible direction for future studies which concern the predicates in the relational syllogisms. The binary predicates discussed in this paper are general binary predicates without additional properties. However, in natural language, some binary predicates have some special properties. For example, many comparative adjectives as well as some locative prepositions (such as “in front of”) and relational nouns (such as “ancestor of”) are transitive in the sense that if $(\texttt {x}, \texttt {y}) \in \texttt {r}$ and $(\texttt {y}, \texttt {z}) \in \texttt {r}$, then $(\texttt {x}, \texttt {z}) \in \texttt {r}$. Owing to these properties, quantified statements with these parts of speech satisfy certain syllogisms that quantified statements with ordinary binary predicates do not satisfy. The following is an example of a valid syllogism with comparative adjectives:

Every basketball player is taller than most jockeys. A swimmer is taller than some basketball player. Therefore, a swimmer is taller than most jockeys.

Note that the above syllogism remains valid if “is taller than” is replaced by “is in front of”, but becomes invalid if “is taller than” is replaced by a general binary predicate such as “likes”, and the difference is mainly due to the fact that both “is taller than” and “is in front of” are transitive while “likes” is not. Thus, a study on these special properties will enable us to identify more valid relational syllogisms. In fact, there are already some studies on relational syllogisms involving comparative adjectives, such as Keene (1969) and Moss (2011). But the syllogisms covered in these studies are mainly restricted to those containing classical quantifiers. Thus, a study on how to extend the Derivation Methods introduced in this paper to relational syllogisms containing binary predicates with special properties will surely yield fruitful results.

Appendix: Counterexamples for Invalid Numerical Syllogisms

This Appendix provides a list of counterexamples for invalid simple syllogisms with numerical quantifiers which may be used for constructing counterexamples for a certain type of invalid relational syllogisms in RELSYLL as described in the proof for Proposition 4. Since RELSYLL only includes relational syllogisms that are based on simple syllogisms of Figures 1 to 3, the following list only includes invalid Figure-1 syllogisms for conciseness. Based on the counterexample for an invalid Figure-1 syllogism $\alpha$ listed below, one can obtain a counterexample for the invalid Figure-2 syllogism that is equivalent to $\alpha$ by interchanging $\texttt {b}$ and $\texttt {c}$, and a counterexample for the invalid Figure-3 syllogism that is equivalent to $\alpha$ by interchanging $\texttt {a}$ and $\texttt {c}$. Also for conciseness, syllogisms that can be invalidated by the same counterexample are placed in the same cell below.

Note that each counterexample listed below is in fact a counterexample for an infinite number of invalid numerical syllogisms, not only because the figures $n, m, k$ below can be substituted by an infinite number of appropriate non-negative integers, but also because from each invalid numerical syllogism one can deduce more invalid syllogisms with stronger conclusions. For example, the first counterexample listed below is not only a counterexample for $nAmA(n + m - 1)A\hbox {-}1$, but also one for $nAmA(n + m - 2)A\hbox {-}1$, because if $(n + m - 1)Aab$ is a false conclusion, then $(n + m - 2)Aab$ must also be a false conclusion.

Type 1: Numerical syllogisms based on valid classical syllogisms but associated with the wrong numerals

Type 2: Numerical syllogisms based on invalid classical syllogisms