# A characteristic of intersection with cartesian product

Fix some binary relation $f$.

Does there necessarily exist a set $C$ such that $(x\times x)\cap f\ne \varnothing \Leftrightarrow x\cap C\ne \varnothing$ for all sets $x$?

-

Not necessarily.

Say $f=\{(a,b)\}$, with $a\neq b$, and assume such a set $C$ exists.

In particular, $\{a,b\}\cap C\neq\varnothing$, since $\{a,b\}\times\{a,b\}\cap f\neq\varnothing$. Hence either $a\in C$ or $b\in C$ (or both). If $a\in C$, then $\{a\}\cap C\neq\varnothing$, but $\{a\}\times\{a\}\cap f=\varnothing$. If $b\in C$, then $\{b\}\cap C\neq\varnothing$ but $\{b\}\times\{b\}\cap f=\varnothing$. So no such $C$ exists.

By the above argument, if $f$ contains a pair $(a,b)$ such that (i) $a\neq b$; and (ii) $(a,a)\notin f$; and (iii) $(b,b)\notin f$; then no such set $C$ can exist.

Conversely, suppose that for all $a,b$, if $(a,b)\in f$ then either $(a,a)$ or $(b,b)$ lies in $f$. I claim that then the set $C$ does exist, by letting $C$ consist precisely of those elements $r$ for which $(r,r)\in f$.

Indeed, suppose that $x$ is a set such that $x\times x\cap f\neq\varnothing$. Then there exist $a,b\in x$ such that $(a,b)\in f$; by assumption, either $(a,a)\in f$, and hence $a\in C$ so $x\cap C\neq\varnothing$; or else $(b,b)\in f$ and hence $b\in C$, so $x\cap C=\varnothing$.

Conversely, if $a\in x\cap C$, then by definition of $C$ we have $(a,a)\in f$, so $x\times x\cap f\neq \varnothing$.

In summary:

A set $C$ as given exists if and only if $f$ satisfies the condition $$(a,b)\in f\implies (a,a)\in f\text{ or }(b,b)\in f.$$

If that is the case, then $C=\{a\mid (a,a)\in f\}$ is the desired set; one can justify that $C$ is a set since it is contained in $\mathrm{dom}(f)\cup\mathrm{range}(f)$.

-