Given the Set S ={1,2,3,4}. Define a relation on S that

1. Mar 27, 2014

knowLittle

1. The problem statement, all variables and given/known data
a.) Is symmetric and transitive, but not reflective:

b.) consists of exactly 8 ordered pairs and is symmetric and transitive:

3. The attempt at a solution
If the question asks me to define some relation, do I need to define some math property like power of some number or something like that or can I just state some set R that satisfies what they require?
R = { (1,2), ( 1,3 ), (1,4 ) , ( 2,3) , (2,1) , (2,4) , ( 3,1) , (3,2) , (3,4) , (4,1), (4,2), (4,3) }
Is this correct?

b.) Any idea

2. Mar 27, 2014

PeroK

For b) R cannot be reflexive, but you could still have aRa for some a, just not all.

Does that help?

3. Mar 27, 2014

pasmith

You have (1,2) and (2,1) in that set, so if the relation is transitive then (1,1) should be in there, but it isn't. And in fact transitivity requires that all ordered pairs be in that set, so the relation is reflexive.

4. Mar 27, 2014

knowLittle

But, the problem states that we don't want transitivity. Should the solution be that there does not exist such relation, then?

5. Mar 27, 2014

pasmith

Actually a symmetric and transitive relation on $\{1,2,3,4\}$ which consists of exactly eight ordered pairs must be reflexive.

There are only four diagonal pairs, so you must have aRb for some distinct a and b.

Symmetry requires that if aRb for distinct a and b then bRa, and hence transitivity requires aRa and bRb. That's four ordered pairs.

If you add aRc for $c \notin \{a,b\}$ then you must also add cRa, cRc, bRc and cRb, which is another five.

Last edited: Mar 27, 2014
6. Mar 27, 2014

knowLittle

So, you are saying that there exists a relation of 9 ordered pairs, but not 8?

7. Mar 27, 2014

pasmith

Part (a) states that you don't want reflexivity.

There are many relations on {1,2,3,4} which are symmetric and transitive but not reflexive.

Last edited: Mar 27, 2014
8. Mar 27, 2014

pasmith

That's not what I'm saying.

Also, part (b) does not require that your relation not be reflexive.

9. Mar 27, 2014

knowLittle

For part a.)
Symmetry does not imply reflexivity?
R= { (1,2) , (2,1 ) , (1,1), ...}

10. Mar 27, 2014

pasmith

What's the "..."?

11. Mar 27, 2014

knowLittle

I was just trying to show the simplest case, when if symmetry and transitivity is required, then reflexivity is implied. So, this is my question. Does symmetry and transitivity imply reflexivity?
The dots meant some other pairs I didn't want to think about.

12. Mar 27, 2014

knowLittle

Nevermind, the properties are defined only when every $x \in S$ is defined in R.

13. Mar 27, 2014

knowLittle

Sorry, but my concepts were off.

The solution to both could be this:

$R = \{ (1,2), (1,1) , (1,3) , (2,1), (2,3) , (2,2) , (3,1), (3,2) \}$

Is this correct?

14. Mar 27, 2014

pasmith

No. {(1,1)} is a relation on S which is symmetric and transitive but is not reflexive.

No, because $(3,3) \notin R$ so R is not transitive: 3R1 and 1R3 require 3R3.

Start with R = {(1,1), (1,2), (2,1), (2,2)}. How can you add four more pairs while keeping R symmetric and transitive? You can't add (1,3) or (2,3) or (3,1) or (3,2), because adding any one of those to R requires adding the other three and (3,3) to R. That's an extra five pairs.

15. Mar 28, 2014

PeroK

An interesting option would be the relation represented by the empty set! That would be symmetric and transitive but not reflexive.