A CORRECTNESS PROOF FOR AL-BARAKĀT’S LOGICAL DIAGRAMS

Abstract

In Baghdad in the mid twelfth century Abū al-Barakāt proposes a radical new procedure for finding the conclusions of premise-pairs in syllogistic logic, and for identifying those premise-pairs that have no conclusions. The procedure makes no use of features of the standard Aristotelian apparatus, such as conversions or syllogistic figures. In place of these al-Barakāt writes out pages of diagrams consisting of labelled horizontal lines. He gives no instructions and no proof that the procedure will yield correct results. So the reader has to work out what his procedure is and whether it is correct. The procedure turns out to be insightful and entirely correct, but this paper may be the first study to give a full description of the procedure and a rigorous proof of its correctness.

1 Al-Barakāt and Aristotle’s logic

In the middle of the twelfth century a Jewish Baghdad scholar named Abū al-Barakāt bin Malkā al-Baghdādī, al-Barakāt for short, published a startling new method in logic, which had the potential to speed up the historical development of logic by several hundred years. Unfortunately the potential was never realised. We know of nobody apart from al-Barakāt himself, from his time up to this last decade, who had the faintest idea what he was talking about. (The brief account of al-Barakāt’s diagrams in al-Ṭūsī’s Persian textbook Asās al-iqtibās [3] confirms this, as I hope to explain elsewhere.) By the time that any logician recognised what al-Barakāt was doing, most of the ideas that he used had been reinvented and become standard for a hundred or so years—the chief of them being Tarski’s ‘model-theoretic consequence’ [14].

To explain al-Barakāt’s method, we need a brief sketch of Aristotle’s logic of categorical syllogisms, as explained in Aristotle’s Prior Analytics i.4–6. This book was written in Greek in the fourth century BC, and translated into Arabic a few hundred years before the time of al-Barakāt. Aristotle introduced four sentence forms, that we can translate as

(1)

Sentences of these four forms are called categorical sentences. The first two sentences are described as universal, and the last two as existential (or by some authors particular). The formulas on the right are first-order sentences whose truth-conditions are what al-Barakāt in his method took to be the truth conditions of the four sentence forms on the left. The letters A and B can be replaced by any two distinct letters. We call A, B and any other letters put in place of them the term letters, or the terms for short.

Aristotle called attention to (categorical) premise-pairs. We follow what al-Barakāt supposed Aristotle had said, disregarding the question whether he was right to suppose this. Al-Barakāt took a premise-pair to be an ordered pair of categorical sentences (the premises) with exactly one term in common. This common term was called the middle term of the premise-pair, and al-Barakāt assumed that it was not both the first term in the first premise and the second term in the second. The minor term of the premise-pair was the letter appearing only in the first premise, and its major term was the letter appearing only in the second premise. In expounding his new method, al-Barakāt assumed that the minor term is A, the middle term is B and the major term is C. With these conventions there are exactly 48 premise-pairs. (Aristotle had slightly different definitions, but in practice he finished up with the same 48 premise-pairs as al-Barakāt.)

Aristotle asked what other sentences follow logically from a premise-pair. In his answers he normally limited himself to categorical sentences whose first term is the minor term of the premise-pair and whose second term is the major term. There are four such categorical sentences, and we will call them the candidate conclusions, or for short the candidates. (With al-Barakāt’s conventions the candidate conclusions are the four categorical sentences with first term A and second term C.)

Aristotle divided premise-pairs into two groups. The first group are those which logically entail at least one of their candidate conclusions. Aristotle and al-Barakāt described the logically strongest candidate that is entailed by the two pemises the conclusion of the premise-pair. The second group are those which don’t logically entail any of their four candidate conclusions. (They might entail other categorical sentences, but this was ignored.) By the time of al-Barakāt the first group of premise-pairs had come to be described as productive (Arabic muntij) and the second group as sterile ( ${}^c\!$ aqīm).

An appropriate modern language for studying al-Barakāt’s methods is the first-order language $L(\Sigma )$ built on the signature $\Sigma $ , where $\Sigma $ consists of 1-ary relation symbols. Structures for this language are called $\Sigma $ -structures. We say that a $\Sigma $ -structure M is without empty terms if for every relation symbol R in $\Sigma $ , the interpretation $R^M$ of R in M is a nonempty set.

Al-Barakāt himself didn’t have the modern notion of a $\Sigma $ -structure. But when $\Sigma $ is the set $\{A,B,C\}$ , al-Barakāt’s counterpart to the notion of a $\Sigma $ -structure was that of an interpretation of the three letters. He gave an interpretation I by supplying, for each letter R in $\Sigma $ , a singular noun or noun phrase $I(R)$ . We write $R^I$ for the set of all objects in the real world that satisfy the description $I(R)$ . We can convert I into a $\Sigma $ -structure M by taking $R^M$ , for each letter R in $\Sigma $ , to be $R^I$ . Then we can take the domain of M to be the set $A^M \cup B^M \cup C^M$ . (In fact it will always be irrelevant what elements M may have that are outside the set $A^M \cup B^M \cup C^M$ .) In the other direction, translating from $\Sigma $ -structures M to interpretations, we have to find for each letter R a singular noun phrase that captures all and only the elements of $R^M$ . (This correspondence between structures and interpretations also applies to the interpretations that Aristotle used to prove sterility.) In general al-Barakāt allowed $\Sigma $ -structures to have empty terms, but in his new method he required them to be without empty terms; we will discuss this point below.

