Kleene Star operation on sets

1.1k Views Asked by At

I have the following question, and do not understand the Kleene star operation in the context of relations.

Let R be the relation $R=\{(0,1),(0,2),(1,4),(1,5),(2,3),(2,4),(2,5)\}^*$ on the set $A=\{0,1,2,3,4,5\}$. Find all minimal, maximal, smallest and largest elements, if possible, of set A with regards to relation R.

We have only defined the Kleene star operation in the context of formal languages. Namely $V^* = \bigcup_{i\in \mathbb{N}} A^n$, where $A^n$ is defined recursively as $V^0 = \{\epsilon\}$, V is the set of all strings of length 1 and $V^{i+1} = \{vw : w\in V^i \wedge v\in V\}$.

Does the Kleene star have it's own definition when used with sets? What does the above set R mean? I assume it somehow affects the maximal elements and largest element of the given set. Could someone please clarify this for me?

1

There are 1 best solutions below

2
On BEST ANSWER

My best guess is that the author is using this notation to denote the transitive closure of the relation $\{\langle 0,1\rangle,\langle 0,2\rangle,\langle 1,4\rangle,\langle 1,5\rangle,\langle 2,3\rangle,\langle 2,4\rangle,\langle 2,5\rangle\}$. That is, it represents repeated composition rather than repeated concatenation. On that interpretation you do get a relation for which the question makes good sense.