Return to Question

Given an algebraic theory (whose equations involve only expressions of depth at most 2) and a natural number \$n\$, compute the number of non-isomorphic models of order \$n\$.

Given an algebraic theory (whose equations involve only expressions of depth at most 2) and a natural number \$n\$, compute the number of distinct models of order \$n\$, up to isomorphism.

Let's take a quick example. A monoid is such an algebraic structure. We need to have one function \$f_1\$, with \$s_1=2\$. There is just one equational relationship: \$f_1(f_1(x, y), z) = f_1(x, f_1(y, z))\$.

We are interested in models of the algebraic theories. A model, simply put, is just an implementation of the functions. We choose an underlying set \$M\$, and we implement the required functions \$f_i\$ as taking \$s_i\$ arguments from the set \$M\$, and returning an element of \$M\$, so that the equations hold when you plug in any element of \$M\$ for the variables. For example, if we take \$M = \{0,1,2\}\$, and \$f_1\$ to be the addition modulo 3, we get a model for the monoid. The order of a model is simply the size of \$M\$. So the model above has order 3.

Input: The theory of monoids. There is one function f taking 2 arguments.

f(f(x, y), z) = f(x, f(y, z))

n = 2.

Output: 4.

Now we need to make sure they are all non-isomorphic. In fact, the two constant functions are isomorphic, since the relabelling that swaps 0 and 1 converts between them. Also, and and nand are equivalent by that relabelling. So we've got 4 different possibilities.

Let's take a quick example. A semigroup is such an algebraic structure. We need to have one function \$f_1\$, with \$s_1=2\$. There is just one equational relationship: \$f_1(f_1(x, y), z) = f_1(x, f_1(y, z))\$.

We are interested in models of the algebraic theories. A model, simply put, is just an implementation of the functions. We choose an underlying set \$M\$, and we implement the required functions \$f_i\$ as taking \$s_i\$ arguments from the set \$M\$, and returning an element of \$M\$, so that the equations hold when you plug in any element of \$M\$ for the variables. For example, if we take \$M = \{0,1,2\}\$, and \$f_1\$ to be the addition modulo 3, we get a model for the semigroup. The order of a model is simply the size of \$M\$. So the model above has order 3.

Input: The theory of groupoids. There is one function f taking 2 arguments.

f(f(x, y), z) = f(x, f(y, z))

n = 2.

Output: 5.

Now we need to make sure they are all non-isomorphic. In fact, the two constant functions are isomorphic, since the relabelling that swaps 0 and 1 converts between them. So we've got 5 different possibilities.