1.1 Al-Barakāt’s new method

In his book [1], pp. 126–148, al-Barakāt advertised a method for showing whether a premise-pair is productive or sterile, and for finding its conclusion if it is productive. Al-Barakāt runs through the 48 premise-pairs with minor term A and major term C. For each sterile premise-pair he normally writes down diagrams giving three models $M_1, M_2, M_3$ of the premise-pair, without empty terms, such that

$$ \begin{align*} \begin{array}{l} M_1 \models \forall x (Ax \to Cx), \\ M_2 \models \forall x (Ax \to \neg Cx), \\ M_3 \models \exists x (Ax \land Cx) \land \exists x (Ax \land \neg Cx). \end{array} \end{align*} $$

This is equivalent to what Aristotle does, except that Aristotle omits the interpretation $M_3$ . But if the premise-pair is productive, al-Barakāt does something very different from Aristotle. He gives several models of the premise-pair (the number varies, but again al-Barakāt gives only models without empty terms), and verifies that there is a candidate conclusion $\theta $ such that each of these models is also a model of $\theta $ . If there is such a $\theta $ , he always chooses as conclusion the logically strongest one. (See the examples in Section 3.)

The effect is that in both cases, the sterile and the productive, al-Barakāt starts by looking at the range of models that the premise-pair can have. If he finds models like $M_1, M_2, M_3$ above then he reckons he has shown that the premise-pair is sterile. If he can’t find three such models, then he looks instead for a candidate conclusion as above, and fortunately he always finds one, proving productivity.

We can sum up al-Barakāt’s method as follows (in my words, not those of al-Barakāt).

Procedure One. Let the premise-pair be $(\phi ,\psi )$ , with minor and major terms A and C respectively. Examine in turn all the models of $\{\phi ,\psi \}$ without empty terms. If there is a candidate conclusion $\theta $ such that each of these models is also a model of $\theta $ , then the logically strongest such sentence $\theta $ is the conclusion of $(\phi ,\psi )$ . As you run through the models of the premise-pair without empty terms, look out for three models $M_1, M_2$ and $M_3$ of $\{\phi ,\psi \}$ , such that

$$ \begin{align*} \begin{array}{l} M_1 \models \forall x (Ax \to Cx), \\ M_2 \models \forall x (Ax \to \neg Cx), \\ M_3 \models \exists x (Ax \land Cx) \land \exists x (Ax \land \neg Cx). \end{array} \end{align*} $$

If you find three such models, the premise-pair $\{\phi ,\psi \}$ is sterile.

This procedure raises several questions. The most obvious is that every consistent first-order theory has infinitely many models, so how does al-Barakāt think there is any hope of examining them all in turn? We will deal with this question in the next two subsections. Another obvious question is what connection al-Barakāt is invoking between sterility and finding the three models $M_1, M_2, M_3$ . We will answer this question in Theorem 2.9 A third question is whether al-Barakāt is entitled to use only models without empty terms. We will deal with this question in Theorem 2.1

1.2 First refinement: Barakāt classes

In fact what Barakāt does is two refinements distant from Procedure One, although it follows Procedure One in general intention. The first refinement is to replace structures by equivalence classes of structures; we will see in the second refinement how al-Barakāt identifies these equivalence classes.

Let us assume that $\Sigma $ is the set $\{A,B,C\}$ . By an interior type of $\Sigma $ we mean a formula of $L(\Sigma )$ of the form

(2) $$ \begin{align} A^{f(A)}x \land B^{f(B)}x \land C^{f(C)}x, \end{align} $$

where $A^1$ means A, $A^0$ means $\neg A$ and similarly with the other letters, and f is a function, $f : \Sigma \to 2$ , which takes the value 1 at least once. We note for future reference that this interior type is uniquely determined by the nonempty subset $\{R : f(R) = 1\}$ of $\Sigma $ . We write $\mathcal {F}$ for the set of functions $f : \Sigma \to 2$ that take the value 1 at least once.

We write $tp_f(x)$ for the interior type defined using the function $f \in \mathcal {F}$ as in (2). If M is a $\Sigma $ -structure, we define $tp_f(M)$ to be the set of elements of M that satisfy $tp_f(x)$ . We say that the $\Sigma $ -structures M and N are Barakāt-equivalent if

(3) $$ \begin{align} \text{ for every } f \in \mathcal{F}, \ \ tp_f(M) = \emptyset \text{ if and only if } tp_f(N) = \emptyset. \end{align} $$

A Barakāt class is an equivalence class of the relation of Barakāt-equivalence on the class of $\Sigma $ -structures.

We will prove in Theorem 2.3 that if two $\Sigma $ -structures are Barakāt-equivalent, then they are models of exactly the same categorical sentences. So we can speak of Barakāt classes being models of categorical sentences.

