# Find a relation which is reflexive and symmetric but not transitive on integers

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?

• 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. Jul 7, 2020 at 16:04
• $(a,b)\in R \iff |a-b|\le 1$ Jul 7, 2020 at 16:07
• The $\gcd$ also works well. Jul 7, 2020 at 16:08
• 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 Jul 7, 2020 at 16:26
• 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.$ Jul 7, 2020 at 19:23

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