I'm a bit stuck with some questions for discrete math.

For the relation R = {(x,y) : x + 2y ≤ 3}, defined by A = {0,1,2,3}, determine if it is reflexive, symmetric, antisymmetric and transitive.

The 2y is throwing me a bit here. To determine if it is reflexive, I have done the following: x + 2x ≤ 3, which is a no with counter example (1,2), as that would give me (1,4) and be greater than 3. Is every second number doubled? Ie. (x,2x) or (x,2y)?

I have concluded this relation is not symmetric, as it does not imply y + 2x ≤ 3, on the basis that is x=2 and y=1, this would result in 2 + 2(1) for x + 2y but 1 + 2(2) for y + 2x, which is greater than 3. I have no confidence in this answer however.

I'm floundering on this one. Every time it was touched on during the lecture, it was simple examples, like x + y is even, or if there was an equality, there wasn't a defined set for it.

For determining transitive, what would I use as z?

Thank you everybody. I appreciate the help.

  • $\begingroup$ For this example, try writing out all pairs of numbers $(x,y)$ such that $x+2*y \leq 3$ (where $x,y \in \{0,1,2,3\}$). For example, $(0,1)$ would work, because $0+2*1 = 2$ and certainly $2\leq 3$. Note that the pair I write down is just two numbers ($x=0, y=1$), but when checking that the relation is satisfied I multiplied $y$ by $2$. $\endgroup$ – Theo C. May 9 at 23:44

I think you got the first two.

Let's try transitive: if $(x,y)\in\mathcal R$ and $(y,z)\in\mathcal R$, then $x+2y\le3$ and $y+2z\le3$. We need to check if $x+2z\le3$. Well, after trying a few things, I think I have a counter example. Namely $(3,0)\in\mathcal R$ and $(0,1)\in \mathcal R$. Clearly though, $(3,1)\not\in\mathcal R$.

Thus $\mathcal R$ isn't transitive.

Finally for antisymmetry, note that $(0,1)\in\mathcal R$. And $(1,0)\in\mathcal R$. But $0\neq1$.


$R = \{(x,y)~:~x+2y\leq 3\}$ is in words, a first thing is related to a second thing if the sum of the first thing and twice the second thing is at most $3$.


For a relation to be reflexive, that would mean that every thing is related to itself, so we need to check to see if $1$ is related to $1$, to see if $2$ is related to $2$, to see that $3$ is related to $3$, and so on. Checking to see if $1$ is related to $2$ is meaningless for checking reflexivity. We want to see if $(x,x)$ is in the relation for every $x$.

Here, we can check to see if $(\color{red}{0},\color{blue}{0})$ is in the relation. Indeed, $\color{red}{0}+2\cdot\color{blue}{0} \leq 3$ is true so $(0,0)$ is in the relation. Next, we find that $1$ is in fact related to $1$ since $\color{red}{1}+2\cdot \color{blue}{1}\leq 3$ is also true. We find however that $(\color{red}{2},\color{blue}{2})$ is not in the relation since $\color{red}{2}+2\cdot \color{blue}{2}\leq 3$ is false. Similarly so for $(3,3)$.


As for symmetry, your counterexample is a good one. Indeed, $(2,1)$ is in the relation but $(1,2)$ is not.


As for transitivity, it is a bit tedious for this example, but I would begin by writing out every element in the relation, then checking to see if any second entry of one matches first entry of another and from there checking if the first entry of one is related to the second entry of the other.

For example, we know that $(\color{red}{0},\color{blue}{0})$ is in the relation and so is $(\color{blue}{0},\color{green}{1})$ so we want to check that $(\color{red}{0},\color{green}{1})$ is in the relation as well, and more generally if $(\color{red}{x},\color{blue}{y})$ and $(\color{blue}{y},\color{green}{z})$ then we want to check that $(\color{red}{x},\color{green}{z})$ is as well.

Remember that $x,y,z$ don't need to necessarily all be distinct values (like how in my example two of them were both zero). Look carefully and see if you can find any that don't work.

You should find that $(3,0)$ is in the relation and so is $(0,1)$ but $(3,1)$ is not in the relation so it is not transitive.

  • $\begingroup$ You've explained it more clearly in this post than in the 2 hours of lectures I watched. Thank you so much. $\endgroup$ – Ian May 10 at 0:33

I think in this case, it would be best to write out all pairs: $$R = \{(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (3, 0)\},$$ or as a matrix, $$A = \begin{pmatrix} 1 & 1 & \color{red}1 & 1 \\ 1 & 1 & 0 & 0 \\ \color{red}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \color{blue}0\end{pmatrix}.$$ The highlighted red entry shows that $A$ is not symmetric, and hence neither is $A$. Explicitly, $(2, 0) \in R$, but $(0, 2) \notin R$.

The highlighted blue entry shows that $A$ does not have $1$s down the diagonal, and hence $R$ is not reflexive. Explicitly, $(3, 3) \notin R$.

To test transitivity, we compute $A^2$: $$A = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & \color{green}0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{pmatrix}, \quad A^2 = \begin{pmatrix} 2 & 2 & 1 & 1 \\ 2 & 2 & \color{green}1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{pmatrix}.$$ For transitive relations, we require that $(A^2)_{ij} \neq 0 \implies (A)_{ij} \neq 0$. The highlighted green entries prove this is not the case. In particular, the $\color{green}1$ in $A^2$ shows that there must be some $z \in A$ such that $(2, z), (z, 1) \in R$ (in fact, the number $1$ indicates that there is only one such $z$), but the $\color{green}0$ in $A$ shows that $(2, 1) \notin R$. Explicitly, $z = 0$ is such an element of $A$, so $(2, 0), (0, 1) \in R$, but $(2, 1) \notin R$.

  • $\begingroup$ Thank you Theo, this helped a lot with the graphing component that followed. May I ask, were (1,3) and (2,1) not included as they would exceed the set with the 2y factor? $\endgroup$ – Ian May 12 at 1:01
  • $\begingroup$ @Ian Yes, that's right. We have $(1, 3) \notin R$ as $1 + 2 \cdot 3 = 7 > 3$ and similarly, $(2, 1) \notin R$ since $2 + 2 \cdot 1 = 4 > 3$. $\endgroup$ – Theo Bendit May 12 at 1:22

It might be more helpful to think of the relation like this. Don't forget that, here, $R$ is a subset of $A \times A.$. Then

$$R = \{(x,y) \in A \times A | x + 2y \le 3\}$$

With that established, the (perhaps) cleaner way of thinking of this:

$$\text{x and y are related by R (i.e. xRy)} \iff (x,y) \in R \subseteq A\times A\iff x + 2y \le 3$$

In testing reflexivity, we seek $(x,x) \in R$ for all $x \in A$. By the above, that would require $x+2x = 3x \le 3$. As you have seen, there is a counterexample.

For symmetry, whenever $(x,y) \in R$, we want $(y,x) \in R$. That would mean that, whenever $x+2y \le 3$, that $y + 2x \le 3$. Again, you have a counterexample to this.

For transitivity, you want whenever $(x,y), (y,z) \in R$ that $(x,z) \in R$. This would mean that

$$\left.\begin{matrix} x + 2y \le 3\\ y + 2z \le 3 \end{matrix}\right\} \implies x + 2z \le 3$$

I'll tell you right away that there is a counterexample to this as well.


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.