8
$\begingroup$

Although I haven't explicitly found this definition anywhere, it seems to me that the model-theoretic means of defining a product for $\mathcal{L}$-structures is as follows. Given a constant $c$ in the language $c^{\mathcal{M}\times\mathcal{N}}=(c^\mathcal{M},c^\mathcal{N})$; a function $f$, $f^{\mathcal{M}\times\mathcal{N}}((x_1,y_1),\dots,(x_n,y_n))=(f^\mathcal{M}(x_1,\dots,x_n),f^\mathcal{N}(y_1,\dots,y_n))$; and a relation $R$, $((x_1,y_1),\dots,(x_n,y_n))\in R^{\mathcal{M}\times\mathcal{N}}\iff (x_1,\dots,x_n)\in R^\mathcal{M}\land (y_1,\dots,y_n)\in R^\mathcal{N}$. (I based this off of observations from groups, rings, and preorders. Since this is only an observation, please correct me if I'm wrong.)

My question is what kinds of theories are perserved under this product? Specifically if $\mathcal{M},\mathcal{N}\models T$, is there a way of finding $S$ such that $\mathcal{M}\times\mathcal{N}\models S\subseteq T$? For instance, the theory of commutative rings is preserved, but the theory of division rings is not. I've tried to see if there is any pattern in the sentences specifically, but that failed to yield any results. I suspect that the answer is that it's not a property of specific sentences, but rather of the theories themselves. I suspect this because the sentence for the property of inverses in groups and that for the property of inverses in integral domains are almost exactly the same, structurally speaking, but only the former is preserved under products.

Edit: Confused division rings for integral domains originally.

$\endgroup$
4
  • 1
    $\begingroup$ In the algebraic setting (no relations; just operations), varieties (definable by equations) are closed under homomorphisms, subalgebras and direct products; quasi-varieties (definable by quasi-equations) are closed under the formation of subalgebras, direct products and ultra products. I don't know if there is an alternative characterization, or a well-known example of a class precisely closed under direct products; but then again, so isn't the case of groups and rings which you use as an example. $\endgroup$ – amrsa Jun 24 at 15:11
  • 2
    $\begingroup$ The Los-Tarski theorem says a theory is closed under substructures iff it's a universal theory. Lyndon proved a theory is closed under homomorphic images iff it's a positive theory. These are called preservation theorems and I bet there is one for products. $\endgroup$ – Eran Jun 24 at 15:29
  • 3
    $\begingroup$ The definition of the product of structures can be found e.g. in Hodges' model theory book(s), which I think also have a number of preservation results of the type you're looking for. $\endgroup$ – Noah Schweber Jun 24 at 15:29
  • 2
    $\begingroup$ Keisler showed that the theories closed under the more general reduced direct products (reduced by a filter on the index set) are characterized as the Horn theories. But the classes of structures closed under ordinary direct products is more general (e.g. the class of atomic Boolean algebras) and harder to characterize. $\endgroup$ – bof Jun 24 at 15:49
10
$\begingroup$

The definition of product you suggest is indeed the standard one. It can be naturally extended to define the product $\prod_{i\in I} M_i$ of any family of structures $(M_i)_{i\in I}$. Here I'll include the case $I = \emptyset$. Then the product is the singleton structure $\{*\}$ with $f(*,\dots,*) = *$ for any function symbol $f$ and $R(*,\dots,*)$ for any relation symbol $R$. Below, when I talk about formulas being preserved under products, I mean under products of arbitrary families of structures (including the empty family - but I'll comment more on that below).

A simple (but non-optimal, see below) answer to your question is that strict Horn formulas are preserved under products.

A strict basic Horn formula has the form $\left(\bigwedge_{i=1}^n \varphi_i(x)\right)\rightarrow \psi(x)$, where each of the $\varphi_i(x)$ and $\psi(x)$ are atomic formulas. We allow the case $n = 0$, so any atomic formula is a basic Horn formula. A strict Horn formula is built from from basic Horn formulas by $\land$, $\forall$, and $\exists$ (but no $\lor$ or $\lnot$).

You can check that the strict basic Horn formulas are preserved under products, and then prove by induction that all strict Horn formulas are preserved under products. From this it follows that if $T$ is any theory and $S$ is the set of all strict Horn sentences which are entailed by $T$, then any product of models of $T$ is a model of $S$.

What's the word "strict" doing there? Well, we can define basic Horn formula and Horn formula exactly the same way, except we also allow $\psi(x)$ to be the contradictory formula $\bot$. A more common (and equivalent) definition is that a basic Horn formula is one of the form $\bigvee_{i=1}^n \varphi_i(x)$, where at most one of the $\varphi_i$ is an atomic formula, and the rest are negated atomic formulas. The point is that strict Horn formulas are preserved under arbitrary products, while Horn formulas are only preserved under products of non-empty families of structures.

