Partially Ordered Sets · Partial Orders

Lesson 5

Nikolai Chukhin · Alexander S. Kulikov

Problem. Which of the following pairs \((X,\preceq)\) are posets (that is, \(\preceq\) satisfies the three properties of partial order)?

5 points

  1. \(X=\mathbb{R}\) is the set of real numbers and \(x \preceq y\), if \(x \le y\)

  2. \(X=\mathbb{R}\times \mathbb{R}=\{(x_{1}, x_{2}) \colon x_{1}, x_{2} \in \mathbb{R}\}\) is the set of (ordered) pairs of real numbers and \((x_{1},x_{2}) \preceq (y_{1}, y_{2})\), if \(x_{1} \le y_{1}\) and \(x_{2} \le y_{2}\)

  3. \(X=\mathbb{R}\times \mathbb{R}=\{(x_{1}, x_{2}) \colon x_{1}, x_{2} \in \mathbb{R}\}\) is the set of (ordered) pairs of real numbers and \((x_{1},x_{2}) \preceq (y_{1}, y_{2})\), if at least one of the two holds: 1) \(x_{1} < y_{1}\) or 2) \(x_{1}=y_{1}\) and \(x_{2} \le y_{2}\)

  4. \(X=\{f \colon \mathbb{R}\to \mathbb{R}\}\) is the set of functions from \(\mathbb{R}\) to \(\mathbb{R}\) and \(f \preceq g\), if \(f(x) \le g(x)\) for all \(x \in \mathbb{R}\)

  5. \(X=\{f \colon \mathbb{Z}_{>0}\to \mathbb{R}_{>0}\}\) is the set of functions from \(\mathbb{Z}_{>0}\) to \(\mathbb{R}_{>0}\) and \(f \preceq g\), if \(f(x)=O(g(x))\);

  6. \(X=\mathbb{Z}_{>0}\) is the set of positive integers and \(x \preceq y\), if \(x \mid y\) (\(x\) divides \(y\))

  7. \(X=\mathbb{Z}_{>0}\) is the set of positive integers and \(x \preceq y\), if any prime divisor of \(x\) is also a divisor of \(y\)

  8. \(X=2^{U}\) is the set of all subsets of some set \(U\) and \(A \preceq B\), if \(A \subseteq B\)

  9. \(X=\{\text{a}, \text{b}, \dotsc, \text{z}\}\) is the set of letters of the Latin alphabet and \(x \preceq y\), if \(x\) in alphabet comes no later than \(y\)

  10. \(X\) is an arbitrary set and \(x \preceq y\), if \(x=y\)