2

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?

Paulo Henrique L. Amorim
  • 446
  • 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.

     – doobdood Jul 07 '20 at 16:04
  • 3
    $(a,b)\in R \iff |a-b|\le 1$ – Exodd Jul 07 '20 at 16:07
  • The $\gcd$ also works well. – Red Sleuth Jul 07 '20 at 16:08
  • I was tryung to see if dont have problems in the reflexive part, because it need to work for all intergers, the gcd(0,0) and lcm(0,0) is defined? – Paulo Henrique L. Amorim Jul 07 '20 at 16:10
  • @Exodd Its amazing I can see it fit perfect in this case, I tried to use absolute value. but i never manged to reach this expression, you have this on top of your mind or you used some steps to construct this relation? – Paulo Henrique L. Amorim Jul 07 '20 at 16:18
  • 1
    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 – Exodd Jul 07 '20 at 16:26
  • 1
    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.$ – DanielWainfleet Jul 07 '20 at 19:23

1 Answers1

2

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

Saša
  • 15,906