= Second-order relation variable
{title2=$R^{(k)}$}
A <second-order relation variable> of arity $k\ge1$ can be assigned a <subset> of the $k$-fold <Cartesian product> $D^k$; its application $R(x_1,\ldots,x_k)$ is true exactly when the <tuple> $(x_1,\ldots,x_k)$ belongs to that <subset>. Arity is the number of arguments, so a unary <second-order relation variable> is a predicate on individual objects. For a <finite set> $D$ of <cardinality> $n$, there are $n^k$ possible <tuples> and $2^{n^k}$ possible relations under <full semantics for second-order logic>. A relation is encoded by $n^k$ membership bits once the objects have been numbered; the number of possible witnesses can be exponential even when each witness has a short encoding.
Back to article page
