Explicit least witnesses to existentials on positive natural numbers #

Implemented via calling out to Nat.find.

source

ink

instance PNat.decidablePredExistsNat {p : ℕ+ → Prop} [inst : DecidablePred p] :

DecidablePred fun n' => ∃ n x, p n

Equations

PNat.decidablePredExistsNat n' = decidable_of_iff' (∃ h, p { val := n', property := h }) (_ : (∃ x x_1, p x) ↔ ∃ h, p { val := n', property := h })

source

ink

def PNat.findX {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) :

{ n // p n ∧ ∀ (m : ℕ+), m < n → ¬p m }

The PNat version of Nat.findX

Equations

One or more equations did not get rendered due to their size.

source

ink

def PNat.find {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) :

ℕ+

If p is a (decidable) predicate on ℕ+ and hp : ∃ (n : ℕ+), p n∃ (n : ℕ+), p n is a proof that there exists some positive natural number satisfying p, then PNat.find hp is the smallest positive natural number satisfying p. Note that PNat.find is protected, meaning that you can't just write find, even if the PNat namespace is open.

The API for PNat.find is:

PNat.find_spec is the proof that PNat.find hp satisfies p.
PNat.find_min is the proof that if m < PNat.find hp then m does not satisfy p.
PNat.find_min' is the proof that if m does satisfy p then PNat.find hp ≤ m≤ m.

Equations

PNat.find h = ↑(PNat.findX h)

source

ink

theorem PNat.find_spec {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) :

p (PNat.find h)

source

ink

theorem PNat.find_min {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) {m : ℕ+} :

m < PNat.find h → ¬p m

source

ink

theorem PNat.find_min' {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) {m : ℕ+} (hm : p m) :

PNat.find h ≤ m

source

ink

theorem PNat.find_eq_iff {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) {m : ℕ+} :

PNat.find h = m ↔ p m ∧ ∀ (n : ℕ+), n < m → ¬p n

source

ink

@[simp]

theorem PNat.find_lt_iff {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) (n : ℕ+) :

PNat.find h < n ↔ ∃ m, m < n ∧ p m

source

ink

@[simp]

theorem PNat.find_le_iff {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) (n : ℕ+) :

PNat.find h ≤ n ↔ ∃ m, m ≤ n ∧ p m

source

ink

@[simp]

theorem PNat.le_find_iff {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) (n : ℕ+) :

n ≤ PNat.find h ↔ ∀ (m : ℕ+), m < n → ¬p m

source

ink

@[simp]

theorem PNat.lt_find_iff {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) (n : ℕ+) :

n < PNat.find h ↔ ∀ (m : ℕ+), m ≤ n → ¬p m

source

ink

@[simp]

theorem PNat.find_eq_one {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) :

PNat.find h = 1 ↔ p 1

source

ink

theorem PNat.one_le_find {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) :

1 < PNat.find h ↔ ¬p 1

source

ink

theorem PNat.find_mono {p : ℕ+ → Prop} {q : ℕ+ → Prop} [inst : DecidablePred p] [inst : DecidablePred q] (h : (n : ℕ+) → q n → p n) {hp : ∃ n, p n} {hq : ∃ n, q n} :

PNat.find hp ≤ PNat.find hq

source

ink

theorem PNat.find_le {p : ℕ+ → Prop} [inst : DecidablePred p] {n : ℕ+} {h : ∃ n, p n} (hn : p n) :

PNat.find h ≤ n

source

ink

theorem PNat.find_comp_succ {p : ℕ+ → Prop} [inst : DecidablePred p] (h : ∃ n, p n) (h₂ : ∃ n, p (n + 1)) (h1 : ¬p 1) :

PNat.find h = PNat.find h₂ + 1