11.20 Partition

Workshop 6.pdf

Note

• Upper Bound: If \(\exists q,\forall s\in S:sRq\), then \(q\) is an upper bound of \(S\)
• Lower Bound: If \(\exists q,\forall s\in S:qRs\), then \(q\) is an lower bound of \(S\)

---

Exercise 1 We equip the set \(E = \mathbb{R}^2\) with the relation \(\mathcal{R}\) defined by \((x, y) \ \mathcal{R} \ (x', y') \iff \exists a > 0, \ \exists b > 0 \ | \ x' = ax \ \text{and} \ y' = by.\)

(a) Show that \(\mathcal{R}\) is an equivalence relation.

easy

(b) Give the equivalence class of the elements \(A = (1, 0)\), \(B = (0, -1)\) and \(C = (1, 1)\).

\(A/R=\{(a,0):a>0\},B/R=\{(0,-b):b>0\},C/R=\{(a,b):a,b>0\}\)​

(c) Determine the equivalence classes of \(\mathcal{R}\).

\(\{(a,0):a>0\},\{(0,-b):b>0\},\{\left(0,0\right)\},\{(a,-b):a,b>0\},\{(-a,b):a,b>0\},\{(a,b):a,b>0\},\{(-a,-b):a,b>0\}\)

Exercise 2 Let \(E\) be a fixed set containing at least two elements. We consider the following binary relation on \(\mathcal{F}(E, \mathbb{R}_+)\): \(\forall(f,g)\in\mathcal{F}(E,\mathbb{R}_{+})\times\mathcal{F}(E,\mathbb{R}_{+}),\ f\preceq g\;\iff\;\left\lbrack\forall x\in E,\ f(x)\leq g(x)\right\rbrack\)

(a) Show that \(\preceq\) defines an order relation on \(\mathcal{F}(E, \mathbb{R}_+).\)

easy

(b) Is the order thus defined total?

No, not for any \(f,g\) can be compared

(c) Let \(f \in \mathcal{F}(E, \mathbb{R}_+)\). Write the definitions of "f is upper bounded" and "\(\{f\}\) is upper bounded."

\(\exists M\in\mathbb{R}_{+},\forall x\in E,f\left(x\right)\leq M\)

\(\exists g\in\mathcal{F}(E,\mathbb{R}_{+}),\forall x\in E,f\left(x\right)\leq g\left(x\right)\;\)​

(d) Show that, for this order, \(\mathcal{F}(E, \mathbb{R}_+)\) has a smallest element by specifying it.

\(f(x)=0,\forall x\in \R_+\)

Exercise 3 We define the relation \(R\) on \(\mathbb{N}^*\) by \(pRq \iff \exists k \in \mathbb{N}^*, \ q = p^k.\) Show that \(R\) defines a partial order on \(\mathbb{N}^*\). Determine the upper bounds of \(\{2, 3\}\) for this order.

no upper bounds

Exercise 4 We equip \(\mathbb{R}^2\) with the relation denoted \(\prec\) defined by \((x, y) \prec (x', y') \iff x \leq x' \ \text{and} \ y \leq y'.\)

(a) Show that \(\prec\) is an order relation on \(\mathbb{R}^2\). Is the order total?

no

(b) Does the closed disk with center \(O\) and radius 1 have any upper bounds? A greatest element? A supremum?

yes,no,yes

Exercise 5 We define on \(\mathbb{R}^2\) the relation \(\prec\) by \((x, y) \prec (x', y') \iff \left( x < x' \right) \ \text{or} \ \left( x = x' \ \text{and} \ y \leq y' \right)\) Prove that this defines an order relation on \(\mathbb{R}^2\).

Exercise 6 \((\star)\) Let \(E\) be an ordered set. Prove that every subset of \(E\) has a maximal element if and only if every increasing sequence of \(E\) is stationary.

Stationary sequence \((u_n)\), \(\exists k \in \mathbb{N}, \, \text{s.t. } \forall n \geq k, \, u_n = u_k\)

Proof

\(\Rightarrow\)) Let's \(A\subseteq E\) and \(a_m\) is the maximal element in \(A\)

Since \(E\) is an ordered set, thus by transitivity, we can construct any increasing sequence of \(E\)

Consider any increasing sequence \((a_n)\), then \(\forall n\geq m,a_{n}\geq a_{m}\)

Also Since \(a_m\) is the maximal element, then \(\forall n,a_{m}\geq a_{n}\)

By anti-symmetry, we have \(a_m=a_n\)

\(\Leftarrow)\) Consider any increasing sequence \((a_n)\), then \(\forall n\geq m,a_{n}\geq a_{m}\)

Since we have \(a_m=a_n\), then \(\forall n\geq m,a_{m}\geq a_{n}\)

Also since \((a_n)\) is increasing, then \(\forall n\leq m,a_m\geq a_n\)

Then we have \(\forall n,a_m\geq a_n\)

Thus \(a_m\) is the maximal element in \(E\)

Exercise 7 \((\star)\) An order \(\leq\) on a set \(E\) is said to be well-founded if there is no strictly decreasing infinite sequence \((x_n)\) of \(E\). Show that \(\mathbb{N}^2\) equipped with the lexicographic order (the order from exercise 5) is well-founded.

Proof

We define on \(\mathbb{N}^2\) the relation \(\prec\) by \((x, y) \prec (x', y') \iff \left( x < x' \right) \ \text{or} \ \left( x = x' \ \text{and} \ y \leq y' \right)\)

We need to show there is no strictly decreasing infinite sequence \((x_{n},y_{n})\) of \(\mathbb{N}^2\)​

Suppose there exists strictly decreasing infinite sequence \((x_{n},y_{n})\) of \(\mathbb{N}^2\) then \(\forall t,\left(x_{t+1},y_{t+1}\right)\prec\left(x_{t},y_{t}\right)\)

Then \(x_{t+1}<x_{t}\) or ( \(x_{t+1}=x_{t}\) and \(y_{t+1}\leq y_{t}\) )

Then there must exist \(t\) s.t. \(x_t=0\), then \(x_{t+1}=-1\) can not hold, thus \(x_{n+1}=0\)

Then there must exist \(t\) s.t. \(y_{t}=0\), then \(y_{t+1}=-1\) after many steps

Finally, at least \(x\) or \(y\) be negative which is a contradiction to \(\N^2\)

‍