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$


$\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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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)$.

  • $\begingroup$ 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$ $\endgroup$ – oliverjones Apr 5 '15 at 4:49
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Apr 5 '15 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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