1
$\begingroup$

I'm having trouble determining which properties work/don't work, as well as how to go about proving them:

Determine whether the given relation R on the set A is reflexive, irreflexive, symmetric, asymmetric, antisymmetric, or transitive. Justify your answer for each of the six properties.

a. 𝐴 = ℤ+; (𝑎, 𝑏) ∈ 𝑅 if and only if |𝑎 − 𝑏| ≤ 2.

b. 𝐴 = ℤ+; (𝑎, 𝑏) ∈ 𝑅 if and only if gcd(𝑎, 𝑏) = 1.

(if you guys could tell me which properties work/don't work only, that would also be helpful)

$\endgroup$
  • $\begingroup$ What are your thoughts? Do you know the definitions of the six properties? Where are you stuck trying to apply the definitions? $\endgroup$ – Arthur Apr 16 '17 at 0:48
  • $\begingroup$ I understand the properties in (a,b) ∊ R format, however I'm not sure how to go about in application. More specifically, deriving sets from the definitions in part a and b, and proving that they indeed have a certain property. $\endgroup$ – bobozoid Apr 16 '17 at 0:56
  • $\begingroup$ So, let's take reflexivity, for example. The definition says $$\forall a:(a,a)\in R$$In case a., because you're told that for any $a,b$ (also if $a$ and $b$ are equal), $(a,b)\in R$ is equivalent to $|a-b|\leq 2$, the definition translates to $\forall a, |a-a|\leq 2$. Does that look true to you? If it does, prove it. If not, find a counterexample. In case b., it translates to $\forall a: \gcd(a,a)=1$. Does that look true to you? If it does, prove it. If not, find a counterexample. Now do the she for the other five properties. $\endgroup$ – Arthur Apr 16 '17 at 1:12
  • $\begingroup$ Ah that clears things up quite a bit. So for all a (and at times, b), if the definition becomes false then that instance would be a counterexample? $\endgroup$ – bobozoid Apr 16 '17 at 1:17
  • $\begingroup$ If there is a single counterexample, then the property does not hold. For instance, $\gcd(1,1)=1$, so so far, it looks like b. is reflexive. However, the next number we check, we get $\gcd(2,2)=2\neq 1$. This means that "For all $a$, $\gcd(a,a)=1$" is false. Therefore, b. is not reflexive. $\endgroup$ – Arthur Apr 16 '17 at 1:31

Your Answer

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

Browse other questions tagged or ask your own question.