Collection of Maths Problems

Verifying properties of relations

Task number: 3368

• Variant

  \(X=\{a,b,c\}\), \(R=\{(a,a),(a,b),(b,b),(b,a),(c,c)\}\)

• Solution

  Reflexivity: all pairs \((x,x), x\in X\) i.e. \((a,a),(b,b),(c,c)\) belong to \(R\), so it is reflexive.

  Symmetry: The only two pairs in \(R\) with distinct elements are \((a,b)\) and \((b,a)\), and swapping the elements in each of them again yields a pair in \(R\).

  We can verify transitivity by brute force, composing every two pairs; the only non-trivial cases are the composition of \((a,b)\) with \((b,a)\) and conversely.

  A counterexample for antisymmetry is the pair \((a,b), (b,a)\in R\), because \(a\ne b\).

• Answer

  The relation \(R\) is reflexive, symmetric and transitive, but is not antisymmetric.

• Variant

  \(X=\{a,b,c\}\), \(R=\{(a,a),(c,c)\}\)

• Solution

  The relation is not reflxeive, because \((b,b)\notin R\).

  The relation is symmetric: swapping elements yields the same relation.

  Transitivity: composing a loop with itself yields the same loop.

  Antisymmetry: the condition \(xRy \land yRx\) is fulfilled only for \(x=y=a\) and \(x=y=c\), so the relation is antisymmetric.

• Answer

  The relation is not reflexive, however it is symmetric, transitive and antisymmetric.

• Variant

  \((X,R)=(\mathbb N,\leq)\),

• Solution

  Reflexivity: \(\forall x\in \mathbb N: x\leq x\) is valid.

  Counterexample for symmetry: \(1 \leq 2 \land 2 \not\leq 1\).

  Transitivity: \(\forall x,y,z \in \mathbb N: x\leq y \land y\leq z \Rightarrow x\leq z\) is valid.

  Antisymmetry: \(\forall x,y \in \mathbb N: x\leq y \land y\leq x \Rightarrow x=y\) is valid.

• Answer

  The relation is reflexive, antisymmetric and transitive, but is not symmetric.

• Variant

  \(X=\{1{,}2,…,10\}\), \(R=\{(x,y): gcd(x,y)=1\}\), i.e. \(x\) and \(y\) are relatively prime.

• Solution

  It would be possible to solve this exercise by determining all pairs \(R=\{(1{,}1),(1{,}2),…,(10{,}9)\}\) and using brute force, but that would be inefficient.

  It is better to use properties of the greatest common divisor.

  Reflexivity does not hold, because \(gcd(2{,}2)=2 \ \Longrightarrow \ (2{,}2)\notin R\).

  Symmetry holds, because \(gcd(x,y)=gcd(y,x)\).

  Transitivity does not hold, because \(gcd(2{,}1)=gcd(1{,}2)=1\), but \(gcd(2{,}2)=2\).

  Antisymmetry does not hold, because \(gcd(2{,}1)=gcd(1{,}2)\), but \(2\ne 1\).