[Prev][Next][Index][Thread]

Re: Linear notation

Date: 01 Jan 92 18:42:53 PST (Wed)
To: linear@cs.stanford.edu

	From: aa%taurus.bitnet@TAUNIVM.TAU.AC.IL
	Date: Wed, 1 Jan 92 10:26:37+020

	I am curious to know: what were the reaons [Peirce] found to
	distinguish between two disjunctions and conjunctions, and what were
	their intended meanings?

Read Peirce, he's great and he's easy to get hold of.  He was one of
the more popular of the 19th century logicians and while his work isn't
quite as widely available as Lewis Carroll's it comes close.  (By
comparison Schroeder is virtually unobtainable, and only in the
original German at that.  Schroeder's hero Dedekind, the first lattice
theorist, is obtainable in English--Dover Press--but has lousy notation
compared to either Peirce or Schroeder.)  Look for Volume 3, Exact
Logic, of Peirce's collected works from Harvard U. Press 1933, or the
corresponding volume in the Indiana U. Press collection 1982, or the
Eisele edition of his mathematical writings, and there are other such
editions.  Start with his 1870 and 1883 papers on binary relations.

Relational composition of course needs no introduction.  A related
interesting question is where in the literature is composition treated
as a sibling of ordinary conjunction?  The short answer is that this
view of relational composition as a second conjunction is a big part of
what has made this calculus so attractive to many of its fans, Peirce
and Schroeder in particular.

In fact one can have composition (or concatenation) be the *only*
conjunction.  This describes for example Jim Lambek's 1958 calculus of
sentence structure [Lam], which can be viewed equivalently as either a
proof system or (up to weak generative capacity as shown by Gaifman
around 1960) a context-free grammar, with theoremhood corresponding to
derivability and hence easily decided (pointed out to me last month by
Eric Arts).  Kleene's calculus of regular expressions can be similarly
viewed as a monotone logic in which composition or concatenation is the
*only* conjunction, + is disjunction, and * makes it a sort of
propositional Datalog.  I very recently combined these two systems to
form Action Logic [Pr], whose language is that of regular expressions
plus Lambek's two implications, giving it just enough nonmonotonicity
to make a proper logic out of it.  The equational theory of this setup
turns out to conservatively extend the equational theory of regular
expressions, but unlike that theory is finitely axiomatizable and
defines star to be reflexive transitive closure.

But this view of composition/concatenation as a form of conjunction
predates even Peirce and seems to be due to De Morgan in 1860 [DeM].
The following footnote appears exactly 1/3 way through "On the
Syllogism IV" (p.221 in Heath's anthology "On the Syllogism", Routledge
& Kegan Paul, 1966).  Here De Morgan argues that, allowing for the
obvious differences, composition L;M of relations L and M resembles
conjunction XY of "terms" (predicates) X and Y.  Indeed he notates it
LM the better to suggest conjunction---the L;M notation now in almost
universal use, and in (fortuitous?) agreement with Algol 60 and dynamic
logic, was introduced later by Peirce.

	[A propos of the *composition* L;M of binary relations L and M]
	A mathematician may raise a moment's question as to whether L
	and M are properly said to be *compounded* in the sense in
	which X and Y are said to be compounded in the term XY.  In the
	phrase *brother of parent*, are *brother* and *parent*
	compounded in the same manner as *white* and *ball* in the term
	*white ball*.  I hold the affirmative, so far as concerns the
	distinction between *composition* and *aggregation*: not
	denying the essential distinction between *relation* and
	*attribute*.  According to the conceptions by which *man* and
	*brute* are aggregated in *animal*, while *animal* and *reason*
	are compounded in *man*, one primary feature of the distinction
	is that an impossible component puts the compound out of
	existence, an impossible aggregant does not put the aggregate
	out of existence.  In this particular the compound relation `L
	of M' classes with the compound term `both X and Y.'

(De Morgan uses "aggregation" and "compounding" to mean respectively
disjunction and conjunction.)

The last two sentences assert that just as the conjunction X0 vanishes
so does the composition L;0, whereas *aggregating* 0 to either X or L
(with aggregation defined as union in both cases) makes neither
vanish.

Although De Morgan greatly admired Boole's calculus, he never became
more proficient with it than to appreciate the idea behind AvB =
A+B-AB.  If he had pursued it as far as Jevons and Peirce did he might
have noticed that his analogy above was the zeroary case of the more
general analogy that both conjunction and composition distribute over
union.  Had he further known of the interdependence of distributivity
and residuation he would have taken this yet further to point out that
his "Theorem K" (in 1939 terminology that composition is residuated,
i.e. is the partially invertible multiplication of what one might call
a semifield) held also for conjunction, suitably phrased.

