2
$\begingroup$

Could anyone give me three concrete mathematical relations $R$ on $\mathbb{Z}$ that satisfy exactly two of the following, no two of which satisfy the same two axioms:

1) Axiom of reflexivity ($\forall a\in \mathbb{Z}, (a,a)\in R$)

2) Symmetric axiom ($\forall a,b\in \mathbb{Z} ((a,b)\in R\Leftrightarrow (b,a)\in R$)

3) Axiom of transitivity ($\forall a,b,c\in\mathbb{Z} (((a,b)\in R\wedge (b,c)\in R)\Rightarrow (a,c)\in R$)

?

I'm completely lost as to how to find a relation that's reflexive and symmetric but not transitive. And the same goes for finding relations that are reflexive and transitive but not symmetric and relations that are symmetric and transitive but not reflexive.

I know the relation $(a,b)$ on $\mathbb{Z}$ defined as $a^2 + b^2 =1$ is symmetric but neither transitive nor reflexive. Personally, I'm not even sure there exists a relation that is reflexive and symmetric but not transitive, because I hypothesize that reflexive relations imply subtraction (i.e. they can always be rearranged so that some part of the equation has $(a-b)$ in it). I've thought of as many relations as I could, but with no luck. $a|b$, $ad=bc$ for some $c,d\in\mathbb{Z}$, and $a^m=b^n$ for some $m,n\in\mathbb{Z}$ are all equivalence relations.

Btw, if some of these relations do not exist, could someone at least give me a hint as to how to prove why that is?

$\endgroup$
  • $\begingroup$ It might prove easier to think of relations on a set $\{1, 2, \cdots, n\}$ for some (small, preferably) integer $n$. Remember what a relation fundamentally is: a relation $R$ on a set $S$ is some subset of the Cartesian product $S \times S$. [cont.] $\endgroup$ – Eevee Trainer Oct 9 '19 at 3:14
  • $\begingroup$ Thus it becomes convenient to think of subsets of $\{ \; (i,j) \; \}_{i,j=1}^n$ for some small $n$. Usually $2$ or $3$ is more than sufficient for what you need, or you can make appeals to the empty relation. These might not have the same intuitive grasp as, say, "$a \sim b$ if and only if $a^2 + b^2 = 1$ for $a,b \in \Bbb Z$," but they're easier to construct and easier to prove. $\endgroup$ – Eevee Trainer Oct 9 '19 at 3:14
  • 1
    $\begingroup$ You have the definitions of symmetry and reflexivity swapped. A symmetric relation has $(a,b)\in R\iff(b,a)\in R$. A reflexive relation as $(a,a)\in R$ for all $a$. $\endgroup$ – user856 Oct 9 '19 at 4:34
  • $\begingroup$ A notable previous question: Are there real-life relations which are symmetric and reflexive but not transitive? $\endgroup$ – user856 Oct 9 '19 at 5:03
1
$\begingroup$
  • The relation $i\sim j\Leftrightarrow|i-j|\leq5$ is reflexive and symmetric but not transitive.

This is an example of a tolerance relation. Tolerance relations, like this example, admit things that are "close" to each other but aknowledge that two objects might both be close to a third object without being close to each other.

  • The relation $i\leq j$ is reflexive and transitive but not symmetric.

This is an example of a partial order. These, alongside equivalence relations, are the primary subclasses of relations that get studied, since they describe the inequalities of numbers that we are used to.

  • The empty relation on $\mathbb Z$ is symmetric and transitive but not reflexive.

There is a fairly common false proof that symmetric and transitive relations must be reflexive, but the empty relation is a counterexample. For the most part, common and well-behaved relations that you would verify as equivalence relations will very clearly be seen to be reflexive, but it is a part of the proof that must be verified.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ would you mind telling me how you arrived at those relations? $\endgroup$ – user706791 Oct 9 '19 at 13:14
  • $\begingroup$ @fordjones I just added some explanation to the three examples. $\endgroup$ – Matthew Daly Oct 9 '19 at 14:59
  • $\begingroup$ Sorry for my stupidity, but would you mind explaining to me how two objects can both be close to a third object but not close to each other using the first relation? I might be misunderstanding, but are you referring to the two objects as $i$ and $j$? $\endgroup$ – user706791 Oct 11 '19 at 19:21
1
$\begingroup$

To construct a small example of a symmetric and reflexive, but not transitive, relation $R$ on $\mathbb{Z}$, you might begin by deciding you want $(0,1),(1,2)\in R$ but $(0,2)\not\in R$. If this can be arranged, then $R$ will not be transitive.

So start with $(0,1),(1,2)\in R$. Now it's easy to make $R$ reflexive by including $(a,a)\in R$ for all $a\in \mathbb{Z}$. And if you include $(1,0)$ and $(2,1)$, $R$ will be symmetric also. Importantly, you did not put $(0,2)$ in $R$, so $R$ is not transitive.

| cite | improve this answer | |
$\endgroup$

Your Answer

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