10
$\begingroup$

This question already has an answer here:

Pretty much what the title asks. But here's some context:

Suppose $X$ is finite and $R$ is a relation on $X$ that is not reflexive but it is symmetric. Also, suppose we can rule out $xRy$ and $yRz$ both occurring $\forall x,y,z\in X$ s.t. $x\neq y$ and $y\neq z$ and $x\neq z$. So we can rule out that $xRy$ and $yRz$ when $x,y,z$ are distinct. At this point, it seems that $R$ might be vacuously transitive. However, since $R$ is symmetric, $xRy$ and $yRx$ are both fine. But since $R$ is not reflexive, we cannot have $xRx$, which seems to be a violation of transitivity if $xRy$ and $yRx$. Is this a "legitimate" counter-example?

$\endgroup$

marked as duplicate by Matthew Towers, Mike Earnest, Ilmari Karonen, Daniel Fischer Sep 5 '18 at 21:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ I have some trouble connecting your title to the actual text. E.g. you say "But since $R$ is not reflexive, we cannot have $xRx$". This is not true. You can have $xRx$ for certain elements of $X$, just no all. So do you have some wrong assumptions about what reflexivity (and the other properties) mean and therefore your title is imprecise, or do you want to ask a different question instead? $\endgroup$ – M. Winter Sep 5 '18 at 15:25
  • 1
    $\begingroup$ A relation which is symmetric and transitive is called a "partial equivalence relation"; it's equivalent to giving an equivalence relation on a subset of $X$. If this subset is a proper subset of $X$, then the relation is not reflexive. $\endgroup$ – Daniel Schepler Sep 5 '18 at 19:28
  • $\begingroup$ I could've sworn we had a canonical question that covered all the permutations of this question (i.e. transitive and symmetric but not reflexive, transitive and reflexive but not symmetric, symmetric and reflexive but not transitive). Maybe I'm just imagining things. $\endgroup$ – Ilmari Karonen Sep 5 '18 at 20:04
  • $\begingroup$ Ah, I was mistaken. We don't seem to have a canonical question on it, although I did once post this answer which covers all the variations. $\endgroup$ – Ilmari Karonen Sep 5 '18 at 20:07
17
$\begingroup$

Symmetric means we can represent the relation as an undirected graph. Transitive means this graph is composed of connected components which either look like a point or $K_n$ with each point connected to itself. Reflexivity means each point is connected to itself.

Thus, a necessary and sufficient condition is that one component is a point (i.e.- one element is not related to any other). In exactly these cases your proof fails because it requires each $x$ to be related to another $y$.

$\endgroup$
  • $\begingroup$ This should be the accepted answer, it describes all possible relations that have the desired properties. $\endgroup$ – Rchn Sep 5 '18 at 8:58
14
$\begingroup$

The answer is yes; the empty relation (on any nonempty set $X$) is transitive, symmetric, and not reflexive.

$\endgroup$
  • $\begingroup$ Noted. Thanks. Do you have any input into the example alluded to in the rest of the question? $\endgroup$ – amarsh Sep 5 '18 at 1:11
  • $\begingroup$ Sorry, I don't understand that example, it seems incompletely described. Perhaps you could flesh it out, and ask that as a separate question? $\endgroup$ – vadim123 Sep 5 '18 at 1:13
9
$\begingroup$

If there exists $(x,y)$ in a symmetric relation, there also exists $(y,x)$. If this relation is transitive, then $(x,x)$ and $(y,y)$ must exist in the relation. However, this is not sufficient to make the relation reflexive.   That would further require that every $x$ in the underlying set has some $y$ where $(x,y)$ is in the symmetric-and-transitive relation.

A symmetric and transitve relation, $R$, over set $A$, is also reflexive exactly when $\forall x{\in}A~\exists y{\in} A :(x,y)\in R$.


A symmetric and non-reflexive relation, $R$, over set $A$, may be transitive only if there is something (in $A$) not related to anything.   A symmetric $R$ where something is not related to anything is not neccessarily transitive, but it may be.  

$${\begin{Bmatrix}(0,0),&(0,1),&&(0,3)\\(1,0),&(1,1),&&(1,3)\\~\\(3,0),&(3,1),&&(3,3)\\&&&&(4,4)\end{Bmatrix}{\text{ is a symmetric, non-reflexive, transitive relation}\\\text{over the set }\{0,1,2,3,4\}}\\\begin{Bmatrix}&(0,1)\\(1,0),&(1,1),&&(1,3)\\~\\&(3,1)\\&&&&(4,4)\end{Bmatrix}{\text{ is a symmetric, non-reflexive, non-transitive relation}\\\text{where something (2) is not related to anything}}}$$

