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’d like to hear about Horn clauses, especially why they are so important. When I see the definition, I want to say, so?
My normal tendency is to keep long posts as “unread” for about a year before I delete them. Short posts are less intimidating
And this is an interesting topic, keep going!
Model theory — correct me if I’m wrong — is crucial here because infinite directed graphs can have properties very different from finite directed graphs. Within the former, “locally finite” is different. There are also generalizations to hypergraphs (with n-ary relations) and locally finite hypergraphs.
I couldn’t figure out how to contact you so here goes:
Here is a little video that my brother, a cousin, and I made with the help of 30 of my high school math students. We built a 64 foot Sierpinski triangle out of about 12000 tortilla chips and then made a humorous and exciting commercial for Doritos to be entered in a contest. While it didn’t win, I was quite happy with the result and having my students learn some more about fractals. Please check out the video and the project page showing some of the making of. Please feel free to post on your blog if you think it’s worthy.
http://www.blownapartstudios.com/
Thanks,
Cory Poole
http://en.wikipedia.org/wiki/Los%27s_theorem#.C5.81o.C5.9B.27s_theorem
Łoś’s theorem, also called the fundamental theorem of ultraproducts, is due to Jerzy Łoś (the surname is pronounced [ˈwɔɕ], approximately “wash”). It states that any first-order formula is true in the ultraproduct if and only if the set of indices i such that the formula is true in Mi is a member of U. More precisely:
Let σ be a ***signature***, U an ultrafilter over a set I, and for each i \in I let Mi be a σ-structure. Let M be the ultraproduct of the Mi with respect to U, that is, M = \prod_{ i\in I }M_i/U.
Then, for each a^{1}, \ldots, a^{n} \in \prod M_{i} , where a^{k} = (a^{k}_{i})_{i \in I} , and for every σ-formula φ
M \models \phi[[a^1], \ldots, [a^n]] if and only if
\{ i \in I : M_{i} \models \phi[a^1_{i}, \ldots, a^n_{i} ] \} \in U.
The theorem is proved by induction on the complexity of the formula φ. The fact that U is an ultrafilter (and not just a filter) is used in the negation clause, and the axiom of choice is needed at the existential quantifier step….