2
$\begingroup$

Suppose that two structures $A$ and $B$ whose cardinality is greater than 1 (added in a revision) have the same positive primitive theory. Does it follow that the union of the full Horn theory of $A$ and that of $B$ is consistent? (Here I allow possibly empty finite conjunctions in the antecedent of a basic Horn formula and $\bot$ in the consequent; also a Horn sentence can have an arbitrarily many quantifiers.)

One way of having a contradiction from two Horn theories is having a sentence in one and its negation in the other. Such a sentence is positive primitive (or negations thereof). Hence the question in the beginning. In fact, it is true of any concrete structures that I can think of.

$\endgroup$
12
  • 2
    $\begingroup$ There is still something wrong with the question. You might want to specify exactly what form of sentence you mean by "p.p." or "Horn". Otherwise, please explain why a sentence from one Horn theory whose negation belongs to another Horn theory must be p.p. $\endgroup$ May 17 at 16:21
  • 1
    $\begingroup$ Doesn't $(\mathbb{Z},<)$ and $(\mathbb{N},<)$ give a counterexample? $\endgroup$ May 17 at 16:22
  • 1
    $\begingroup$ Take $A$ to be the $1$-element unstructured set and $B$ to be the $2$-element unstructured set. There are homomorphisms in both directions, so they satisfy the same p.p. sentences. The Horn sentence that separates them is $(\exists x)(\forall y)(x=y)$. $\endgroup$ May 17 at 16:36
  • 1
    $\begingroup$ OK, then take $A$ to be a complete irreflexive graph on an infinite set and take $B$ to equal $A$ union a single isolated point. $A$ and $B$ are mutually embeddable, so the satisfy the same p.p sentences. The Horn sentence that separates them is $(\forall x)(\exists y)(E(x,y))$. $\endgroup$ May 17 at 16:40
  • 1
    $\begingroup$ @Pteromys: Regarding Alex's suggestion, $(\mathbb Z,<)$ and $(\mathbb N,<)$ have the same finitely generated substructures up to isomorphism so they satisfy the same p.p. sentences. Now you need an example of a Horn sentence that is true in $(\mathbb Z,<)$ and false in $(\mathbb N,<)$. $\endgroup$ May 17 at 17:50

1 Answer 1

3
$\begingroup$

First of all, I stated a misunderstanding of mine in my original post: arbitrarily quantified literals also have as their negations Horn sentences. This explains Dr Alex Kruckman's examples on strict total orders and Professor Keith Kearnes's example on graphs.

Secondly, here is an example involving total orders in the language $\{\le\}$. Consider again naturals and integers. The chain of natural numbers satisfy the Horn sentence $(\exists x)(\forall y)[y \le x \to y = x]$, where as the chain of integers satisfy the Horn sentence $(\forall x)(\exists y)[y \not \ge x]$. Now the theory of partial orders is Horn, so it suffices to show that no partial order satisfies those two Horn sentences. This is easy, as the minimum element of a partial order, if it exists, cannot have an element strictly below it or an element incomparable with it.

$\endgroup$

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.