7
$\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$
14
$\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$
6
$\begingroup$

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

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

$\endgroup$
5
$\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$
  • $\begingroup$ Doesn't reflexive relation "x works at the same place as x" hold true if x works? $\endgroup$ – buzzee Dec 29 '15 at 15:01
  • 2
    $\begingroup$ @buzzee yes, and that is exactly the point! For the relation to be reflexive, it must be true that $x$ works the same place as $x$ for every person $x$. But it isn't true for every $x$. As you remark, it is only true, if $x$ works. $\endgroup$ – Mankind Dec 29 '15 at 15:43
  • $\begingroup$ Then if we say every x works at the same place as x, it's true. $\endgroup$ – buzzee Dec 29 '15 at 16:32
  • $\begingroup$ @buzzee if every person $x$ works, then my relation would be reflexive, yes. But it isn't, the reason being that there's lots of people, who don't work. But anyway, I like Mauro ALLEGRANZA's example even better: $x$ is a brother of $y$ is not reflexive. $\endgroup$ – Mankind Dec 29 '15 at 16:38
  • $\begingroup$ (his answer seems to have disappeared now though) $\endgroup$ – Mankind Dec 29 '15 at 17:21
3
$\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$ +1  I was reading the other answers, and I was just going to suggest the relation: for all $x,y\in\mathbb{R}$, $x\,R\,y\quad\Longleftrightarrow\quad x \times y \ne 0 $.  Your answer is better because is can be described more succinctly ($x$ and $y$ have the same sign), and it’s less trivial, in that it yields two equivalence classes when applied to $\mathbb{R}\setminus\{0\}$  (with mine, all of $\mathbb{R}\setminus\{0\}$ is equivalent). $\endgroup$ – Scott Dec 29 '15 at 21:07
2
$\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$
0
$\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$
0
$\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$

protected by Jyrki Lahtonen Feb 23 at 5:46

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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