Discrete Math - Confused about relations where x + 2y ≤ 3

Question

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.

Answer 1

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$.

Answer 2

$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$.

Reflexivity:

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)$.

Symmetry:

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

Transitivity:

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.

Answer 3

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.

Answer 4

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$.