Ars Mathematica

Now to the actual definition of Horn clause. First, some standard logical terminology. A term is simply an expression built out of variables and function symbols. For example, x y^-1 z is a term in the language of groups. An atomic formula is a formula that consists of relation symbols (including equality) applied to terms. So xy = yx is an example of an atomic formula in the language of groups. What makes an atomic formula atomic is that it’s not built out of smaller logical formulas.

A Horn clause is built out of atomic formulas in a particular way. Let A_1, … A_n and B
be atomic formulas. Then a Horn clause is a logical formula of the form

A_1 and … and A_n implies B.

As a degenerate special case, the left-hand side of the implication can be empty, which is the same as asserting formula B holds unconditionally.

J. P. May’s book, A Concise Course in Algebraic Topology, is available for download on his homepage. The book provides an overview of classical algebraic topology: homology and homotopy groups, K-theory, and cobordism.

I don’t normally link to sites that require registration, such as the New York Times, but of the final week of the NFL regular season features both a reference to Boolean algebra and an explanation of how the Broncos can get into the playoffs in disjunctive normal form:

George Boole, the 19th-century philosopher, developed Boolean algebra, the system of precisely defined conjunctions and operators that made possible computer logic and playoff tie-breaker scenarios. Without Boole, it would be impossible to explain that the Broncos can make the playoffs with a win AND {(a Jets loss AND losses by [Ravens or Steelers]) OR (a Jets loss AND Texans win) OR (a Ravens loss AND [Steelers loss OR Texans win])}. It would be even be more difficult to explain that the Broncos can also clinch with a loss AND {(Steelers AND Ravens AND Texans AND Jaguars losses) OR (Steelers AND Ravens AND Texans AND Jets losses) OR (Steelers AND Ravens AND Jaguars AND Jets losses) OR (Steelers AND Jaguars AND Jets AND Texans losses) OR (Jets AND Jaguars AND Texans AND Ravens losses)}. We all owe Boole a parenthetical debt of gratitude for making things so crystal clear.

I realize that 99% of mathematicians are in the “the new decade doesn’t begin until 2011″ camp, but I started wondering, how does mathematics look different now than it did in 2000? The big news of the decade was the solution of the Poincaré conjecture and more generally the geometrization conjecture. At the time, I remember hearing it widely predicted that this spelled doom for the topic of 3-manifolds. Is that what really happened?

Also, while progress in certain areas, such as algebraic geometry, algebraic topology, and number theory are high profile, what’s happened in the rest of mathematics? Graph theory saw the proof of the graph minor theorem (which I remember being earlier, but Wikipedia claims was only completed in 2004), but I don’t know what else happened in the area. Were there any major new breakthroughs, or changes in perspective in group theory? Logic? Universal algebra? Game theory?

In a related note, the proof of a conjecture known as the Fundamental Lemma made Time magazine’s list of the top scientific discoveries of 2009.

Dan Piponi of Neighborhood of Infinity has written a paper about how he has successfully used automatic differentiation in the movie industry. Unfortunately, in the course of the article he gives the best argument against the use of automatic differentiation I’ve heard:

In this paper we will present one approach to automatic
differentiation and describe one application that was used with considerable success during the post-production of Matrix Reloaded and Revolutions.

I rest my case.

Two series of monographs on logic are now available (for free) on Project Euclid:

• Perspectives on Logic.
• Lecture Notes on Logic.

I think several of the monographs are well-known in their areas, such as Model Theory of Fields.

CMU students conduct a mock protest at the G20. Slogans include “Safer Data Mining” and “MapReduce, MapReuse, MapRecycle: Green Data Processing”.

The Bohr-Einstein debates, now in convenient puppet form.