Proving reflexivity, symmetry and transitivity,..., on a relation on words

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

$\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.

Answer 4

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.