The question is stated as: Let $A$ be the set of integers, find a relation $R$ which is reflexive and symmetric in $A$ but not transitive in $A$.

By definition we have that.

  • $R$ is reflexive in $A$$ \Leftrightarrow (\forall x)(x \in A \Rightarrow xRx)$
  • $R$ is symmetric in $A$$ \Leftrightarrow (\forall x)(\forall y)([x\in A \land y \in A \land xRy] \Rightarrow yRx)$
  • $R$ is transitive in $A$$ \Leftrightarrow (\forall x)(\forall y)(\forall z)([x\in A \land y \in A \land z \in A \land xRz \land zRy] \Rightarrow xRy)$

What i thinked is to define such a relation using least common multiple, and greatest of two numbers as the following:

  • Let $lcm(x,y)$ be the least common multiple of $x$ and $y$
  • Let $max(x,y)$ be the greatest number from $\{x,y\}$
  • Then let $R = \{(x,y) : x \in A \land y \in A \land lcm(x,y) = max(x,y) \}$

It is transitive because $(\forall x)(x \in A \Rightarrow lcm(x,x) = x = max(x,x))$.

It is symmetric too because if the if $lcm(x,y) = max(x,y)$ holds true, its obvious that $lcm(y,x) = max(y,x)$ will be true too for any integers.

But it is not transitive, i tried to show this with one counter example: $(6,3) \in R \land (3,9) \in R$ but $(6,9) \notin R$.

The way I defined the relation is correct? Its possible to retrieve relations from numerical sets holding choosed properties in a easy way?

  • $\begingroup$ Looks right to me! :) As for constructing relations with specific properties, I don't think there's a better way than a heuristic approach such as the one you've employed. I could be wrong though. $\endgroup$
    – doobdood
    Jul 7, 2020 at 16:04
  • 3
    $\begingroup$ $(a,b)\in R \iff |a-b|\le 1$ $\endgroup$
    – Exodd
    Jul 7, 2020 at 16:07
  • $\begingroup$ The $\gcd$ also works well. $\endgroup$
    – Red Sleuth
    Jul 7, 2020 at 16:08
  • 1
    $\begingroup$ the steps were: (-) I need to build a path (looking at the naturals as nodes of a graph) so connect $n$ to $n+1$ (-) I need it symmetric, so $n$ is connected to $n+1$ and $n-1$ (-) I need it reflexive, so $n$ is also connected to $n$ (-) oh, this is actually $|a-b|\le 1$ (-) profit $\endgroup$
    – Exodd
    Jul 7, 2020 at 16:26
  • 1
    $\begingroup$ Another one: $(x,y)\in R$ iff $(x=y\lor \gcd(x,y)=1).$ We have $(0,1)\in R$ and $(1,2)\in R$ but $(0,2) \not \in R.$ $\endgroup$ Jul 7, 2020 at 19:23

1 Answer 1


One simple example:

$$a R b\iff ab\not\equiv 3\mod 10$$

$aRa$ because $a^2$ cannot end with digit 3.

$aRb \iff bRa$, because $ab=ba$.

But this relation is not transitive. For example, for $a=3$, $b=5$, $c=11$ we have $aRb$, $bRc$ but not $aRc$.

EDIT: Actually the simplest example I have found so far is this one:

$$a R b\iff a+b \ne101 $$

Obviously, it's reflexive, symmetric but not transitive ($a=10, b=20, c=91)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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