Is $a>b\iff \neg(b\geq a)$ true in constructive maths?

Question

1. Is $a>b\iff \neg(b\geq a)\;$ true in constructive maths? Why (not)?

2. Also: is $\neg(a > b) \iff b\geq a\;$ true in constructive maths? Why (not)?

Answer 1

The question does not indicate what kind of objects $a$ and $b$ are supposed to be. I will comment here on the most commonly interesting case: when $a$ and $b$ are real numbers. I will also comment on the case when $a$ and $b$ are natural or rational numbers.

There are many constructive systems, and they differ in many ways. One kind of constructive system treats real numbers as Cauchy sequences of rational numbers with a fixed modulus of convergence, e.g. a sequence $(a_n)$ is defined to be a real number if $|a_n - a_m| < 2^{-n}$ when $n < m$. Bishop's system of constructive analysis treats the reals this way, for example.

In this setting, $(a_n) < (b_n)$ is defined to mean that, for some $m$, $a_m + 2^{-m} < b_m - 2^{-m}$. (See my note below.) This is classically equivalent to $\lim a_n < \lim b_n$, of course, as an easy exercise.

However $(a_n) \leq (b_n)$ is defined to mean that for all $n$, $a_n \leq b_n + 2^{-n}$. (Again, see my note.) This is equivalent to the classical definition of $\lim a_n < \lim b_n$. The key point, though, is that $(a_n) < (b_n)$ is defined as an existential statement and $(a_n)\leq (b_n)$ is defined as a different universal statement. Neither of these statements is defined as the negation of the other one, because that would not be a useful way to define them in constructive mathematics.

In these systems, $(a_n) \leq (b_n)$ is also not defined as $[(a_n) = (b_n)] \lor [(a_n) < (b_n)]$. Neither of the order relations $<$, $\leq$ on the reals is defined in terms of the other.

Finally, $(a_n) = (b_n)$ is defined as $[(a_n) \leq (b_n)] \land [(b_n) \leq (a_n)]$.

These definitions are very different for reals than for naturals or rationals. For the latter two systems, we do have the full trichotomy principle, informally because if we have two naturals or rationals we can just look at them to see which is bigger or whether they are equal. This breaks down for the reals because of their representation as sequences of rationals.

With these definitions of the order on the reals, we do have that $(a_n) < (b_n) \to \lnot [(b_n) \leq (a_n)]$. To see this, assume we have an $m$ such that $a_m + 2^m < b_m - 2^m$. Then, if we also assume $b_m < a_m + 2^m$, we can obtain a contradiction $a_m < a_m$. Obtaining a contradiction is how we prove the negation of a statement in constructive systems.

On the other hand, we will not be able to prove $\lnot (b \leq a) \to (a < b)$ constructively. This is more difficult to show because we have to produce a counterexample. In this case, the underlying issue is Markov's principle. Wikipedia lists an equivalent form of Markov's principle as:

For each real number $x$, if it is contradictory that $x$ is equal to $0$, then there exists $y ∈ Q$ such that $0 < y < |x|$, often expressed by saying that x is apart from, or constructively unequal to, $0$.

In this case, if we know $\lnot (x = 0)$ then we can show constructively $\lnot (|x| \leq 0)$. However, without Markov's principle we cannot prove that $\lnot (x = 0) \to (\exists y)[0 < y < |x|]$, so we cannot prove $\lnot (a \leq 0) \to 0 < a$. Markov's principle is not usually included in constructive systems, although it has been thoroughly studied in that context.

The difficulty with Markov's principle is that it is true in the standard, classical natural numbers, so counterexamples that show it is not provable constructively have to use nonstandard models in some way, which makes these counterexamples difficult.

(Note: I am writing this from the top of my head, and so it may be necessary to replace $2^{-n}$ with $2^{-n-1}$ everywhere above, or similar small changes, depending on the source you'd like to follow. There can be some subtleties. But the key point is still that $a < b$ is a "positive" statement and $a \leq b$ is a "negative" statement, and the difference between them is tied to Markov's principle.)

Answer 2

(Disclamer: This is based on what I remember about counterexamples involving creative subjects in intuitionism and my memory is a bit rusty. I may have made a mistake.)

I'm pretty sure that (1) is not true in intuitionism. Here is why:

Let $P$ be a mathematical proposition which has not yet been proved or disproved. Let $a$ be the decimal number $0.a_1a_2a_3\ldots$ where $a_i$ is 1 if $P$ has been proved or disproved at day number $i$ counting from today, while $a_i$ is $0$ if $P$ has still not been proved or disproved on that day. Let $b$ be $0$.

$b\geq a$ is absurd, as proving that would amount to proving that $P$ cannot be proved or disproved, which cannot be done in intuitionism (it's very different from an axiomatic system). Hence $\neg(b\geq a)$.

On the other hand, $a>b$ is not true (at present) because we cannot indicate a day in the future when $P$ will be proved.

Therefore, (1) is not true (at present).

Answer 3

If $a < b$ then $\neg(b \leq a)$ since if $b < a$ or $b = a$ then we have $a < a$ (Contradiction), so this implication actually holds.

If $a\leq b$ then $\neg(b<a)$, since if $b<a$ then $a < b$ and $a = b$ both imply $a<a$ (Contradiction).

---

To be more precise, here is a Natural deduction proof of the first implication:

a < b (As.)
| b <= a, i.e.: b < a v a = b (As.)
| | b < a (As.)
| | | a < a (Transitivity of <)
| | b < a implies a < a (Implication Introduction)
| | a = b
| | | a < a (property of =)
| | a = b implies a < a (Implication Introduction)
| | a < a (v Elimination)
| | Contradiction (Irreflexivity of <)
| not(b <= a) (Implication Introduction)
a < b implies (not( b <= a )) (Implication Introduction)

Constructing a counterexample for the reverse implications is not so easy. Here I'm assuming the existence of a so called "smooth topos", where you can do smooth infinitesimal analysis.

Given some preparations, define $\Delta := \{x : x^2 = 0\}$. The you can prove: for all $\varepsilon \in \Delta$ we have $\neg 0< \varepsilon$ and (!) $\neg0> \varepsilon$ even though there is an $\varepsilon \in \Delta$ with $\varepsilon \neq 0$. In this case $\neg 0 < \varepsilon$ even though $0\geq \varepsilon$ is false (this proves that the reverse implication in 2. is unprovable). Also since $\varepsilon \neq 0$ and $\neg \varepsilon > 0$ we have $\neg \varepsilon \leq 0$ even though $\varepsilon > 0$ is false (this proves that the reverse implication in 1. is unprovable). For more detailed information see "A primer of smooth infinitesimal analyis" by Bell.

For a more "down to earth" approach you can try modifying the answer given here, I guess.