Procedure Two. This is the same as Procedure One, except that instead of examining in turn all $\Sigma $ -structures without empty terms that are models of the premises, we examine in turn all those Barakāt classes of structures without empty terms that are models of the premises.

This is certainly better than Procedure One, because the number of Barakāt classes of structures without empty terms is a relatively small finite number. In fact Theorem 2.4 will prove that it is exactly 109 (the third ‘Gergonne number’ as defined before Theorem 2.4). Procedure Two can be turned straightforwardly into a computer program. In Chapter 4 of [11] there is a report generated by a run of such a program in C++. The report lists all the productive categorical premise-pairs and their conclusions, all the sterile premise-pairs, and other information about numbers of models. The program takes only a few seconds to run. It is efficient, and following al-Barakāt it makes no use at all of much of the apparatus of Aristotle’s logic (affirmative/negative, conversions, ectheses, figures).

The program uses a way of representing Barakāt classes. Al-Barakāt had his own idea of how to represent them: he used Barakāt diagrams, which consist of labelled horizontal lines. These diagrams are the first thing that strikes the eye as one looks at al-Barakāt’s text. Reducing Procedure Two to one that works with Barakāt diagrams is the second refinement of Procedure One.

1.3 Second refinement: Barakāt diagrams

We first explain Barakāt diagrams for two letters. Suppose the letters are A and B. Suppose also that we have an interpretation I of these letters, such that the sets $A^I$ and $B^I$ are not empty. These sets $A^I$ and $B^I$ can be related in any of five ways. We show how al-Barakāt represents these relationships with diagrams consisting of labelled horizontal lines. (The manuscript Esad Efendi 1931 of al-Barakāt’s book, on pages 44B–45A, gives diagrams of the five cases.)

First case. $A^I = B^I$ .

Second case. $A^I \subset B^I$ .

Third case. $B^I \subset A^I$ . This is as the second case but with A and B the other way round.

Fourth case. $A^I \cap B^I = \emptyset $ .

Fifth case. $A^I$ overlaps $B^I$ , i.e., none of the first four cases applies:

Some of these cases allow more than one picture, but the pictures for one case count as equivalent. Also al-Barakāt allows them to be written with B on the upper line and A on the lower.

In the fourth case al-Barakāt avoids writing

probably because it leaves open the possibility that the righthand endpoint of the B line overlaps the lefthand endpoint of the A line. If he had allowed this notation for the fourth case, and adopted a convention to avoid the overlap reading, it would be tempting to say that he anticipated the well-known result of [2], that there are exactly thirteen possible relationships between two bounded nonempty left-closed right-open intervals on a line. But it would be misleading, because al-Barakāt never makes any use of the linear ordering of his horizontal lines. (I thank Valentin Goranko for raising this point.)

We turn to Barakāt diagrams for three letters, taking $\Sigma $ to be $\{A,B,C\}$ . To diagram a $\Sigma $ -structure M we draw three horizontal lines, for A, B and C respectively, so that the layout of the lines indicates whether $A^M \cap B^M \cap C^M$ is nonempty, and whether $A^M \setminus (B^M \cup C^M)$ is nonempty, and so on.

For example al-Barakāt gives the diagram

(4)

with suggested nouns that yield the required structure: every human is an animal but not every animal is a human, and no animal is a stone. A three-line diagram of this kind includes a two-line diagram for each pair of letters; for example (4) restricted to A and C indicates that A and C are disjoint. These two-letter diagrams suffice to determine which categorical sentences are true in the structure represented by the diagram.

If we use the noun labels to define an $\{A,B,C\}$ -structure M, then the diagram above tells us which of the sets $tp_f(M)$ introduced in Section 1.2 are nonempty. Divide the diagram into segments marked by the ends of the three lines:

(5)

Each nonempty segment indicates that a certain $tp_f(M)$ is nonempty. The leftmost is for the function $f_1$ with $\{R :f_1(R) = 1\} = \{B\}$ . Then $\{R : f_2(R) = 1\} = \{A,B\}$ , and $tp_{f_3}$ repeats $tp_{f_1}$ . Finally $\{R : f_4{R} = 1\} = \{C\}$ . So two $\{A,B,C\}$ -structures with the same diagram are Barakāt-equivalent. This is how al-Barakāt represents Barakāt classes. The Barakāt class of a structure determines what categorical sentences are true in the structure, so that we can speak of diagrams satisfying or being models of categorical sentences.

The noun labels deserve a comment. In the cases where he is proving sterility, al-Barakāt is following Aristotle’s custom of giving interpretations. The interpretations serve to prove that structures in the required Barakāt class exist—though today we would reckon that it’s a trivial exercise to find for each Barakāt diagram a $\Sigma $ -structure to match it. But when al-Barakāt is proving productivity or finding conclusions, the interpretations and the labels that name them serve no logical purpose at all. There is a very similar use of logically irrelevant nouns in the sixth century Syriac introductory logic textbook of Paul the Persian. In [10] it is suggested that Paul included these nouns for educational rather than logical reasons. Possibly the same holds for al-Barakāt; but one also wonders if he found this usage in an earlier logical text and it played some role in bringing him to his method.

