Well it is certainly the case that there is no set number of structures we can apply to a set there is a set number of structures in all the other classes described in the above ontology. The number of families of sets over a set is $2^{2^n}$. The number of N-ary relations over a set is $2^{n^k}$ which in the case of unary relations is $2^n$, in the case of binary relations is $2^{n^2}$, and in the case of ternary relations is $2^{n^3}$.
Some species although different from other species have the same growth rates as them. Coreflexive relations have a growth rate of $2^n$ like unary relations because both of them involve picking out subsets of a set. This leads to a natural bijection between unary relations and coreflexive binary relations based upon membership so for example the unary relation $\{(1), (2), (3)\}$ might go to the binary relation $\{(1, \; 1), (2, \; 2), (3, \; 3)\}$.
We can get the growth rates for a variety of other classes of structures. For reflexive relations we get $2^{n^2 -n}$, for symmetric relations we get $2^{\frac{n^2}{2}+\frac{n}{2}}$, for independency relations we get $2^{\frac{n^2}{2} - \frac{n}{2}}$, for antisymmetric relations we get $2^n 3^{\frac{n^2}{2}+\frac{n}{2}}$, for asymmetric relations we get just $3^{\frac{n^2}{2}+\frac{n}{2}}$, for functions we get $(n+1)^n$, and for binary operations we get $(n+1)^{2^{n}}$.
Each of these growth rates can be expressed as transseries, for example, $(n+1)^{2^{n}}$ can be expressed as $e^{\log(x+1)e^{\log(2)x}}$. The ontological order is a suborder of the asymptotic order on the collection of species as every subspecies of some other species has a smaller growth rate then its parent species.
No comments:
Post a Comment