1
$\begingroup$

I am new here and this is the first time that I am asking a question here, and it's also the first time that I am using $\LaTeX$, so I apologize if I make some mistakes. I study in a non-English university, so I am sorry if my questions are a bit flimsy. Due to universities being closed, I have to learn everything from home with some class notes that my teacher put online. I am taking a discrete mathematics class for the first time, and I find it do-able, but it gets a bit hard to study it by myself. I have been doing some exercises regarding relations, but I ran into some difficulties for these two questions:

1) Let $R$ be a relation defined on $\mathbb{R}_+ \times \mathbb{R}_+$ where $(x_1,y_1)\mathrel{R}(x_2,y_2)$ if and only if $x_1 \times y_2 \leq x_2 \times y_1$. Prove or refute the following : $R$ is a partial order.

2) Let $R_1$ and $R_2$ be two relations defined on $X$. Show that if $R_1$ and $R_2$ are equivalence relations, then $R_1 \cap R_2$ defined on $X$ is also a equivalent relation.

Here is what I have been able to do so far:

1) I don't know how to do this. I really need help with this kind of question.

2) To show that $R_1 \cap R_2$ is an equivalence relation when $R_1$ and $R_2$ are equivalence relations, I supposed that if $x\mathrel{(R_1 \cap R_2)}y$ and $y\mathrel{(R_1 \cap R_2)}z$, then $x \mathrel{R_1} y$ and $y \mathrel{R_1} z$, so $x \mathrel{R_1} z$ and for $R_2$ we have $x \mathrel{(R_1 \cap R_2)} z$. I think that this proves that $R_1 \cap R_2$ is transitive, but I am not sure. Assuming this is correct (please explain how), how could I phrase this in a proper way?

Thanks! Your help is really appreciated.

$\endgroup$

2 Answers 2

1
$\begingroup$

1) To see whether this relation is a partial order or not, you need to check the three properties in the definition. For example, to show reflexivity, take $(x,y) \in \mathbb{R}_+ \times \mathbb{R}_+$ and check if $(x,y)R(x,y)$ follows. Similarly, for antisymmetry take two pairs $(x_1, y_1), (x_2, y_2)$, then assuming $(x_1, y_1)R(x_2, y_2)$ and $(x_2, y_2)R(x_1, y_1)$, use the definition of $R$ to see if these pairs have to be equal. Follow the same procedure with three pairs for transitivity. Once you plug in what $R$ means into your assumptions, these properties follow or fail shortly.

2) Your reasoning is correct. Start by stating your hypotheses clearly: "Let $x(R_1 \cap R_2)y$ and $y(R_1 \cap R_2)z$". I sometimes like to say "We want to show that $x(R_1 \cap R_2)z$", but that's a personal preference. Then, write down your reasoning in enough detail. For example, depending on the expected level of detail you might need to say "... then $xR_1z$ by the transitivity of $R_1$" or keep it brief like you did. Keep doing this for the three properties of equivalence relations and finally say that this completes the proof of $(R_1 \cap R_2)$ being an equivalence relation.

$\endgroup$
4
  • $\begingroup$ 1) Yes, but I am unable to do it. Can you write the answer? I think that I may understand it better if I can see it. $\endgroup$
    – user764644
    Commented Apr 1, 2020 at 0:08
  • $\begingroup$ 2) I could only find the transitive property. I am stuck with the symmetric and the relfexive $\endgroup$
    – user764644
    Commented Apr 1, 2020 at 0:10
  • $\begingroup$ 1) Anti-symmetry: Let $(x_1,y_1), (x_2,y_2) \in \mathbb{R} \times \mathbb{R}$ and suppose (i) $(x_1, y_1)R(x_2, y_2)$ as well as (ii) $(x_2, y_2)R(x_1, y_1)$. By (i), $x_1 y_2 \leq x_2 y_1$ and by (ii) $x_2 y_1 \leq x_1 y_2$, which together imply $x_1y_2 = x_2y_1$. Does this mean $(x_1, y_1)$ has to be equal to $(x_2, y_2)$? I'll let you think about it. Hint: think about signs of numbers. If you still need to check them, apply the same steps for transitivity and reflexivity. Pick arbitrary points, assume the hypotheses and see if the property always holds or if there is a counterexample. $\endgroup$ Commented Apr 1, 2020 at 0:25
  • $\begingroup$ 2) Symmetry: Suppose $x(R_1 \cap R_2)y$. Then, $xR_1y$ and since $R_1$ is an equivalence relation, it is symmetric and we get $yR_1x$. The same reasoning applies to $yR_2x$. These two together mean $y(R_1 \cap R_2)x$. I'm leaving reflexivity to you since it is the easiest one. $\endgroup$ Commented Apr 1, 2020 at 0:33
0
$\begingroup$

Hint for (1). Recall that a partial order is a binary relation that is reflexive, antisymmetric and transitive. Thus you need to prove or disprove (by giving a counterexample) that the following properties hold for all $x_1, x_2, y_1, y_2$ in ${\Bbb R}_+$.

  1. (reflexivity) $x_1y_1 \leqslant x_1y_1$
  2. (antisymetry) if $x_1y_2 \leqslant x_2y_1$ and $x_2y_1 \leqslant x_1y_2$, then $x_1 = x_2$ and $y_1 = y_2$.
  3. (transitivity) if $x_1y_2 \leqslant x_2y_1$ and $x_2y_3 \leqslant x_3y_2$, then $x_1y_3 \leqslant x_3y_1$.

If one of these three properties fails to be true, then your relation is not a preorder.

(2) Your argument for transitivity is correct. You could start by saying

By definition, $$ (*)\quad x \mathrel{(R_1 \cap R_2)} y \iff x \mathrel{R_1} y \ \text{ and }\ x \mathrel{R_2} y. $$ and then use $(*)$ to prove that $R_1 \cap R_2$ is reflexive, symmetric and transitive.

$\endgroup$
1
  • $\begingroup$ 1) I tried, but I keep failing at it! Can you answer it for me? Maybe ill see things clearly if I see the answer... 2) I tried to do the reflexive and the symmetric properties, but it didn't work... :( $\endgroup$
    – user764644
    Commented Apr 1, 2020 at 0:12

You must log in to answer this question.