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 uncountably many pairwise non-isomorphic models. Could somebody please help me with this?

Does it have at least infinite many pairwise non-isomorphic models?

  • $\begingroup$ This is your third question about this theory. Just out of curiosity, why are you so interested in it? $\endgroup$ Commented Dec 11, 2014 at 1:35
  • $\begingroup$ I'm going through possible questions on exam and my understanding is still far from required level. This theory was given on exam last year. $\endgroup$
    – Levitan
    Commented Dec 11, 2014 at 1:52

1 Answer 1


As pointed out in the answers to your previous question, models of this theory are graphs of degree $2$ with arbitrarily long chains. Another way of putting it is this: a model is any disjoint union of copies of infinite chains and finite loops (of length at least $3$), such that either there's at least one infinite chain or there are finite loops of arbitrarily large size.

So for any subset $S\subseteq \{3,4,5,\dots\}$, we can make a countable model $M_S = C_\infty \sqcup (\coprod_{n\in S} C_n)$, where $C_\infty$ is an infinite chain and $C_n$ is a loop of length $n$. Clearly if $S\neq T$, $M_S \not\cong M_T$, and there are continuum many subsets of $\{3,4,5,\dots\}$, so there are continuum many nonisomorphic countable models.

However, any completion of this theory has only countably many countable models. To see this, note that for each $n\geq 3$, a completion $T$ will say either "there are exactly $k$ loops of length $n$" for some $k\in \mathbb{N}$, or "there are more than $k$ loops of length $n$" for all $k\in \mathbb{N}$. In the latter case, any countable model must have countably many loops of length $n$. Hence the number of finite loops of each length is determined by $T$, and the isomorphism type of a model of $T$ is decided by how many infinite chains there are. There are countably many choices: $0, 1, 2, \dots, \aleph_0$ (except that $0$ is ruled out if $T$ does not allow for arbitrarily large finite loops).


You must log in to answer this question.

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