Question on Relations

Question

Each of the following defines a relation on the positive integers $\mathbb{N}$:

1-) "$x$ is greater than $y$", 2-) "$xy$ is the square of an integer", 3-) $x$ + $y$ = $10$, 4-) $x$ + $4y$ = $10$

Determine which of the following relations are (a) Reflexive, (b) Symmetric, (c) Antisymmetric, (d) Transitive.

My thoughts:

For part (a), 1 isn't reflexive, 2 is reflexive as $x \cdot x = x^2$ gives us a square of an integer, 3 is also reflexive since $x + x = 10$ is true for $x = 5$(Or is it false because it's only true for $x=5$ and not the other positive integers?), 4 is also reflexive since $x + 4x = 10$ is true for $x=2$(Or is it false because it's only true for $x=2$ and not the other positive integers?).

For part (b) 1 is not symmetric, 2 is symmetric, 3 is symmetric, 4 is symmetric because if we have $x + 4y = 10$, then we must also have $y + 4x = 10$, solving them gives us $x=2,y=2$. Or is it false because it is not true for other positive integers?

For part (c) For 1, $x > y$ and $y > x$ cannot be true together and so it is antisymmetric. ( Since for antisymmetric, we have something of the form p implies q. But since p is always false in this case, we have that p implies q is always true and so we have that the relation $x > y$ is always antisymmetric ). For 2, since $xy = m^{2}$, where $m$ $\in \mathbb{Z}$, and $yx = m^{2}$, $xy = yx$ does not imply $x=y$. Therefore, 2 is not antisymmetric. For 3, if $x + y = 10$, and $y + x = 10$, then $x + y = y + x$ does not imply $x=y$. Therefore, 3 is not antisymmetric. For 4, if $x + 4y = 10$ and $y + 4x = 10$, then solving these equations gives us $y=2$ and $x=2$, which does mean $x=y$. But, it is only true for $x=y=2$, so would it be antisymmetric since it does satisfy the requirement for antisymmetric(but only for $x=y=2$), or is not antisymmetric, because it does not fulfill the requirement for antisymmetric for all positive integers x and y?

For (d), 1 is transitive, 2 is not transitive, because if we have $xy = m^2$, $yz = n^2$, then $xz = ( \frac{m \cdot n}{y})^{2}$, it is not necessary that $\frac{mn}{y}$ is an integer. For 3, If we have $x + y = 10$, $y + z = 10$, then $x + z = (10-y) + (10-y) = 20 - 2y$, and it is equal to 10 if $y = 5$. So is it transitive because the requirement is fulfilled but only for $y=5$, or is it not transitive because the requirement is not fulfilled for all positive integers y? For 4, if we have $x + 4y = 10$, $y + 4z = 10$, then $x + 4z = 20 - 5y$ and it is equal to 10 if $y=2$. So is it transitive because the requirement is fulfilled but only for $y=2$, or is it not transitive because the requirement is not fulfilled for all positive integers y?

I tried my best, thank you for reading this.

Please correct any mistakes I made or any misunderstandings I have about relations. Thank you!

Answer 1

(a.1) correct. (a.2) correct. (a.3) No, this is not reflexive. Reflexive relations would have satisfied that every element in the domain is related to itself. While it happens to be true that $5$ is related to $5$, it is not true that $4$ is related to $4$ since $4+4\neq 10$. It fails to be true that every element in the domain is related to itself so it is not reflexive. (The related property of being non-reflexive where every element is not related to itself also fails since 5 actually is related to itself). (a.4) Same issue as (a.3). This also is not reflexive since again $4$ is not related to itself since $4+4\cdot 4 \neq 10$.

(b.1) correct. (b.2) correct. (b.3) correct. (b.4) No. Recall that a relation is symmetric iff whenever we have the case that one thing is related to another we must also have that the relation holds in the other direction as well. That is, if $x\sim y$ then we must also have $y\sim x$. Here, note that $6$ is related to $1$ since $6+4\cdot 1 = 10$ is true. However, reversing the roles looking at if $1$ is related to $6$ they are not related since $1+4\cdot 6 \neq 10$.

(c.1) correct. (c.2) correct. (c.3) correct. (c.4) The relation does happen to be antisymmetric since the only case where both $x+4y=10$ and $y+4x=10$ are true simultaneously are when $x=y=2$. All other cases we would only have exactly one or none of $x$ related to $y$ or $y$ related to $x$, never both.

(d.1) correct. (d.2) Incorrect. When you have $xy$ is a square and $yz$ is a square, the question is if $xz$ is a square. It will happen to be true that $xz$ is a square and this can be seen by considering things by looking at the prime decomposition of the numbers involved. $xy$ being a square can be rephrased as "For every prime $p$, the exponent of $p$ in the prime decompositions of $x$ and $y$ must be the same parity. They are either both even, or both odd." We see then that for each prime $p$ the exponent of $p$ in $x$ is the same parity as the exponent of $p$ in $y$ as well as the exponent of $p$ in $y$ is the same parity as the exponent of $p$ in $z$ that it must be true that the exponent of $p$ in $x$ is the same parity as the exponent of $p$ in $z$.

(d.3) This is not transitive. Note that $\color{red}{8}$ (playing the role of $x$) is related to $2$ (playing the role of $y$) since $\color{red}{8}+2=10$. Further, $2$ is related to $\color{blue}{8}$ (playing the role of $z$) since $2+\color{blue}{8}=10$. It is not true however that $\color{red}{8}$ is related to $\color{blue}{8}$ since $\color{red}{8}+\color{blue}{8}\neq 10$.

(d.4) correct. It is indeed transitive since by your analysis if it happened to be true that $x$ is related to $y$ and $y$ is related to $z$ then it follows that $y$ must have been equal to $2$ which implies that all three are equal to $2$ and we do in this case have $x$ is related to $z$ since $2$ is indeed related to $2$. Since there are no other cases of $x$ being related to $y$ while simultaneously $y$ being related to $z$ to check, we are done.

Answer 2

For part (a), 1 isn't reflexive,

Correct. As $n > n$, is never true it is never reflexive.

2 is reflexive as x⋅x=x2 gives us a square of an integer,

Correct. For every $n\in\mathbb N, n\cdot n = n^2$ a perfect square.

3 is also reflexive since x+x=10 is true for x=5(Or is it false because it's only true for x=5 and not the other positive integers?),

The latter. To be reflexive it must be that ALL $n \in \mathbb N$ we must have $n + n = 10$. That's obviously not true for all $n$. It doesn't matter if it were true for all $n$ but $1$. So long as there is a single counter example (and we have an infinite number of counter examples) is it not reflexive.

Ditto for 4)

For part (b) 1 is not symmetric,

Correct. If $n > m$ then we do not ever have $m> n$.

2 is symmetric

Correct. Multiplication is commutative so if $nm = k^2$ is a perfect square then $mn = k^2$ as well.

, 3 is symmetric

Correct. Addition is commutative so if $n+m = 10$ then $m +n = n+m=10$.

4 is symmetric because if we have x+4y=10, then we must also have y+4x=10, solving them gives us x=2,y=2. Or is it false because it is not true for other positive integers?

The later. Symmetric means true for all pairs of natural numbers. A single counter-example will dispute it. So not symmetric.

This is a bit of a tricky relation as we will see later. The only positive integer solutions to $x + 4y = 10$ are $(x=2, y=2)$ or $(x=6, y=1)$.

So we have $6 + 4*1=10$ but $1+ 4*6 \ne 10$ so that is the one and only counter example.

Not symmetric. (A weird thing will happen when we test for transitivity)

For part (c) For 1, x>y and y>x cannot be true together and so it is antisymmetric. ( Since for antisymmetric, we have something of the form p implies q. But since p is always false in this case, we have that p implies q is always true and so we have that the relation x>y is always antisymmetric ).

Not sure what your statement $p$ or $q$ are supposed to be.

The way I like to think of "antisymmetric" is this:

Given that $a R B$ for an arbitrary pair $a,b$ we might be able to conclude three possible results:

$bRa$ is always true. If so this is symmetric.
$bRa$ might sometimes be true, but sometimes not. Then this is... boring. (We don't have a term for this.
$a$ and $b$ were arbitrary. If by chance we picked an $a$ and $b$ so that $a = b$ than $aRb$ is the same statement as $aRa$ is the same as $bRa$ and $bRa$ will occur trivially. But if we ignore these trivial exceptional cases and assume we picked an arbitrary $a,b$ but $a\ne b$. Then if $bRa$ is impossible then $R$ is antisymmetric.

Anyway. If $n > m$ then $m>n$ is impossible. SO this relation is anti-symmetric.

For 2, since xy=m2, where m ∈Z, and yx=m2, xy=yx does not imply x=y. Therefore, 2 is not antisymmetric.

Correct. Again multiplication is commutative so $xy = m^2$ where $x \ne y$ would mean $yx = m^2$. SO non-trivial symmetry is not impossible.

Of course an example of $xy = m^2$ but $x\ne y$ could support your case. (But there are many counter examples.)

For 3, if x+y=10, and y+x=10, then x+y=y+x does not imply x=y. Therefore, 3 is not antisymmetric.

Correct. But counter examples are good idea. Sometimes we can do relationships are many small sets or with conditions.

It's possible to have a relation on small sets. Say for instance if our set wasn't $\mathbb N$ but the set $\{1,2,3,5,6\}$ and we had the relation $x + y = 10$. That relation IS anti-symmetric because in that case $x + y = y+x = 10\implies x=y=5$.

For 4, if x+4y=10 and y+4x=10, then solving these equations gives us y=2 and x=2, which does mean x=y. But, it is only true for x=y=2, so would it be antisymmetric since it does satisfy the requirement for antisymmetric(but only for x=y=2

For (d), 1 is transitive,

Order is defined to be transitive. $a> b; b> c \implies a>c$. That's a given axiom. (It is the only reason we are allow to write shorthand such as $a > b > c$. That would be nonsense and wrong if we didn't know order must be transitive.

So ... correct.

2 is not transitive, because if we have xy=m2 , yz=n2, then xz=(m⋅ny)2, it is not necessary that mny is an integer.

Actually, yes, it is necessary that if $(\frac {mn}y)^2 = xy \in \mathbb N$ is an integer that $\frac {mn}y$ is an integer.

The square root of an integer is either an integer itself or irrational. And $\frac {mn}y$ is rational. And $(\frac {mn}y)^2=xy$ is an integer. Ergo: $\frac {mn}y$ is an integer.

SO is transitive.

[A HUGE lash to me with a wet noodle for me for not seeing that right away.]

Note if If you have $ab = k^2$ and $a$ is not a perfect square then it has prime factors to an odd power. But that means be has those same factors to an odd power. But the if $bc = m^2$ then $b$ has those prime factors to an odd power so $c$ must have the same odd factors to an odd power. So $ac$ will have those prime factors to an even power.

So transitivity makes sense.

More formally: suppose $ab = k^2$ and $bc = m^2$. Rewrite $a$ as $a = a'j^2$ we $j^2$ is factoring out all square factors of $a$ and $a'$ is a square free factor of whats left. ($a'=1$ if $a$ is a perfect square). Rewrite $b$ as $b=b'h^2$ with the same conditions.

$ab = a'b'(jh)^2 = k^2$ which means $a'b'$ must be a perfect square. But any prime factor of $a'$ is to a single power so it must be a factor of $b'$ and vice versa. So $a' = b'$.

And if we rewrite $c$ ac $c=c'g^2$ with the same conditions then $bc = m^2$ by the same argument would imply $c' = b' =a'$.

So we have $ac = a'c'(jg)^2 = (a'jg)^2$.

So it transitive.

For 3, If we have x+y=10, y+z=10, then x+z=(10−y)+(10−y)=20−2y, and it is equal to 10 if y=5. So is it transitive because the requirement is fulfilled but only for y=5, or is it not transitive because the requirement is not fulfilled for all positive integers y?

To be transitive it must be true for all pairs of pairs.

If $a + b = 10$ and $b+c = 10$ it's easy to see that $a = 10-b$ and $c =10-b = a$. There $a +c = a+a = 2a$ and $2a$ does not need to be equal to $10$. (Unless $a$ is "forced" to be $5$. But as we can have $a$ be any value from $1$ to $9$ we don't have to have $a=5$.) SO not transitive.

For 4, if we have x+4y=10, y+4z=10, then x+4z=20−5y and it is equal to 10 if y=2. So is it transitive because the requirement is fulfilled but only for y=2, or is it not transitive because the requirement is not fulfilled for all positive integers y?

This is tricky. A single counterexample would disprove transitivity. And if our set were the reals, or the rationals, and (I think) even the integers (including negatives) counterexamples would abound.

But $x + 4y = 10$ and $y + 4z = 10$ implies $x= 10-4y$ which has positive integer solutions if $y=1, x=6$ or $y=2, x=2$.

But $y=1,x=6$ can not be a solution to $y + 4z = 10$.

So the only solution possible at all where $x$ is related to $y$ and $y$ is related to $z$ is $x=y=z=2$. That the only example where $x+4y=10; y+4z = 10$.

And if that were the case then $x + 4z =10$.

So it is transitive.

But not because there is one case where it holds. But because in every case it holds. (but every case is only one case).

There are no counterexamples. Normally we would expect counter-examples but here there are none.

It is transitive.