0

Given R is a relation, I need to prove 2 things.

1) $R^+=R \ ;R^* $

2) $R^*=I \cup R^+$

For (1) I proceeded as

$ \Rightarrow R^+$

$ \Rightarrow \bigcup\limits_{n=1}^\infty R^n \qquad \qquad \qquad $ {definition of $R^+$}

$ \Rightarrow \bigcup\limits_{n=1}^\infty R \ ; R^{n-1} \qquad \qquad $ {definition of composition}

$ \Rightarrow R\ ; \Bigg(\bigcup\limits_{n=1}^\infty R^{n-1} \Bigg)$

$ \Rightarrow R\ ; \Bigg(\bigcup\limits_{n=0}^\infty R^{n} \Bigg) \qquad \qquad $ {renaming}

$ \Rightarrow R \ ; R^* $

But I am not sure how to tackle the 2nd one i.e. $R^*=I \cup R^+$

TechJ
  • 295

1 Answers1

1

For (1) note, that for example "$R^+$" is not a statement, but an object, namely a relation, so the implication arrow "$\Rightarrow$" does not make sense, you need an equals sign instead, that is $$ R^+ = \bigcup_{n\ge 1} R^n = \text{... and so on} $$ otherwise you are right.

For (2) you can proceed along the same line of thought (it's just the other way round): \begin{align*} R^* &= \bigcup_{n=0}^\infty R^n & \text{Definition}\\ &= R^0 \cup \bigcup_{n=1}^\infty R^n & \text{property of union}\\ &= R^0 \cup R^+ & \text{Definition of $R^+$}\\ &= I \cup R^+ \end{align*}

martini
  • 84,101