Given two relations on a set, I want to see if one is reflexive/transitive/symmetric, and find some relation compositions.

Question

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)\}$?

Answer 1

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

Answer 2

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

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

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:

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.