Unfortunately not every Barakāt class of $\Sigma $ -structures can be diagrammed in this way. We say that a $\Sigma $ -structure is diagrammable if there is a Barakāt diagram that correctly reports its Barakāt class. We will see in Theorem 2.5 that a $\Sigma $ -structure M is undiagrammable if and only if it meets any one of three conditions. The first is that M has one or more empty terms; Barakāt diagrams have no way of recording an empty set. The second and third conditions are that M is a model of the two categorical theories that we write at (10) and (11).

Procedure Three. This is the same as Procedure Two, except that instead of inspecting Barakāt classes that are models of the premises, we inspect Barakāt diagrams that are models of the premises.

The move to Procedure Three makes the entire procedure straightforward to carry out on paper, and I think al-Barakāt is right when he claims that it is intuitive—at least in its proofs of productivity. But we will need to show that Procedure Three still gives correct results in spite of being limited to diagrammable structures.

2 Mathematical theory

Al-Barakāt makes no attempt at all to prove that his method gives correct results, nor does he publish any of the calculations that would be needed to prove this. We are completely in the dark about how much of the background theory he really understood. For example did he know which structures are not diagrammable?

Size matters. Al-Barakāt’s method stands at an intermediate level of complexity, simple enough for anyone to check through the details of any number of individual cases (as al-Barakāt does in plenty), but too complex to be guaranteed correct without a mathematical proof. The Gergonne number $\gamma (3) = 109$ that we calculate in Theorem 2.4 is a witness to this intermediate level. If al-Barakāt had tried to extend his method to logics at the next level of complexity (such as Ibn Sīnā’s temporal $(dt)$ fragment, cf. [11]), he would have hit $\gamma (4) = 32,297$ and been completely overwhelmed.

For the same reason al-Barakāt’s approach is feasible only for syllogisms with two premises. Applying it to compound syllogisms with three premises would be another way of hitting $\gamma (4)$ . For compound syllogisms, proof procedures like that of [12] have the advantage over al-Barakāt’s method. (I thank a referee for raising this question.)

2.1 Empty terms

Was al-Barakāt justified in restricting his new method to structures or interpretations that have no empty terms? In this form the question may be unanswerable, because it depends on various prior questions about what he was assuming and what he was trying to do.

But we can say something about the context in which he made this choice. In the previous century Ibn Sīnā (c. 976–1037) had allowed empty terms, but with a different reading of the categorical sentences from that in (1). Instead Ibn Sīnā gave these sentences truth conditions corresponding to the following first-order sentences:

(6)

(See [8] and [4] pp. 106ff.) The effect of this reading is that if the term A is interpreted so as to be empty, then Ibn Sīnā counts ‘Every A is a B’ and ‘Some A is a B’ as both false, and ‘No A is a B’ and ‘Not every A is a B’ as both true. When all terms are interpreted as nonempty then the readings (1) and (6) make the same assignments of truth value. In the tenth century al-Fārābī (c. 870–950) in some of his more mature work also allowed empty terms and adopted readings equivalent to (6) (see [5] pp. 34f).

From passages elsewhere in [1] we know that al-Barakāt started out from a position where terms can be interpreted as empty and the readings (6) apply. There is one obvious reason for him to turn his back on empty terms when he uses his method: his diagrams have no way to represent empty sets. But then he can reasonably be asked whether he is changing the inferences of syllogistic logic by renouncing empty terms. With the help of first-order logic we can give a partially reassuring answer to this question.

Theorem 2.1. Let $\Sigma $ be a signature consisting of 1-ary relation symbols, and let categorical sentences be read as first-order according to the readings (6). If M is a $\Sigma $ -structure then there is a $\Sigma $ -structure $M^+$ that is without empty terms and is a model of exactly the same categorical sentences as M.

Proof. We form $M^+$ by adding to M the following new elements. Whenever R is a letter with $R^M = \emptyset $ , we add a new element $a_R$ , putting it in $R^{M^+}$ but not in $S^{M^+}$ for any other letter S. It is left to the reader to check that this works, bearing in mind that the two term letters in a categorical sentence must always be distinct letters.□

Corollary 2.2. Let categorical sentences be read as first-order according to the readings (6). Then the following are equivalent, for any set T of categorical sentences and any categorical sentence $\theta $ . (Here $\vdash $ is first-order consequence.)

1. (a) $T \vdash \theta $ .

2. (b) If M is any structure without empty terms that is a model of T, then M is also a model of $\theta $ .

Proof. The implication (a) $\Rightarrow $ (b) is immediate. In the other direction, suppose $\theta '$ is a categorical sentence logically equivalent to $\neg \theta $ . (There always is such a $\theta '$ , as we can check from (6).) If (a) fails to hold then there is a model M of $T \cup \{\theta '\}$ . Hence by the theorem there is a structure $M^+$ that is without empty terms and is also a model of $T \cup \{\theta '\}$ , and so (b) fails.□

Note that Theorem 2.1 and its Corollary hold only under the readings (6). Under these readings ‘Every A is a B’ and ‘No A is a B’ together form a logical inconsistency, but under the readings (1) they can both be true in the same $\Sigma $ -structure when empty terms are allowed.

