Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
For the second part, there is a natural example: The "strictly larger than"-ordering on $X$. –  Michael Greinecker Feb 15 '12 at 9:31
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Thank you very much!! I wish I could accept both answers, though. –  roboguy12 Feb 15 '12 at 3:19
add comment

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

share|improve this answer
    
By 1 X 2 do you mean 1 ~ 2? Like, ~ is the relation marker? –  roboguy12 Feb 15 '12 at 3:05
    
I edited to clarify. –  JDH Feb 15 '12 at 3:07
    
Ok thank you! That makes sense, do you have any ideas for the second part? (transitive but neither reflexive nor symmetric) –  roboguy12 Feb 15 '12 at 3:14
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.