Ars Mathematica

The New York Times recently featured this defense of a recent controversial article:

[Hoyt replied to this criticism by saying]—with emphasis in the original— that “The story says O’Keefe dressed up as a pimp and trained his hidden camera on Acorn counselors. It does not say he did those two things at the same time.”

Apparently, the New York Times has adopted as part of its style-book the truth-functional and beloved of first-order logicians everywhere. (In most forms of formal logic the statement “A and B” is true if and only if each of A and B are true. Outside of logic, and rarely works that way. Even programming languages frequently deviate from a pure truth-functional and.)

I’m now enamored by the idea that the New York Times style guide is being taken over by logicians. The next step will be when they start publishing an edition in Loglan.

(Joke swiped from Neddy Merrill at Edge of the American West.)

I just found an interesting website: Connexions. It is a website that hosts a large variety of textbooks and academic monographs, all available under an open-content license. A significant fraction of the collection are applied mathematics books that range from the high school level to the graduate level.

One reason math is hard to teach is that you have someone who found something easy to understand trying to each it to someone who finds it hard to understand. This post at Language Log is an interesting example of someone in a different field running into the same problem.

Linguists use the idea that language constructs are recursive. The example that Mark at Language Log gives is that of “stone traffic barrier”. Here, “stone” and “traffic” are both adjectives. Adjectives can modify not only single-world nouns, but more complex phrases that stand in for nouns. Here, “stone” modifies “traffic barrier”. If you parenthesize it like it’s a piece of mathematics, you would write “(stone (traffic barrier)”. Mark comments that he’s regularly surprised how difficult people find the concept.

It also makes me wonder if mathematics is hard to teach at a basic syntactic level in a way that we would never appreciate. Syntactically, mathematics is defined entirely in terms of recursive syntactic constructions, as the Wikipedia page for well-formed formula illustrates. Getting across the idea of order of operations of arithmetic would be pretty hard if you’re talking to somebody who hasn’t learned the idea of recursive syntax in the first place. It makes me wonder if learning how to diagram English sentences would make it easier to learn algebra.

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.)

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 aⁿ = 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.