1

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)

closed as off-topic by Ram Tobolski, Keelan, Five σ, James Kingsbery, Swami Vishwananda Apr 7 '15 at 5:03

  • This question does not appear to be about philosophy within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

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

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 or ask your own question.