$\endgroup$
  • $\begingroup$ Sorry, assume that we already know that $R$ is symmetric and not reflexive ($\forall x \in X$, not just for some $\x in X$!!!) independently of whether or not it is transitive. Now, can $R$ be transitive given that info? Edit: Sorry I didn't make the parenthetical clear $\endgroup$ – amarsh Sep 5 '18 at 1:30
  • $\begingroup$ +1. I had a feeling in my guts that quantifiers were very important for this question! $\endgroup$ – Adrian Keister Sep 5 '18 at 1:32
  • $\begingroup$ @amarsh: Yes, as Vadim123 points out, the empty relation on a non-empty set satisfies that. $\endgroup$ – Henning Makholm Sep 5 '18 at 1:35
  • 1
    $\begingroup$ @amarsh: It sounds like you mean irreflexive when you say "not reflexive". $\endgroup$ – Henning Makholm Sep 5 '18 at 1:36
  • $\begingroup$ @HenningMakholm I guess. I just hadn't thought that it was irreflexive, just that it wasn't reflexive. $\endgroup$ – amarsh Sep 5 '18 at 1:39
1
$\begingroup$

Transitive symmetric relations on $X$ are the same thing as a partition of $X$ plus a choice of subset $S \subset X$ of elements that do satisfy reflexivity. The extreme cases $S=X$ and $S$ empty are (respectively) equivalence relations, and disjoint unions of complete graphs. Examples of the latter are irreflexive relations like "sibling", "roommate", "spouse", "coreligionist", and "fellow conspirator".

It would be interesting to see a natural example with $S$ a proper subset.

$\endgroup$
1
$\begingroup$

I once wondered this too and was puzzled about it for a while. The trick behind it is that one needs to pay very careful and close attention to the exact and precise statement of the properties in question. Those little nitty gritty words really do count. You have to pay attention here to the logical structure. To wit:

  1. The statement of symmetry is: For all $x$ and $y$ in the domain and codomain, IF $x\ R\ y$ THEN $y\ R\ x$.
  2. The statement of transitivity is: For all $x$ and $y$ in the domain and codomain, IF $x\ R\ y$ and $y\ R\ z$ THEN $x\ R\ z$.

The key words are the bolded ones: "IF", "THEN". These are implications. They do not assert the truth of the statements they join, and moreover, can only be used to infer anything about the truth of one of the joined statements if that of the other is suitably affirmed or denied. In particular, with regard to symmetry, there is nothing else present that allows us to assume that the hypothesis of the implication - $x\ R\ y$ - is true, and that is what we need to conclude that $x\ R\ x$ by the reasoning given in the original post. In particular, if we want to show that $x\ R\ x$ for every $x$, then we need that $x\ R\ y$ for at least one $y$ as well for each of those $x$-values. Yet we have nothing that tells us that is the case. There are no statements with any existential quantifiers on them that tell us that anything has to exist which validates the hypothesis of the implication in the symmetry law. It has a universal quantifier but no existential quantifiers.

Thus the argument, while valid, is not sound.

A counterexample can be constructed from any equivalence relation by simply deleting for any given $x$ all pairs of the form $(x, y)$ from the graph. This will falsify reflexivity but will leave the other two unchanged since nothing can be concluded from them when their hypotheses are untrue.

$\endgroup$
  • 1
    $\begingroup$ That's the most complete answer possible. Of course the counterexample of an empty relation on a non-empty set provided by vadim123 in his answer is just a special case of this (as it has to be). $\endgroup$ – Ister Sep 5 '18 at 8:00
  • $\begingroup$ What you are trying to say via "They are not universally quantified statements." you are not saying. Your IFs are implicitly quantified so make the quantifiers explicit so you can correctly talk about the role of quantifiers. However, parts of your presentation athough applicable to propositions doesn't necessarily work for predicates. (You are not following your own advice.) $\endgroup$ – philipxy Sep 5 '18 at 21:41
  • $\begingroup$ @philipxy : I'm not exactly sure what you mean by that their are implicit quantifiers. $\endgroup$ – The_Sympathizer Sep 6 '18 at 3:08
  • $\begingroup$ ADD: I suppose you may be right - they must quantify over the domain. $\endgroup$ – The_Sympathizer Sep 6 '18 at 3:09
  • $\begingroup$ I'll see if I can revise it. The gist of this has to be sound, but it may need some ironing. Thanks. $\endgroup$ – The_Sympathizer Sep 6 '18 at 3:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.