2
$\begingroup$

I'm trying to think of a simple example of a two coordinate $(a,b)\in R$ relation which is reflexive, transitive, but not symmetric and not antisymmetric over $\mathbb{N}$ (meaning $R\subseteq\mathbb{N}\times\mathbb{N}$).

I can't seem to think of one. I would be glad to see some suggestions without actually proving them. I just struggling to think of an example.

$\endgroup$
  • $\begingroup$ See my comments on what symmetry / antisymmetry mean from a graphical point of view here. Here is another post of mine from a few years ago that gives similar graph theoretical interpretations of reflexivity and transitivity. Armed with those interpretations and the idea of drawing graphs, try coming up with an example. $\endgroup$ – JMoravitz Dec 14 '19 at 14:52
  • $\begingroup$ Take $R=\{(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(1,3)\}$ $\endgroup$ – almagest Dec 14 '19 at 14:55
5
$\begingroup$

I'm not sure I can think of an intuitive mathematical example that violates both symmetry and antisymmetry, but there are certainly small artificial relations.

Consider $\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4)\}$ over $\{1,2,3,4\}$. It is not symmetric because $3\sim4$ but not $4\sim3$ and it is not antisymmetric because $1\sim2$ and $2\sim1$ but $1\neq2$.

If you want to extend that to all of $\mathbb N$, you can just do $\{(i,i)\mid i\in\mathbb N\}\cup\{(1,2),(2,1),(3,4)\}$ for the same reason.


Actually, almagest did inspire me to think of a less contrived example over $\mathbb N$: $$R=\left\{(a,b)\in\mathbb N^2\mid \left\lfloor\frac a2\right\rfloor \le \left\lfloor\frac b2\right\rfloor\right\}$$

$\endgroup$
1
$\begingroup$

The question asks to find a preorder on $\mathbb{N}$ that is neither an equivalence relation nor a partial order. One such relation is the relation $R$ where $(m,n) \in R$ iff $m$ and $n$ are both even, or $m$ and $n$ are both odd, or $m$ is even and $n$ is odd. This is not an equivalence relation because, assuming that the natural numbers include zero, $(0,1) \in R$, but $(1,0) \not\in R$. It is also not a partial order, because $(2,4)$ and $(4,2)$ are both in $R$, for example.

$\endgroup$

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.