For an arbitrary set M there is a relation $R \subseteq 2^M \times 2^M$ about $$ A \mathrel R B \Leftrightarrow A \cup \{x\} = B$$ The join is a disjoint join. There are not more details what is $x$.

Show that $R^*$, the reflexive and transitive hull of R is a order relation.

So I have to show, that $R^*$ is reflexive, transitive and anti-symmetric.

I'm a little confused.

To show that $R^*$ is reflexive: Let $a \in A$ and $a \in B$. How can $(a,a)\in R^*$. For this case a have to be $x$. Or do I understand something wrong? I really have problems understanding what I should do now, though I know what reflexive, transitive and antisymmetric means. How do I write it down formally correct?

This is an old exercise. Please give me not a complete solution, just a hint. Perhaps the reflexive part.


1 Answer 1


Since the union is specified be a disjoint union, $R$ is not itself reflexive: you cannot choose $x\in A$, since in that case $A$ and $\{x\}$ are not disjoint. In fact $A\,R\,B$ if and only if $B$ is obtained from $A$ by adding one extra element of $M$ that was not in $A$.

I would begin by taking the reflexive closure of $R$, which I’ll call $R^+$: $$R^+=R\cup\left\{\langle A,A\rangle:A\in 2^M\right\}\;,$$ so for $A,B\in 2^M$ we have $A\,R^+\,B$ if and only if $A\subseteq B$ and $|B\setminus A|\le 1$. What needs to be added to $R^+$ to get the transitive closure $R^*$ of $R^+$? It’s a standard result that it’s obtained by adding $R^+\circ R^+$, $R^+\circ R^+\circ R^+$, and so on, so that

$$R^*=\bigcup_{n\ge 1}(R^+)^n\;,$$

where $(R^+)^1=R^+$ and $(R^+)^{n+1}=(R^+)^n\circ R^+$ for each $n\ge 1$. For $n\ge 1$ let $$R_n=\bigcup_{k=1}^n(R^+)^k$$ and show by induction on $n$ that for any $A,B\in 2^M$, $A\,R_n\,B$ if and only if $A\subseteq B$ and $|B\setminus A|\le n$. It follows that $A\,R^*\,B$ if and only if $A\subseteq B$ and $B\setminus A$ is finite. Writing this in the same style as the original definition of $R$, we can say that $A\,R^*\,B$ if and only if there is a finite $F\subseteq M$ such that $A\sqcup F=B$, where $\sqcup$ denotes disjoint union.

By construction $R^*$ is reflexive and transitive, so all that remains is to show that $R^*$ is antisymmetric, but that’s immediate: if $A\,R^*\,B$ and $B\,R^*\,A$, then $A\subseteq B$ and $B\subseteq A$, so $A=B$.

  • $\begingroup$ But x must be an element of M so that this exercise/proof makes sense, right? $\endgroup$
    – Elternhaus
    Dec 11, 2013 at 8:42
  • $\begingroup$ @Elternhaus: Yes, everything is taking place in $M$. $\endgroup$ Dec 11, 2013 at 8:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .