7
$\begingroup$

This is an extension of this question, suggested by Noah Schweber.

Suppose I have some set of relations $(R_i)_{i\in I}$ over a set $D$: $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.

Noah defines a relation $R$ to be set-ary iff, whenever $\{x_1,...,x_n\} = \{y_1,...,y_n\}$ then $(x_1,...,x_n)\in R$ if and only if $(y_1,...,y_n)\in R$.

I would like to know if there is always a set of set-ary relations from which $(R_i)_{i\in I}$ are first-order definable. For example, can $<$ on $\mathbb{Z}$ be defined by set-ary relations?

$\endgroup$
6
$\begingroup$

Any unary or symmetric binary relation is set-ary. Thus, to provide an affirmative answer to the question, for domains $D$ with at least 3 elements, it suffices to show that any relation on such a domain is definable from unary and symmetric binary relations.

Case 1. $D$ is finite but has at least $3$ elements.

In this case, any relation on $D$ is p.p.-definable from unary relations and equivalence relations. To see this, let $\Omega$ be the set of all unary relations and equivalence relations on $D$. It is not hard to see that the only polymorphisms $f:\langle D; \Omega\rangle^k\to \langle D; \Omega\rangle$ are the projection maps. This implies that any finitary relation on $D$ is p.p.-definable from $\Omega$, according to the results of

Bodnarcuk, V. G.; Kaluznin, L. A.; Kotov, V. N.; Romov, B. A.
Galois theory for Post algebras. I, II.
Kibernetika (Kiev) 1969, no. 3, 1–10; ibid. 1969, no. 5, 1-9.

Case 2. $D$ is infinite.

Let $R$ be a $k$-ary relation on $D$. Partition $D$ into $k+1$ subsets of equal size, $D_0, D_1, \ldots, D_k$. For each $k$-tuple, $t=(i_0,\ldots,i_{k-1})\in \{0,\ldots,k\}^k$ I will explain how to define $$R_t = R\cap (D_{i_0}\times \cdots \times D_{i_{k-1}}).$$ Then $R$ can be defined as the union of the $R_t$'s.

Let $E = D_j$ for some $D_j$ different from any of $D_{i_0}, \ldots, D_{i_{k-1}}$. This is possible, since there are more than $k$ of the $D_j$'s. Now choose an injection $f:R_t\to E$. It is easy to check that $|R_t|\leq |D|=|E|$, so this is possible.

For any $r=(r_0,\ldots,r_{k-1})\in R_t$, and any $i<k$, put the pairs $(r_i, f(r)), (f(r), r_i)$ into a relation $S_i$. Put no other pairs in $S_i$.

The relation $R_t$ is definable from the unary relation $E$ and symmetric binary relations $S_i$. Namely, $(r_0,\ldots,r_{k-1})\in R_t$ iff $r_i\notin E$ for any $i$, and, $\exists e\in E$ such that $(r_i,e)\in S_i$ for each $i$. \\\


The unary relations and the symmetric binary relations are not enough to p.p.-define all relations on a $2$-element domain. For example, you can't p.p.-define $$\{(0,0,1), (0,1,0), (1,0,0)\}.$$ But you can p.p.-define all relations on the $2$-element domain from set-ary unary and ternary relations by an argument like the one for Case 1

$\endgroup$
  • 1
    $\begingroup$ The proof in case 1 seems overkill - just pin down each element $e$ by a unary relation $U_e$ holding on exactly that element, and define an arbitrary finite-arity relation $R$ as $$R(x_1,...,x_n)\iff\bigvee_{R(y_1,...,y_n)}(U_{y_1}(x_1)\wedge ...\wedge U_{y_n}(x_n)).$$ Or am I missing something? (I also don't understand why this wouldn't get you all relations on a $2$-element domain - are you using a more restrictive notion of "definability?") $\endgroup$ – Noah Schweber Feb 26 at 4:08
  • $\begingroup$ I should have said: I was going for p.p.-definability on finite domains (because I could), but first-order definability on infinite domains. (I just edited my answer to say this.) $\endgroup$ – Keith Kearnes Feb 26 at 4:13
  • $\begingroup$ Ah, sorry, I read too quickly. "PP-definable" means "definable by an existential quantification over a conjunction of positive relation instances," right? $\endgroup$ – Noah Schweber Feb 26 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.