1
$\begingroup$

Problem

I have these two relations over $A$, and I am supposed to determine whether they are reflexive, symmetric, antisymmetric, and/or transitive. I have determined that they are not reflexive or symmetric, however I'm unsure whether they're both antisymmetric, and I don't understand how to determine whether or not they're transitive. Will someone please explain?

Let $A = \{1,2,3,4,5,6\}$

$R_1 = \{(x,y) | \lceil log_2x]\rceil < \lceil log_2y\rceil \}$

$R_2 = \{(x,y) | \lceil log_2x]\rceil = 2 + \lceil log_2y\rceil \}$

Attempt

I see that for BOTH $(x,y) \rightarrow \neg(y,x)$ so my guess is that they're both antisymmetric. Is that correct? If so, which one is transitive? Is it possible for a relation to be both symmetric and transitive?

Ordered pairs which satisfy each relation

$R_1: (1,2) (1,3) (1,4) (1,5) (1,6) (2,3) (2,4) (2,5) (2,6) (3,5) (3,6) (4,5) (4,6)$

$R_2: (3,1) (4,1) (5,2) (6,2)$

$\endgroup$
10
  • $\begingroup$ There's no need for java code here, it clutters up your post. About your original question, you should remind yourself of the definitions of "antisymmetric" and "transitive" first. If you have done so and continue to have problems, by all means report your specific issues. $\endgroup$ – Scaramouche Jul 31 '13 at 7:44
  • $\begingroup$ Antisymmetric: $ \forall a, b \in X,\ R(a,b) \wedge a \ne b \Rightarrow \lnot R(b,a).$ As I stated in my question, I know the definition of antisymmetric, but do not understand the definition of transitive. Those are my specific issues. $\endgroup$ – user87509 Jul 31 '13 at 7:48
  • $\begingroup$ So, ignoring your specific $A$, are there any numbers $x\neq y$ such that $\lceil \log x\rceil<\lceil\log y\rceil$ while simultaneously $\lceil \log y\rceil < \lceil \log x \rceil$? Generally, if a relation isn't antisymmetric then there must be $x\neq y$ with $xRy$ and $yRx$. $\endgroup$ – Kevin Arlin Jul 31 '13 at 7:50
  • $\begingroup$ I'm not restricted to testing the relations with $A$? $\endgroup$ – user87509 Jul 31 '13 at 7:52
  • $\begingroup$ It's fine only to think about $A$, the answer just isn't any different for $R_1$. $\endgroup$ – Kevin Arlin Jul 31 '13 at 7:53
1
$\begingroup$

You are correct in thinking that both relations are antisymmetric.

A relation $R$ on a set $A$ is transitive if the following holds: whenever $x,y,z\in A$ with $\langle x,y\rangle\in R$ and $\langle y,z\rangle\in R$, then $\langle x,z\rangle\in R$ as well. If you think of the members of $A$ as stepping stones, then you can think of $\langle x,y\rangle\in R$ as meaning that it’s possible to step from $x$ to $y$. Then transitivity says that if you can step from $x$ to $y$, and you can also step from $y$ to $z$, then you can step directly from $x$ to $z$.

For example, in $R_1$ you can step from $1$ to $4$ and from $4$ to $6$ (because $\langle 1,4\rangle$ and $\langle 4,6\rangle$ are both in $R_1$), and sure enough, you can also step directly from $1$ to $6$ (because $\langle 1,6\rangle\in R_1$). $R_1$ is small enough so that if necessary you can check every possible instance of transitivity to make sure that there are no failures. However, it’s easier to work directly from the definition of $R_1$: if $$\lceil\log_2x\rceil<\lceil\log_2y\rceil$$ and $$\lceil\log_2y\rceil<\lceil\log_2z\rceil\;,$$ is it always going to be true that $$\lceil\log_2x\rceil<\lceil\log_2z\rceil\;?$$

It may be easier to check $R_2$ from the list of ordered pairs. Can you find any $x,y,z\in A$ such that $\langle x,y\rangle$ and $\langle y,z\rangle$ are in $R_2$, but $\langle x,z\rangle$ is not? HINT: Can you even find any $x,y,z\in A$ such that $\langle x,y\rangle$ and $\langle y,z\rangle$ are in $R_2$?

$\endgroup$
2
  • $\begingroup$ THANK YOU SO MUCH!!!! I get it! The stepping stone analogy really did it for me. Just to be sure, it is true that both are anti-symmetric, while $R_1$ is also transitive, correct? $\endgroup$ – user87509 Jul 31 '13 at 8:07
  • $\begingroup$ @positiveimpact: You're welcome! All of that is correct, and in addition $R_2$ is transitive, though for a rather silly reason: the set $A$ is small enough that there are no ‘linked’ pairs $\langle x,y\rangle$ and $\langle y,z\rangle$ in $R_2$, so there is no linked pair with $\langle x,z\rangle\notin R_2$, i.e., no violation of transitivity. If $A$ included $9$, then $R_2$ would include $\langle 9,3\rangle$ and $\langle 3,1\rangle$ but not $\langle 9,1\rangle$ so it would not be transitive. $\endgroup$ – Brian M. Scott Jul 31 '13 at 8:14
2
$\begingroup$

Yes. it is correct as you can see the pair $(a,a) \notin R_1$ while $a\in A $ . As well both of your relation are transitive.

if $(x,y) \in R_1$ and $(y,z) \in R_1$ $$ log_2x <log_2y<log_2z => (x,z) \in R_1 $$

so it is transitive.

And about a relation that can be both . For example take equality relation it is clearly symmetric and also transitive.

I hope this will answer your question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy