-2
$\begingroup$

Suppose we have some relations on the set [1,2,3,4].

  1. $R_{1}=\{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$

  2. $R_{2}=\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$

  3. $R_{3}=\{(2,4),(4,2)\}$

  4. $R_{4}=\{(1,1),(2,2),(3,3),(4,4)\}$

  5. $R_{5}=\{(1,2),(2,3),(3,4)\}$

  6. $R_{6}=\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)\}$

I need to determine if these relations are reflexive/symmetric/anti-symmetric and transitive.

Can someone please give me a detailed explanation on what we need to check to determine these properties. I'm very confused. I'm getting my answers wrong.

I will be very grateful, thanks a lot.

$\endgroup$
  • $\begingroup$ Check if the relations $R_1$ etc satisfy the properties defining symmetry etc. Symmetric means : $\forall x,y [xRy \leftrightarrow yRx]$. $\endgroup$ – Mauro ALLEGRANZA May 25 at 12:00
  • $\begingroup$ Consider e.g. $R_1$; we have $(2,4) \in R_1$. What about $(4,2)$ ? $\endgroup$ – Mauro ALLEGRANZA May 25 at 12:01
  • $\begingroup$ Yes, R1 is not symmetric. I'm getting more confused on anti symmetric and transitive. $\endgroup$ – Sonny Jordan May 25 at 12:45
2
$\begingroup$

All you have to do is checking the definitions.

For example, let’s work $R_1$ out.

  • Can $R_1$ be reflexive? Recall the definition:

    A relation $R$ over a set $A$ is said to be reflexive iff for each $a \in A$ one has $(a,a) \in R$.

    The answer is no, because $(1,1) \notin R_1$.

  • Can $R_1$ be antireflexive? Recall the definition:

    A relation $R$ over a set $A$ is antireflexive iff for each $a \in A$ one has $(a,a) \notin R$.

    The answer is no, because $(2,2) \in R_1$.

  • Can $R_1$ be symmetric? Recall the definition:

    A relation $R$ over a set $A$ is symmetric iff for each $a \in A$ one has $(a,b) \in R \Rightarrow (b,a) \in R$.

    The answer is no, because $(2,4) \in R_1$ but $(4,2) \notin R_1$.

  • Can $R_1$ be antisymmetric? Recall the definition:

    A relation $R$ over a set $A$ is antisymmetric iff for each $a, b\in A$ one has $(a,b) \in R \land (b,a) \in R \Rightarrow a=b$.

    The answer is no, because $(2,3) \in R_1$ and also $(3,2) \in R_1$, but $2\neq 3$.

  • Can $R_1$ be asymmetric? Recall the definition:

    A relation $R$ over a set $A$ is asymmetric iff for each $a,b\in A$ one has $(a,b) \in R \Rightarrow (b,a) \notin R$.

    The answer is no, because $(2,3) \in R_1$ and $(3,2) \in R_1$.

  • Can $R_1$ be transitive? Recall the definition:

    A relation $R$ over a set $A$ is transitive iff for each $a,b,c \in A$ one has $(a,b) , (b,c) \in R \Rightarrow (a,c) \in R$.

    The answer is yes, because a direct inspection shows that each couple of possible consecutive connections $(a,b) , (b,c) \in R_1$ is closed by an arc $(a,c) \in R_1$. In fact:

    • the path $(2,2)$ & $(2,2)$ is closed by $(2,2)$;
    • the path $(2,2)$ & $(2,3)$ is closed by $(2,3)$;
    • the path $(2,2)$ & $(2,4)$ is closed by $(2,4)$;
    • the path $(2,2)$ & $(2,3)$ is closed by $(2,3)$;
    • the path $(2,3)$ & $(3,2)$ is closed by $(2,2)$;
    • the path $(2,3)$ & $(3,3)$ is closed by $(2,3)$;
    • the path $(2,3)$ & $(3,4)$ is closed by $(2,4)$;
    • the path $(3,2)$ & $(2,2)$ is closed by $(3,2)$;
    • the path $(3,2)$ & $(2,3)$ is closed by $(3,3)$;
    • the path $(3,2)$ & $(2,4)$ is closed by $(3,4)$;
    • the path $(3,3)$ & $(3,2)$ is closed by $(3,2)$;
    • the path $(3,3)$ & $(3,3)$ is closed by $(3,3)$;
    • the path $(3,3)$ & $(3,4)$ is closed by $(3,4)$.

Remaining relations can be studied in a similar fashion.

$\endgroup$
  • $\begingroup$ Did we conclude that this is transitive by using logic? Such as p implies q, but since p is false, q being false or true will mean our proposition is always true. Sorry if I am incorrect, I am confused in the relations chapter. $\endgroup$ – Sonny Jordan May 25 at 13:22
  • $\begingroup$ @SonnyJordan : No, it’s not logic. See the edited post. ;-) $\endgroup$ – Pacciu May 25 at 14:03
  • $\begingroup$ Why didn't we check (2,4) or (3,4)? $\endgroup$ – Sonny Jordan May 25 at 14:07
  • $\begingroup$ Because there are no pairs in $R_1$ with $4$ in the first coordinate, i.e. there are no connections which are consecutive to $(2,4)$ and $(3,4)$. $\endgroup$ – Pacciu May 25 at 14:15
  • $\begingroup$ Have you ever tried to draw the oriented graph of $R_1$? $\endgroup$ – Pacciu May 25 at 14:17
0
$\begingroup$

A relation $R$ on set $A$ is said to be reflexive if $\forall a \in A ~ (a,a) \in R$.

A relation $R$ on set $A$ is said to be symmetric if $ (a,b) \in R \mathrm{~then~} (b,a) \in R$. $\phi$ is also symmetric.

A relation $R$ on set $A$ is said to be anti-symmetric if $ (a,b) \in R \mathrm{~and~} (b,a) \in R \mathrm{~then~} a = b$. No symmetric pair must be present.

A relation $R$ on set $A$ is said to be Transitive if $(a,b) \in R \mathrm{~and~} (b,c) \in R \mathrm{~then~} (a,c) \in R$.


$R_1$ does not have $(4,2)$ hence it is not symmetric although it is reflexive, transitive. However $R_1$ is not antisymmetric (as we have symmetric pairs).

$\endgroup$

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.