Number of non-isomorphic models of the structure

Question

I just have started to study some model theory and I have difficulties with following two problems:

Prove that every theory of signature, consisting only of a finite number of unary predicate symbols and equality, has an at most countable number of countable models up to isomorphism.

And

Prove that every theory of signature, consisitng only of binary predicate $R$ and equality, with axioms $$\forall x \forall y (R(x,y) \rightarrow R(y,x))$$ $$\forall x R(x,x)$$ has exactly continuum countable models up to isomorphism.

For the first problem, I came up with the following. Instead of models of theories let's investigate models of signature. Fix the order of predicate symbols. Then we can introduce function $ \phi: M \rightarrow \{0,1\}^n$ which assigns to each element of the model n-tuple of values of predicates on this element.

Now we also can introduce an equivalence relation on $M$: two elements are equivalent if they are assigned equal n-tuples. Two models are isomorphic iff corresponding equivalence classes have the same cardinality. If we have $n$ predicate symbols, then there are $2^n$ tuples, which define a partition of classes. Let's choose an arbitrary model. We can define a function $\psi : M \rightarrow \{1, 2, 3, ..., 2^n\}$ which also determine partition. There are countably many such functions. Therefore, there are at most countable number of models up to isomorphism.

For the second problem, I don't have any clear ideas.

Any hints and ideas are appreciated.

Thanks!

Answer 1

As I meant to suggest in the Comments, the second problem can be related to (undirected) graphs (on countably infinitely many nodes) which are nonisomorphic.

The goal is to show there are continuum many such nonisomorphic models of the theory described as having a single binary predicate $R(x,y)$ and the predicate calculus with equality, and non-logical axioms:

$$ \forall x \forall y (R(x,y) \rightarrow R(y,x)) $$

$$ \forall x R(x,x) $$

As @AlexKruckman points out, the wording of the Question lends itself to an interpretation that any extension of this theory would also have continuum many models (up to isomorphism), but that claim would be false. Alex gives an example of one extension that has only a single model (up to isomorphism). So we will focus on the cardinality of the unextended theory, whose countably infinite models have a natural interpretation as undirected graphs on countably many nodes.

That is, when $R(x,y)$ is true, either $x=y$ or there exists an edge between nodes $x$ and $y$.

The easy direction is to show there are at most continuum many nonisomorphic models. We may suppose that up to isomorphism the domain of any such model is the natural numbers $\mathbb N$, and the interpretation of $R(x,y)$ in that domain gives a subset of the countable set $\mathbb N \times \mathbb N$. Since there are continuum many subsets of this countably infinite set, there are at most continuum many nonisomorphic models.

To show the other direction, that there are at least contiuum many nonisomorphic models, it suffices to constuct such a collection of models. In particular let $S \subseteq \mathbb N$ be an arbitrary subset of natural numbers (which for convenience we assume to be positive integers only, excluding zero).

Let the entries of $S$ (if any) be taken in ascending order, and construct an undirected graph on $\mathbb N$ which consists of simple paths, one of length $k$ for each $k\in S$. The shortest such path will begin at $1$ and go up to $k_1+1$, where $k_1=\min S$, and the next shortest path (if any) of length $k_2$ begins at $k_1 + 2$ and goes to $k_1 + k_2 + 2$, and so on.

Since two such constructed models for subsets $S,S'$ are isomorphic iff they consist of paths of corresponding lengths, this can only occur when $S=S'$. Therefore we have (at least) continuum many nonisomorphic models, and the demonstration is finished.