Proposition 1.Let $X$, $Y$ be non-empty sets and $R\subseteq X\times Y$ be a relation with domain $X$. $R$ is injective, if and only if
\[R\left[\bigcap S\right] = \bigcap_{A\in S} R[A]\]for all $S\subseteq P(X)$.
Proof.(“$\rightarrow$”) Assume $R$ is injective. Let $S\subseteq P(X)$.
- (“$\subseteq$”) Trivial.
- (“$\supseteq$”) Let $y\in\bigcap_{A\in S} R[A]$. Let $A\in S$, then there is an $x\in A$ such that $xRy$. But for every $A’\in S$ there is an $x’\in A’$ such that $x’Ry$. Since $R$ is injective, we have $x=x’$, hence $x\in A’$. This shows $x\in\bigcap S$, so $y\in R\left[\bigcap S\right]$.
(“$\leftarrow$”) Assume
\[R\left[\bigcap S\right] = \bigcap_{A\in S} R[A]\]for all $S\subseteq P(X)$. Let $x\in X$, then there is a $y\in Y$ such that $xRy$. Suppose $x’\in X$ and $x’Ry$. Since $\{x\}$, $\{x’\}\subseteq X$, the assumption gives us
\[R[\{x\}\cap\{x'\}] = R[\{x\}]\cap R[\{x'\}].\]Since $xRy$ and $x’Ry$, we have $y\in R[\{x\}]\cap R[\{x’\}]$, so $y\in R[\{x\}\cap\{x’\}]$. That means $\{x\}\cap\{x’\}$ is not empty, so we must have $x=x’$. Thus $R$ is injective. $\square$