Note also that if we restrict ourselves to structures without empty terms, then the readings (6) and (1) are equivalent. So we are entitled to use the simpler readings (1) when we are discussing al-Barakāt’s procedures, as we did in Section 1

The reason why Corollary 2.2 gives only partial reassurance is as follows. Write $\Vdash $ for al-Barakāt’s notion of entailment, whatever it may have been. If it was anything like the notions we find in Aristotle and Ibn Sīnā, then it preserves truth in the sense that if $T \Vdash \theta $ then any model of T is a model of $\theta $ , and hence $T \vdash \theta $ . Now Aristotle managed to show, by an examination of each of the 48 separate cases, that for every categorical premise-pair $\Phi $ and candidate conclusion $\theta $ , if $\Phi \vdash \theta $ then there is a proof which deduces $\theta $ from $\Phi $ by undeniable inferences, so that $\Phi \Vdash \theta $ . So at least for categorical premise-pairs and candidates, Aristotle’s version of $\Vdash $ coincides with $\vdash $ even if they are intensionally different. But it could be argued that al-Barakāt has abandoned Aristotle’s proofs by chains of undeniable inferences. This might leave him with no reason to believe that if $\Phi \vdash \theta $ then $\Phi \Vdash \theta $ , unless he is breaking conventions radically and taking $\vdash $ as a definition of $\Vdash $ . This is not the place to pursue this issue any further.

Tarski would have commented that his own notion of consequence in [14] quantifies over arbitrary $\Sigma $ -structures M, regardless of whether their sets $A^M$ etc. are definable by noun phrases available to us. But he would also have agreed that this is not a point of conflict with al-Barakāt’s method, since every $\{A,B,C\}$ -structure is Barakāt-equivalent to some $\{A,B,C\}$ -structure whose sets we can define by noun phrases.

2.2 Barakāt classes

For the rest of this paper we read categorical sentences according to the reading (1).

Theorem 2.3. The categorical sentences true in a structure are determined by the Barakāt class of the structure.

Proof. Let the signature $\Sigma $ consist of the n distinct 1-ary relation symbols $A_0, \ldots $ , $A_{n-1}$ where n is a positive integer.

Claim. Every categorical sentence of $L(\Sigma )$ is logically equivalent to a boolean combination of sentences of the form

(7) $$ \begin{align} \exists x \bigwedge_{i < n} A_i^{f(i)}x, \end{align} $$

where $f: n \to 2$ takes the value $1$ for at least one argument, and we read $A^1$ as A and $A^0$ as $\neg A$ .

Proof of claim. Observe first the logical equivalences

(8) $$ \begin{align} \begin{array}{lll} \forall x (Ax \to Bx) & \equiv & \neg \exists x (A^1x \land B^0x) \\ \forall x (Ax \to \neg Bx) & \equiv & \neg \exists x (A^1x \land B^1 x) \\ \exists x (Ax \land Bx) & \equiv & \exists x (A^1x \land B^1x) \\ \exists x (Ax \land \neg Bx) & \equiv & \exists x (A^1x \land B^0 x). \end{array} \end{align} $$

The conjunctions can be expanded to include all n relation symbols by using the equivalence

(9) $$ \begin{align} \exists x \phi(x) \ \equiv \ (\exists x (\phi(x) \land R^1x) \lor \exists x (\phi(x) \land R^0x)) \end{align} $$

for any 1-ary relation symbol R. $\Box $ Claim.

The theorem follows from the claim.□

We write $\Sigma (n)$ for the signature consisting of the n 1-ary relation symbols $A_0, \ldots , A_{n-1}$ ( $n \geqslant 0$ ). We write $\gamma (n)$ for the number of Barakāt classes of $\Sigma (n)$ -structures without empty terms. We call $\gamma (n)$ the n-th Gergonne number, in view of [6] where Gergonne considered the case of $\gamma (2)$ . The number $\gamma (2)$ counts the Barakāt classes of $\{A,B\}$ -structures without empty terms; in Section 1.3 we confirmed Gergonne’s observation that this number is 5.

Theorem 2.4. The Gergonne number $\gamma (n)$ is given recursively by:

$$ \begin{align*} \begin{array}{l} \gamma(0) = 1, \\ \gamma(n+1) = 2^{2^{n+1} - 1} - \sum_{0 \leq i \leq n} \left( \begin{array}{c} n+1 \\ i \end{array} \right) \gamma(i). \end{array} \end{align*} $$

In particular

$$ \begin{align*} \gamma(0) = \gamma(1) = 1; \ \ \gamma(2) = 5; \ \ \gamma(3) = 109; \ \ \gamma(4) = 32,297. \end{align*} $$

Proof. All $\Sigma (0)$ -structures are Barakāt equivalent, so that $\gamma (0) = 1$ .

Recall from Section 1.2 that there is a natural bijection between the nonempty subsets of $\Sigma (n)$ and the interior types of $\Sigma (n)$ . So the Barakāt class of a $\Sigma (n)$ -structure M can be characterised by giving the set $\mathbb {C}$ of nonempty subsets of $\Sigma (n)$ corresponding to the interior types realised in M. And conversely for each set $\mathbb {C}$ of nonempty subsets of $\Sigma (n)$ we can build a $\Sigma (n)$ -structure M which realises all and only the interior types corresponding to sets in $\mathbb {C}$ . The structure M is without empty terms if and only if every letter in $\Sigma (n)$ appears in at least one of the sets in $\mathbb {C}$ , in other words if $\bigcup \mathbb {C} = \Sigma (n)$ .

