2
$\begingroup$

As there is limit for title to put the full question, I will put the full question below.

Question: Given $R$ and $S$ are relations on $A = \{1,2,3,4\}$ such that $R = \{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,4)\}$ and $S = \{(1,1),(1,3),(3,4)\}$...

  1. Is $R$ reflexive? Transitive? Symmetric?
  2. Find $S \circ R$ and $S \circ S$.

Well..Since $1$ from set $A$ is not included in set $R$, can I straightly say that since $1$ is not included in $R$ so $R$ is none of the symmetric, transitive and reflexive?

And also are $S \circ R = \{(2,4),(3,4)\}$ and $S\circ S = \{(1,1),(1,4)\}$?

$\endgroup$
1
$\begingroup$

$ \newcommand{\CC}{\mathcal{C}} $ Observe that, if we represent your initial relations $R,S$ as a directed graph (where $x$ points to $y$ iff $(x,y) \in R$ or $S$, depending on the relation), then we have these graphs respectively:

enter image description here

In graphs like these, certain properties can be intuitively and visually observed:

  • Reflexivity appears if every node points to itself.
  • Symmetry happens if, whenever $x$ points to $y$ (and thus a path exists), then $y$ points to $x$ (and thus a path to "backtrack" exists). Basically, there are no "stray," one-way edges - only closed loops.
  • Transitivity is visible when, if there exists paths $x$ to $y$ and $y$ to $z$, then there is a path $x$ to $z$. For distinct nodes, then this means that, whenever two sides of a triangle are filled in, the last one is too, though the direction depends on the direction of the other sides in question.
  • Your equivalence classes are all of the nodes in each of the disjoint graphs you have. (Two graphs are disjoint if, basically, one is entirely separate from another, totally isolated.)

Is $R$ reflexive? Transitive? Symmetric?

  • $R$ is not reflexive, since $1$ is not pointing to itself, i.e. $(1,1) \not \in R$.
  • $R$ is not symmetric, since while $2$ and $3$ point to $4$, they do not point back. That is, $(2,4) \in R$ but $(4,2) \not \in R$; similarly, $(3,4) \in R$ but $(4,3) \not \in R$.
  • $R$ is transitive, since every necessary "triangle" is closed, with the third side always pointing in the right direction.

Note that the three properties above are independent of each other, to some degree. A relation can be any one of these while not the others. For instance

enter image description here

Also note that "$R$ is not reflexive" is not necessarily the same as "$R$ is irreflexive", and similar for symmetry and antisymmetry. A relation can be both, or neither, or one, or the other.

Note in particular: while $(1,1) \not \in R$ shows that $R$ is not reflexive, it does not show symmetry or transitivity (or, rather, the lack thereof), because $(x,1),(1,x) \not \in R$ for any $x \in A$ in the first place, so it's not really a concern.


Find $S \circ R$ and $S \circ S$.

Personally, when possible, I like to approach this sort of problem visually. Write out the elements of the relevant set, in columns -- three for any given composition of relations, but since we're finding multiple compositions we can do this more compactly with four columns to find both compositions.

For convenience, I will also label the columns $\mathcal C_i$, for $i=1,2,3,4$. Then, in the gaps between $\CC_1$ and $\CC_2$, draw arrows between the two, where $x$ in $\CC_1$ points to $y$ in $\CC_2$ if and only if $(x,y) \in R$. Next, draw arrows similarly in the gap for $\CC_2$ and $\CC_3$ representing the relation $S$: $x$ in $\CC_2$ points to $y$ in $\CC_3$ if and only if $(x,y) \in S$. Do this exact same thing for the next column.

In short: the arrows in the first gap represent the first "mapping" for the relation under $R$, and those in the subsequent gaps represent that for $S$. As you might imagine, following from $\CC_1$ to $\CC_3$ gives you $S \circ R$; followings from $\CC_2$ to $\CC_4$ gives you $S \circ S$. (This in particular might be more intuitive if you read $S \circ R$ as "$S$ after $R$," for instance, and think about function composition - in a definition sense, functions are just special relations.)

Anyhow, the diagram you get for your case is this:

enter image description here

You might be guessing what comes next. Essentially, if $x$ in $\CC_1$ points to $y$ in $\CC_2$, and then to $z$ in $\CC_3$, then $(x,z) \in S \circ R$. Or put differently: if there is a path from $x$ in $\CC_1$ to $z$ in $\CC_3$ you can walk along, then $(x,z) \in S \circ R$.

Similarly, the existence of such a path for $x$ in $\CC_2$ to $z$ in $\CC_4$ gives $(x,z) \in S \circ S$.

It will usually be easiest to just start in $\CC_3$, and see if you can trace backwards to $\CC_1$ (and similar for $\CC_4$ and $\CC_2$), but that's up to you. Anyhow, with this in mind, it becomes clear that

$$S \circ R = \big\{ (2,4),(3,4) \big\} \qquad S \circ S = \big\{ (1,1),(1,3),(1,4) \big\}$$

Thus, your answers in this respect are correct (once we account for your comments in Bram28's answer).


...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.

$\endgroup$
-1
$\begingroup$

1) The element $1$ not being used in $R$ indeed makes it irreflexive. However, it does not mean that it is not symmetric or transitive. For example, the relation $Q = \{ \}$ (i.e. the empty relation) would be perfectly symmetric and transitive, even if it contains no elements at all of the set it is defined over! So, you'll need to do some more work on that one

2) Your SoS is missing something ...

$\endgroup$
4
  • $\begingroup$ 1) So, if this is the case, the R will be irreflexive, anti-symmetric and transitive. Am I right? Because R is not symmetric as (2,4) belongs to R but (4,2) doesn't belong to R. R is transitive because (2,2),(2,3),(3,2) do exist in R. 2)Ya just noticed after I post the question, should have one more (1,3) Anyway, Thanks for answering the question $\endgroup$ – Hanyi Koh Oct 8 '19 at 17:31
  • $\begingroup$ @HanyiKoh Being anti-symmetric is not the same as not being symmetric .... but it is definitely not symmetric, correct. You'll need to verify more cases for transitivity. And yes, (1,3) should be added, very good. $\endgroup$ – Bram28 Oct 8 '19 at 17:35
  • $\begingroup$ Thanks for the advise! Just read through some articles about the transitivity, seems like if there is a element doesn't satisfy the condition of being transitivity the whole set will turn out to be not transitive as well. So the R is not transitive. $\endgroup$ – Hanyi Koh Oct 8 '19 at 18:00
  • $\begingroup$ @HanyiKoh Wait, so where is it not transitive? $\endgroup$ – Bram28 Oct 8 '19 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.