De Morgan then notes some differences, e.g. whereas conjunction Xx of a
term X with its "contrary" (Boolean complement) x is 0, composition L;l
of a relation L with its complement l need not be 0.

In place of a separate complement operation De Morgan always used the
case of the letter to indicate its sign.  We all know that trick, and
we know that to support it every operation must have its De Morgan
dual.

De Morgan certainly knew this but seems not to have liked the De Morgan
dual of composition, perhaps for lack of a reasonable way of expressing
it in English.  The English for L;M is "L of an M", as in "Alice is an
enemy of a son of Bob, Alice(enemy;son)Bob".  The English for Peirce's
"relative sum" L+,M, the De Morgan dual of composition, is best put as
"L of all non-M" ("Alice is an enemy of all non-sons of Bob") or
equally well as "non-L only of M" ("Alice is a non-enemy only of sons
of Bob").  This composes one instance of negation with either of the
equally natural English constructs "L of all M" and "L only of M".

So what De Morgan supplied in lieu of an explicit De Morgan dual of
composition were these two constructs, which he notated as respectively
LM' ($LM^\prime$) and L,M ($L_\prime M$).  Either one (noting that LM'
= l,m) can perform the function of a De Morgan dual of composition,
with the additional advantage that in "pushing complement through" the
composition, the complement only has to be pushed further down in one
argument, and moreover you can choose which.

Given that only one such construct was needed, one might ask why De
Morgan defined both.  Perhaps for the aforementioned choice.  His
discussion however suggests that he felt he was really only defining
one construct, the prime, which served to change the default
existential quantifier on the input or output of the primed relation
into a universal quantifier when it was in the superscript or subscript
position respectively.  But this is one of those situations where a
seemingly reasonable intuition simply doesn't formalize, at least not
in the sense of being able to treat prime as an operation on binary
relations.  Your guess is at least as good as mine as to what M' means
on its own.

Incidentally while checking out some of the background for this I found
a likely source of Ward and Dilworth's 1939 use of the notation (A,B)
for their disjunction.   In "On the Syllogism:  III, and on logic in
general," [DeM58] De Morgan uses this notation for aggregates, where
(A,B) is clearly intended to be read associatively as A+B rather than
as the doubleton {A,B}.

I still do not know why Birkhoff had earlier (1933) used (A,B) for meet
instead, although one can imagine that in the formative period of
lattice theory lattices could easily have turned upside down a few
times before settling down.  I am finding the same phenomenon today
trying to get schedule-automaton duality settled down to a fixed
horizontal orientation.  I am now firmly settled on schedules (as
conjunctions of necessary events) on the left, and automata (as
disjunctions of possible worlds) on the right.  In a couple of days I
will put "Arithmetic+Logic+Geometry=Concurrency" in pub/algecon.tex on
boole.stanford.edu---it discusses the horizontal orientation issue for
conjunctive and disjunctive sets.

If ever you tire of reading Agatha Christie or whatever you do for
recreational reading, I *strongly* recommend Peter Heath's introduction
to his collection of De Morgan's half dozen papers "On the Syllogism."
I had read it shortly before giving a talk at the Edinburgh Jumelage in
1989 on concurrency models of linear logic.  It made such an impression
on me that when I got to the bit early on in my talk about the
Peirce-Schroeder calculus of binary relations being the first model of
linear logic I found myself launched on a half-hour history of De
Morgan's syllogistic exploits.  I was not sure as to how well known the
binary relation model was to the linear logic experts there, but I
gathered from talking to people after the talk that it was news to all
of them, Girard included.

============================

        @Article(
DeM58,  Author="De Morgan, A.",
        Title="On the Syllogism, no. {III}, and on logic in general",
        Year=1858)

        @Article(
DeM,    Author="De Morgan, A.",
        Title="On the Syllogism, no. {IV}, and on the logic of relations",
        Journal="Trans. Cambridge Phil. Soc.", Volume=10,
        Pages="331-358", Year=1860)


        @Article(
Lam58,  Author="Lambek, J.",
        Title="The Mathematics of Sentence Structure",
        Journal="American Math. Monthly", Volume=65, Number=3,
        Pages="154-170", Year=1958)

	@InProceedings(
Pr,	Author="Pratt, V.R.",
	Title="Action Logic and Pure Induction",
	Booktitle="Logics in AI: European Workshop JELIA '90, LNCS 478",
	Editor="J. van Eijck", Publisher="Springer-Verlag", Pages="97-120",
	Address="Amsterdam, NL", Month=Sep, Year=1990,
	FTP="boole.stanford.edu:pub/jelia.{tex,dvi}")