What scientists say and what journalists here are frequently two different things. Tim Lambert at Deltoid has decided to take the fight to the enemy by calling journalists out by name. For example, here he targets a sensationalist story by Jonathan Leake on how researchers have shown that Facebook causes students to do worse in school. The actual research was much more preliminary and equivocal.
Also, I had no idea that deltoid was a geometrical term. (I think of the muscle.)
This article from the New Scientist features this quote:
If this doesn’t blow your socks off, then Hogan, who has just been appointed director of Fermilab’s Center for Particle Astrophysics, has an even bigger shock in store: “If the GEO600 result is what I suspect it is, then we are all living in a giant cosmic hologram.”
Say what?
I thought I would give a series of examples in increasing exoticness, starting with rings.
A ring has a signature that consists of two binary operations, + and ., one unary operation (-), and two constants (or nullary operations), 0 and 1. The axioms for a ring consist of the associative law for both + and ., the commutative law for +, and the appropriate axioms for -, 0, and 1. Since these all consist of equations, these are all Horn clauses.
Commutative rings are also axiomitizable by adding the commutative law for multiplication. Commutativity is just one of a large family of additional equations that can imposed on the theory of a ring. The whole topic is well-studied, and goes by the name of polynomial identity rings.
In the usual axiomatization of rings, unary minus is not explicitly included. Instead, the existence of an additive inverse is postulated, and uniqueness is proven. This axiom is not a Horn clause, but since the element is unique, you can reformulate it by introducing a new function for the additive inverse.
This trick is not universally applicable. The axioms for division rings, where every nonzero element has a multiplicative inverse, cannot be given in terms of Horn clauses, even by introducing a new function symbol for inverses. One immediate problem is that the inverse is only a partial function, since zero does not have an inverse. This problem can be finessed by extending the notion of Horn clauses to partially-defined functions (something that I will address in a later post). A more serious problem is that there is no way to express the notion that an element is either zero, or has an inverse.
Integral domains also cannot be axiomatized by Horn clauses: the notion that ab = 0 implies that a = 0 or b = 0 is inexpressible. Horn clauses can express the idea that a ring has a zero nilradical, by introducing infinitely many axioms of the form an = 0 implies a = 0, one for each n.
Chad Orzel announced he’s giving up reading blogs for Lent. The Catholic custom is to give up something enjoyable over the time between Ash Wednesday and Easter. (My father’s mother was Catholic, and once when I was a kid suggested I give up something for Easter. My offer to give up peas was not well-received.)
I was thinking that for any blogger less prolific than Chad, the ultimate Lenten sacrifice would be to give up not blogging. Few blogging-related activities in life are more pleasurable than putting off finishing a post because it’s not quite perfect.
I’m not making any promises, though.
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.
My normal tendency is to write long posts that I never finish. I’ll start off this series with small posts to see if I can break the habit.
The idea of Horn clauses emerged from model theory, so I will begin there. Model theory considers ideas that can expressed in very limited languages. You begin with a small vocabulary of constants, function symbols and relation symbols, known as the signature. For example, you can express the theory of groups in terms of two function symbols and one constant: the group product, the inverse function, and a constant that represents the unit. The theory of directed graphs can be described by a single relation symbol R(x,y) that expresses whether a directed edge begins at x and ends at y.
When coupled with first-order logic, even a very limited language can be very expressive. Set theory itself, for example, can be expressed using a single relation symbol (set membership). Horn clauses are special first-order logical statements that are not nearly as expressive, but still cover very many cases, as we shall see.
I was musing about the foundations of mathematics the other day, when it occurred to me that you could make a pretty good case that the key foundational idea of mathematics is that of Horn clauses (also known as universal Horn sentences). Horn clauses, despite begin obscure outside certain areas, are ubiquitous. Many (perhaps most?) basic mathematical objects can be described by Horn clauses. Fundamental category theoretic notions have Horn clause interpretations. Even first-order logic, which contains Horn clauses as a special case, can be viewed as having inference rules in the form of Horn clauses applied at the level of proofs.
I thought I’d spend a couple of posts describing Horn clauses, and laying out the case for their ubiquity.
Next post here.
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.