Consider a first order language with a single binary relation $R$ and consider the theory of a set $A$, Th($A$), where $A$ is the set containing a single axiom describing that there are exactly three elements: $A = \{ \exists x \exists y \exists z (x \neq y \land x \neq z \land y \neq z \land \forall w(w = x \lor w = y \lor w = z))\}$.

I'm trying to show that i. $T$ has countably infinite many structures up to isomorphism and ii. to find a decision procedure for $T$.

Here are my thoughts: i. I understand how to find a class of countably many structures, e.g., the class of structures whose domains consist of $i$, $i+1$, $i+2$ for any $i \in \mathbb{N}$. We see in my example any two models are isomorphic, but I'm unsure of how to show that there can't be a larger class or isomorphic models of any sort.

ii. Since $A$ contains a single axiom and is therefore enumerable, then its consequences, are enumerable and hence $T$ is enumerable. We may write out all strings representing proofs and by Los Vaught Test (we showed in part i. that $T$ is $\aleph_0$-categorical), we know $T$ is complete so for every formula we must reach at some point a proof of either it or its negation.

I'd appreciate any insight as to whether I am on the right track and hints of any sort would be much appreciated!

  • 3
    $\begingroup$ (i) is false, as it is rather obvious that there are only finitely many structures up to isomorphism (there are only finitely many binary relations on any 3-element set)... $\endgroup$ – Eric Wofsey Apr 9 '18 at 5:06
  • 1
    $\begingroup$ @EricWofsey but what about my example of structures with domains of a different set of three natural numbers? These structures are isomorphic and there are infinite of them. $\endgroup$ – Raton Apr 9 '18 at 5:10
  • 3
    $\begingroup$ "Up to isomorphism" means you consider isomorphic structures to be the same. In any case, you haven't actually named any examples, since you never said what the binary relations are. $\endgroup$ – Eric Wofsey Apr 9 '18 at 5:12
  • $\begingroup$ @EricWofsey and also, this complicates part ii since we can't claim that Th($A$) is complete any more by the Los Vaught Test... $\endgroup$ – Raton Apr 9 '18 at 5:19
  • $\begingroup$ @EricWofsey I understand how we would come up with a bijective mapping, call it $h$, between domains of any two structures of $T$, but how would we show that $h(R(a,b)) = R(h(a),h(b))$? $\endgroup$ – Raton Apr 9 '18 at 5:40

There are two key observations here.

The first is purely combinatorial:

Fix a three-element set $\{a, b, c\}$. There are only finitely many binary relations on $\{a, b, c\}$. That is, there are only finitely many models of your theory with domain $\{a, b, c\}$.

The second observation is:

The statement we want to prove is $$\mbox{"Each model of $T$ is isomorphic to some structure with domain $\{a, b, c\}$."}$$

Since this will let us count the models of $T$ up to isomorphism, by counting the models of $T$ with domain $\{a, b, c\}$ up to isomorphism.

So suppose $(\{x, y, z\}; R)$ is a model of $T$. Pick a bijection $f:\{x,y,z\}\rightarrow\{a, b, c\}$; do you see a way to use $f$ to define a relation $S$ on $\{a, b, c\}$ such that $f$ is an isomorphism from $(\{x, y, z\}; R)$ to $(\{a, b, c\}; S)$?

HINT: you're going to define $S$ in terms of $R$ and $h$. Suppose for example that $R(x, y)$ holds; using $h$, does this suggest some fact about the $S$ we want to build?

  • $\begingroup$ what is $h$? Do you mean $f$? I understand that we have $8$ isomorphic classes of structures ($\{a\}, \{b\}, \{a,b\}, \cdots$). Why is it important to define $S$ in terms of $R$ and do you have any hints as to how to go about it? $\endgroup$ – Raton Apr 9 '18 at 23:30
  • $\begingroup$ also, regarding ii. if my decision procedure is to look at one structure in each of the 8 isomorphic classes and decide whether the formula holds in each. If the formula fails in at least one structure, we reject and otherwise accept. Is this correct reasoning and what do you recommend I add to make it more rigorous? Once again, thank you. $\endgroup$ – Raton Apr 9 '18 at 23:33
  • $\begingroup$ I meant $2^9$ iso classes $\endgroup$ – Raton Apr 10 '18 at 0:59

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.