1
$\begingroup$

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 Answers 1

2

(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.

  • 0
    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.2011-07-12