Let A be a finite non-empty set and S a finite symbol set. Show that there are only finitely many S-structures with A as the domain

Let k be the number of elements in A,

for all constant symbols c in S there is k-many interpretations I(c).

Here's where I am a bit confused. I am having issues figuring out how many interpretations there would be for each n-ary function symbol f (and similarly for n-ary relation symbol R)

  • Well, what exactly is an n-ary function, in set-theoretic terms? How would you list them all?
    – user9166
    Apr 5, 2015 at 15:25
  • You'll probably have more luck with mathematical logic questions on math.SE. Apr 5, 2015 at 15:59
  • 6
    belongs to mathematical logic / set theory. Not philosophical. Apr 5, 2015 at 17:21

1 Answer 1


For an n-ary function symbol, there are k^n elements of the domain; for each one you need to choose one of k elements to send it to. So the total number of possible function interpretations would be k^(k^n).

For an n-ary relation, you have 2 possibilities for each of k^n possible n-ary lists. So what would be the total number of possible relation interpretations?


Not the answer you're looking for? Browse other questions tagged .