11.2 Quick review and some even Exercises

A relation $R$ on $A$ can have the following properties.

Reflexive: $xRx$ for every $x \in A$. Symmetric: Whenever $xRy$ there is also $yRx$. Transitive: Whenever $xRy$ and $yRz$ there is also $xRz$.

When trying to decide if a relation has a property, it may be easiest to look for evidence that it doesn't.

Not reflexive if: $xRx$ missing for any $x \in A$. Not symmetric if: $xRy$ but $yRx$ missing. Not transitive if: $xRy$ and $yRz$ but $xRz$ missing.

Proofs! Let's say that $R$ is a relation on $A$.

To prove $R$ is reflexive:

Assume $x$ is an element of $A$. [Use definition of $R$ to argue that $xRx$ is true.] Therefore, $R$ is reflexive.

To prove $R$ is symmetric:

Assume $xRy$. [Use definition of $R$ to argue that $yRx$ is true.] Therefore, $R$ is symmetric.

To prove $R$ is symmetric:

Assume $xRy$ and $yRz$. [Use definition of $R$ to argue that $xRz$ is true.] Therefore, $R$ is transitive.

Exercise 2: Consider the relation $R =\{ (a,b),(a,c),(c,c),(b,b),(c,b),(b,c)\}$ on the set $A = \{a,b,c\}$. Is $R$ reflexive? Symmetric? Transitive? If a property does not hold, say why.

Reflexive? Look for $(x,x) \notin R$. Symmteric? Look for an $(x,y)\in R$ where $(y,x) \notin R$. Transitive? Look for an $(x,y)$ and $(y,z)$ in $R$ where $(x,z) \notin R$.

Transitive is the hardest to check because you must find two pairs that link up. Here's the pseudocode I do in my head.

xxxxxxxxxx
   for (x,y) in R
      for (w,z) in R
         if y==w then
            if (x,z) not in R
               print "not transitive: (x,y) and (y,z) but no (x,z)"
               exit
   print "transitive. No counterexample found"

Solution 2: $R$ is not reflexive. As an example $(a,a)\notin R$. $R$ is not symmetric. As an example $(a,b) \in R$ but $(b,a)\notin R$. $R$ is transitive because there is no counterexample.

Exercise 6: Consider the relation $R=\{(x,x) \,:\, x \in \mathbb{Z}\}$. Is this $R$ reflexive? Symmetric? Transitive? If a property does not hold, say why. What familiar relation is this?

As an example of proving properties, I'll solve this problem by proving it has all three relations.

Proof that $R$ is reflexive: Assume $x$ is an integer. By definition of $R$, since $x \in \mathbb{Z}$, $(x,x)\in R$, so $R$ is reflexive.

Proof that $R$ is symmetric: Assume $(x,y) \in R$. Because the only elements in $R$ have the form $(x,x)$, this must mean $x=y$. But, since $(x,y) \in R$ and $x=y$ we know $(y,x) \in R$ too. Therefore $R$ is symmetric.

Proof that $R$ is trasitive: Assume $(x,y) \in R$ and $(y,z) \in R$. Because the only elements in $R$ have the form $(x,x)$, this must mean $x=y$ and $y=z$. But, since $(x,y) \in R$ and $y=z$ we know $(x,z) \in R$ too. Therefore $R$ is transitive.

Solution 6: $R$ is all three. Since integers are only related to themselves, it would seem that this relation is equality.