Monthly Archives: February 2010

Homomorphisms and Horn Clauses

Posted on by

The idea of a homomorphism extends neatly to general signatures. A function between two objects with the same signature is a homomorphism if it preserves all function and relation symbols. So φ is a homomorphism if for each n-ary function symbol f

φ( f(x1, …, xn) ) = f( φ(x1, …, φ(xn) )

and each n-ary relation symbol R

R(x1, …, xn) implies R(φ(x1, …, φ(xn))

This coincides with the usual definition of homomorphism for groups and rings. For partially-ordered sets, homomorphisms correspond to order-preserving maps.

Previous post here.

Computational Topology

Posted on by

This post at Geomblog is a nice survey of the different approaches to computational topology, which includes both computational approaches to topology and applications of topology to particular areas within computation.

Analytics X Competition

Posted on by

Famously, Netflix offered a million dollar prize for a group that could beat Netflix’ own algorithm for predicting customer movie rankings. The contest, whose main beneficiary was Netflix itself, garnered considerable participation.

The Analytics X Competition is a similar contest, but aimed at benefiting the public directly. The contest is to predict crime rates by zip code in the city of Philadelphia. (The contest is privately funded, though, so the prizes are much smaller. Still it’s an interesting idea.)

Formal Logic at the NYT

Posted on by

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

Connexions

Posted on by

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.

Horn Clause Example: Graphs and Partial Orders

Posted on by

Classical algebraic structures such as groups and rings can be given entirely in terms of equations, so they don’t require the full expressiveness of Horn clauses.

Directed graphs (with at most one edge between nodes) can be represented by their adjacency relation: for two vertices x and y, the adjacency relation R(x,y) holds if there is an edge from x to y. Undirected graphs can be modeled by requiring that directed edges between two vertices go in both directions: R(x,y) implies R(y,x).

Partially-ordered sets can also be modeled in terms of Horn clauses. The three properties of a partial order are all Horn clauses:

  • reflexivity — x ≤ x
  • transitivity — x ≤ y and y ≤ z implies x ≤ z.
  • asymmetry — x ≤ y and y ≤ x implies x = y.

(Thus preorders, which drop the asymmetry axiom, are also given by Horn clauses.)

Total orders, which impose the requirement x ≤ y or y ≤ x, cannot be given by Horn clauses.

Previous post here. Next post here.

I Have Marshall McLuhan Right Here

Posted on by

Here’s a post and comment thread at Computational Complexity from way back in November that struck me as funny when I came across it. In the post itself, Lance complains about the scarcity of publicly-accessible proofs of Barrington’s Theorem. In the comments, the eponymous David Max Barrington appears, and gives the proof.

Recursion Hard to Teach

Posted on by

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.

Deltoid Versus Media

Posted on by

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

But where’s the H on my forehead?

Posted on by

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?