Example of a relation that is symmetric and transitive, but not reflexive [duplicate]

$\begingroup$

Can you give an example of a relation that is symmetric and transitive, but not reflexive?

By definition,

1. $R$, a relation in a set $X$, is reflexive if and only if $\forall x\in X$, $x\,R\,x$.

2. $R$ is symmetric if and only if $\forall x, y\in X$, $x\,R\,y\implies y\,R\,x$.

3. $R$ is transitive if and only if $\forall x, y, z\in X$, $x\,R\,y\land y\,R\,z\implies x\,R\,z$.

I can give a relation $\leqslant$, in a set of real numbers, as an example of reflexive and transitive, but not symmetric. But I can't think of a relation that is symmetric and transitive, but not reflexive.

$\endgroup$ 5

7 Answers

$\begingroup$

Take $X=\{0,1,2\}$ and let the relation be $\{(0,0),(1,1),(0,1),(1,0)\}$

This is not reflexive because $(2,2)$ isn't in the relation.

Addendum: More generally, if we regard the relation $R$ as a subset of $X\times X$, then $R$ can't be reflexive if the projections $\pi_1(R)$ and $\pi_2(R)$ onto the two factors of $X\times X$ aren't both equal to $X$.

$\endgroup$ 0 $\begingroup$

Take a set where no element is in relation with the other ones.

P.S. If $xRy$, then $yRx$ by symmetry, hence $xRx$ by transitivity. In particular, reflexivity holds in all points in relation with something other.

$\endgroup$ $\begingroup$

$x$ works at the same place as $y$ (defined on the set of all people).

Certainly it is symmetric and transitive, but it is not reflexive, as a guy without a job isn't related to himself.

$\endgroup$ 7 $\begingroup$

Or, for real numbers $x$ and $y$, let $xRy$ iff the product $xy$ is strictly positive, in other words for all $x,y\in\mathbb{R}$: $$xRy\quad\Longleftrightarrow\quad xy>0 $$ This is not reflexive because the number zero does not produce a strictly positive product with itself.

If, in the spirit of BrianO's answer, we take away the set of points failing to relate to anything, we are left with $\mathbb{R}\setminus\{ 0 \}$ on which set this $R$ is an equivalence relation, the equivalence classes being the set of the two signs, positive and negative. An equivalent definition of the same $R$ is: $$xRy\quad\Longleftrightarrow\quad \frac{x}{|x|}=\frac{y}{|y|}$$ which can also be used in $\mathbb{R}^n$ (or other normed vector spaces if you know what that is).

$\endgroup$ 1 $\begingroup$

If $R$ is a relation that is transitive and symmetric, then $R$ is reflexive on $dom(R) = \{a\mid (\exists b)\, aRb\}$: if $a\in dom(R)$, then there is $b$ such that $aRb$, thus $bRa$ by symmetry, so $aRa$ by transitivity.

Note that if $R$ is symmetric, then $dom(R) = range(R) = \{b\mid (\exists a)\, aRb\}$.

Hence, to get an example of a relation $R$ on a set $A$ that is transitive and symmetric but not reflexive (on $A$), there has to be some $a\in A$ which is not $R$-related to any $b\in A$. There are many examples of this:

• $A = \{0, 1\}$ and $R= \{(0,0)\}$,

  not reflexive on $A$ because $(1,1)\notin R$,

• $A = \{0, 1, 2\}$ and $R= \{(0,0), (0,1), (1,0), (1,1)\}$,

  not reflexive on $A$ because $(2,2)\notin R$.

$\endgroup$ $\begingroup$

This is called a “partial equivalence relation (PER)”. PERs can be used to simultaneously quotient a set and imbue the quotiented set with a notion of equivalence.

A genuinely useful example (copied straight from the linked page) is functions that respect equivalence relations of the domain and codomain. Suppose we have sets $X$ and $Y$, with (partial or otherwise) equivalence relations $\approx_X$ and $\approx_Y$, respectively. We define the partial equivalence relation $\approx_{X \to Y}$ by $$ f \approx_{X \to Y} f' := \forall x,x' \in X. x \approx_X x' \implies f(x) \approx_Y f'(x') $$ Then, $\{~f~|~f \approx_{X \to Y} f~\}$ are exactly the functions that preserve equivalence. Furthermore, $\approx_{X \to Y}$ is an equivalence relation on that set, equating $f$ and $f'$ exactly when they map the same inputs (up to $\approx_X$) to the same outputs (up to $\approx_Y$). This is true even if equality of functions in the underlying set theory is more intensional – hence the use of this technique in type theory.

$\endgroup$ $\begingroup$

I had the same question as you did but as soon as I read yours I noticed where the confusion came from: it lied in the if and only if part of the definition of symmetry.

The point is that for a relation $R$ to be reflexive $aRa$ has to hold for each and every element just like you have stated in the definition. But the definition of of symmetry reads: if and only if $aRb \implies bRa$ which means if no such relation exists, you can't use it. So if $\exists a \vert \forall b \in X, a\not R b$ (which means there is at least one element that is not in relation with any other) then you can't use the definition of symmetry to prove $aRa$.

This doesn't necessarily mean the relation is not symmetric, it only means you can't prove it using the given facts. If only we were given the fact that $R$ is a serial relation we would be able to prove it. So if you take @MPW's case and add $(2,2)$ to it you still wouldn't be able to prove reflexivity. That's because $2$ is not in relation with any other element.

$\endgroup$