Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a symbol vocabulary that contains $c$ constant symbols, $p_k$ predicate symbols of each arity $k$, and $f_n$ function symbols of each arity $k$, where $1\le k \le A$. Let the domain size be fixed at $D$. For any given interpretation-model combination, each predicate or function symbol is mapped onto a relation or function, respectively, of the same arity. You may assume that the functions in the model allow some input tuples to have no value for the function(i.e., the value is the invisible object). Derive a formula for the no. of possible interpretation-model combinations for a domain with $D$ elements. Don't worry about elimination redundant combinations.

I've understood the first half of the question, that there are $k$ predicate symbols $(p_1,p_2, \dots, p_k)$ and there are also $k$ function symbols $(f_1,f_2, \dots, f_k)$.

What is it meant by interpretation-model combinations for a domain? And how do I derive a formula for the no. of possible interpretation-model combinations for a domain with $D$ elements?

share|improve this question
add comment

1 Answer

This isn't standard jargon as far as I know. I suppose the thought might be: Here's a language, some constants, some predicates, some function-expressions. Here's a model (a structure) build from stuff in domain D with size $D$, some objects (one for each constant), some relations (the same number of n-place relations as n-place predicates), some functions. Keeping that model-structure fixed, we could permute which constant gets assigned which objects as interpretation, which n-place predicate gets assigned which n-place relation as interpretation, which n-place function gets assigned which n-place function. So: one fixed model-structure, many interpretations based on it.

So count the number of suitable model-structures you can build from D, and multiply by the number of interpretations we can get from each one by permuting assignments.

(This isn't very interesting, it has to be said!)

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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