What theories are preserved under the product?

Question

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.

Answer 1

I was able to track down a copy of Weinstein's thesis (on microfilm, no less) and I can reproduce his characterization of direct product sentences here. It is fairly technical, and it is somewhat unsatisfying in that rather than being an inductively defined class of formulas (like the Horn sentences and strict Horn sentences), it is a class defined in terms of a recursive decision procedure.

There is an argument in Chang and Keisler that sentences preserved under finite direct products are preserved under arbitrary direct products, so really all we need to do is characterize the sentences that are preserved under finite direct products.

First some notation. Given formulas $\varphi_0$, $\varphi_1$, and $\varphi$, we write $\varphi_0 \times \varphi_1 \Rightarrow \varphi$ to mean that whenever $M \models \varphi_0(a_1,\dots,a_n)$ and $N \models \varphi_1(b_1,\dots,b_n)$, then $M \times N \models \varphi((a_1,b_1),\dots,(a_n,b_n))$. For any set of formulas $S$, we write

• $\neg S$ for the set of negations of elements of $S$,
• $\exists x S$ for the set of formulas of the form $\exists x \varphi$ for $\varphi \in S$ (for the particular variable $x$),
• $\forall x S$ for the set of formulas of the form $\forall x \varphi$ for $\varphi \in S$,
• $\bigvee S$ for the set of finite disjunctions of elements of $S$ (including the empty disjunction $\top$),
• $\bigwedge S$ for the set of finite conjunctions of elements of $S$ (including the empty conjunction $\bot$), and
• $\bigwedge^\ast S$ for the set of all maximal consistent conjunctions of elements of $S$.

In the case of $\bigvee S$ and $\bigwedge S$, assume that we have some fixed reasonable convention for listing these formulas to avoid redundancy. (For instance, we could require that the disjuncts/conjuncts are listed in some fixed lexicographic ordering with no repetitions.) In particular, when $S$ is finite, we want $\bigvee S$ and $\bigwedge S$ to be finite, and we want the maps $S \mapsto \bigvee S$ and $S \mapsto \bigwedge S$ to be computable.

Also, assume that we choose $\bigwedge^\ast S$ so that $\bigwedge^\ast S \subseteq \bigwedge S$. One thing to note is that there isn't a computable way to determine $\bigwedge^\ast S$ as a subset of $\bigwedge S$.

Let $(v_n)_{n< \omega}$ be an enumeration of our variables. Given a finite set of atomic formulas $S$, we define the following finite sets of atomic formulas:

• $S_0 = \bigvee \bigwedge (S \cup \neg S)$.
• $S_{n+1} = \bigvee \bigwedge \exists v_n S_n$, when $n$ is even.
• $S_{n+1} = \bigvee \bigwedge \forall v_n S_n$, when $n$ is odd.
• $S^\ast_0 = \bigvee \bigwedge^\ast (S \cup \neg S)$.
• $S^\ast_{n+1} = \bigvee \bigwedge^\ast \exists v_n S^\ast_n$, when $n$ is even.
• $S^\ast_{n+1} = \bigvee \bigwedge^\ast \forall v_n S^\ast_n$, when $n$ is odd.

Some things to note:

• The sequence $S_n$ is uniformly computable as a function of $S$, but the sequence $S^\ast_n$ will typically not be.
• We will always have $S^\ast_n \subseteq S_n$ for every $n<\omega$.
• Every formula is equivalent to a formula in $S^\ast_n$ for some $S$ and some $n$. A fortiori, this implies that every formula is equivalent to a formula in $S_n$ for some $S$ and some $n$.

Weinstein proved the following lemma:

Lemma. Let $F$ be a finite autonomous set of formulas closed under $\wedge$ and $\vee$ up to equivalence. Let $u$ be any variable and let $\varphi_0$, $\varphi_1$, and $\varphi$ be formulas in $\bigvee\bigwedge\exists u F$. The following condition $(\ast)$ is sufficient to ensure that $\varphi_0 \times \varphi_1 \Rightarrow \varphi$.

