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.

The relation R ,$uRv$ is defined iif a word u is the suffix of a word v. u is a suffix of v if there exist another word w such that $v = wu $

I have to verify the 6 following relations.

  1. Reflexive : Yes because $wu = wu$
  2. Symmetric : No because $v = wu$ , $u \ne wu$
  3. Transitive : Yes , example : u="to", v="potato" and u2="otato", v="potato" and uRu2
  4. Asymmetric : No, v = wu, v $\ne$ u , except if w is an empty word
  5. Antisymmetric : No. ex: "to" R "potato" but "to" $\ne$ "potato"
  6. Irreflexive : No. ex: $wu = wu$.

Can you help me for those that are incorrect

share|improve this question
add comment

4 Answers 4

up vote 2 down vote accepted

Here a few comments/corrections. (I am assuming that the empty word $\lambda$ is included, otherwise some answers are different.)

  1. Reflexive: $\newcommand{\R}{\operatorname{R}} u\R u$ for all $u$. The relation is reflexive because any word is a suffix of itself. (Letting $\lambda$ denote the empty string, $w = \lambda w$.)
  2. Symmetric: The relation is not symmetric, which you ought to demonstrate with a counterexample. For example, with $u =$ "at" and $v =$ "cat", $u \R v$. However, $\newcommand{\notR}{\!\not{\!\!\R}} v \notR u$ as "cat" is not a suffix of "at".
  3. Transitive: You need to show that if $u \R v$ and $v \R w$ then $u \R w$ for all $u$, $v$, and $w$. Unpackage the definition: $v = xu$ for some $x$ and $w = yv$ for some $y$. Now, $w = y(xu) = (yx)u$, showing that $u \R w$.
  4. Asymmetric: The relation is not asymmetric, since $u \R u$.
  5. Antisymmetric: You need to show that if $u \R v$ and $v \R u$ then $u = v$. Using the definition of the relation, $v = xu$ for some $x$ and $u = yv$ for some $y$. Thus, $v = x(yv) = (xy)v$, so $xy = \lambda$, which implies that $x = y = \lambda$. (There's no cancellation possible in concatenating strings.)
  6. Irreflexive: The relation is reflexive, so it cannot be irreflexive.
share|improve this answer
add comment

I think you might have got some of the definitions of the properties wrong.

For the reflexive property, you need to prove that $uRu$ for all words $u$. That is, you need to show that there is a word $w$ such that $u = wu$. The equality holds if $w$ is the empty word, regardless of what word $u$ is, so the relation is reflexive.

A relation is symmetric if $uRv$ implies $vRu$ for all words $u$ and $v$. If we can find a pair of words $u$ and $v$ such that only one of these holds, the relation is not symmetric. Let $u = \text{otato}$ and $v = \text{potato}$. Clearly, $u$ is a suffix of $v$ but not the other way around, so the relation is not symmetric.

The transitive property states that if $tRu$ and $uRv$ then $tRv$ for all words $t$, $u$, and $v$. A single example is not enough to prove that the relation has this property; we need to generalize the reasoning. Using the definition of the relation, $tRu$ and $uRv$ means that there are words $w_1$ and $w_2$ such that $u = w_1t$ and $v = w_2u$. It follows that $v = w_2w_1t$. Seeing as $w_2w_1$ is a word (of course), the relation is transitive.

For the asymmetric property, you need to show that if $uRv$, then $v\not Ru$ for all words $u$ and $v$. Note that the relation cannot have this property, because it is reflexive: both $uRu$ and $u \not R u$ cannot hold.

The antisymmetric property is a little tricky. It states that if both $uRv$ and $vRu$, then $u = v$ for all words $u$ and $v$. Using the definition of the relation again, $uRv$ and $vRu$ means that there are words $w_1$ and $w_2$ such that $v = w_1u$ and $u = w_2v$. In other words, $v = w_1w_2v$, so $w_1w_2$, and thus $w_1$ and $w_2$ as well, must be the empty word. This means that $u = w_2v = v$, and so the antisymmetric property holds.

Finally, the irreflexive property states that $uRu$ does not hold for any word $u$. This is clearly not the case; we showed that it holds for all words earlier! In other words, the relation is not irreflexive.

share|improve this answer
add comment

Show reflexivity using the empty word. Your proof isn't correct there.

For symmetry, specify that if $w$ is non-empty, then $u\:R\:wu$ but it is not the case that $wu\:R\:u$.

Your example for transitivity is good, but you want a more general argument. If $u\:R\:v$ and $v\:R\:w$, then there exist words $w_1,w_2$ such that $v=w_1u$ and $w=w_2v$. Now, $w_2w_1$ is a word, and $w=w_2w_1u$, so $u\:R\:w$.

A (non-empty) reflexive relation cannot be asymmetric, nor can it be irreflexive. (Why?) This should suggest how to show that $R$ is not asymmetric or irreflexive.

Actually, your relation is antisymmetric. You must show that if $u$ is a suffix of $v$ and $v$ is a suffix of $u,$ then in fact $u$ and $v$ are the same word. Think on it a bit.

share|improve this answer
add comment

$\forall u,v, \left [uRv \Leftrightarrow \exists w,v=wu\right]$


Reflexive

Property

$\forall u, u R u$

Property for this specific relation

$\forall u, \exists w, u = wu$

Proof it is true

We can take $w=\varepsilon$


Symmetric

Property

$\forall u,v, \left[uRv \Rightarrow vRu \right]$

Property for this specific relation

$\forall u,v,\left[\left[\exists w_1, v=w_1u\right] \Rightarrow \left[\exists w_2, u = w_2v\right] \right]$

Proof it is false

Take some non-empty word $x$

We have $\varepsilon R x$ by taking $w_1=x$

But we do not have $xR\varepsilon$ because $\forall w_2, \left|\varepsilon\right|<\left|x\right|\le \left|w_2x\right|$ so $\varepsilon\not= w_2x$


As you can see, you have an existence implying another existence. So to prove it you just need to exhibit a word working but if you want to disprove it, you need to show that no word works. I think your major problem was that you thought $w_1$ and $w_2$ had to be the same. They don't. Now try redoing your exercise with that in mind. If you still can't do it, I can give details for all properties but you would learn much more from it if you did it yourself.

And when I say "exhibit a word", I mean a word that depends on $u$ because the thing you did, taking the example "potato" to prove a property you want for all words isn't a valid way of doing it. Either you take an unspecified couple of words that verify your relation and show that you can find the $w$ for the other words (that depend on the property you try to prove) to verify the relation too to prove that it is true. Or you take a specific couple of words and prove that you cannot find a $w$ for the other couple of words to verify your relation to prove it is false.

share|improve this answer
add comment

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.