1
$\begingroup$

It is well-known that Horn sentences are "preserved" under products (see for instance Show that the direct product of structures satisfies a Horn sentence).

I was wondering what happens with the converse. I.e. if a Horn sentence is true in the product is it true in the components? What if all components are equal (i.e. we have a power structure)?

$\endgroup$

1 Answer 1

4
$\begingroup$

No. For example, "There are at least four elements" is expressible as a Horn sentence but does not "descend to factors" (even in power structures) for obvious reasons.


To see that "There are at least four elements" is indeed expressible as a Horn sentence, we proceed as follows:

  • For each pair of distinct variables $i,j\in\{1,2,3,4\}$, the expression $x_i\not=x_j$ is a negated atomic formula and so is a Horn formula. (Clause $2$ with $n=1$ in the linked post)

  • The arbitrary conjunction of Horn formulas is again a Horn formula, so $$\bigwedge_{1\le i<j\le 4}x_i\not=x_j$$ is a Horn formula. (Clause $3$, repeatedly)

  • Finally, we can existentially generalize, so that $$\exists x_1,x_2,x_3,x_4\left(\bigwedge_{1\le i<j\le 4}x_i\not=x_j\right)$$ is a Horn sentence as claimed. (Clause 5, repeatedly)


EDIT: Note that while the above shows that it is easy to express "There are at least $k$ elements" for each $k$ as a Horn sentence, things are murkier if we want to say "There are not exactly $k$ elements" - while the preservation theorem says that this can't be done for composite $k$, it turns out to be doable-but-tricky for prime $k$. See this MO thread.

$\endgroup$
2
  • $\begingroup$ Noah: quick question about the edit: is it that the preservation theorem shows that it can't be done for any composite $k$, or that there exists a composite $k$ for which it can't be done? (A clue about the reasoning involved would be nice too $ \ddot{\smile}$.) $\endgroup$
    – Rob Arthan
    Commented Aug 8 at 20:17
  • 1
    $\begingroup$ @RobArthan Suppose $k=ab$. Let $\varphi$ be a Horn sentence saying "There are not exactly $k$ elements" and let $\mathfrak{A},\mathfrak{B}$ be structures with cardinalities $a,b$ respectively. If $a\not=1\not=b$ then $\mathfrak{A}\models\varphi$ and $\mathfrak{B}\models\varphi$ but $\mathfrak{A}\times\mathfrak{B}\not\models\varphi$, contradicting the preservation theorem. $\endgroup$ Commented Aug 8 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .