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