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$

1 Answer 1

6
+50
$\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$
3
  • 2
    $\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$ Feb 26, 2019 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$ Feb 26, 2019 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$ Feb 26, 2019 at 4:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .