-1
$\begingroup$

Suppose $T$ is a complete theory in a countable language with infinite models.

  1. How we could say there are at most $2^{\aleph_0}$ non-isomorphic countable models of T?

  2. What we could say about number of finite models which are non-isomorphic?

$\endgroup$

closed as off-topic by user21820, Namaste, C. Falcon, Aweygan, user91500 Jan 21 '17 at 8:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Namaste, C. Falcon, Aweygan, user91500
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Hint for part 1: Any countably infinite model is isomorphic to one whose carrier set is $\mathbb N$. $\endgroup$ – Henning Makholm Jan 20 '17 at 15:52
4
$\begingroup$

Every countable model is isomorphic to a model whose base set is $\mathbb{N}$, so we can assume that our models have a base set $\mathbb{N}$. Now let $S$ denote the set of all possible interpretations of the language $L$. The set $S$ can be mapped one-one in a set of cardinality $2^{\aleph_0}$, since the language is countable.

Indeed, for simplicity, let's assume there are only function symbols (the relational symbols being not much harder to treat), and let $\{f_n \mid n\in \mathbb{N}\}$ be an enumeration of the language, and for all $n$, let $a(n)$ denote the arity of $n$. Then $S$ can be sent one-one into $\displaystyle \prod_{n\in \mathbb{N}} F(\mathbb{N}^{a(n)}, \mathbb{N})$ (where $F(X,Y)$ denotes the set of functions from $X$ to $Y$).Now this is of cardinality $2^{\aleph_0}$ so there are at most $2^\aleph_0$ $L$-structures so at most $2^{\aleph_0}$ models. QED.

Since $T$ is complete and has infinite models, it cannot have any finite model. Indeed let for all $n$ $F_n$ be the sentence $\exists x_1,.... \exists x_n, (x_1\neq x_2 \land... \land x_{n-1} \neq x_n)$ (where the non written part are existentital quantifiers, and $x_i\neq x_j$ for $i\neq j$). Then if $T$ disproved any of the $F_n$, it couldn't have any infinite model, so out of completeness, for any $n$, $T\vdash F_n$, so that any model of $T$ must be infinite.

$\endgroup$
  • 4
    $\begingroup$ A more economical way to state that the universe has at least $n$ elements would be $$\forall x_1\forall x_2\ldots \forall x_{n-1}\exists y(y\ne x_1\land y\ne x_2\land\cdots\land y\ne x_{n-1})$$ $\endgroup$ – Henning Makholm Jan 20 '17 at 16:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.