I'm solving exercise $1.1.2$ of Hodges' Model Theory:
Let $X$ be a set and $L$ a signature; write $\kappa (X,L)$ for the number of distinct $L$-structures which have domain $X$. Show that if $X$ is a finite set, then $\kappa (X,L)$ is eithere finite or at least $2^\omega$.
This is what I came up with:
Let $L$ be a signature. There are three possibilities:
- $L$ has a finite number of relations and operations. Thus is quite trivial to understand why there are at most a finite number of $L$-structures on $X$. We observe $n$-ary relations (and also $(n-1)$-ary functions) are subsets of $X^n$, which is finite by hypothesis, and you have at most $2^{2^n}$ possible interpretations for each $n$-ary symbol of $L$. Having $L$ a finite number of relations and operations, $\kappa(X,L)$ is a finite multiplications of finite cardinals, thus finite.
- $L$ has a countably infinite number of relations or operations. Then by the same line of reasoning, you get $$ \kappa(X,L) \geq \prod_{k_n : n\in\Bbb{N}} 2^{2^{k_n}} = 2^{\sum_{k_n:n\in\Bbb{N}} 2^{k_n}} = 2^\omega. $$ Where we enumerated the relations and operations symbols of $L$ and defined $k_n$ to be the arity of the $n$-th symbol (if the symbol is an operation, add $1$ to the arity).
- $L$ has an uncountably infinite number of relations or operations. Then, if you select a countable subset of the symbols, the reduced signature has at least $2^\omega$ structures implementing it. Thus $\kappa(X,L) \geq 2^\omega$ for sure.
I'm very doubtful my reasoning is rigorous, especially from a set-theoretic standpoint. I'll appreciate corrections.
Thank you.