1
$\begingroup$

I was just trying to figure out this problem I came across. For a set $X = \{1, 2, 3, 4, 5\}$ is it possible to come up with a relation on $X$ that is symmetric, but neither reflexive nor transitive?

Also, it is possible to find a relation that is transitive, but neither reflexive nor symmetric?

Thank you!

  • 1
    For the second part, there is a natural example: The "strictly larger than"-ordering on $X$.2012-02-15

3 Answers 3

2

Let $R$ relate $1$ to $2$ and also $2$ to $1$, but only these. That is, $R=\{(1,2),(2,1)\}$. This is clearly symmetric, but it is not reflexive, since $R$ doesn't relate any number to itself, and it isn't transitive, since $R$ relates $1$ to $2$ and $2$ to $1$, but not $1$ to $1$.

  • 0
    Ok thank you! That makes sense, do you have any ideas for the second part? (transitive but neither reflexive nor symmetric)2012-02-15
4

For the relation $R$ to be not transitive, let $(1,2)\in R$ and $(2,3)\in R$ but $(1,3)\notin R$. If it is to be symmetric, then $(2,1)\in R$ and $(3,2)\in R$. A check shows that $R=\{(1,2),(2,3),(2,1),(3,2)\}$ satisfies the first part.

For the relation to be not symmetric, let $(1,2)\in R$ but $(2,1)\notin R$. A check shows that $R=\{(1,2)\}$ satisfies the second part.

3

In what follows I use $aR\,b$ as an abbreviation for $(a,b)\in R$.

To attack problems like these, start with a small relation that satisfies the positive condition. For your second problem, for instance, you could begin by letting $1 R\,2$, $2 R\,3$, and $1R\,3$; if you stop there, you have a transitive relation. Is it reflexive? Is it symmetric? Can you stop at this point?

Of course, you could have started simply with $1R\,1$, which is also transitive, but it’s clearly symmetric, so that’s a bad idea. The same objection rules out starting with $\varnothing$, the empty relation, in which nothing is related to anything: it’s also symmetric. The next simplest way to get transitivity is the one that I actually used.

The same approach works for your first problem and yields the answer suggested by JDH: starting with $1R\,1$ isn’t very helpful, but starting with $1R\,2$ and $2R\,1$ works without further modification.