# In Logic Theory

In logic theory, if we have a finite domain A of k elements, then we can construct only finitely many structures (finite structures) each of which has A as domain. I think the number of structures will be $2^{k}$. How to prove it - if my claim is right?

-
2^k is the number of subsets of a set with k elements –  mathcast Dec 6 '10 at 20:18
The number of structures depends on the signature of the theory. For example each additional unary function symbol multiplies the number of structures by $k^k$ and each unary relation symbol multiplies the number of structures by $2^k$. –  Carl Mummert Dec 6 '10 at 20:38
Sorry, I didn't get the idea!! –  Janice Dec 6 '10 at 21:31
Janice, Carl is trying to tell you that the answer depends on the signature of the theory. Do you have a particular theory in mind? –  Qiaochu Yuan Dec 6 '10 at 21:42
The question is not well posed, because each different signature will give you a different number of structures. If the signature is infinite you may even have an infinite number of structures with a 2 element domain. See en.wikipedia.org/wiki/Signature_%28logic%29 –  Carl Mummert Dec 6 '10 at 21:43

Janice : As Carl pointed out, the answer depends on the signature (language) one uses.

For example, suppose the language consists of a single unary relation symbol $\dot R$. Any structure in this language has the form $(A,R)$, where $R\subseteq A$. If we fix $A$ with $|A|=k$, there are precisely $2^k$ structures of this form (one for each subset of $A$).

Carl's comment was: Suppose your language consists of a single unary function symbol $\dot f$. Any structure of this language has the form $(A,f)$ where $f:A\to A$. The number of functions from a finite set $A$ to a finite set $B$ is $|B|^{|A|}$, so there are $k^k$ such functions $f$, and therefore we have $k^k$ models in this case.

In general, a language consists of:

1. For each positive integer $n$, some $n$-ary function symbols $\dot f$. Each of them will be interpreted as a function $f:A^n\to A$. There are $k^{k^n}$ possible interpretations, if $A$ is fixed and $|A|=k$.
2. For each positive integer $n$, some $n$-ary relation symbols $\dot R$. Each of them will be interpreted as a set $R\subseteq A^n$. There are $2^{k^n}$ many possible interpretations.
3. Some constant symbols $\dot c$. Each of them will be interpreted as an element of $A$, and there are $k$ possible interpretations.

We can interpret different symbols independently of one another, and we understand that order matters, so $(A,R,S)$ and $(A,S,R)$ are interpreted as different structures if $R\ne S$.

Say that $\rho_n,\lambda_n,\tau$ are cardinals (they may be $0$, they may be infinite), and that our language has precisely $\rho_n$ $n$-ary function symbols, precisely $\lambda_n$ $n$-ary relation symbols (for each positive integer $n$), and precisely $\tau$ constant symbols. Then the number of structures in this language that have domain $A$ with $|A|=k$ finite is precisely $$\prod_{n\ge 1}(k^{k^n})^{\rho_n}\cdot\prod_{n\ge 1}(2^{k^n})^{\lambda_n}\cdot k^\tau,$$ where (as usual) we understand that empty products equal 1.

Here, the products are cardinals in the set theoretic sense. If you are only interested in finite languages, this product gives the right answer, when we interpret products as numbers the usual way.

-
The language is a first order language, and a structure is the same as an interpretation. Does this change anything? –  Janice Dec 6 '10 at 23:50
@Janice : Nothing changes. –  Andres Caicedo Dec 6 '10 at 23:59
Nice answer (+1). Something I didn't mention before, and which novices might not appreciate, is the problem of free variables. Many authors (but not nearly all) define an interpretation to consist of a structure $M$ and a function that assigns an element of $M$ to each variable in the language. That assignment function is used to define the truth valuation for formulas in the language, in this approach. Since the supply of free variables is infinite, if $|M| > 1$ then there are also an uncountable number of assignment functions to worry about. –  Carl Mummert Dec 7 '10 at 0:36