0

Let $A = \left \{ 1,2,3,4 \right \}$. Give an example of $R$ over $A$ so that it is symmetric and transitive but not reflexive.

My answer: $R = \begin{Bmatrix} (2,1)(1,2)(2,3)(1,3) \end{Bmatrix}$

Correct answer: $R = \begin{Bmatrix} (1,1)(2,2)(3,3) \end{Bmatrix}$

Question: Is my answer right? How is the ”correct” answer both transitive and symmetric?

Daniel Andersson
  • 375
  • 2
  • 9

4 Answers4

1

Your answer is not correct because it is not symmetric: $(1,3)$ is in $S$ but $(3,1)$ isn’t. The correct answer is symmetric $(a,b)\in S$ means $(b,a)\in S$ is trivially true, and transitive by the same triviality. You’re correct in saying that this question has many, many different solutions, however.

auscrypt
  • 8,186
  • Well, (1,2) and (2,1) is in my S. at least one is only necessary for symmetric right? – Daniel Andersson Jun 04 '19 at 10:33
  • No, symmetry requires an inverse for every element in the relation. $\forall(x,y)\in S:(y,x)\in S$. – Graham Kemp Jun 04 '19 at 10:40
  • But the correct answer don't have any of that (1,1)(2,2)(3,3) ? So i guess its every element or nothing? – Daniel Andersson Jun 04 '19 at 10:46
  • Both $(1,1)$ and its inverse $(1,1)$ are elements of $S$, so too for the others. Which of the three elements in ${(1,1),(2,2),(3,3)}$ does not have a corresponding inverse in the relation? @DanielAndersson – Graham Kemp Jun 04 '19 at 10:47
  • So in beginner terms we can say that "reflexive" depends on the conditions of A. But transitive and reflexive depends on the conditions of R? – Daniel Andersson Jun 04 '19 at 11:16
0

The relation $R=\{(1,1)\}$ is symmetric, transitive but not reflexive. The same holds for any relation $R$ which is a proper subset of the diagonal $\{(1,1),(2,2),(3,3),(4,4)\}$.

Wuestenfux
  • 20,964
0

Your answer is not transitive. You have $(2,1)$ and $(1,2)$ as elements in $S$, but not $(2,2)$ .

The correct answer is clearly symmetric because for every $(x,y)\in\{(1,1),(2,2),(3,3)\}$ then $(y,x)$ is too. It is transitive because there is no triple of $x,y,z$ where $(x,y)\in S,(y,z)\in S,(x,z)\notin S$.

It is not Reflexive because $(4,4)\notin S$. As @Wuestenfux pointed out while I was typing this, any proper subset of $\{(1,1),(2,2),(3,3),(4,4)\}$ will suffice, as will other sets, such as $\{(1,1),(1,2),(2,1),(2,2)\}$.

Graham Kemp
  • 129,094
  • My answer is transitive because i got (1,2)(2,3)(1,3) --- (a,b)(b,c)(a,c) right? – Daniel Andersson Jun 04 '19 at 10:35
  • Transitivity requires all combinations to satisfy the implication, not just a single example. – Graham Kemp Jun 04 '19 at 10:36
  • Are you sure? This video tells me no: https://youtu.be/WauEBdi1HHg?t=437 – Daniel Andersson Jun 04 '19 at 10:40
  • @DanielAndersson I am sure. The video clearly tells you "yes". It is written on the whiteboard right at the start that if there exists a triple of $a,b,c$ where $\langle a,b\rangle\in S\land \langle b,c\rangle\in S\land\langle a,c\rangle\notin S$, then $S$ is not transitive. So transitivity requires there to be no such counter example: that is that all triples must satisfy the implication: $\langle a,b\rangle\in S\land \langle b,c\rangle\in S\to\langle a,c\rangle\in S$. – Graham Kemp Jun 04 '19 at 10:59
0

Your answer is not symmetric because $(2,3) \in S$ but $(3,2) \notin S$.

A relation $S$ is symmetric if $(a,b) \in S$ if and only if $(b,a) \in S$. Now, check the answer again and you can see that this symmetry condition is satisfied $(1,1) \in S$ and $(1,1) \in S$, etc.

A relation $S$ is transitive if $(a,b),(b,c) \in S$ then $(a,c) \in S$. In correct answer, you can see that there are also no two elements that breaks this condition (Note that $(1,1),(2,2) \in S$ does not even fit to the definition so it does not break the condition).

ArsenBerk
  • 13,211
  • I thought i only needed (1,2) and (2,1) for S to be symmetric? "For all" is only for reflexive right? – Daniel Andersson Jun 04 '19 at 10:37
  • "For all" phrase in definition of reflexivity actually depends on the set that relation is defined on (in this case $A$). So it says, a relation is reflexive if for all $a \in A$, $(a,a) \in S$. But for the symmetry, "for all" phrase is for the set $S$ and we don't have anything to do with $A$. So it says, a relation is symmetric if for all $(a,b) \in S$ we have $(b,a) \in S$. – ArsenBerk Jun 04 '19 at 10:40
  • 1
    $\forall \langle a,b\rangle \in S~(\langle b,a\rangle \in S)$ and $\forall a\in A~\forall b\in A~(\langle a,b\rangle\in S\to\langle b,a\rangle\in S)$ are equivalent statements (since $S\subseteq A{\times}A$). @ArsenBerk – Graham Kemp Jun 04 '19 at 10:44
  • @GrahamKemp It's a good point actually. "we don't have anything to do with $A$" was just careless thing to say. I was thinking about the empty relation since it is also symmetric and transitive but not reflexive and empty relation having no pairs does not break symmetry but breaks reflexivity because $A$ is not empty. So in that case, empty relation is symmetric whatever the set $A$ is but it's reflexivity depends on set $A$. That's why I came up with an argument like that one. – ArsenBerk Jun 04 '19 at 10:58