I have a language $L=\{P\}$ with equation, where $P$ is binary predicate symbol. Language's formulas are:

$\varphi \equiv \forall x \forall y (\neg P(x,x) \land (P(x,y) \to P(y,x)))$,

$\psi \equiv \forall x \exists y \exists z(y\ne z \land P(x, y) \land P(x,z) \land \forall v (P(x,v) \to (v=y \lor v =z )))$

and for every $n \in N^+$

$\xi_n \equiv \exists x_1 \exists x_2 ... \exists x_n (\bigwedge \limits _{i=1}^{n-1}P(x_i, x_{i+1}) \land \bigwedge \limits _{i=1 }^{n}\bigwedge \limits _{j=i+1}^{n} x_i \ne x_j)$

Theory $T=\{\varphi,\psi\} \cup \{\xi_n | n \in N^+\}$ is being considered.

In my question models with countable field only are considered(I mean for every implementation $M$ injection from $M$ to $N$ should exist)

I need to decide if $T$ has the smallest model $M$. With smallest model I mean such model, that for any $M'$ of theory $T$ there exist injective homomorphism from $M$ to $M'$. Could somebody please help me with this?


No. Let $C_\infty$ be an infinite chain, and let $C_n$ be a finite loop of length $n$. Then $C_\infty$ is a model of your theory, and so is $\coprod_{n\geq 3} C_n$, the disjoint union of a loop of length $n$ for all $n\in \mathbb{N}$ with $n\geq 3$. But obviously neither of these models embed into the other.

However, any completion of this theory has a smallest model. In my answer to your previous question, I described all completions of this theory and all of their countable models. In any completion, the model with the fewest possible infinite chains ($0$ if the completion allows arbitrarily large finite loops, $1$ if not) will embed into every other model.


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.