$(\ast)$ For every disjunct $\psi_0$ of $\varphi_0$ and every disjunct $\psi_1$ of $\varphi_1$, there is a disjunct $\psi$ of $\varphi$ such that for every conjunct $\exists u \chi$ of $\psi$, there are conjuncts $\exists u \chi_0$ of $\psi_0$ and $\exists u \chi_1$ of $\psi_1$ such that $\chi_0 \times \chi_1 \Rightarrow \chi$.

Moreover, if $\varphi_0$ and $\varphi_1$ are elements of $\bigvee \bigwedge^\ast \exists u F$, then $(\ast)$ is necessary and sufficient for $\varphi_0 \times \varphi_1 \Rightarrow \varphi$ to hold.

Finally, the above statements hold with all instances of $\exists$ replaced with $\forall$.

The definition of autonomous sets is given in Chang and Keisler. All that's relevant here is that our sets $S_n$ are all autononomous.

This lemma motivates the definition of the following primitive recursive predicate: $R(\varphi_0,\varphi_1,\varphi)$ holds if and only if $\varphi_0$, $\varphi_1$, and $\varphi$ belong to some common $S_n$ and

• if $n$ is $0$, then $\varphi_0 \times \varphi_1 \Rightarrow \varphi$;
• if $n$ is odd, then $(\ast\ast)$ for every disjunct $\psi_0$ of $\varphi_0$ and every disjunct $\psi_1$ of $\varphi_1$, there is a disjunct $\psi$ of $\varphi$ such that for every conjunct $\exists v_{n-1} \chi$ of $\psi$ there are conjuncts $\exists v_{n-1} \chi_0$ of $\psi_0$ and $\exists v_{n-1} \chi_1$ of $\psi_1$ such that $R(\chi_0,\chi_1,\chi)$ holds;
• if $n$ is even and positive, then $(\ast\ast)$ holds with $\forall$ instead of $\exists$.

This is a computable predicate because we can take $S$ to be the set of atomic formulas occurring in our formulas and we only need to check $n$ that is roughly as large as the quantifier ranks of our formulas.

The lemma enails that $R(x,y,z)$ satisfies the following:

• For any $\varphi_0$, $\varphi_1$, and $\varphi$ in some $S_n$, if $R(\varphi_0,\varphi_1,\varphi)$ holds, then $\varphi_0 \times \varphi_1 \Rightarrow \varphi$.
• For any $\psi_0$, $\psi_1$, and $\psi$ in some $S^\ast_n$, if $\psi_0 \times \psi_1 \Rightarrow \psi$, then $R(\psi_0,\psi_1,\psi)$ holds.

In particular, this means that a sentence $\chi$ is preserved under binary direct products (and therefore finite direct products and also arbitrary direct products) if and only if it is logically equivalent to a sentence $\varphi$ in some $S_n$ such that $R(\varphi,\varphi,\varphi)$ holds.

Answer 2

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.

Answer 3

A (first-order) formula is preserved by direct factors if, whenever it holds in a direct product $A\times B$, it also holds in the factors $A$ and $B$. Keisler gave some kind of complicated syntactical characterization of formulas preserved by direct factors: Keisler, H. J., Properties preserved under direct factors. Notices of the American Mathematical Society, vol. 10 (1963), p. 302. Abstract 63T–169.

Now consider formulas of the form $$Q[(\varphi_1\to\alpha_1)\land(\varphi_2\to\alpha_2)\land\cdots\land(\varphi_n\to\alpha_n)]\tag1$$ where each $\alpha_i$ is an atomic formula, each $\varphi_i$ is a formula preserved by direct factors, and $Q$ is a quantifier prefix. Formulas of the form $(1)$ are more general than Horn formulas and are still preserved by direct products. I believe it has been conjectured by someone (Weinstein? Keisler?) that every formula which is preserved by direct products is equaivalent to a formula of the form $(1)$. If true this would, when combined with Keisler's characterization of formulas preserved by factors, give a syntactical characterization of sentences preserved by products.