2
$\begingroup$

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
    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$.2010-12-06
  • 0
    Sorry, I didn't get the idea!!2010-12-06
  • 0
    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?2010-12-06
  • 0
    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 http://en.wikipedia.org/wiki/Signature_%28logic%292010-12-06
  • 0
    2^k is the number of subsets of a set with k elements2010-12-06

1 Answers 1