H. P. GRICE E J. L. SPERANZA: LA CONVERSAZIONE -- I VERBALI: ROTA

 G.: Bostock has brought me a volume with the reverence other people reserve for liturgy. S.: Rota, I take it. G.: Naturally. Fondamenti di teoria combinatoria, which Bostock presents as if it were simply logic with a better tailor. S.: And you have told him, I hope, that counting is not the first-order predicate calculus with identity merely because it also uses symbols. G.: I had hoped you would tell me that, since you delight in saving philosophers from mathematics one notation at a time. S.: Gladly. First-order predicate calculus with identity is one thing; combinatorics is another. They may shake hands, but they do not marry. G.: Begin at the altar, then. S.: Very well. In first-order predicate calculus with identity one writes formulas like ∀x(Fx → Gx), ∃xFx, and x = y. G.: Which already sounds Anglican. S.: It is merely extensional. One quantifies over individuals in a domain D, interprets predicate letters by subsets or relations on D, and treats identity as the distinguished two-place relation satisfying reflexivity and the indiscernibility clauses. G.: In English, then: one says there is something, everything, and the occasional thing is the same thing. S.: Exactly. Semantics is given by a structure M = ⟨D, I⟩, where I assigns denotations to constants, predicate letters, and function symbols. Truth is defined recursively. G.: Bostock would call that home. S.: Quite. And proof theory then proceeds by axioms or natural deduction. One proves things like ∀xFx ⊢ ∃xFx, or derives ∀x(x = x), or uses Leibniz-style substitution principles. G.: One also writes enough brackets to keep the undergraduates from roaming. S.: That too. But combinatorics is not primarily about satisfaction in structures for a predicate language. It is about finite or discrete structures themselves and the invariants or counts attached to them. G.: Fancy counting with a conscience, then. S.: Better than that. Consider a finite set X with |X| = n. The combinatorial question is often: how many objects of a given sort can be built from X? G.: Such as? S.: Subsets, partitions, permutations, trees, matroids, chains in a poset, lattice paths, set systems, incidence structures, and all the rest. G.: Whereas predicate calculus asks whether a formula is true in a structure, not how many trees have gone missing from it. S.: Precisely. In logic one asks whether M ⊨ φ. In combinatorics one asks for quantities like the number of subsets of X, namely 2^n, or the number of permutations, namely n!, or the number of k-element subsets, namely (nk)\binom{n}{k}(kn​). G.: The symbols already look more muscular. S.: They are. Rota’s genius lies in seeing that these counts sit inside algebraic structures. He does not merely count; he organises the ways of counting. G.: Which is why the title says fondamenti. S.: Yes, but not in the Hilbertian sense. Not foundations as formal metatheory of mathematics, but foundations as unifying concepts inside a mathematical domain. G.: So Bostock hears “foundations” and thinks Gödel, completeness, consistency, decidability. S.: Exactly. While Rota means something closer to: here is the invariant machinery beneath these discrete constructions. G.: A little unfair on both of them, but not unamusing. S.: Now let me be concrete. Take a finite partially ordered set P. One may define its zeta function in the incidence algebra by ζ(x,y) = 1 if x ≤ y, and 0 otherwise. G.: Incidence algebra already sounds more civilised than extensional semantics. S.: It is different civilised behaviour. The incidence algebra I(P) consists of functions f on intervals [x,y] with convolution (f∗g)(x,y)=∑x≤z≤yf(x,z)g(z,y)(f * g)(x,y) = \sum_{x \le z \le y} f(x,z)g(z,y)(f∗g)(x,y)=∑x≤z≤y​f(x,z)g(z,y). G.: Which is what I call a sentence only if written on a blackboard. S.: Quite. Now the Möbius function μ is the convolution inverse of ζ, so μ * ζ = ζ * μ = δ, where δ(x,y) = 1 if x = y and 0 otherwise. G.: There is your identity again, but now it behaves itself. S.: Yes, but not as logical identity. Here δ is the identity element of an algebra under convolution. G.: So already the same sign is wearing overalls rather than a gown. S.: Precisely. And Möbius inversion says that if g(x) = ∑y≤xf(y)\sum_{y \le x} f(y)∑y≤x​f(y), then f(x)=∑y≤xμ(y,x)g(y)f(x) = \sum_{y \le x} \mu(y,x)g(y)f(x)=∑y≤x​μ(y,x)g(y). G.: This is what you call not first-order predicate calculus with identity. S.: Exactly. There is no formula φ of FOPC whose central business is to invert cumulative sums over a poset by means of an incidence algebra. G.: You disappoint the literal-minded. S.: They deserve it. Rota’s world is discrete structure and algebraic inversion, not truth conditions for quantified formulas. G.: Yet Bostock still feels at home enough to show it off. S.: Because the style of rigour is congenial. Exactness, proof, combinable rules, invariant forms, no woolliness, and above all no metaphysical upholstery. G.: Which is why mathematicians pass for blue-collar literae humaniores in Oxford. S.: A splendid phrase. G.: Keep it if you like. S.: Gladly. But the contrast sharpens if we compare typical questions. In first-order logic one asks whether ∀x(Fx→Gx),Fa⊢Ga\forall x(Fx \to Gx), Fa \vdash Ga∀x(Fx→Gx),Fa⊢Ga. In combinatorics one asks how many labelled graphs on n vertices there are, namely 2(n2)2^{\binom{n}{2}}2(2n​). G.: The one is valid or invalid. The other proliferates. S.: Exactly. Or take partitions of an n-element set. Their number is the Bell number B_n. One studies generating functions like ∑n≥0Bnxnn!=eex−1\sum_{n \ge 0} B_n \frac{x^n}{n!} = e^{e^x - 1}∑n≥0​Bn​n!xn​=eex−1. G.: That already sounds like a foreign policy I do not trust. S.: It is perfectly innocent. Or not innocent, but mathematically innocent. G.: Which is already more than can be said for some philosophies of logic. S.: Quite. Another difference. In first-order logic the combinatorial content often enters only incidentally, for example in counting models up to isomorphism of finite cardinality, or in finite model theory later on. But in Rota the counting is central and structural. G.: So the theorem is not “this formula has a model,” but “these configurations are counted by this polynomial.” S.: Very often yes. For example, the characteristic polynomial of a lattice or matroid captures enumerative and geometric information at once. G.: Matroids. There is a word that sounds like a bad college. S.: It is a good concept. A matroid M on a finite set E abstracts dependence. One may define it by independent sets, rank function, closure operator, circuits, or bases. G.: That at least sounds almost logical. S.: There are bridges, yes. But again, not first-order predicate calculus with identity. A matroid is a combinatorial structure satisfying exchange axioms, such as: if A and B are independent and |A| < |B|, then there exists b in B \ A such that A ∪ {b} is independent. G.: This is a civilisation in which dependence has better manners than in ordinary life. S.: Exactly. And Rota excelled in seeing relations between these structures, incidence algebras, Möbius functions, generating functions, and geometric arrangements. G.: Which makes his “foundations” more like the plumbing beneath several rooms than the legal title to the house. S.: Very good. Whereas Bostock’s foundations are closer to the legal title, the survey map, and the questions whether the property is even consistent. G.: Then where does identity enter on the logical side in your proper Bostockian manner? S.: In first-order logic with identity one adds axioms or rules ensuring reflexivity, x=xx = xx=x, and substitution: from x=yx = yx=y infer F(x)↔F(y)F(x) \leftrightarrow F(y)F(x)↔F(y), or in relational form substitute co-designative terms salva veritate in extensional contexts. G.: Salva veritate always sounds like a headmaster’s wife. S.: She is a useful woman. But combinatorics does not revolve around such substitutional discipline. It revolves around structures whose elements may be labelled or unlabelled, counted or quotiented by symmetry. G.: Ah, symmetry. The mathematician’s excuse for everything. S.: A very good excuse. Pólya counting, for instance, uses group actions to count colourings modulo symmetry. If a finite group G acts on a finite set X, one counts orbits by Burnside’s lemma: ∣X/G∣=1∣G∣∑g∈G∣Fix(g)∣.|X/G| = \frac{1}{|G|}\sum_{g\in G} |\mathrm{Fix}(g)|.∣X/G∣=∣G∣1​g∈G∑​∣Fix(g)∣. G.: I can already hear Bostock pretending that this is just logic with harder furniture. S.: He would be wrong, though with dignity. Burnside’s lemma is not a theorem of first-order predicate calculus with identity. It belongs to the combinatorial analysis of group actions. G.: And Rota loves precisely such machinery. S.: Yes. Also generating functions. Ordinary generating functions, exponential generating functions, formal power series, recurrence relations, all used not to interpret formulas but to organise enumeration. G.: It runs in the blood, I suppose. He comes from the land of Peano. S.: Harvard educated, though. G.: It runs in the blood, though. S.: Very likely. Italy gave him Peano’s atmosphere, or at least its afterglow: notation, exactness, symbolic courage, and the thought that mathematics may also be written elegantly. G.: Peano, unlike many philosophers, understood that a symbol can improve a room. S.: Yes. Yet Rota’s higher degree being American helps explain why some Italians deny him full philosophical citizenship while some Americans grant it as a curiosity. G.: Which is perfectly national on both sides. S.: Quite. But his philosophical side is real enough. He wrote on phenomenology, on Husserl, on mathematical intuition, on the primacy of identity, and on all the uneasy points where mathematicians become reflective. G.: Thereby irritating both departments. S.: Exactly. The mathematicians suspect literature, the philosophers suspect theorems. G.: The right combination for a tolerable man. S.: Very likely. Now, let me sharpen the formal contrast once more. In first-order logic we have syntax: if P is an n-ary predicate and t1,…,tn are terms, then P(t1,…,tn) is a formula; if φ and ψ are formulas, so are ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), ∀xφ, ∃xφ. G.: A proper grammar of obedience. S.: And semantics: M,s ⊨ ∀xφ iff for every d in D, M,s[x↦d] ⊨ φ. M,s ⊨ ∃xφ iff for some d in D, M,s[x↦d] ⊨ φ. M,s ⊨ t1 = t2 iff the denotations of t1 and t2 under s coincide. G.: Whereas in Rota one instead defines structures and counts them, or studies functions on them. S.: Precisely. For example, the exponential formula says that if a class of labelled structures is built from connected components, then the exponential generating function of all structures is the exponential of that of the connected ones. G.: That is a much more social theorem. S.: It is. Or think of Stirling numbers of the second kind S(n,k), counting partitions of an n-element set into k nonempty blocks. They satisfy S(n,k)=S(n−1,k−1)+kS(n−1,k).S(n,k)=S(n-1,k-1)+kS(n-1,k).S(n,k)=S(n−1,k−1)+kS(n−1,k). G.: A recurrence relation. Which is what philosophers call a habit. S.: Exactly. But again, nothing about ∀x(Fx → Gx). The problems are structurally different. G.: Yet the English undergraduate, seeing symbols, thinks “logic.” S.: Especially if logic is the only serious symbolism he has met. To him, combinatorics may look like logic after exercise. G.: Which is why Bostock carries the book as if it were confession. S.: Yes. He senses rigour and mistakes the species. G.: A familiar philosophical error. S.: Indeed. Another contrast: logic is often indifferent to finitude unless explicitly restricted. A first-order theory may have infinite models; compactness and Löwenheim-Skolem almost insist on it. Combinatorics typically delights in finite objects. G.: The finite is friendlier to blackboards. S.: And to actual counting. Rota’s world is discrete, often finite, often algebraically organised. His infinites are formal or generating, not model-theoretic by default. G.: Which is already enough to keep him out of the stricter Sub-Faculty sense of “logic.” S.: Yes. Bostock’s bread and butter would be proof, entailment, quantification, identity, perhaps set theory and metalogic. Rota’s is posets, lattices, incidence algebras, combinatorial identities, finite geometries, and the like. G.: Yet one should not deny the adjacency. S.: Certainly not. Boolean algebras, lattices, order theory, closure operators, dependence relations, all sit near algebraic logic. A logician with taste can admire them. G.: That is Bostock’s better side. S.: Quite. He shows it to you because he thinks you will appreciate the ideal of exact structure, even if not the exact subfield. G.: And I do, up to a point. It is why I can make jokes about foundations without wishing the blackboard dead. S.: Rota would approve. He liked blackboards better than many philosophers like prose. G.: Aune once realised that I could care less about blackboards, which drove him from the playgroup more quickly than any maxim. S.: A pity. Rota would have kept him there with chalk. G.: Perhaps. Now tell me how a combinatorial argument differs, in feel, from a logical proof. S.: A good combinatorial proof often counts the same set in two ways, constructs a bijection, or exploits an algebraic generating device. A logical proof derives formulas from rules preserving truth in all interpretations. G.: So one may prove (nk)=(nn−k)\binom{n}{k} = \binom{n}{n-k}(kn​)=(n−kn​) by exhibiting a complement map, whereas one proves ∀x(Fx→Gx),∀x(Gx→Hx)⊢∀x(Fx→Hx)\forall x(Fx \to Gx), \forall x(Gx \to Hx) \vdash \forall x(Fx \to Hx)∀x(Fx→Gx),∀x(Gx→Hx)⊢∀x(Fx→Hx) by derivation. S.: Exactly. The first is combinatorial bijective insight. The second is proof-theoretic discipline. G.: And Bostock, poor man, hopes they are really cousins. S.: They are cousins, but not identical twins. G.: That will disappoint him less if I say it kindly. S.: Say instead that Rota provides a mathematics of structured possibility, not a logic of formal consequence. G.: Very nice. S.: Thank you. G.: Keep it. Now, blue-collar passing for literae humaniores. Do you think that unfair to mathematics? S.: Not unfair, only classically English. Greats men always speak as if mathematics were manual labour improved by notation. G.: Which is why it secretly attracts them. A proof is a respectable form of work. S.: Exactly. And combinatorics is almost artisan by temperament. One arranges, counts, classifies, inverts, constructs. G.: A cabinet-maker’s Platonism. S.: Splendid. G.: Keep that too. S.: Happily. But Rota’s phenomenological side complicates the picture. He is not simply a cabinet-maker. G.: No. He likes to peer into the workshop and ask what sort of vision of identity made the cabinet possible. S.: Hence his essays on Husserl and the primacy of identity. G.: Which, ironically, returns him closer to philosophy than Bostock’s safer admiration can manage. S.: Because once you ask what identity is doing in mathematics, you are no longer merely counting. G.: And once you write Whitehead or Rota for a laurea, one suspects the laurel never quite comes off. S.: There is your wreath again. G.: It belongs here. Once one writes on Whitehead for a laurea, Whitehead sits round the skull. Once on Rota, perhaps the chalk does. S.: Better chalk than laurel, perhaps. G.: Easier to wash out. Now, Peano again. How much does that ancestry matter? S.: Intellectually, a good deal. Italy had a strong symbolic and foundational mathematical tradition: Peano, his notation, his axiomatic style, the civilised confidence that mathematics may write itself clearly. G.: Whereas Oxford in philosophy inherited symbols as a controlled embarrassment. S.: Very much so. Hence the charm of Rota to an English logic-minded undergraduate: he sees symbols not apologising for themselves. G.: Which Bostock finds bracing. S.: Yes. But if he says it is logic, one must still correct him. G.: Kindly. S.: Kindly, but firmly. Fondamenti di teoria combinatoria is not first-order predicate calculus with identity. It is a foundational exploration of discrete mathematical structure. G.: Put more simply? S.: Predicate calculus asks what follows from what in a formal language over a domain. Combinatorics asks how many structures there are, how they are arranged, and what invariants govern them. G.: Better. And where the two touch? S.: In shared rigour, in adjacent algebraic structures, in the common dislike of vagueness, and occasionally in dependence and order. But the central questions differ. G.: Then Bostock arrives with the book under his arm like a relic that has refused a miracle on demand. S.: And you, being you, ask whether it fundamentally combines the fundamentals. G.: To which Providence, for once, remains silent. S.: Or answers by generating function. G.: That would be a distinctly Harvard deity. S.: Harvard educated, as I said snugly. G.: It runs in the blood, though. S.: Peano would agree, in better notation. G.: Then the final moral? S.: That Rota is mathematical enough to impress a logician, philosophical enough to unsettle one, and combinatorial enough to remind Oxford that not every serious symbol belongs to predicate calculus with identity. G.: Dry enough? S.: Sufficiently Vigevanese, with Harvard chalk on the cuffs.