4
$\begingroup$

Find the smallest relation containing the relation $\{ (1,2),(2,1),(2,3),(3,4),(4,1) \}$ that is:

  1. Reflexive and transitive
  2. Reflexive, symmetric and transitive

Well my first attempt:

  1. Reflexive: $ S_1 = \{ (1,1),(2,2),(3,3),(4,4) \}$
  2. Symmetric: $ S_2=\{ (3,2),(4,3),(1,4) \}$
  3. Transitive: $S_3= ? $Is where I'm stuck.

So that $S_1\cup S_2 \cup S_3 $ would be my equivalence relation?

Also, When you're testing for transitivity, what combinations do we test for? If we take: $(1,2) \land (2,3)\land(3,4) \rightarrow(1,3)$, must it be done for the converse? Starting with $(2,1)$ rather than $(1,2)$. It seems that there are many conbinations of $x,y$ that need to be tested. Is this correct? In fact, is my attempt correct to begin with?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It is very important in logic to understand your definition as hard as you can: $$\forall_{x,y,z\in X}\, xRy\wedge yRz\Rightarrow xRz$$ So. That tells us that if we have two elements, let's say, following your example, $(1,2)$ and $(2,3)$, there must be direct connection between $1$ and $3$. Do the same for all possible pairs from $S$, $S_1$ and $S_2$ (where $S$ is your base relation), and you will have your answer. And yes, you may have many elements in your relation after all those changes.

$\endgroup$
3
  • $\begingroup$ Right, so taking: $(1,2) \land (2,3)\land(3,4) \rightarrow(1,3)$, then ordered pair $(1,3)$ would need to be added, correct? $\endgroup$
    – Dimitri
    Nov 23, 2013 at 3:29
  • 1
    $\begingroup$ $(1,3)$ and $(1,4)$ to be very accurate, but you have your $(1,4)$ in symmetry, so, yes. Also, it will make things a lot easier if you think of your relation as of directed graph - draw it, and check what more do you need: if you have an edge between A, B and B, C, you need another one between A and C, and this one goes to your $S_3$. Graphs are good for this because you can see all: reflexivity, symmetry and transitivity from them. $\endgroup$
    – Annisar
    Nov 23, 2013 at 3:31
  • $\begingroup$ I understand, thank you. $\endgroup$
    – Dimitri
    Nov 23, 2013 at 3:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .