# Show that there are only finitely many $\mathcal{L}$-structures with domain $D$

Question: Let $D$ be finite and non-empty, let $\mathcal{L}$ be finite.

Show that there are only finitely many $\mathcal{L}$-structures with domain $D$

(1) Let $k$ be the cardinality of $D$.

(2)For every constant symbol $c\in Const_\mathcal{L}$ there are $k$ possible ways of choosing $\mathfrak{I}(c)$.

(3) For every $n$-ary predicate symbol $P\in Pred_\mathcal{L}$ there are $2^{(k^n)}$ possible ways of choosing $\mathfrak{I}(P)$.

(4) Finally, for every $n$-place function symbol $f\in Func_\mathcal{L}$ there are $k^{(k^n)}$ possible ways of choosing $\mathfrak{I}(f)$.

(5) Since there are only finitely many symbols in $\mathcal{L}$, the numbers of possible interpretations mappings $\mathfrak{I}$ on $\mathcal{L}$ is a finite product of finite numbers of the form $k$ or $2^{(k^n)}$ or $k^{(k^n)}$; but such a product is of course finite. $\square$

Definitions:

$\mathfrak{I}$ is defined on $\mathcal{L}$ as follows:

for $n$-ary predicates $P$ in $\mathcal{L}$: $\mathfrak{I}(P)\subset D\times...\times D=D^n$

for $n$-ary function symbols $f$ in $\mathcal{L}$: $\mathfrak{I}(f): D\times... \times D\rightarrow D$

($\mathfrak{I}(f)$ is a function from $D^n$ to $D$)

for every constant $c$ in $\mathcal{L}: \mathfrak{I}(c)\in D$

Points of contention:

(1) I interpret domain $D$ as $D=\{d_1,...,d_k\}$

(2) Since $\mathfrak{I}(c)\in D=\{d_1,...,d_k\}$. So we can choose $k$ possibilities for $\mathfrak{I}(c)$.

(3) I dont understand why there are $2^{(k^n)}$ possible ways of choosing $\mathfrak{I}(P)$.

I would have thought $\{d_1,...,d_k\}\times...\times\{d_1,...,d_k\}$, so $k^n$ ways. Where does the power of $2$ come from?

(4) I feel this stems from (3)

(5) Understand this argument.

• For 3), the number of $n$-tuples with entries in $D$ is. $k^n$. For every $n$-tuple, there are two choices for the truth value of $P$ at that $n$-tuple, for a total of $2^{(k^n)}$ choices. – André Nicolas Apr 2 '15 at 12:51

If $P$ is an $n$-place relation symbol, its interpretation must be a subset of $D^n$. $|D|=k$, so $|D^n|=k^n$, and $D^n$ therefore has $2^{k^n}$ subsets, any one of which can be $\mathfrak{I}(P)$. If $f$ is an $n$-place function symbol, its interpretation must be a function from $D^n$ to $D$. For each of the $n^k$ elements $\overline d$ of $D^n$ there are $k$ choices for the value of the function at $\overline d$, so there are $k^{k^n}$ possible functions from $D^n$ to $D$ and hence $k^{k^n}$ possible choices for $\mathfrak{I}(f)$.
• Why is there $k^{k^n}$ many $\mathfrak{I}(f)$ I am not convinced. If $A=\{a,b\}$ and $f$:binary then $A^n = \{(a,b),(a,a),(b,a),(b,b)\}$ I only can come up this 8 possiblities not $2^{2^2} =16$ – oliverjones Apr 5 '15 at 4:49
• @oliverjones: There is one function for each possible assignment of value $a$ or $b$ to each of those four ordered pairs, That’s $2^4$ possible assignments. Listing the values in the same order in which you listed the pairs, the $16$ functions send the four elements of $A^2$ to $$aaaa,aaab,aaba,aabb,abaa,abab,abba,abbb\;,$$ $$baaa,baab,baba,babb,bbaa,bbab,bbba\;,$$ and $bbbb$. – Brian M. Scott Apr 5 '15 at 16:29