# Existence of the $P$ closure of binary relation $R$

From wikipedia, for an arbitrary binary relation $R\subseteq S×S,$ and an arbitrary property $P$, the $P$ closure of $R$ is defined as:

The least relation $Q\subseteq S×S$ that contains $R$ (i.e. $R\subseteq Q$) and for which property $P$ holds (i.e. $P(Q)$ is true).

For instance, the symmetric closure is the least symmetric relation containing $R$, the reflexive transitive closure $R$* is the smallest preorder containing $R$, and the reflexive transitive symmetric closure $R\equiv$ is the smallest equivalence relation containing $R$.

For arbitrary $P$ and $R$, the $P$ closure of $R$ need not exist. In the above examples, these exist because reflexivity, transitivity and symmetry are closed under arbitrary intersections. In such cases, the $P$ closure can be directly defined as the intersection of all sets with property $P$ containing $R$.

1. I was wondering what are some examples of properties $P$ that are not closed under arbitrary intersections?
2. Is property $P$ being closed under arbitrary intersections the sufficient and necessary condition for existence of the $P$ closure of an arbitrary relation $R$?

Thanks and regards!

-

(1) Say that a relation $R$ on a set $S$ has a cycle if there are an integer $n \ge 1$ and distinct elements $s_0,s_1,\dots,s_n \in S$ such that $\{\langle s_n,s_0 \rangle\} \cup \{\langle s_k,s_{k+1} \rangle:k=0,1,\dots,n-1\} \subseteq R$, and let $P$ be the property of having a cycle. Let $R = \{\langle n,n+1 \rangle:n \in \mathbb Z\}$, a relation on $\mathbb Z$. For each $n \in \mathbb Z$ the relation $R_n = R \cup \{\langle n,n-1 \rangle\}$ has a cycle, namely, $\{\langle n,n-1 \rangle, \langle n-1, n \rangle\}$, but obviously $R = \bigcap\limits_{n \in \mathbb Z} R_n$ does not. Thus, this $P$ is not closed under intersections, and $R$ has no $P$-closure. (In this case each $R_n$ is a minimal relation containing $R$ with property $P$, but there is no minimum relation of this kind.)

(2) Yes, with one small caveat noted in the edit. Suppose that $R$ has a $P$-closure $\overline{R}$. Then by definition $\overline{R} \subseteq T$ whenever $T$ is a relation on $S$ containing $R$ and having property $P$, and $\overline{R}$ is itself such a relation, so $$\overline{R} = \bigcap\{T\subseteq S \times S:R \subseteq T\text{ and }T\text{ has }P\}.$$

Conversely, if $P$ is closed under intersections, then $\bigcap\{T\subseteq S \times S:R \subseteq T\text{ and }T\text{ has }P\}$ is clearly the smallest relation on $S$ containing $R$ and having $P$, so it is the $P$-closure of $R$.

Edit: As ccc points out, in the ‘Conversely’ part of the argument it is necessary to assume that $\{T\subseteq S \times S:R \subseteq T\text{ and }T\text{ has }P\}$ is non-empty.

-
In (2) don't you need there to be at least one $T$ containing $R$ which satisfies $P$ in order for the argument of the intersection to be nonempty? For example, $P$ could be "is a graph with at most one edge," which is closed under intersection, but there's no closure of a graph with two edges. – user83827 Jul 11 '11 at 22:30
@ccc: You’re quite right; I’ve edited the answer accordingly. – Brian M. Scott Jul 11 '11 at 22:37
I do not understand. "Property" as it seems to be defined in this game is a general notion defined on all relations on $S$. We will not be able to make inferences about general intersection properties of $P$ from its intersection behaviour on relations that contain $R$. – André Nicolas Jul 11 '11 at 23:24
@user6312: $R$ is arbitrary. The point is that every relation has a $P$-closure iff $P$ is closed under intersections and every relation is contained in one with $P$. – Brian M. Scott Jul 12 '11 at 19:59
I interpreted half of Question $2$ as meaning of a given relation. It is certainly reasonable to interpret it as "of all relations", and that was the probable intent, in which case there is no issue. – André Nicolas Jul 12 '11 at 20:12