I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Relations and Functions. To be specific, I'm stuck on the following practice question:
Let A = {a, b, c, d}. Give an example of a relation R on A^2 which is
reflexive, symmetric and not transitive. Explain.
I don't really understand how to do reflexive etc., how would I find the resulting relation? Any help is appreciated! Thanks.
On
One approach to this is to write out the relation's matrix: a $4 \times 4$ matrix with $1$s where the relation holds, and $0$s where it doesn't. A reflexive relation must have $1$s along the diagonal, and a symmetric relation must have a symmetric matrix.
A transitive relation, on the other hand, has the following property: If there are $1$s in $(i, j)$ and $(j, i)$, and also in $(j, k)$ and $(k, j)$, then there must also be $1$s in $(i, k)$ and $(k, i)$. Can you find a $4 \times 4$ matrix that has $1$s along the diagonal, and is symmetric, but does not have the transitive property?
On
Hint One can think of a reflexive, symmetric relation $\sim$ on a set $X$ as a simple graph whose vertices are the elements of $X$ and which, for each pair $x, y$ of distinct vertices, has an edge between $x$ and $y$ iff $x \sim y$ (or equivalently, since $\sim$ is symmetric $y \sim x$). Unwinding the definitions, a relation is transitive if whenever $x$ and $y$ are connected by an edge and $y$ and $z$ are likewise connected by an edge, then so are $x$ and $z$.
On
$A^2$ itself is a relation on $A^2$.
Evidently it is reflexive, symmetric and transitive so to achieve a non-transitive relation we simply must delete pairs.
The demand of reflexivitiy forbids us to delete pairs on the diagonal.
Well, let's "take out" $\langle a,b\rangle$ then.
Wait a minute... In order to spare symmetry we are forced to take out $\langle b,a\rangle$ as well.
What remains is the reflexive and symmetric relation $R=A^2-\{\langle a,b\rangle,\langle b,a\rangle\}$.
Is this relation transitive? No: $\langle a,c\rangle\in R\wedge \langle c,b\rangle\in R$, but $\langle a,b\rangle\notin R$.
Since you have a finite set of 4 elements, you can draw the relation as a directed graph: draw a "node" for each of the elements $a, b, c, d$ – a circle with the element's name in it. Then draw directed "edges" indicating which elements are related: draw an arrow from, say, node $a$ to node $b$ if $a R b$ (that is, $(a,b) \in R$).
A relation $R$ on $A$ is reflexive iff every $x \in A$ bears $R$ to itself. So $R$ is reflexive iff every node has an arrow from itself to itself (a loop).
$R$ is symmetric iff whenever there's an arrow from one $n_1$ node to another node $n_2$, there's also an arrow in the opposite direction, from $n_2$ to $n_1$.
Finally, $R$ is transitive iff whenever there are arrows $n_1 \to n_2 \to n_3$, there's also an arrow $n_1 \to n_3$.
For $R$ to not be reflexive, some element (at least one) $x \in A$ has to not bear the relation to itself. For $R$ to not be symmetric, there just has to be some pair of elements $x, y \in A$ such that $xRy$ but not $yRx$. For $R$ to not be transitive, the condition just has to fail for some $x, y, z \in A$: for example, $aRb$ and $bRc$ but not $aRc$.
Examples among people (or cats) of symmetric relations: "is the same height as", "are siblings", "are related", "are the same gender"; examples of relations that are not transitive: "is 1 inch shorter than", "is 2 years younger than", "is a parent of"; examples of transitive relations: "is shorter than", "is younger than", "is an ancestor of".