Collection of Maths Problems

Orders of pairs

Task number: 4150

• Variant

  Comparison in both coordinates \(\le_S\):

  \((a,b)\le_S(x,y) \Leftrightarrow a\le x \wedge b\le y\)

• Solution

  Reflexivity: \((a,b)\le_S(a,b)\) because \(a\le a \wedge b\le b\)

  Antisymmetry: \((a,b)\le_S(x,y)\) and \((x,y)\le_S(a,b)\) means \(a\le x\ \wedge\ b\le y \ \wedge\ x\le a\ \wedge\ y\le b\ \Rightarrow\ a=x \wedge b=y\) and hence also \((a,b)=(x,y)\).

  Transitivity: \((a,b)\le_S(x,y)\) and \((x,y)\le_S(c,d)\) implies \(a\le x\le c\) and \(b\le y \le d\) and hence also \((a,b)\le_S(c,d)\).

• Answer

  The relation \(\le_S\) is a partial order. It is not linear, because pairs \((1{,}2)\) and \((2{,}1)\) are incomparable.

• Variant

  Comparison in at least one coordinate \(\le_U\):

  \((a,b)\le_U(x,y) \Leftrightarrow a\le x \vee b\le y\)

• Answer

  It is not a partial order, because pairs \((1{,}2)\le_U(2{,}1)\) and \((2{,}1)\le_U(1{,}2)\) do not fulfill the axiom of antisymmetry.

• Variant

  Comparison in both coordinates in distinct directions \(\le_Z\):

  \((a,b)\le_Z(x,y) \Leftrightarrow a\le x \wedge b\ge y\)

• Solution

  Reflexivity: \((a,b)\le_Z(a,b)\) because \(a\le a \wedge b\ge b\)

  Antisymmetry: \((a,b)\le_Z(x,y)\) and \((x,y)\le_Z(a,b)\) means \(a\le x\ \wedge\ b\ge y \ \wedge\ x\le a\ \wedge\ y\ge b\ \Rightarrow\ a=x \wedge b=y\) and hence also \((a,b)=(x,y)\).

  Transitivity: \((a,b)\le_Z(x,y)\) and \((x,y)\le_Z(c,d)\) imply \(a\le x\le c\) and \(b\ge y \ge d\) and hence also \((a,b)\le_Z(c,d)\).

• Answer

  The relation \(\le_Z\) is a partial order. It is not linear, because pairs \((1{,}1)\) and \((2{,}2)\) are incomparable.

• Variant

  Lexicographic comparison \(\le_L\):

  \((a,b)\le_L(x,y) \Leftrightarrow a < x \vee (a=x \wedge b\le y)\)

• Solution

  Reflexivity: \((a,b)\le_L(a,b)\) because \(a= a \wedge b\le b\)

  Antisymmetry: \((a,b)\le_L(x,y)\) and \((x,y)\le_L(a,b)\) imply \(a=x\), from what follows \(b\le y \wedge y\le b \Rightarrow b=y\) and hence also \((a,b)=(x,y)\).

  Transitivity: for \((a,b)\le_L(x,y)\) and \((x,y)\le_L(c,d)\) one of the following cases applies
  \(a < x< c\) and hence \((a,b)\le_L(c,d)\) or
  \(a < x= c\) and hence \((a,b)\le_L(c,d)\) or
  \(a=x < c\) and hence \((a,b)\le_L(c,d)\) or
  \(a= x= c\) and \(b\le y \le d\) and hence \((a,b)\le_L(c,d)\).

• Answer

  The relation \(\le_L\) is a partial order. It is indeed linear, because distinct pairs \((a,b)\) and \((x,y)\) one of the following cases applies and each yields a comparison: \( a < x \) or \( a > x \) or \(a=x \wedge b<y\) or \(a=x \wedge b>y\).

• Variant

  Lexicographic-maximum comparison \(\le_M\):

  \((a,b)\le_M(x,y) \Leftrightarrow \max(a,b) < \max(x,y) \vee (a,b)\le_L(x,y)\)

• Answer

  It is not a partial order: \((1{,}3)\le_M(2{,}1)\) in lexicographic comparison but \((2{,}1)\le_M(1{,}3)\) in maximum comparison.

• Variant

  Maximum comparison, but ties are treated lexicographically \(\le_N\):

  \((a,b)\le_N(x,y) \Leftrightarrow \max(a,b) < \max(x,y) \vee [\max(a,b)=\max(x,y) \wedge (a,b)\le_L(x,y)]\)

• Solution

  Reflexivity: \((a,b)\le_N(a,b)\) because \(\max(a,b)=\max(a,b) \wedge (a,b)\le_L (a,b)\)

  Antisymmetry: \((a,b)\le_N(x,y)\) and \((x,y)\le_N(a,b)\) imply \(\max(a,b)=\max(x,y)\), from what follows \((a,b)\le_L (x,y) \wedge (x,y)\le_L (a,b) \Rightarrow (a,b)=(x,y)\).

  Transitivity: for \((a,b)\le_N(x,y)\) a \((x,y)\le_N(c,d)\) one of the following cases applies
  \(\max(a,b)<\max(x,y)<\max(c,d)\) and hence \((a,b)\le_N(c,d)\) or
  \(\max(a,b)<\max(x,y)=\max(c,d)\) and hence \((a,b)\le_N(c,d)\) or
  \(\max(a,b)=\max(x,y)<\max(c,d)\) and hence \((a,b)\le_N(c,d)\) or
  \(\max(a,b)=\max(x,y)=\max(c,d)\), then \((a,b)\le_L(x,y)\le_L(c,d)\) and thus also \((a,b)\le_N(c,d)\).

• Answer

  The relation \(\le_N\) is a linear order.