By a cover of $\Sigma (n)$ we will mean a set $\mathbb {C}$ of nonempty subsets of $\Sigma (n)$ such that $\bigcup \mathbb {C} = \Sigma (n)$ . By the previous paragraph, the number $\gamma (n)$ of Barakāt classes of $\Sigma (n)$ -structures without empty terms is the number of covers of $\Sigma (n)$ .

The recursive formula given above for this number is known; see for example [7]. The number of nonempty subsets of $\Sigma (n)$ is $2^n - 1$ , so the number $\kappa (n)$ of sets of nonempty subsets of $\Sigma (n)$ is $2^{2^n - 1}$ . For each set $\mathbb {C}$ of nonempty subsets of $\Sigma (n)$ , $\bigcup \mathbb {C}$ is some subset X of $\Sigma (n)$ . So $\gamma (n)$ is $\kappa (n)$ minus, for each proper subset X of $\Sigma (n)$ , the number of $\mathbb {C}$ with $\bigcup \mathbb {C} = X$ . One can check that the number of $\mathbb {C}$ with $\bigcup \mathbb {C} = X$ is $\gamma (|X|)$ . The recursive formula follows.□

2.3 Diagrammable structures

We say that a theory is a type one block if it is the theory

(10) $$ \begin{align} \exists x (Ax \land Bx \land \neg Cx), \ \ \exists x (Ax \land \neg Bx \land Cx), \ \ \exists x (\neg Ax \land Bx \land Cx) \end{align} $$

or a theory got from this one by replacing $A, B, C$ by any three distinct letters. We say that a theory is a type two block if it is the theory

(11) $$ \begin{align} \begin{array}{l} \exists x (Ax \land Bx \land Cx), \ \ \exists x (Ax \land \neg Bx \land \neg Cx), \\ \exists x (\neg Ax \land Bx \land \neg Cx), \ \ \exists x (\neg Ax \land \neg Bx \land Cx) \end{array} \end{align} $$

or a theory got from this one by replacing $A, B, C$ by any three distinct letters.

Theorem 2.5. An $\{A,B,C\}$ -structure is diagrammable if and only if it is without empty terms and is not a model of any type one or type two block.

Proof. $\Rightarrow $ : Suppose for example that the $\{A,B,C\}$ –structure M is a model of the type two block shown at (11). Then since it satisfies $\exists x (Ax \land Bx \land Cx)$ , its Barakāt diagram contains a segment of the form $\equiv $ . Because M also satisfies $\exists x (Ax \land \neg Bx \land \neg Cx)$ , there must be a segment of the diagram consisting of just a part of the line labelled A; without loss of generality put this to the left of $\equiv $ . Likewise because M satisfies $\exists x (\neg Ax \land Bx \land \neg Cx)$ , the diagram must have a segment consisting of just a part of the line labelled B, and this must be on the other side of the segment $\equiv $ :

(12)

But M also satisfies $\exists x (\neg Ax \land \neg Bx \land Cx)$ , and there is no third side available for the corresponding segment of the line labelled C.

The argument for blocks of type one is similar.

$\Leftarrow $ : Assume M is not a model of either a type one block or a type two block. Since it is not a model of a type one block, we have without loss of generality that $A^M \cap B^M \subseteq C^M$ .

Case 1: $A^M \cap B^M = \emptyset $ . Then we can draw diagrams for $\{A,C\}$ and for $\{B,C\}$ . Moreover we can draw them so that the line labelled C, where it is nonempty, reaches the righthand side of the diagram for $\{A,C\}$ and the lefthand side of the diagram for $\{B,C\}$ . We get a diagram for $\{A,B,C\}$ by juxtaposing these two diagrams, adding a link in the C line if M satisfies $\exists x (\neg Ax \land \neg Bx \land Cx)$ .

Case 2: $A^M \cap B^M \neq \emptyset $ . In this case also $A^M \cap B^M \cap C^M \neq \emptyset $ . So since M is not a model of a type two block, it satisfies at least one of the sentences

(13) $$ \begin{align} \forall x (Ax \to (Bx \lor Cx)), \ \ \forall x (Bx \to (Ax \lor Cx)), \ \ \forall x (Cx \to (Ax \lor Bx)). \end{align} $$

Case 2(i): $M \models \forall x (Ax \to (Bx \lor Cx))$ . In this case M can be diagrammed by the whole or part of the diagram

(14)

The two segments missing in the diagram are for $A^M \cap B^M \setminus C^M$ and $A^M \setminus (B^M \cup C^M)$ , both of which are empty.

Case 2(ii): $M \models \forall x (Bx \to (Ax \lor Cx))$ . This is the same as 2(i) but with A and B transposed.

Case 2(iii): $M \models \forall x (Cx \to (Ax \lor Bx))$ . In this case the whole or part of the diagram

(15)

suffices, since the two segments missing are both empty in M.□

