4
$\begingroup$

Set $A = \{0,7,1\}$

1. So for a relation that is reflexive and transitive but neither an equivalence relation nor partial order...Can a relation be both partial order and equivalence?

Attempt: $R_1=\{(0,0),(7,7),(1,1),(0,1),(1,0),(0,7)\}$

Is $R_1$ Reflexive? Yes because $(0,0),(7,7),(1,1)$ exist in the relation.

Is $R_1$ Symmetric? No because every edge of the relation does not have either a two way street or a loop (if you drew $R_1$ as a diagraph)

Is $R_1$ Antisymmetric? No because there exists a two way street between two distinct vertices.

Now the part where I doubt myself...

Is $R_1$ Transitive? Yes? I don't think $(0,7)$ would break transitivity. If $R_2=\{(0,7)\}$ is transitive then the addition of $(0,7)$ to an already transitive relation wouldn't make it not transitive? Could someone please help clarify?

2. Relation on $A$ that is not reflexive, not transitive, not antisymmetric, but is symmetric.

I got $R_2=\{(0,7),(7,0),(7,7)\}$, I believe that is correct since it misses $(0,0)$ and $(1,1)$ and therefore is not reflexive. It is not antisymmetric since the diagraph has no one way streets. It is symmetric because there exists a two way street between each distinct vertices.

Could some please let me know if I am correct?

$\endgroup$
1
  • $\begingroup$ One common def'n of partial order is a relation that is reflexive and transitive. See, e.g. Kunen, Set Theory, or anything on the subject of forcing, where poset means partially ordered set. $\endgroup$ Jan 5, 2016 at 23:44

1 Answer 1

1
$\begingroup$

$Q1$

Can a relation be both partial order and equivalence?

Yes, for example, the equality relation.

Is $R_1$ Transitive?

No. It has $(1,0)$ and $(0,7)$ but not $(1,7)$. As this example show, if you add an ordered pair to a transitive relation it can become non-transitive.

A relation on set $A$ that is both reflexive and transitive but neither an equivalence relation nor a partial order (meaning it is neither symmetric nor antisymmetric) is:

$$R_3 = \left\{(0,0),\, (7,7),\, (1,1),\, (0,7),\, (7,1),\, (0,1),\, (1,7) \right\}$$

Reflexive? Yes, because it has $(0,0),\, (7,7),\, (1,1)$.

Transitive? Yes. We go through the relevant cases:

$$(0,7) \mbox{ and } (7,1) \Rightarrow (0,1) \qquad\checkmark$$ $$(7,1) \mbox{ and } (1,7) \Rightarrow (7,7) \qquad\checkmark$$ $$(0,1) \mbox{ and } (1,7) \Rightarrow (0,7) \qquad\checkmark$$ $$(1,7) \mbox{ and } (7,1) \Rightarrow (1,1) \qquad\checkmark$$

Symmetric? No, because we have $(0,1)$ but not $(1,0)$

Antisymmetric? No, because we have $(1,7)$ and $(7,1)$.

$Q2$

Your relation, $R_2$, is correct but your explanations for symmetric and antisymmetric are the wrong way around.

$R_2$ is not antisymmetric because there is as two-way street between distinct vertices, namely, $0$ and $7$.

$R_2$ is symmetric because there is no one-way street between distinct vertices.

Also, $R_2$ is not transitive because it has $(0,7)$ and $(7,0)$ but not $(0,0)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .