Универсальное отношение

Если ${\displaystyle U=U_{X}}$ — универсальное отношение на множестве ${\displaystyle X}$, то для произвольных бинарных отношений ${\displaystyle R,S}$ на ${\displaystyle X}$ имеет место равенство

${\displaystyle R\circ U\circ S=\operatorname {pr} _{1}(R)\times \operatorname {pr} _{2}(S),\quad \quad \quad \quad (*)}$

где ${\displaystyle \operatorname {pr} _{1}}$ и ${\displaystyle \operatorname {pr} _{2}}$ обозначают соответственно первую и вторую проекции бинарного отношения^[a].

Верно и обратное: если ${\displaystyle U}$ — такое бинарное отношение на ${\displaystyle X}$, что для произвольных бинарных отношений ${\displaystyle R,S}$ на ${\displaystyle X}$ имеет место ${\displaystyle (*)}$, то ${\displaystyle U}$ — универсальное отношение на ${\displaystyle X}$. (Для доказательства достаточно положить ${\displaystyle R=S=\Delta _{X}}$, где ${\displaystyle \Delta _{X}=\{(x,x):x\in X\}}$ — отношение равенства на ${\displaystyle X}$.)

Если в равенстве ${\displaystyle (*)}$ положить ${\displaystyle R=\Delta _{X}}$ или ${\displaystyle S=\Delta _{X}}$, то соответственно получатся равенства:

• ${\displaystyle R\circ U=\operatorname {pr} _{1}(R)\times X}$;
• ${\displaystyle U\circ S=X\times \operatorname {pr} _{2}(S)}$.

Как и равенство ${\displaystyle (*)}$, каждое из них являются определяющим для универсального отношения ${\displaystyle U}$.

В более общем случае, универсальным бинарным отношением между множествами ${\displaystyle X}$ и ${\displaystyle Y}$ называют отношение ${\displaystyle U}$, определённое условием^[5]

${\displaystyle xUy}$ для всех ${\displaystyle x\in X}$, ${\displaystyle y\in Y}$,

то есть ${\displaystyle U=X\times Y}$.

Равенства из предыдущего раздела сохраняют силу и для этого случая. Более точно, пусть ${\displaystyle U=X\times Y}$ — универсальное отношение между ${\displaystyle X}$ и ${\displaystyle Y}$, тогда:

• ${\displaystyle R\circ U\circ S=\operatorname {pr} _{1}(R)\times \operatorname {pr} _{2}(S)}$ для произвольных множеств ${\displaystyle W}$, ${\displaystyle Z}$ и бинарных отношений ${\displaystyle R\subseteq W\times X}$ и ${\displaystyle S\subseteq Y\times Z}$;
• ${\displaystyle R\circ U=\operatorname {pr} _{1}(R)\times Y}$ для произвольных множества ${\displaystyle W}$ и бинарного отношения ${\displaystyle R\subseteq W\times X}$;
• ${\displaystyle U\circ S=X\times \operatorname {pr} _{2}(S)}$ для произвольных множества ${\displaystyle Z}$ и бинарного отношения ${\displaystyle S\subseteq Y\times Z}$.

Каждое из этих свойств является определяющим для универсального отношения ${\displaystyle U}$.

В самом общем случае универсальным ${\displaystyle n}$-арным отношением между множествами ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ называют ${\displaystyle n}$-арное отношение, состоящее из всех возможных кортежей ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$, то есть совпадающее с декартовым произведением ${\displaystyle X_{1}\times X_{2}\times \ldots \times X_{n}}$.