0
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ @zoli the answer is transitive. $\endgroup$ – Graham Kemp Jun 4 '19 at 10:29
  • $\begingroup$ @GrahamKemp: you are right … $\endgroup$ – zoli Jun 4 '19 at 10:31
  • $\begingroup$ The simplest answer is the empty relation. $\endgroup$ – Somos Jun 4 '19 at 17:18
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Well, (1,2) and (2,1) is in my S. at least one is only necessary for symmetric right? $\endgroup$ – Daniel Andersson Jun 4 '19 at 10:33
  • $\begingroup$ No, symmetry requires an inverse for every element in the relation. $\forall(x,y)\in S:(y,x)\in S$. $\endgroup$ – Graham Kemp Jun 4 '19 at 10:40
  • $\begingroup$ But the correct answer don't have any of that (1,1)(2,2)(3,3) ? So i guess its every element or nothing? $\endgroup$ – Daniel Andersson Jun 4 '19 at 10:46
  • $\begingroup$ 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 $\endgroup$ – Graham Kemp Jun 4 '19 at 10:47
  • $\begingroup$ 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? $\endgroup$ – Daniel Andersson Jun 4 '19 at 11:16
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ I thought i only needed (1,2) and (2,1) for S to be symmetric? "For all" is only for reflexive right? $\endgroup$ – Daniel Andersson Jun 4 '19 at 10:37
  • $\begingroup$ "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$. $\endgroup$ – ArsenBerk Jun 4 '19 at 10:40
  • 1
    $\begingroup$ $\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 $\endgroup$ – Graham Kemp Jun 4 '19 at 10:44
  • $\begingroup$ @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. $\endgroup$ – ArsenBerk Jun 4 '19 at 10:58
0
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ My answer is transitive because i got (1,2)(2,3)(1,3) --- (a,b)(b,c)(a,c) right? $\endgroup$ – Daniel Andersson Jun 4 '19 at 10:35
  • $\begingroup$ Transitivity requires all combinations to satisfy the implication, not just a single example. $\endgroup$ – Graham Kemp Jun 4 '19 at 10:36
  • $\begingroup$ Are you sure? This video tells me no: youtu.be/WauEBdi1HHg?t=437 $\endgroup$ – Daniel Andersson Jun 4 '19 at 10:40
  • $\begingroup$ @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$. $\endgroup$ – Graham Kemp Jun 4 '19 at 10:59

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.