Hipparchus on Compound Statements

There's an interesting article by Richard Stanley in the April '97 
issue of "American Mathematical Monthly" on the subject of a remark 
made by Plutarch (50-120 AD) referring to a combinatorial result of 
Hipparchus (190-127 BC).  Apparently Plutarch's offhand comment 
is the only existing record of this result.

The article quotes Plutarch as follows

    "Chrysippus says that the number of compound propositions
     that can be made from only ten simple propositions exceeds
     a million.  (Hipparchus, to be sure, refuted this by
     showing that on the affirmative side there are 103,049
     compound statements, and on the negative side 310,952.)"

The exactly meaning of these numbers has been something of a mystery 
for Greek scholars.  For example, Heath's "History of Greek 
Mathematics" says

    "In pure mathematics [Hipparchus] is said to have
     considered a problem in permutations and combinations,
     the problem of finding the number of different
     possible combinations of 10 axioms or assumptions,
     which he made to be 103,049 (v.l. 101,049) or 310,952
     according as the axioms were affirmed or denied.  It
     seems impossible to make anything of these figures."

However, Stanley's article points out that 103,049 is the number
of "bracketings" of a string of 10 letters, as shown by Schroder.
(See M2898 in Sloane & Plouffe's Encyclopedia of integer sequences.)
This certainly suggests that Hipparchus was calculating something
that was somehow related to the number of "bracketings" of n 
letters, although as Stanley says

    "...it remains to determine exactly what Hipparchus 
     and Plutarch meant by a 'compound proposition'.
     In Stoic logic, compound propositions are built 
     up from simple ones using such connectives as 
     'and', 'or',  and 'if...then'.  This does not
     seem like enough information to pinpoint exactly
     what Hipparchus had in mind."

It might be worth noting that the number 103,049 appears, slightly
disguised, in another sequence in Sloane's Encyclopedia, namely
M1659, which are identified as the number of "Royal paths in a
lattice".  The first 10 values of this sequence are

    1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, ...

so these numbers are exactly twice the values of the number of
"bracketings" given in M2898.  I don't have any idea what a "royal
path in a lattice" might be, but I do recognize these numbers in
relation to certain compound statements in Boolean logic involving 
n ordered elements with the connectives 'and', 'or', and parentheses.

For example, with the usual Boolean notation conventions on n simple
statements A,B,..., we have

 n = 1       A

 n = 2       A+B
             AB

 n = 3       A+B+C   
             A+BC    (A+B)C
             AB+C    A(B+C)
             ABC

 n = 4       A+B+C+D
             A+B+CD    A+(B+C)D    (A+B+C)D
             A+BC+D    (A+B)(C+D)  (A+B)C+D   A+B(C+D)
             A+BCD     (A+B)CD     (A+BC)D
             AB+C+D    A(B+C)+D    A(B+C+D)
             AB+CD     A(B+D)D     A(B+CD)    (AB+C)D
             ABC+D     AB(C+D)     A(BC+D)
             ABCD

Thus for n = 1,2,3,4 we have 1,2,6,22 compound statements 
respectively.  I won't type them all out, but for n=5 it looks
like there are 90 such expressions, and so on.  The number of
compound statements that can be made from 10 elements in this
way is 206098, which is exactly twice Hipparchus's number.  But
notice that these expressions are symmetrical in the sense that
the number of distinct parenthesizations of (+ * * +) is the
same as (* + + *) by the duality of AND and OR.  Thus, it seems
conceivable that Hipparchus might have had something like these
compound Boolean statements in mind.

Also, notice that the above expressions are what's called 
"monotonic", meaning that they don't involve any negations of 
the basic elements.  Dedekind's Problem is to determine the 
number of monotonic Boolean expressions in n variables, but of 
course we don't require the basic elements to be _ordered_ as 
they are in the expressions above.  As a result, the total number 
of monotonic expressions in n variables grows much more rapidly 
than the sequence M1659.  There could be a relation between the 
"affirmative statements" of Hipparchus and what we call monotonic 
Boolean functions.

Of course, if we allow negations of the variables (but still 
require the elements to be ordered as above), then the number of 
possible expressions will certainly be larger.  However, I suspect 
it will be much larger even than the number 310,952, so it isn't 
clear where this "negative statement" number comes from.  It seem 
strange that it is so close to three times the affirmative number, 
i.e., 310952  =  3(103049) + 1805.  It's hard to think of introducing
negation could just increase the number of possible expression by
a factor if 3.  You can almost imagine Hipparchus negating each of 
the above monotone expressions and then applying something like 
DeMorgan's rules to express them as direct statements in the negated 
elements, but it seems this should just give the same number of 
negative expressions as affirmative expressions.

So the "negation" number 310952 is still quite mysterious, but the 
fact that the "affirmative" number 103049 has a valid foundation makes 
it all the more tantalizing, since it clearly suggests that Hipparchus
knew some non-trivial combinatorics.  Also, it seems unlikely that 
these results were produced in isolation.  There must have been a
body of combinatorial knowledge circa 150 BC that has not come down
to us.

Return to MathPages Main Menu
Сайт управляется системой uCoz