0

I am not understanding the following counterexample (found in a solutions manual) for a transitive and symmetric relation that is not reflexive.

Consider set $A = \{1,2,3\}$. Then $R = \{(1, 3), (3, 1), (1, 1), (3, 3)\}$ is symmetric and transitive, but not reflexive. The definition of a symmetric relation is for all elements x and y in set A, if $xRy$ then $yRx$. Clearly 2 is an element of A, but it is not symmetric according to the definition. And doesn't the existence of $(1, 1)$ and $(3, 3)$ point to reflexivity of R?

Asaf Karagila
  • 393,674
TomD1
  • 93
  • 2
    You’re not reading the definition of symmetric carefully enough. It says that *if* $x\mathrel{R}y$, for some $x,y\in A$, then also $y\mathrel{R}x$. It says absolutely nothing about pairs $x,y\in A$ when $x\not\mathrel{R}y$. – Brian M. Scott Nov 06 '16 at 20:22
  • For every single $2Ry$, all zero of them, we also have $yR2$. $2Ry$ occurs zero times and every single zero time that it does, $2Ry$ occurs in all zero cases. So it is symmetric. (And no, that isn't being a smart-ass.) – fleablood Nov 06 '16 at 20:53
  • @fleablood, so by the same token, 2 must also be reflexive and transitive, is that what you are implying? – TomD1 Nov 06 '16 at 21:02
  • No. 2 is an element. It isn't a relation at all. A reflexive relation is one in which all elements a related to themselves. A symmetric relation is one where every time one element is related to the other, the other is related to to first. – fleablood Nov 07 '16 at 00:16
  • 2 not R 2 so I most certainly do NOT mean "2 is reflexive". – fleablood Nov 07 '16 at 00:22

3 Answers3

2

Consider the null set as your relation.

Jacob Wakem
  • 2,382
  • Isn't the null set transitive, symmetric, and reflexive? – fleablood Nov 06 '16 at 20:50
  • @fleablood I specified it to be merely the relation. You get to choose any set over which the relation is taken such as to avoid reflexivity. – Jacob Wakem Nov 06 '16 at 21:22
  • But if ... oh, I see what you are saying. The empty set is never reflexive over a non empty set, wheras it is always symmetric and transitive. I had a brain fart when I wrote that comment. – fleablood Nov 07 '16 at 00:20
  • @fleablood My original answer just said to consider the null set. It gets them thinking and builds rapport. – Jacob Wakem Nov 07 '16 at 00:52
  • Yeah, I briefly thought "if no xRx then all xRx" which is.... idiotic. It was a ... hiccup. – fleablood Nov 07 '16 at 01:00
  • A null set as a relation? Is that even possible? There are no elements in such a set, hence why should any of the three properties holds? – TomD1 Nov 07 '16 at 02:49
  • @TomD1 They hold vacuously except for reflexivity. – Jacob Wakem Nov 07 '16 at 04:50
2

Don't just bold the "for all elements". Bold the if.

Definition of "symmetric"

"For all elements $x$ and $y$ in the set:" This means $(x,y)$ can be $(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)$.

of those

"If $xRy$ ..." This means $(x,y)$ can be $(1,1),(3,1),(1,3),(3,3)$ neither $x$ nor $y$ can be $2$ because we don't have any $2Ry$ or $xR2$.

"then $yRx$". $1R1$ and $1R1$. check. $3R1$ and $1R3$. check. $1R3$ and $3R1$. check. $3R3$ and $3R3$. check.

So R is symmetric. It doesn't matter that $2 \not R y$ because $2 \not R y$. We only need to check IF $2R y$ then $yR2$ is always true. But as $2Ry$ NEVER occurs, this is vacuously true.

Now, definition of reflexive.

For all $x$ in the set, we will have $xRx$. Let's check: $1R1$, check. $2R2$, FAIL. $3R3$, check. It fails and is not reflexive.

So, Transitive and symmetric does not imply reflexive.

But Transitive and symmetric AND $\forall x, \exists y| xRy$ does imply reflexive.

(As for all $x$ there is a $y$ so that $xRy$. So by symmetry $yRx$ so by trasitivity $xRy$ and $yRx$ so $xRx$.)

Also if R is transitive and symmetric but NOT reflexive there MUST exists some $x$ where $x$ is not related to anything. In this counter example, that element is $2$. $2$ is not related to anything.

fleablood
  • 124,253
  • Nice answer! So if I'm understanding this correctly, the difference between symmetric/transitive and reflexive is that the symmetric property already restricts the set in question to R while reflexive considers all of set A. Am I interpreting this correctly? – TomD1 Nov 06 '16 at 21:16
  • Not really. A relation is collection of pairs from a set. Symmetric simply means whenever (x,y) is in the collection, then (y,x) is to. Transitive means whenever (x,y) and (y,z) are in the collection, then (x,z) is too. Whereas reflexive means all for all x in the set, (x,x) is in the collection. Symmetric and transitive are two see separate properties that determine if some pair or pairs exist, another must also. Reflexive is a property that says certain pairs must exist. – fleablood Nov 07 '16 at 00:28
  • @fleablood There's a typo (I presume) which may be confusing to some. In your definition of reflexivity you say 'For all x in the set then xRx. This is not a conditional statement, so 'then' has no place there. It should just be 'For all x in the set xRx' Unless you want to say that 'for all x in the set, if x is in the set then xRx' but that expression has some redundancy to it. – Mariusz Popieluch Aug 15 '17 at 16:29
  • meh... I would think a "for" is conditional and a "then" is consequential, so semantically it is correct and not a typo. But you are right , I could be confusing. I didn't need it but I put it in so the sentence would parse better I think "For all x xRx" is hard to read without a clause break. But, I'll put in a different one. – fleablood Aug 15 '17 at 16:46
  • I can barely remember answering this.... – fleablood Aug 15 '17 at 16:48
1

The symmetry condition is a universally quantified implication. It tells us that for all $x, y \in A$ we must have that if $x R y$ then $y R x$. But there are no $z \in \{1,2,3\]$ such that $zR2$ or $2Rz$, so this condition is vacuously satisfied.

The reflexivity condition is also universally quantified but does not involve implication. It tells us that for all $x \in A$ we must have that $xRx$. But since there is no $z \in \{1,2,3\]$ such that $zR2$ or $2Rz$, this does not hold.

Hans Hüttel
  • 4,271