Given is relation $R=\left\{(a,b) \in S \times S: a+b \text{ is an even number }\right\}$ over the set $S=\mathbb{N}$. Is this relation antisymmetric, connex? Justify your decision.

A relation is antisymmetric if $\forall x,y \in A: xRy \wedge yRx \Rightarrow x=y$

A relation is connex, if $\forall x,y \in A: (x,y) \in R \vee (y,x) \in R $ or $x=y$

The sum of two numbers is even if and only if both summands are even or both summands are odd.

antisymmetric: If we have $aRb$, then both summands are either even or odd, same applies for $bRa$. Buth now the implication says $x=y$, so we might end up with an odd number which means that this relation is not antisymmetric.

connex: If we concentrate at the 3th condition of connexivity, i.e. $x=y$, then we will end up with an even number because both summands will either be even or uneven and thus the sum will be even. So the relation is connex.

This task was confusing me a lot.. I'm pretty sure that this relation is reflexive, symmetric and transitive but I'm not sure about these two properties. Did I do it correctly?

  • 2
    $\begingroup$ Yes, it seems fine to me. $\endgroup$ – Shaun Dec 3 '17 at 15:22

The addition is commutative. So, $(2,4)\in R$ and $(4,2)\in R$. Then $R$ is not antisymmetric.

The second condition: $(2,3)\not\in R$ and $(3,2)\not\in R$ and $2\ne 3$. The relation is not connex.

  • $\begingroup$ BTW: the relation in question is symmetric. Which relation $\rho$ on a set $A$ is both symmetric and antisymmetric? Let $(x,y)\in\rho$. By symmetry $(y,x)\in\rho$. Then by antisymmetry $x=y$ and $\rho$ is the equality relation on some subset $B\subset A$. $\endgroup$ – szw1710 Dec 3 '17 at 16:00
  • $\begingroup$ But how can be $(2,3) \in R$ if the sum of it is odd? $\endgroup$ – cnmesr Dec 3 '17 at 16:00
  • $\begingroup$ I have misread the definition. I considered odd sum. Thanks - I corrected the answer. It was enough to switch the examples. $\endgroup$ – szw1710 Dec 3 '17 at 16:02
  • $\begingroup$ Ok thank you :) For showing the relation is not connex, you have used summands whose sum is odd. Thus they do not belong to $R$. Would your example really show that this relation is not connex then? $\endgroup$ – cnmesr Dec 3 '17 at 16:15
  • 1
    $\begingroup$ Yes, of course. Examine the connexity condition by its negation. $\endgroup$ – szw1710 Dec 3 '17 at 16:25

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.