Looking for exercices to improve my reasoning skills about ordering relations ( between numbers in particular ).

Question

I think I grasp what is an ordering relation in gerneral ( reflexive, antisymmetric, transitive relation). I also have heard about trichotomy law for real numbers: for all real $a$, $b$ , either $a<b$ OR $a=b$ OR $a>b$.

However I noticed that my intuition is wery weak when it comes to reasoning about ordering relations in general, and in particular, with reasoning relations between numbers.

Does anyone know about a reference in which I could find exercices , in order to improve my ability to make valid inferences about this subjet matter?

Feel free to point a less than college level reference.

Thanks in advance.

Answer 1

Introduction to Lattices and Order by Davey and Priestley is quite good. The first chapter has some exercises that will help you improve your intuitions and reasoning. The same is also true of Lattices and Ordered Algebraic Structures by Blyth.

Answer 2

Order relations on finite sets are relatively easy to imagine. Think of a a total order as a list starting with a largest element, a second largest element, a third largest element and so on. Note that these elements are unique, i.e. for any $x \in X$, there is at most one element directly below $x$ (if you consider the natural order on $\mathbb{N}$, the element directly below $n$ would be $n-1$). For partial orders, this need not neccessarily be true; an element could have several other elements directly below and several elements above it. For example, the $\subseteq$-relation is a partial order on $\mathcal{P}(\mathbb{N})$, and the element $A = \{3,5\}$ has infinitely many elements directly above it (for example, $\{3,5,6\}, \{3,5,4\}, \{3,5,99\}$ and so on).

Regardless of the other answers, proving the following propositions could help you understand the concept of order relations a little better:

• Prove that if $X$ is a finite set and $\leq$ is a total order on $X$, $X$ has a unique smallest element. Then, conclude that $X$ has a unique second smallest element, a unique third smallest element and so on. Lastly, conclude that $\leq$ is a total order on $X$ if and only if there is a bijection $f: X\rightarrow\{1,...,|X|\}$ such that $x \leq y \Leftrightarrow f(x) \leq f(y)$. (This basically shows that all total orders on finite sets behave like a list of natural numbers)
• Prove that if $\leq$ is a partial/total order, then so is $\geq$, defined by $x \geq y :\Leftrightarrow y \leq x$.
• Prove that if $\leq$ is a partial order and $x_1,...,x_n \in X$ such that $x_1 \leq x_2$, $x_2 \leq x_3$, ..., $x_{n-1} \leq x_n$, it follows that $x_1 \leq x_n$.
• Prove that if $\leq$ is a partial order, there can be no $n$ different elements $x_1,...,x_n \in X$ ($n \geq 2$) such that $x_1 \leq x_2 \leq x_3 ... \leq x_n \leq x_1$.
• [Hard] Prove that if $X$ is a finite set and $\leq$ is a reflexive and antisymmetric relation, $\leq$ is a partial order on $X$ if and only if the function $p: \mathcal{P}(X) \rightarrow \mathcal{P}(X), A \mapsto \{x \in A\;|\;\forall y \in A: y \leq x \implies y = x\}$ satisfies $p(A) \subseteq B \subseteq A \implies p(A) = p(B)$ for all sets $A,B \subseteq X$.