Question

1. Let S be the set of all strings of English letters. Determine whether these relations are reflexive, irreflexive, symmetric, antisymmetric, and/or transitive.

a) R1 = {(a, b) | a and b have no letters in common}

b) R2 = {(a, b) | a and b are not the same length}

c) R3 = {(a, b) | a is longer than b}

Answer 1

a) Given, $R_{1}=\{(a, b) \mid a \text{~and~} b \text{~have no letters in common}\}$

Since a string cannot have common letters with itself, $R_{1}$ is not reflexive,

A string always has letters in common with itself, hence $R_{1}$ is irreflexive,

If string $a$ and $b$ have no letters in common, then strings $b$ and $a$ have no letters in common either. Therefore, $R_{1}$ is symmetric.

If string $a$ and $b$ have no letters in common and if string $b$ and $a$ also have letters in common, then strings $a$ and $b$ are not necessarily the same string.

For example, $uvw$ and $xyz$ have no letters in common while they are not the same string.

Hence $R_{1}$ is not antisymmetric.

If string $a$ and $b$ have no letters in common and if string $b$ and $c$ also have no letters in common, then strings $a$ and $c$ can contain common letters. For example, if $a = xyz, b = pqr \text{~and~} c = evx$ we see that string $a$ and $b$ have no letters in common and string $b$ and $c$ also have no letters in common, but strings $a$ and $c$ contains a common letter $x$. Thus, $R_{1}$ is not transitive.

b. Given, $R_{2}=\{(a, b) \mid a \text{~and~} b \text{~are not the same length} \}$

As a string always has the same length as itself, $R_{2}$ is not reflexive,

$R_{2}$ is irreflexive because a string always has the same length as itself.

$R_{2}$ is symmetric because if string $a$ and $b$ do not have the same length, then strings $b$ and $a$ do not have the same length.

$R_{2}$ is not antisymmetric because if string $a$ and $b$ do not have the same length and if string $b$ and $a$ also do not have the same length, then strings $a$ and $b$ are not necessarily the same string.

If string $a$ and $b$ do not have the same length and if string $b$ and $c$ do not have the same length, then strings $a$ and $c$ can have the same length. Hence $R_{2}$ is not transitive.

c. Given,

Since a string is never longer than itself, $R_{3}$ is not reflexive.

$R_{3}$ is irreflexive because a string is never longer than itself.

$R_{3}$ is not symmetric because if string $a$ is longer than $b$, then $b$ cannot be longer than $a$.

$R_{3}$ is antisymmetric because "$a$ is longer than $b$ and $b$ cannot be longer than $a$" cannot be true except when $b= a$.

$R_{3}$ is transitive because if string $a$ is longer than $b$ and if string $b$ is longer than $c$, then string $a$ has to be longer than $c$.