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$
  • $\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$ – DanielWainfleet Jan 5 '16 at 23:44
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$

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.