Exercise 2.5.5 david marker's

Question

please help me to solve it,

Let $L = \{E\}$ where $E$ is a binary relation symbol. Let $T$ be the $L$-theory of an equivalence relation with infinitely many infinite classes.

a) Write axioms for $T$.

b) How many models of $T$ are there of cardinality $\aleph_{0}$? $\aleph_{1}$? $\aleph_{2}$? $\aleph_{\omega_{1}}$?

c) Is $T$ complete?

I am eager to learn logic and this exercise!

Answer 1

The axioms are easy, for each $n$, the axioms

$$\exists x_1, \ldots , x_n(\wedge_{l\neq j} \neg x_i Ex_j)$$ $$\forall y\exists x_1, \ldots , x_n(\wedge x_i\neq x_j\wedge \wedge x_i Ey)$$

and of course the axioms saying $E$ is an equivalence relation.

In $\aleph_0$ there is only one model, with a countable number of classes, each one being countable. As a consequence the theory is complete.

For $\aleph_{\alpha}$, $0<\alpha$, let $\kappa_i$ be the number of classes with $\aleph_i$ many elements where $i\leq \alpha$. Then each $\kappa_1\leq |\alpha|+\aleph_0$ because there may be only a finite number of classes with a given cardinality. These numbers characterize the model. This if we look at models of size $\leq \aleph_{\alpha}$ there are $|\omega+\alpha|^{|1+\alpha|}$ many models. In particular for models of size $\aleph_0$ or $\aleph_1$ there are $\aleph_0^2=\aleph_0$ many models. For example a model could have $5$ countable classes and $\aleph_0$ many classes of size $\aleph_1$. Lastly remark that in this counting there are some that do not satisfy the axioms, eg a finite number of classes, but these will not affect the final result, as the true number of models will always be infinite.

Answer 2

a) You need to write down a sentence which states that "$E$ is an equivalence relation". Furthemore, for each $n\in \mathbb{Z}_+$ you need sentences which express that "for each element $x$ there exists at least $n$ distinct elements not related to $x$ via $E$" and "for each element $x$ there exists at least $n$ distinct elements which are related to $x$ via $E$".

b) Here we are only counting models up to isomorphism. For $\aleph_0$ there is only one model up to isomorphism (use for instance a back-and-forth argument). I am not sure about rest of the cardinals, since my set theory is bit rusty, but I suspect that there are many models.

c) The theory is complete, and one can prove this by applying Los-Vaught test: $T$ clearly does not have finite models and in part b) you have shown that every two countable models of $T$ are isomorphic.