What is the pattern in these ordering properties?

221 Views Asked by At

I'm not exactly sure what my question is, but I've observed something about orders and would like to see if there is more of a story to this.


Let's assume $\;\lt\;$ is an order on some unspecified domain, and let's define $$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} \tag{0} a \le b \;\equiv\; a \lt b \lor a = b $$ Now, as I recently discovered (when writing answer https://math.stackexchange.com/a/2251407/11994 where I used $\Ref{3}$), if the domain were the reals or the rationals then the following would hold: \begin{align} \tag{1} \langle \forall z :: z \le a \then z \le b \rangle \;\equiv\; a \le b \\ \tag{2} \langle \forall z :: z \lt a \then z \lt b \rangle \;\equiv\; a \le b \\ \tag{3} \langle \forall z :: z \lt a \then z \le b \rangle \;\equiv\; a \le b \\ \tag{4} \langle \forall z :: z \le a \then z \lt b \rangle \;\equiv\; a \lt b \\ \end{align} Now visually it looks like $\Ref{4}$ is the odd one out, but let's see if that intuition is correct: I was wondering what kind of order we need to prove each of the above.

First let's look at the $\;\when\;$ direction: there, for all 4 equivalences, we only need the fact that $\;\lt\;$ is transitive. For example, for $\Ref{3}$ we have that $\;z \lt a\;$ and $\;a \le b\;$ imply $\;z \lt b\;$ by transitivity.

For the $\;\then\;$ direction of $\Ref{1}$ and $\Ref{4}$ we see that we can simply choose $\;z := a\;$, and use the fact that $\;\le\;$ is reflexive (by definition $\Ref{0}$), in other words $\;a \le a\;$.

For $\Ref{2}$ we can choose $\;z := b\;$, and assuming $\;\lt\;$ is irreflexive (so $\;\lnot(b \lt b)\;$) we get $\;\lnot(b \lt a)\;$, and further assuming $\;\lt\;$ is trichotomous (so $\;a \lt b \lor a = b \lor b \lt a\;$) we get $\;a \le b\;$.

Finally the $\;\then\;$ direction of $\Ref{3}$ is the most complex one. The best approach I found was to go existential: $$\calc \langle \forall z :: z \lt a \then z \le b \rangle \op\then\hint{see below, where $\;\lt\;$ is transitive and irreflexive} \langle \forall z :: z \lt a \then \lnot (b \lt z) \rangle \op\equiv\hint{logic: DeMorgan} \lnot \langle \exists z :: z \lt a \land b \lt z \rangle \op\then\hint{$\;\lt\;$ is dense, so $\;b \lt a\;$ implies there is a $\;z\;$ between them} \lnot (b \lt a) \op\then\hint{$\;\lt\;$ is trichotomous} a \le b \endcalc$$ where the first step above is proved as follows: $$\calc z \le b \;\then\; \lnot(b \lt z) \op\equiv\hint{logic} \lnot(z \le b \land b \lt z) \op\when\hint{$\;\lt\;$ is transitive} \lnot(z \lt z) \op\equiv\hint{$\;\lt\;$ is irreflexive} \true \endcalc$$ So here we require that $\;\lt\;$ is transitive, irreflexive, trichotomous, and dense.

To summarize the requirements on $\;\lt\;$ that seem necessary to prove the statements above: $$\begin{array}{cl} \Ref{1}&\text{transitive}\\ \Ref{2}&\text{transitive, irreflexive, trichotomous}\\ \Ref{3}&\text{transitive, irreflexive, trichotomous, dense}\\ \Ref{4}&\text{transitive}\\ \end{array}$$

So by this table $\Ref{3}$ is the odd one out, since it requires the most properties of the order $\;\lt\;$: specifically it requires density, which makes it true for the reals and the rationals, but false for e.g. the integers.


So I think my questions are: Are all of the above indeed necessary, or can some be weakened? And is there something more to this pattern? Why does density only play a role in one of these equivalences? Is there perhaps a more symmetrical way of organizing this information?

3

There are 3 best solutions below

0
On BEST ANSWER

Assume transitivity.

As you've already made the case, lifting density will give you a straightforward counter-example for $(3) (\implies)$.

To lift trichotomy, one must lift one or more of anti-reflexivity, anti-symmetry, or completeness.

Lifting completeness gives a straighforward lattice counter-example for $(2) (\implies)$, so completeness is necessary for $(2) (\implies)$.

Lifting anti-reflexivity, take a domain with some $a, b$ such that $b < b < a \land \lnot (a < a) \land \lnot (a = b) \land (\forall z: z \ge a \lor z \le b)$. Thus, $z \le b \implies z < b$, so $\forall z: z < a \implies z \le b \implies z < b$, yet $a > b \land \lnot (a = b)$, i.e. $\lnot (a \le b)$ -- so anti-reflexivity is necessary for $(2) (\implies)$ as well.

Anti-reflexivity together with transitivity implies anti-symmetry, so anti-symmetry is also necessary for $(2) (\implies)$.

With all of anti-reflexivity, anti-symmetry ans completeness necessary for $(2) (\implies)$, trichotomy is also necessary. Because $LHS (2) \implies LHS (3)$, any premise necessary for $(2) (\implies)$ is also necessary for $(3) (\implies)$, so trichotomy is also necessary for $(3) (\implies)$.

In conclusion: assuming transitivity, all the other premises are necessary as listed.

(Not sure about the rest of your questions, but you may want to check if 42 fits...)

2
On
  1. Domain D is linear is sufficient. Assume left premise. If not a <= b,
    then a < b, thus b < b. Also if D is almost complete (partial) order, then D holds.

  2. D can be a dense linear order or an almost complete dense order for 3 to hold.

0
On

For $(3)$ we can write:

$$\langle \forall z :: z \lt a \then (z \lt b \lor z=b) \rangle \;\equiv\; a \le b$$

which allows us to use the logic from $(2)$.