Note that the axiom of integral domains $\forall x\forall y\,(xy = 0\rightarrow (x = 0\lor y = 0))$ is not a (strict) Horn sentence, and the fact that this axiom is not preserved under products proves that it is not equivalent to a (strict) Horn sentence. Similarly the sentence $\forall x\exists y\, (xy = 1)$ from the theory of groups is a (strict) Horn sentence, and it is preserved under products, but the sentence $\forall x \exists y\, (x\neq 0\rightarrow xy = 1)$ from the theory of fields is not a (strict) Horn sentence (since $x\neq 0$ is not atomic), and it is not preserved under products.

This is all very nice, but it raises the natural question: Is a first-order sentence preserved under products if and only if it is equivalent to a strict Horn sentence?

The answer is no - strict Horn sentences are preserved not just under products, but also under the more general construction of reduced products. And as bof points out in the comments, Keisler proved that a first-order sentence is equivalent to a strict Horn sentence if and only if it is preserved under reduced products. This is Theorem 6.2.5 in Model Theory by Chang and Keisler (which I'll refer to as C&K below). What's actually proven there is that a sentence is equivalent to a Horn sentence if and only if it is preserved under reduced products by proper filters. Taking a reduced product by the improper filter gives a singleton structure, just like the empty product. See C&K Exercise 6.2.8 for the version about strict Horn sentences and arbitrary reduced products.

Some history: Keisler's original proof of Theorem 6.2.5 (from 1965) assumed the continuum hypothesis (CH). This is the proof in Section 6.2 of C&K. The same year, Galvin eliminated the dependence on CH, and Section 6.3 of C&K is largely devoted to an exposition of Galvin's proof. In 1971, Shelah famously proved what is now known as the Keisler-Shelah isomorphism theorem, removing the dependency on CH from the earlier result of Keisler's that two structures are elementarily equivalent if and only if they have isomorphic ultrapowers. In this paper, Shelah asserted that the same technique could be used to give a cleaner proof of Theorem 6.2.5 without CH. Exercise 6.2.4 in C&K asks the reader to work out the details - and the exercise was solved in the form of a published paper by George C. Nelson in 1998 (Preservation Theorems Without Continuum Hypothesis).

To complete the story, here's some additional information from Chang and Keisler:

  • There is an example (Example 6.2.3 in C&K) of a sentence which is preserved under (non-empty) products but which is not preserved under arbitrary reduced products by proper filters (and thus is not equivalent to a Horn sentence). The example given is the conjunction of the finitely many axioms for Boolean algebras, together with the sentence asserting that there exists an atom. This example can be easily modified to one which is preserved under all products but is not equivalent to a strict Horn sentence by replacing "there exists an atom" with "$0=1$ or there exists an atom".
  • Apparently, there is a true characterization of those first-order sentences preserved under products. C&K write "A syntactical characterization of direct product sentences was given by Weinstein (1965). Since his characterization is very complicated, we shall not give it here." It must indeed be very complicated, because C&K don't shy away from including extremely technical material elsewhere in their book! The reference is to Weinstein's PhD thesis "First-order properties preserved by direct product." It seems difficult to track down this thesis online. Maybe it's in the University of Wisconsin library? If someone reading this has a copy or knows the characterization, I would like to know what it is!
  • Finally, C&K show (Propositions 6.2.8 and 6.2.9) that if a universal (respectively, existential) sentence is preserved under (non-empty) products, then it is equivalent to a universal (respectively, existential) Horn sentence. And they give a reference, again to Weinstein's thesis, for the same result for $\forall\exists$-sentences. This is the best possible result, since the counterexample about atoms in Boolean algebras is an $\exists\forall$-sentence.
$\endgroup$
3
  • $\begingroup$ By the way, an example of a sentence preserved by direct products but not reduced products doesn't require the whole axiomatization of Boolean algebras. I think this does the trick: $$\forall y[0\le y]\land\exists x\forall y[y\le x\to(x\le y\lor y\le0)]$$ $\endgroup$ – bof Jun 24 at 18:05
  • $\begingroup$ I don't know what Nelson did in 1998 but I think Chang & Keisler already removed the CH from Keisler's reduced product theorem in their Model Theory book (1960s), and Shelah gave a better proof but maybe too late to be in the C&K book. $\endgroup$ – bof Jun 24 at 18:14
  • $\begingroup$ @bof Thanks for the simpler example and for correcting my history! In your example sentence, I think you also need to include the condition $x\neq 0$. On the history: The first edition of C&K didn't come out till 1973. Somehow I managed to miss that the next Section (6.3) of C&K explains how to remove the dependency on CH. The introduction to Nelson's 1998 paper explains where it fits into the story - I'll edit later to clarify. $\endgroup$ – Alex Kruckman Jun 25 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.