mathlib documentation

data.​list.​intervals

data.​list.​intervals

def list.​Ico  :
ℕ → ℕ → list ℕ

Ico n m is the list of natural numbers n ≤ x < m. (Ico stands for "interval, closed-open".)

See also data/set/intervals.lean for set.Ico, modelling intervals in general preorders, and multiset.Ico and finset.Ico for n ≤ x < m as a multiset or as a finset.

@TODO (anyone): Define Ioo and Icc, state basic lemmas about them. @TODO (anyone): Prove that finset.Ico and set.Ico agree. @TODO (anyone): Also do the versions for integers? @TODO (anyone): One could generalise even further, defining 'locally finite partial orders', for which set.Ico a b is [finite], and 'locally finite total orders', for which there is a list model.

Equations
@[simp]
theorem list.​Ico.​length (n m : ℕ) :
(list.Ico n m).length = m - n

theorem list.​Ico.​nodup (n m : ℕ) :

@[simp]
theorem list.​Ico.​mem {n m l : ℕ} :
l ∈ list.Ico n m ↔ n ≤ l ∧ l < m

theorem list.​Ico.​eq_nil_of_le {n m : ℕ} :
m ≤ n → list.Ico n m = list.nil

theorem list.​Ico.​map_add (n m k : ℕ) :
list.map (has_add.add k) (list.Ico n m) = list.Ico (n + k) (m + k)

theorem list.​Ico.​map_sub (n m k : ℕ) :
k ≤ n → list.map (λ (x : ℕ), x - k) (list.Ico n m) = list.Ico (n - k) (m - k)

@[simp]

@[simp]

theorem list.​Ico.​append_consecutive {n m l : ℕ} :
n ≤ m → m ≤ l → list.Ico n m ++ list.Ico m l = list.Ico n l

@[simp]

@[simp]
theorem list.​Ico.​succ_singleton {n : ℕ} :
list.Ico n (n + 1) = [n]

theorem list.​Ico.​succ_top {n m : ℕ} :
n ≤ m → list.Ico n (m + 1) = list.Ico n m ++ [m]

theorem list.​Ico.​eq_cons {n m : ℕ} :
n < m → list.Ico n m = n :: list.Ico (n + 1) m

@[simp]
theorem list.​Ico.​pred_singleton {m : ℕ} :
0 < m → list.Ico (m - 1) m = [m - 1]

theorem list.​Ico.​chain'_succ (n m : ℕ) :
list.chain' (λ (a b : ℕ), b = a.succ) (list.Ico n m)

@[simp]
theorem list.​Ico.​not_mem_top {n m : ℕ} :

theorem list.​Ico.​filter_lt_of_top_le {n m l : ℕ} :
m ≤ l → list.filter (λ (x : ℕ), x < l) (list.Ico n m) = list.Ico n m

theorem list.​Ico.​filter_lt_of_le_bot {n m l : ℕ} :
l ≤ n → list.filter (λ (x : ℕ), x < l) (list.Ico n m) = list.nil

theorem list.​Ico.​filter_lt_of_ge {n m l : ℕ} :
l ≤ m → list.filter (λ (x : ℕ), x < l) (list.Ico n m) = list.Ico n l

@[simp]
theorem list.​Ico.​filter_lt (n m l : ℕ) :
list.filter (λ (x : ℕ), x < l) (list.Ico n m) = list.Ico n (min m l)

theorem list.​Ico.​filter_le_of_le_bot {n m l : ℕ} :
l ≤ n → list.filter (λ (x : ℕ), l ≤ x) (list.Ico n m) = list.Ico n m

theorem list.​Ico.​filter_le_of_top_le {n m l : ℕ} :
m ≤ l → list.filter (λ (x : ℕ), l ≤ x) (list.Ico n m) = list.nil

theorem list.​Ico.​filter_le_of_le {n m l : ℕ} :
n ≤ l → list.filter (λ (x : ℕ), l ≤ x) (list.Ico n m) = list.Ico l m

@[simp]
theorem list.​Ico.​filter_le (n m l : ℕ) :
list.filter (λ (x : ℕ), l ≤ x) (list.Ico n m) = list.Ico (max n l) m

theorem list.​Ico.​filter_lt_of_succ_bot {n m : ℕ} :
n < m → list.filter (λ (x : ℕ), x < n + 1) (list.Ico n m) = [n]

@[simp]
theorem list.​Ico.​filter_le_of_bot {n m : ℕ} :
n < m → list.filter (λ (x : ℕ), x ≤ n) (list.Ico n m) = [n]

theorem list.​Ico.​trichotomy (n a b : ℕ) :
n < a ∨ b ≤ n ∨ n ∈ list.Ico a b

For any natural numbers n, a, and b, one of the following holds:

  1. n < a
  2. n ≥ b
  3. n ∈ Ico a b