Corollary 2.6. There are exactly 86 Barakāt diagrams for the three letters $A, B, C$ .

Proof. Probably the simplest proof is to run through the 109 Barakāt classes of structures without empty terms, and exclude those that are models of a block of type one or two.□

Lemma 2.7. Let M be an $\{A,B,C\}$ -structure, and suppose M is a model of either a type one block or a type two block. Then M is not a model of any universal categorical sentence.

Proof. Suppose first that M is a model of the type one block $\exists x (Ax \land Bx \land \neg Cx), \exists x (Ax \land \neg Bx \land Cx), \exists x (\neg Ax \land Bx \land Cx)$ . Because of $\exists x (Ax \land \neg Bx \land Cx)$ , M is not a model of $\forall x (Ax \to Bx)$ . Because of $\exists x (\neg Ax \land Bx \land Cx)$ , M is not a model of $\forall x (Bx \to Ax)$ . Because of $\exists x (Ax \land Bx \land \neg Cx)$ , M is not a model of either $\forall x (Ax \to \neg Bx)$ or $\forall x (Bx \to \neg Ax)$ . By symmetry the same argument works for both the other pairs of letters.

The argument for a type two block is similar.□

Theorem 2.8. Let M be an $\{A,B,C\}$ -structure without empty terms.

1. (a) If M is a model of a universal categorical sentence then M is diagrammable.

2. (b) If M is a model of a productive premise-pair then M is diagrammable.

Proof. (a) is by Theorem 2.5 and Lemma 2.7

(b) By (a), if M is a model of the premise-pair $\Phi $ and is not diagrammable then the sentences of $\Phi $ are both existential. A standard fact of syllogistic logic (e.g., [13], Section 5.5) is that every premise-pair consisting of two existential sentences is sterile.□

Theorem 2.9. A premise-pair with minor, middle and major terms $A, B, C$ respectively is sterile if and only if it has three diagrammable models $M_1, M_2, M_3$ such that

$$ \begin{align*} \begin{array}{l} M_1 \models \forall x (Ax \to Cx), \\ M_2 \models \forall x (Ax \to \neg Cx), \\ M_3 \models \exists x (Ax \land Cx) \land \exists x (Ax \land \neg Cx). \end{array} \end{align*} $$

Proof. Let $\Phi $ be a premise-pair with minor, middle and major terms $A, B, C$ respectively.

$\Rightarrow $ : Assume $\Phi $ is sterile. Then $\Phi \not \vdash \exists x (Ax \land \neg Cx)$ , so there exists a model $M_1$ of $\Phi \cup \{\forall x (Ax \to Cx)\}$ . By Theorem 2.1 we can find such a model $M_1$ without empty terms. It is diagrammable by Theorem 2.8(a) since it satisfies a universal sentence.

Similarly the fact that $\Phi \not \vdash \exists x (Ax \land Cx)$ guarantees the existence of $M_2$ as required.

For $M_3$ we have to work a little harder, dividing into two cases. The first case is that $\Phi $ includes a universal sentence. In this case ensure (by taking isomorphic copies if necessary) that the domains of $M_1$ and $M_2$ are disjoint. Since $A^{M_1}$ is nonempty, $M_1$ is a model of $\exists x (Ax \land Cx)$ ; similarly $M_2$ is a model of $\exists x (Ax \land \neg Cx)$ . Form $M_3$ with domain the union of the domains of $M_1$ and $M_2$ , and for each letter R put $R^{M_3} = R^{M_1} \cup R^{M_2}$ . Then it can be checked that $M_3$ is a model of $\Phi $ and of both $\exists x (Ax \land Cx)$ and $\exists x (Ax \land \neg Cx)$ . Since $\Phi $ contains a universal sentence, $M_3$ is diagrammable by Theorem 2.8(a).

The second case is that both sentences of $\Phi $ are existential. We have to put into $M_3$ elements in $A^{M_3} \cap C^{M_3}$ and $A^{M_3} \setminus C^{M_3}$ ; neither of these will be in $C^{M_3} \setminus A^{M_3}$ . We also need to put into $M_3$ two elements to ensure that $M_3$ is a model of $\Phi $ . Since neither of the sentences of $\Phi $ mentions both A and C, we can do this without adding any elements of $C^{M_3} \setminus A^{M_3}$ . We may need to add one further element to ensure that $B^{M_3}$ is not empty; again this element can be put outside $C^{M_3} \setminus A^{M_3}$ . By this construction $M_3 \models \forall x (Cx \to Ax)$ , so that $M_3$ is without empty terms and satisfies a universal categorical sentence. So by Theorem 2.8(a), $M_3$ is diagrammable.

$\Leftarrow $ : In fact the existence of the models $M_1$ and $M_2$ suffices to show that $\Phi $ is sterile. The existence of $M_1$ shows that $\Phi \not \vdash \exists x (Ax \land \neg Cx)$ , and also that $\Phi \not \vdash \forall x (Ax \to \neg Cx)$ (given that $M_1$ is diagrammable and so $A^{M_1}$ is nonempty). Likewise the existence of $M_2$ shows that $\Phi \not \vdash \exists x (Ax \land Cx)$ , and also that $\Phi \not \vdash \forall x (Ax \to Cx)$ (again using the fact that $A^{M_2}$ is nonempty).□

