Can a relation be transitive when it is symmetric but not reflexive?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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}}}$$

Answer 4

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.

Answer 5

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.