Tuesday 11 July 2017

Functions on ordered set

A simple thing that I encountered during my tutorial sessions so I decided to share it here.


Let $(A, \geq)$ be a partially ordered set.

If $(A,+, \times$) is a ring we may add an order $\geq$ that cooperates with the binary operations if

- $a\geq b \Rightarrow ac \geq bc$, if $c \geq 1$.
- $a\geq b \Rightarrow a+c \geq b+c$.

That in fact decide much of the order, and denies the existence of order for any rings with finite characteristic or invertible elements. (That is why complete totally ordered field is so rare, too.) Clearly a finite ring has finite characteristic - and it will be hard to put an partial order on it. If a space has sub-structure that looks like a finite ring it might be bad to have an order as well.

Example 1. We all know that $\mathbb{C}$ has no total order. It is possible to assign a partial order to it that is consistent with the order on the reals? The answer is no, too.

Problem. Consider a poset $(\mathbb{C}, +, \times, \geq)$ that cooperates with the real order. Let $\omega = e^{q\pi i}\neq \pm 1$ where $q\in \mathbb{Q}$. Show that  $\omega$ is not related to 1. Hence or otherwise, show that such an order does not exist.


To further demonstrate why orders cannot cooperate with binary operations we look at the following example.

Definition 2. Let $f:(A, \geq) \to (B, \geq ')$ be a function. $f$ is said to be increasing if $a\geq b$ implies $f(a) \geq ' f(b)$.

Since the strength of different orders varies, it is very hard to compare maximality in different spaces.

Proposition 3. Let $f:(A, \geq) \to (B, \geq ')$ be an increasing bijection. Maximality of $a\in A$ does not imply maximality of $f(a)\in B$.

Proof. Take the identity map of $f: (A, =)\to (A, \geq)$ where $A = \left\{ 1,2\right\}$ and consider 1. 1 is maximal under the equality order but not maximal under the $\geq$ order.

But then crafting an example with respective to the same order is much harder.

Proposition 4. Let $f:(A, \geq) \to (A, \geq)$ be an increasing bijection. Maximality of $a\in A$ does not imply maximality of $f(a)\in B$.

Proof. Consider $A = \mathbb{Z}$ with the order $s \geq t$ iff $(s,t) = (2n+1,2n)$ where $n\in \mathbb{N}$ plus the reflexive relations. The function $f(n) = n+2$ is an increasing bijection, but the maximality of $0$ does not imply the maximality of $f(0) = 2$.

The reason behind is that finite poset failed to work here.

Theorem 5. Let $f:(A, \geq)\to (A, \geq)$ be an increasing bijection, where $|A| < \infty$. Then maximality of $a\in A$ implies maximality of $f(a)\in A$.

Proof. For $a\in A$ define $\langle a \rangle = \left\{ f^k(a) \mid k \in \mathbb{Z}\right\}$. If $A$ is finite then so as $\langle a \rangle$, so there exists $p,q\in \mathbb{Z}$ so that $f^p(a) = f^q(a)$. Taking inverses we have $f^k(a) = a$ for some $k \in \mathbb{N}$. [This is a standard algebra argument.]

Suppose there exists partial order $\geq$ so that $a$ is maximal and $f(a)$ is not, then we have $c \in A$ so that $c > f(a)$. But that implies $f^{k-1}(c) > f^k(a) = a$ which is a contradiction.

Problem. The function $f$ is decreasing if $a\geq b$ implies $f(a) \leq f(b)$. Does the above results [3,4,5] holds for decreasing bijection?

No comments:

Post a Comment