In the light of the proof of Theorem 2.9 one wonders why al-Barakāt bothered with giving the models $M_3$ . Surely if he had read Aristotle’s Prior Analytics with any care he would have known that only $M_1$ and $M_2$ are needed? In a submitted paper with the title ‘Abū l-Barakāt’s logical diagrams and their possible sources’ I suggest that al-Barakāt may have been led to the models $M_3$ by giving too much credence to some ill-judged remarks of Aristotle in Prior Analytics.

To conclude:

Theorem 2.10. Procedure Three, applied to any categorical premise-pair $\Phi $ , either correctly concludes that $\Phi $ is productive and finds its correct conclusion, or it correctly finds three diagrams to show that $\Phi $ is sterile.

Proof. Suppose $\Phi $ is productive. Then by Theorem 2.1 every model M of $\Phi $ satisfies the same categorical sentences as some model $M^+$ without empty terms, and by Theorem 2.8(b) $M^+$ is diagrammable. If $\theta $ is a candidate conclusion of $\Phi $ and $\Phi \vdash \theta $ , then the fact that $\Phi \vdash \theta $ can be discovered by checking that each of the diagrams of models $M^+$ as above satisfies $\theta $ . We can then find which of the entailed candidates is logically strongest, and this is the conclusion of $\Phi $ .

On the other hand if $\Phi $ is sterile, then by Theorem 2.9 it has diagrammable models of the three types required by Procedure Three for showing that it is sterile. Diagrams for these three models will be found if one checks all the 86 Barakāt diagrams.□

We noted earlier that both Aristotle and al-Barakāt restricted themselves to 48 categorical premise-pairs. There are another 16 categorical premise-pairs known as the fourth figure. Logicians were beginning to investigate the fourth figure during al-Barakāt’s lifetime, though he seems to have ignored this development. The theorems above, including Theorem 2.10, apply also to the fourth figure premise-pairs.

There is further discussion of al-Barakāt’s method in [9]. The submitted paper ‘Abū l-Barakāt’s logical diagrams and their possible sources’ mentioned above will consider how al-Barakāt could have arrived at his method, and how al-Barakāt related it to Aristotle’s approach. Also I hope that Amirouche Moktefi and I together will soon give a fuller account of al-Barakāt’s diagrams as logical diagrams.

3 Translation of passages from al-Barakāt

The following translations are from Esad Efendi 1931, one of the more accurate manuscripts of al-Barakāt’s Kitāb al-mu ${}^c$ - tabar fī al-ḥikmat al-ilāhīya. I include page references to the printed edition [1], which I believe is a copy of the edition printed in Hyderabad in 1938–9; but be warned that the diagrams in [1] are hopelessly inaccurate. Two slight corrections to the diagrams in Esad Efendi 1931 are noted in the translation below.

The first passage is from Esad Efendi 1931 pages 47B–48A ([1] 126–128). It is al-Barakāt’s first example, the productive mood known to the Latins as Barbara. There are four Barakāt diagrams of the premises, and al-Barakāt gives them all. (In later examples of productive moods he often gives only a representative sample.) Although al-Barakāt makes brief references to syllogistic figures and to Aristotle-style proofs in his descriptions of individual diagrams, the four diagrams together demonstrate Barbara without any need for these Aristotelian features.

The first [productive mood in the first figure] consists of two affirmative universal sentences, as in:

$$ \begin{align*} &\qquad\qquad\text{Every }\textit{A} \text{ is a } \textit{B}; \text{and every } \textit{B} \text{ is a } \textit{C}. \text{ So there follows an affirmative universal}\\ &\qquad\qquad\text{sentence, namely: Every } \textit{A} \text{ is a } \textit{C}. \end{align*} $$

An example of it is:

/Esad 48A/ because human (i.e., A) is included in the class of animala (i.e., B) and animal is included in the class of bodies (i.e., C), so human (i.e., A) is included in the class of bodies (i.e., C). And also

because human (i.e., A) is included in the class of sentient beings (i.e., B) and sentient is equivalent to the class of animals (i.e., C) so that human (i.e., A) is included in the class of animals (i.e., C). Also

because human (i.e., A) is as a class equivalent to rational (i.e., B), and rational is included in the class of sentient beings (i.e., C), so human (i.e., A) is included in the class of sentient beings (i.e., C). Also

because human (i.e., A) is as a class equivalent to rational (i.e., B) and rational is as a class equivalent to laugher (i.e., C). So human (i.e., A) is as a class equivalent to laugher (i.e., C).

The second example is translated from Esad Efendi 1931 pages 50B–51A ([1], p. 135). It describes a sterile mood. As normally with sterile moods, al-Barakāt gives three examples corresponding to $M_1$ – $M_3$ in Theorem 2.9

And the fifth [sterile first-figure] mood consists of a major premise that is affirmative existential and a minor premise that is negative universal [thus: No A is a B, and some B is a C]. /Esad 51A/

Thus every crow is an animal.

Thus no stone is a human.

Thus some white thing is an animal and some white thing is not an animal.