Least upper bound and greatest lower bound properties for integers

In this file we prove that a bounded above nonempty set of integers has the greatest element, and a counterpart of this statement for the least element.

Main definitions

• Int.leastOfBdd: if P : ℤ → Prop is a decidable predicate, b is a lower bound of the set {m | P m}, and there exists m : ℤ such that P m (this time, no witness is required), then Int.leastOfBdd returns the least number m such that P m, together with proofs of P m and of the minimality. This definition is computable and does not rely on the axiom of choice.
• Int.greatestOfBdd: a similar definition with all inequalities reversed.

Main statements

• Int.exists_least_of_bdd: if P : ℤ → Prop is a predicate such that the set {m : P m} is bounded below and nonempty, then this set has the least element. This lemma uses classical logic to avoid assumption [DecidablePred P]. See Int.leastOfBdd for a constructive counterpart.

• Int.coe_leastOfBdd_eq: (Int.leastOfBdd b Hb Hinh : ℤ) does not depend on b.

• Int.exists_greatest_of_bdd, Int.coe_greatest_of_bdd_eq: versions of the above lemmas with all inequalities reversed.

Tags

integer numbers, least element, greatest element

def Int.leastOfBdd {P : ℤ → Prop} [DecidablePred P] (b : ℤ) (Hb : ∀ (z : ℤ), P z → b ≤ z) (Hinh : ∃ (z : ℤ), P z) : { lb : ℤ // P lb ∧ ∀ (z : ℤ), P z → lb ≤ z }

A computable version of exists_least_of_bdd: given a decidable predicate on the integers, with an explicit lower bound and a proof that it is somewhere true, return the least value for which the predicate is true.

Equations

• b.leastOfBdd Hb Hinh = ⟨b + ↑(Nat.find ⋯), ⋯⟩

theorem Int.isLeast_coe_leastOfBdd {P : ℤ → Prop} [DecidablePred P] (b : ℤ) (Hb : ∀ (z : ℤ), P z → b ≤ z) (Hinh : ∃ (z : ℤ), P z) : IsLeast {z : ℤ | P z} ↑(b.leastOfBdd Hb Hinh)

Int.leastOfBdd is the least integer satisfying a predicate which is false for all z : ℤ with z < b for some fixed b : ℤ.

theorem Int.exists_least_of_bdd {P : ℤ → Prop} (Hbdd : ∃ (b : ℤ), ∀ (z : ℤ), P z → b ≤ z) (Hinh : ∃ (z : ℤ), P z) : ∃ (lb : ℤ), P lb ∧ ∀ (z : ℤ), P z → lb ≤ z

If P : ℤ → Prop is a predicate such that the set {m : P m} is bounded below and nonempty, then this set has the least element. This lemma uses classical logic to avoid assumption [DecidablePred P]. See Int.leastOfBdd for a constructive counterpart.

theorem Int.coe_leastOfBdd_eq {P : ℤ → Prop} [DecidablePred P] {b b' : ℤ} (Hb : ∀ (z : ℤ), P z → b ≤ z) (Hb' : ∀ (z : ℤ), P z → b' ≤ z) (Hinh : ∃ (z : ℤ), P z) : ↑(b.leastOfBdd Hb Hinh) = ↑(b'.leastOfBdd Hb' Hinh)

def Int.greatestOfBdd {P : ℤ → Prop} [DecidablePred P] (b : ℤ) (Hb : ∀ (z : ℤ), P z → z ≤ b) (Hinh : ∃ (z : ℤ), P z) : { ub : ℤ // P ub ∧ ∀ (z : ℤ), P z → z ≤ ub }

A computable version of exists_greatest_of_bdd: given a decidable predicate on the integers, with an explicit upper bound and a proof that it is somewhere true, return the greatest value for which the predicate is true.

Equations

• b.greatestOfBdd Hb Hinh = match (-b).leastOfBdd ⋯ ⋯ with | ⟨lb, ⋯⟩ => ⟨-lb, ⋯⟩

theorem Int.isGreatest_coe_greatestOfBdd {P : ℤ → Prop} [DecidablePred P] (b : ℤ) (Hb : ∀ (z : ℤ), P z → z ≤ b) (Hinh : ∃ (z : ℤ), P z) : IsGreatest {z : ℤ | P z} ↑(b.greatestOfBdd Hb Hinh)

Int.greatestOfBdd is the greatest integer satisfying a predicate which is false for all z : ℤ with b < z for some fixed b : ℤ.

theorem Int.exists_greatest_of_bdd {P : ℤ → Prop} (Hbdd : ∃ (b : ℤ), ∀ (z : ℤ), P z → z ≤ b) (Hinh : ∃ (z : ℤ), P z) : ∃ (ub : ℤ), P ub ∧ ∀ (z : ℤ), P z → z ≤ ub

If P : ℤ → Prop is a predicate such that the set {m : P m} is bounded above and nonempty, then this set has the greatest element. This lemma uses classical logic to avoid assumption [DecidablePred P]. See Int.greatestOfBdd for a constructive counterpart.

theorem Int.coe_greatestOfBdd_eq {P : ℤ → Prop} [DecidablePred P] {b b' : ℤ} (Hb : ∀ (z : ℤ), P z → z ≤ b) (Hb' : ∀ (z : ℤ), P z → z ≤ b') (Hinh : ∃ (z : ℤ), P z) : ↑(b.greatestOfBdd Hb Hinh) = ↑(b'.greatestOfBdd Hb' Hinh)