Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.