Package natural-bits-thm: Properties of natural number to bit-list conversions

Information

Files

• Package tarball natural-bits-thm-1.57.tgz
• Theory source file natural-bits-thm.thy (included in the package tarball)

Theorems

⊦ Bits.normalList []

⊦ ¬Bits.head 0

⊦ Bits.head 1

⊦ fromBool ⊥ = 0

⊦ Bits.fromList [] = 0

⊦ Bits.tail 0 = 0

⊦ Bits.width 0 = 0

⊦ Bits.toList 0 = []

⊦ ∀n. Bits.normalList (Bits.toList n)

⊦ ¬Bits.head 2

⊦ fromBool ⊤ = 1

⊦ Bits.tail 1 = 0

⊦ ∀i. ¬Bits.bit 0 i

⊦ Bits.width 1 = 1

⊦ ∀b. Bits.head (fromBool b) ⇔ b

⊦ ∀b. Bits.tail (fromBool b) = 0

⊦ ∀n. Bits.fromList (Bits.toList n) = n

⊦ ∀n. Bits.and 0 n = 0

⊦ ∀n. Bits.and n 0 = 0

⊦ ∀n. Bits.and n n = n

⊦ ∀n. Bits.append [] n = n

⊦ ∀k. Bits.bound 0 k = 0

⊦ ∀n. Bits.bound n 0 = 0

⊦ ∀n. Bits.or 0 n = n

⊦ ∀n. Bits.or n 0 = n

⊦ ∀n. Bits.or n n = n

⊦ ∀k. Bits.shiftLeft 0 k = 0

⊦ ∀n. Bits.shiftLeft n 0 = n

⊦ ∀k. Bits.shiftRight 0 k = 0

⊦ ∀n. Bits.shiftRight n 0 = n

⊦ Bits.toList 1 = ⊤ :: []

⊦ ∀b. fromBool b < 2

⊦ ∀b. Bits.width (fromBool b) = fromBool b

⊦ ∀b. Bits.cons b 0 = fromBool b

⊦ ∀n. Bits.bit n 0 ⇔ Bits.head n

⊦ ∀n. length (Bits.toList n) = Bits.width n

⊦ ∀k. Bits.fromList (replicate ⊥ k) = 0

⊦ ∀n. Bits.bound n (Bits.width n) = n

⊦ ∀n. Bits.shiftRight n (Bits.width n) = 0

⊦ ∀l. Bits.width (Bits.fromList l) ≤ length l

⊦ ∀m n. m ≤ Bits.or m n

⊦ ∀m n. n ≤ Bits.or m n

⊦ ∀m n. Bits.and m n ≤ m

⊦ ∀m n. Bits.and m n ≤ n

⊦ ∀n k. Bits.bound n k ≤ n

⊦ ∀b. fromBool b = 0 ⇔ ¬b

⊦ ∀b. Bits.fromList (b :: []) = fromBool b

⊦ ∀b. fromBool b = 1 ⇔ b

⊦ ∀n. ¬Bits.head (2 * n)

⊦ ∀n. Bits.tail n = Bits.shiftRight n 1

⊦ ∀n. Bits.head (suc n) ⇔ ¬Bits.head n

⊦ ∀k. Bits.toVector 0 k = replicate ⊥ k

⊦ ∀n. Bits.shiftRight n 1 = Bits.tail n

⊦ ∀n. Bits.cons (Bits.head n) (Bits.tail n) = n

⊦ ∀h t. Bits.head (Bits.cons h t) ⇔ h

⊦ ∀h t. Bits.tail (Bits.cons h t) = t

⊦ ∀n k. length (Bits.toVector n k) = k

⊦ ∀n k. Bits.width (Bits.bound n k) ≤ k

⊦ ∀n. ∃h t. n = Bits.cons h t

⊦ ∀n. n < 2 ↑ Bits.width n

⊦ ∀n. Bits.bit (Bits.tail n) = Bits.bit n ∘ suc

⊦ ∀n. Bits.width n = 0 ⇔ n = 0

⊦ ∀n. Bits.toList n = [] ⇔ n = 0

⊦ ∀n. suc (Bits.cons ⊥ n) = Bits.cons ⊤ n

⊦ ∀n. Bits.bound n 1 = fromBool (Bits.head n)

⊦ ∀l. Bits.normalList l ⇔ Bits.toList (Bits.fromList l) = l

⊦ ∀l. Bits.fromList l = 0 ⇔ all (¬) l

⊦ ∀m n. Bits.and m n = Bits.and n m

⊦ ∀m n. Bits.or m n = Bits.or n m

⊦ ∀m n. max m n ≤ Bits.or m n

⊦ ∀m n. Bits.and m n ≤ min m n

⊦ ∀n k. Bits.bound (Bits.shiftLeft n k) k = 0

⊦ ∀n k. Bits.shiftRight (Bits.bound n k) k = 0

⊦ ∀n k. Bits.shiftRight (Bits.shiftLeft n k) k = n

⊦ ∀b. fromBool b mod 2 = fromBool b

⊦ ∀n. fromBool (Bits.head n) = n mod 2

⊦ ∀n. Bits.cons ⊥ n = 2 * n

⊦ ∀n. suc (Bits.cons ⊤ n) = Bits.cons ⊥ (suc n)

⊦ ∀l. Bits.normalList l ⇔ Bits.width (Bits.fromList l) = length l

⊦ ∀l. Bits.fromList l < 2 ↑ length l

⊦ ∀h t. Bits.width (Bits.cons h t) ≤ suc (Bits.width t)

⊦ ∀n k. Bits.shiftRight n k = (Bits.tail ↑ k) n

⊦ ∀n i. Bits.bit n i ⇒ i < Bits.width n

⊦ ∀n k. Bits.fromList (Bits.toVector n k) = Bits.bound n k

⊦ ∀n. (∀i. ¬Bits.bit n i) ⇔ n = 0

⊦ ∀n. (∀i. ¬Bits.bit n i) ⇒ n = 0

⊦ ∀n. Bits.shiftLeft n 1 = 2 * n

⊦ ∀k. Bits.shiftLeft 1 k = 2 ↑ k

⊦ ∀k. Bits.width (Bits.shiftLeft 1 k) = k + 1

⊦ ∀b₁ b₂. fromBool b₁ = fromBool b₂ ⇔ b₁ ⇔ b₂

⊦ ∀h t. Bits.fromList (h :: t) = Bits.cons h (Bits.fromList t)

⊦ ∀n k. Bits.shiftLeft n k = (Bits.cons ⊥ ↑ k) n

⊦ ∀n₁ n₂. n₁ ≤ n₂ ⇒ Bits.width n₁ ≤ Bits.width n₂

⊦ ∀n i. Bits.bit n (suc i) ⇔ Bits.bit (Bits.tail n) i

⊦ ∀n k. Bits.shiftRight n (suc k) = Bits.tail (Bits.shiftRight n k)

⊦ ∀n k. Bits.shiftRight n (suc k) = Bits.shiftRight (Bits.tail n) k

⊦ ∀n k. Bits.width (Bits.shiftLeft n k) ≤ Bits.width n + k

⊦ ∀k n. Bits.shiftLeft n k = 0 ⇔ n = 0

⊦ ∀n k. Bits.bound (Bits.bound n k) k = Bits.bound n k

⊦ ∀n k. Bits.toVector (Bits.bound n k) k = Bits.toVector n k

⊦ ∀k. Bits.width (2 ↑ k - 1) = k

⊦ ∀b₁ b₂. fromBool b₁ < fromBool b₂ ⇔ ¬b₁ ∧ b₂

⊦ ∀b₁ b₂. fromBool b₁ ≤ fromBool b₂ ⇔ ¬b₁ ∨ b₂

⊦ ∀b k. Bits.normalList (replicate b k) ⇔ k = 0 ∨ b

⊦ ∀q n. Bits.compare q n 0 ⇔ q ∧ n = 0

⊦ ∀n k. Bits.toVector n k = map (Bits.bit n) (interval 0 k)

⊦ ∀n₁ n₂. Bits.head (n₁ * n₂) ⇔ Bits.head n₁ ∧ Bits.head n₂

⊦ ∀m n. Bits.head (Bits.and m n) ⇔ Bits.head m ∧ Bits.head n

⊦ ∀m n. Bits.head (Bits.or m n) ⇔ Bits.head m ∨ Bits.head n

⊦ ∀m n. Bits.tail (Bits.and m n) = Bits.and (Bits.tail m) (Bits.tail n)

⊦ ∀m n. Bits.tail (Bits.or m n) = Bits.or (Bits.tail m) (Bits.tail n)

⊦ ∀m n. Bits.width (max m n) = max (Bits.width m) (Bits.width n)

⊦ ∀n k. Bits.shiftLeft n (suc k) = Bits.cons ⊥ (Bits.shiftLeft n k)

⊦ ∀n k. Bits.shiftLeft n (suc k) = Bits.shiftLeft (Bits.cons ⊥ n) k

⊦ ∀m n. Bits.width (m * n) ≤ Bits.width m + Bits.width n

⊦ ∀n k. Bits.bound n k = n ⇔ Bits.width n ≤ k

⊦ ∀n k. Bits.shiftRight n k = 0 ⇔ Bits.width n ≤ k

⊦ ∀n i. i < n ⇒ ∃r. Uniform.random n r = i

⊦ ∀n. Bits.cons ⊤ n = 1 + 2 * n

⊦ ∀q n. Bits.compare q 0 n ⇔ q ∨ ¬(n = 0)

⊦ ∀h t. Bits.normalList (h :: t) ⇔ if null t then h else Bits.normalList t

⊦ ∀n k. Bits.bound n k = n - Bits.shiftLeft (Bits.shiftRight n k) k

⊦ ∀n₁ n₂. Bits.head (n₁ + n₂) ⇔ ¬(Bits.head n₁ ⇔ Bits.head n₂)

⊦ ∀n₁ n₂. Bits.tail (n₁ + Bits.cons ⊥ n₂) = Bits.tail n₁ + n₂

⊦ ∀m n. Bits.or m n + Bits.and m n = m + n

⊦ ∀n k. Bits.bound n k + Bits.shiftLeft (Bits.shiftRight n k) k = n

⊦ ∀n.
    Uniform.random n =
    λr. let w ← Bits.width (n - 1) in Uniform.random.loop n w r

⊦ ∀k. Bits.fromList (replicate ⊤ k) = 2 ↑ k - 1

⊦ ∀h t. Bits.cons h t = 0 ⇔ ¬h ∧ t = 0

⊦ ∀h t. Bits.cons h t = 1 ⇔ h ∧ t = 0

⊦ ∀n k. Bits.width n ≤ k ⇔ n < 2 ↑ k

⊦ ∀n k.
    Bits.bound n (suc k) =
    Bits.cons (Bits.head n) (Bits.bound (Bits.tail n) k)

⊦ ∀h t₁ t₂. Bits.cons h t₁ < Bits.cons h t₂ ⇔ t₁ < t₂

⊦ ∀h t₁ t₂. Bits.cons h t₁ ≤ Bits.cons h t₂ ⇔ t₁ ≤ t₂

⊦ ∀h t n. Bits.append (h :: t) n = Bits.cons h (Bits.append t n)

⊦ ∀n k i. Bits.bit n (k + i) ⇔ Bits.bit (Bits.shiftRight n k) i

⊦ ∀n k₁ k₂.
    Bits.shiftLeft n (k₁ + k₂) = Bits.shiftLeft (Bits.shiftLeft n k₁) k₂

⊦ ∀n k₁ k₂.
    Bits.shiftRight n (k₁ + k₂) = Bits.shiftRight (Bits.shiftRight n k₁) k₂

⊦ ∀n j k. Bits.bound (Bits.bound n j) k = Bits.bound n (min j k)

⊦ ∀k n₁ n₂. Bits.shiftLeft (n₁ * n₂) k = n₁ * Bits.shiftLeft n₂ k

⊦ ∀k n₁ n₂. Bits.shiftLeft n₁ k = Bits.shiftLeft n₂ k ⇔ n₁ = n₂

⊦ ∀k n₁ n₂. Bits.shiftLeft n₁ k ≤ Bits.shiftLeft n₂ k ⇔ n₁ ≤ n₂

⊦ ∀n₁ n₂ k. Bits.bound (n₁ + Bits.shiftLeft n₂ k) k = Bits.bound n₁ k

⊦ ∀m n. (∀i. Bits.bit m i ⇔ Bits.bit n i) ⇒ m = n

⊦ ∀n. Bits.width n = if n = 0 then 0 else Bits.width (Bits.tail n) + 1

⊦ ∀n.
    Bits.toList n =
    if n = 0 then [] else Bits.head n :: Bits.toList (Bits.tail n)

⊦ ∀h t. ¬(t = 0) ⇒ Bits.width (Bits.cons h t) = suc (Bits.width t)

⊦ ∀m n. Bits.width (m + n) ≤ max (Bits.width m) (Bits.width n) + 1

⊦ ∀m n. Bits.or m n = 0 ⇔ m = 0 ∧ n = 0

⊦ ∀l i. Bits.bit (Bits.fromList l) i ⇔ i < length l ∧ nth l i

⊦ ∀l k. k ≤ length l ⇒ Bits.toVector (Bits.fromList l) k = take k l

⊦ ∀l k. Bits.toVector (Bits.fromList l) (length l + k) = l @ replicate ⊥ k

⊦ ∀l₁ l₂.
    Bits.fromList (l₁ @ l₂) =
    Bits.fromList l₁ + Bits.shiftLeft (Bits.fromList l₂) (length l₁)

⊦ ∀h₁ h₂ t₁ t₂. t₁ < t₂ ⇒ Bits.cons h₁ t₁ < Bits.cons h₂ t₂

⊦ ∀h t. Bits.fromList (h :: t) = 0 ⇔ ¬h ∧ Bits.fromList t = 0

⊦ ∀n k. ¬(n = 0) ⇒ Bits.width (Bits.shiftLeft n k) = Bits.width n + k

⊦ ∀n k. Bits.and n (2 ↑ k - 1) = Bits.bound n k

⊦ ∀h₁ h₂ t. Bits.cons h₁ t < Bits.cons h₂ t ⇔ fromBool h₁ < fromBool h₂

⊦ ∀h₁ h₂ t. Bits.cons h₁ t ≤ Bits.cons h₂ t ⇔ fromBool h₁ ≤ fromBool h₂

⊦ ∀m n i. Bits.bit (Bits.and m n) i ⇔ Bits.bit m i ∧ Bits.bit n i

⊦ ∀n i k. Bits.bit (Bits.bound n k) i ⇔ i < k ∧ Bits.bit n i

⊦ ∀m n i. Bits.bit (Bits.or m n) i ⇔ Bits.bit m i ∨ Bits.bit n i

⊦ ∀m n k.
    Bits.bound (Bits.and m n) k =
    Bits.and (Bits.bound m k) (Bits.bound n k)

⊦ ∀m n k.
    Bits.bound (Bits.or m n) k = Bits.or (Bits.bound m k) (Bits.bound n k)

⊦ ∀k n₁ n₂.
    Bits.shiftLeft (n₁ + n₂) k = Bits.shiftLeft n₁ k + Bits.shiftLeft n₂ k

⊦ ∀n j k. Bits.width n ≤ j + k ⇒ Bits.width (Bits.shiftRight n k) ≤ j

⊦ ∀n j k.
    Bits.bound (Bits.shiftLeft n k) (j + k) =
    Bits.shiftLeft (Bits.bound n j) k

⊦ ∀n₁ n₂ k.
    Bits.shiftRight (n₁ + Bits.shiftLeft n₂ k) k =
    Bits.shiftRight n₁ k + n₂

⊦ ∀n j k.
    Bits.shiftRight (Bits.bound n (j + k)) k =
    Bits.bound (Bits.shiftRight n k) j

⊦ ∀n k.
    Bits.bound n (suc k) =
    Bits.bound n k + Bits.shiftLeft (fromBool (Bits.bit n k)) k

⊦ ∀l k.
    Bits.bound (Bits.fromList l) k =
    Bits.fromList (if length l ≤ k then l else take k l)

⊦ ∀l k.
    Bits.shiftRight (Bits.fromList l) k =
    if length l ≤ k then 0 else Bits.fromList (drop k l)

⊦ ∀m n k.
    Bits.toVector (Bits.and m n) k =
    zipWith (∧) (Bits.toVector m k) (Bits.toVector n k)

⊦ ∀m n k.
    Bits.toVector (Bits.or m n) k =
    zipWith (∨) (Bits.toVector m k) (Bits.toVector n k)

⊦ ∀n i. i < n ⇒ ∃r. Uniform.random.loop n (Bits.width (n - 1)) r = i

⊦ ∀p. p 0 ∧ (∀h t. p t ⇒ p (Bits.cons h t)) ⇒ ∀n. p n

⊦ ∀n k i. Bits.bit (Bits.shiftLeft n k) i ⇔ k ≤ i ∧ Bits.bit n (i - k)

⊦ ∀m n k.
    Bits.bound (Bits.bound m k * Bits.bound n k) k = Bits.bound (m * n) k

⊦ ∀m n k.
    Bits.bound (Bits.bound m k + Bits.bound n k) k = Bits.bound (m + n) k

⊦ ∀h₁ h₂ t₁ t₂. Bits.cons h₁ t₁ = Bits.cons h₂ t₂ ⇔ (h₁ ⇔ h₂) ∧ t₁ = t₂

⊦ ∀h₁ h₂ t₁ t₂.
    Bits.and (Bits.cons h₁ t₁) (Bits.cons h₂ t₂) =
    Bits.cons (h₁ ∧ h₂) (Bits.and t₁ t₂)

⊦ ∀h₁ h₂ t₁ t₂.
    Bits.or (Bits.cons h₁ t₁) (Bits.cons h₂ t₂) =
    Bits.cons (h₁ ∨ h₂) (Bits.or t₁ t₂)

⊦ ∀m n p k. m = n + Bits.shiftLeft p k ⇒ Bits.bound m k = Bits.bound n k

⊦ ∀p. p 0 ∧ (∀n. ¬(n = 0) ∧ p (Bits.tail n) ⇒ p n) ⇒ ∀n. p n

⊦ ∀n k.
    Bits.toVector n k =
    if k = 0 then []
    else Bits.head n :: Bits.toVector (Bits.tail n) (k - 1)

⊦ ∀m n j k.
    Bits.width (Bits.bound m k + Bits.shiftLeft n k) ≤ j + k ⇔
    Bits.width n ≤ j

⊦ ∀l k.
    Bits.toVector (Bits.fromList l) k =
    if length l ≤ k then l @ replicate ⊥ (k - length l) else take k l

⊦ ∀h₁ h₂ t₁ t₂.
    Bits.cons h₁ t₁ < Bits.cons h₂ t₂ ⇔
    t₁ < t₂ ∨ t₁ = t₂ ∧ fromBool h₁ < fromBool h₂

⊦ ∀h₁ h₂ t₁ t₂.
    Bits.cons h₁ t₁ ≤ Bits.cons h₂ t₂ ⇔
    t₁ < t₂ ∨ t₁ = t₂ ∧ fromBool h₁ ≤ fromBool h₂

⊦ ∀q h₁ h₂ t₁ t₂.
    Bits.compare q (Bits.cons h₁ t₁) (Bits.cons h₂ t₂) ⇔
    Bits.compare (¬h₁ ∧ h₂ ∨ ¬(h₁ ∧ ¬h₂) ∧ q) t₁ t₂

External Type Operators

• →
• bool
• Data
  • List
    • list
  • Pair
    • ×
• Number
  • Natural
    • natural
• Probability
  • Random
    • random

External Constants

• =
• select
• Data
  • Bool
    • ∀
    • ∧
    • ⇒
    • ∃
    • ∨
    • ¬
    • cond
    • ⊥
    • ⊤
  • List
    • ::
    • @
    • []
    • all
    • drop
    • foldr
    • interval
    • last
    • length
    • map
    • nth
    • null
    • replicate
    • take
    • zipWith
  • Pair
    • ,
• Function
  • ↑
  • id
  • ∘
• Number
  • Natural
    • *
    • +
    • -
    • <
    • ≤
    • ↑
    • bit0
    • bit1
    • div
    • even
    • fromBool
    • log
    • max
    • min
    • mod
    • odd
    • suc
    • zero
    • Bits
      • Bits.and
      • Bits.append
      • Bits.bit
      • Bits.bound
      • Bits.compare
      • Bits.cons
      • Bits.fromList
      • Bits.head
      • Bits.normalList
      • Bits.or
      • Bits.shiftLeft
      • Bits.shiftRight
      • Bits.tail
      • Bits.toList
      • Bits.toVector
      • Bits.width
    • Uniform
      • Uniform.random
        • Uniform.random.loop
• Probability
  • Random
    • bits
    • split

Assumptions

⊦ ⊤

⊦ null []

⊦ ¬odd 0

⊦ ¬⊥ ⇔ ⊤

⊦ ¬⊤ ⇔ ⊥

⊦ length [] = 0

⊦ bit0 0 = 0

⊦ ∀t. t ⇒ t

⊦ ∀n. 0 ≤ n

⊦ ∀n. n ≤ n

⊦ ∀p. all p []

⊦ ⊥ ⇔ ∀p. p

⊦ ∀x. id x = x

⊦ ∀t. t ∨ ¬t

⊦ ∀m. ¬(m < 0)

⊦ ∀n. 0 < suc n

⊦ ∀n. n < suc n

⊦ ∀n. n ≤ suc n

⊦ (¬) = λp. p ⇒ ⊥

⊦ ∀t. (∀x. t) ⇔ t

⊦ ∀t. (λx. t x) = t

⊦ (∀) = λp. p = λx. ⊤

⊦ ∀x. replicate x 0 = []

⊦ ∀t. ¬¬t ⇔ t

⊦ ∀t. (⊤ ⇔ t) ⇔ t

⊦ ∀t. (t ⇔ ⊤) ⇔ t

⊦ ∀t. ⊥ ∧ t ⇔ ⊥

⊦ ∀t. ⊤ ∧ t ⇔ t

⊦ ∀t. t ∧ ⊥ ⇔ ⊥

⊦ ∀t. t ∧ ⊤ ⇔ t

⊦ ∀t. t ∧ t ⇔ t

⊦ ∀t. ⊥ ⇒ t ⇔ ⊤

⊦ ∀t. ⊤ ⇒ t ⇔ t

⊦ ∀t. t ⇒ ⊤ ⇔ ⊤

⊦ ∀t. ⊥ ∨ t ⇔ t

⊦ ∀t. ⊤ ∨ t ⇔ ⊤

⊦ ∀t. t ∨ ⊥ ⇔ t

⊦ ∀t. t ∨ ⊤ ⇔ ⊤

⊦ ∀t. t ∨ t ⇔ t

⊦ ∀n. ¬(suc n = 0)

⊦ ∀n. Bits.head n ⇔ odd n

⊦ ∀m. m * 0 = 0

⊦ ∀n. 0 + n = n

⊦ ∀m. m + 0 = m

⊦ ∀n. min n n = n

⊦ ∀n. Bits.toVector n 0 = []

⊦ ∀m. interval m 0 = []

⊦ ∀l. [] @ l = l

⊦ ∀l. drop 0 l = l

⊦ ∀l. take 0 l = []

⊦ ∀f. f ↑ 0 = id

⊦ ∀f. map f [] = []

⊦ ∀x. last (x :: []) = x

⊦ ∀t. (⊥ ⇔ t) ⇔ ¬t

⊦ ∀t. (t ⇔ ⊥) ⇔ ¬t

⊦ ∀t. t ⇒ ⊥ ⇔ ¬t

⊦ ∀n. bit1 n = suc (bit0 n)

⊦ ∀n. ¬odd n ⇔ even n

⊦ ∀m. m ↑ 0 = 1

⊦ ∀m. m * 1 = m

⊦ ∀n. n ↑ 1 = n

⊦ ∀n. n div 1 = n

⊦ ∀m. 1 * m = m

⊦ ∀l. null l ⇔ l = []

⊦ ∀l. Bits.fromList l = Bits.append l 0

⊦ ∀f. zipWith f [] [] = []

⊦ ∀h t. ¬null (h :: t)

⊦ ∀m n. m ≤ m + n

⊦ ∀m n. m ≤ max m n

⊦ ∀m n. n ≤ m + n

⊦ ∀m n. n ≤ max m n

⊦ (⇒) = λp q. p ∧ q ⇔ p

⊦ ∀t. (t ⇔ ⊤) ∨ (t ⇔ ⊥)

⊦ ∀m. suc m = m + 1

⊦ ∀n. Bits.toList n = Bits.toVector n (Bits.width n)

⊦ ∀n. odd (suc n) ⇔ ¬odd n

⊦ ∀m. m ≤ 0 ⇔ m = 0

⊦ ∀n. suc n - 1 = n

⊦ ∀t₁ t₂. (if ⊥ then t₁ else t₂) = t₂

⊦ ∀t₁ t₂. (if ⊤ then t₁ else t₂) = t₁

⊦ ∀x n. length (replicate x n) = n

⊦ ∀h t. ¬(h :: t = [])

⊦ ∀b t. (if b then t else t) = t

⊦ ∀m n. length (interval m n) = n

⊦ ∀p x. p x ⇒ p ((select) p)

⊦ ∀f b. foldr f b [] = b

⊦ ∀b. fromBool b = if b then 1 else 0

⊦ ∀n. Bits.tail n = n div 2

⊦ ∀n. 0 < n ⇔ ¬(n = 0)

⊦ ∀n. bit0 (suc n) = suc (suc (bit0 n))

⊦ ∀l. Bits.normalList l ⇔ null l ∨ last l

⊦ ∀x y. x = y ⇔ y = x

⊦ ∀x y. x = y ⇒ y = x

⊦ ∀h t. nth (h :: t) 0 = h

⊦ ∀t₁ t₂. t₁ ∧ t₂ ⇔ t₂ ∧ t₁

⊦ ∀t₁ t₂. t₁ ∨ t₂ ⇔ t₂ ∨ t₁

⊦ ∀m n. m * n = n * m

⊦ ∀m n. m + n = n + m

⊦ ∀m n. m < n ⇒ m ≤ n

⊦ ∀m n. m + n - m = n

⊦ ∀m n. m + n - n = m

⊦ ∀f l. length (map f l) = length l

⊦ ∀n. 2 * n = n + n

⊦ ∀r₁ r₂. ∃r. split r = (r₁, r₂)

⊦ ∀x n. null (replicate x n) ⇔ n = 0

⊦ ∀h t. length (h :: t) = suc (length t)

⊦ ∀n i. Bits.bit n i ⇔ Bits.head (Bits.shiftRight n i)

⊦ ∀m n. ¬(m < n) ⇔ n ≤ m

⊦ ∀m n. ¬(m ≤ n) ⇔ n < m

⊦ ∀m n. m < suc n ⇔ m ≤ n

⊦ ∀m n. suc m ≤ n ⇔ m < n

⊦ ∀m. m = 0 ∨ ∃n. m = suc n

⊦ ∀l n. Bits.append l n = foldr Bits.cons n l

⊦ (∧) = λp q. (λf. f p q) = λf. f ⊤ ⊤

⊦ ∀n. even n ⇔ n mod 2 = 0

⊦ ∀n. ¬(n = 0) ⇒ 0 div n = 0

⊦ (∃) = λp. ∀q. (∀x. p x ⇒ q) ⇒ q

⊦ ∀t₁ t₂. ¬t₁ ⇒ ¬t₂ ⇔ t₂ ⇒ t₁

⊦ ∀m n. m < n ⇒ m div n = 0

⊦ ∀m n. m + suc n = suc (m + n)

⊦ ∀m n. suc m + n = suc (m + n)

⊦ ∀m n. suc m = suc n ⇔ m = n

⊦ ∀m n. suc m < suc n ⇔ m < n

⊦ ∀m n. suc m ≤ suc n ⇔ m ≤ n

⊦ ∀m n. m + n = m ⇔ n = 0

⊦ ∀m n. m + n = n ⇔ m = 0

⊦ ∀n. odd n ⇔ n mod 2 = 1

⊦ ∀k. 1 < k ⇒ log k 1 = 0

⊦ ∀f g x. (f ∘ g) x = f (g x)

⊦ ∀x n. replicate x (suc n) = x :: replicate x n

⊦ ∀t₁ t₂. ¬(t₁ ∧ t₂) ⇔ ¬t₁ ∨ ¬t₂

⊦ ∀t₁ t₂. ¬(t₁ ∨ t₂) ⇔ ¬t₁ ∧ ¬t₂

⊦ ∀m n. max m n = if m ≤ n then n else m

⊦ ∀m n. min m n = if m ≤ n then m else n

⊦ ∀m n. odd (m * n) ⇔ odd m ∧ odd n

⊦ ∀m n. m * suc n = m + m * n

⊦ ∀m n. m ↑ suc n = m * m ↑ n

⊦ ∀m n. map suc (interval m n) = interval (suc m) n

⊦ ∀l₁ l₂. length (l₁ @ l₂) = length l₁ + length l₂

⊦ ∀f n. f ↑ suc n = f ∘ f ↑ n

⊦ ∀f n. f ↑ suc n = f ↑ n ∘ f

⊦ ∀m n. m ≤ n ⇔ ∃d. n = m + d

⊦ ∀f g. (∀x. f x = g x) ⇔ f = g

⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r

⊦ ∀m n. m ≤ n ⇔ m < n ∨ m = n

⊦ ∀n k. Bits.bound n k = n mod 2 ↑ k

⊦ ∀n k. Bits.shiftLeft n k = 2 ↑ k * n

⊦ ∀n k. Bits.shiftRight n k = n div 2 ↑ k

⊦ ∀m n. odd (m + n) ⇔ ¬(odd m ⇔ odd n)

⊦ ∀m n. interval m (suc n) = m :: interval (suc m) n

⊦ ∀m n. m ≤ n ∧ n ≤ m ⇔ m = n

⊦ ∀f. ∃fn. ∀a b. fn (a, b) = f a b

⊦ ∀m n. m < n ⇔ ∃d. n = m + suc d

⊦ ∀n l. length l = n ⇒ ∃r. bits n r = l

⊦ ∀p. (∀x y. p x y) ⇔ ∀y x. p x y

⊦ ∀h t. Bits.cons h t = fromBool h + 2 * t

⊦ ∀m n. m < n ⇔ m ≤ n ∧ ¬(m = n)

⊦ ∀n k.
    Bits.toVector n (suc k) = Bits.head n :: Bits.toVector (Bits.tail n) k

⊦ ∀m n. ¬(m = 0) ⇒ m * n div m = n

⊦ ∀m n. ¬(m = 0) ⇒ m * n mod m = 0

⊦ ∀x y z. x = y ∧ y = z ⇒ x = z

⊦ ∀x₁ x₂ l. last (x₁ :: x₂ :: l) = last (x₂ :: l)

⊦ ∀x n i. i < n ⇒ nth (replicate x n) i = x

⊦ ∀m n p. m * (n * p) = m * n * p

⊦ ∀m n p. m + (n + p) = m + n + p

⊦ ∀m n p. m + n = m + p ⇔ n = p

⊦ ∀p m n. m + p = n + p ⇔ m = n

⊦ ∀m n p. n + m < p + m ⇔ n < p

⊦ ∀m n p. m + n ≤ m + p ⇔ n ≤ p

⊦ ∀m n p. n + m ≤ p + m ⇔ n ≤ p

⊦ ∀m n p. m < n ∧ n ≤ p ⇒ m < p

⊦ ∀m n p. m ≤ n ∧ n ≤ p ⇒ m ≤ p

⊦ ∀l h t. (h :: t) @ l = h :: t @ l

⊦ ∀f g l. map (f ∘ g) l = map f (map g l)

⊦ ∀m n. m * n = 0 ⇔ m = 0 ∨ n = 0

⊦ ∀n r.
    Uniform.random n r =
    let w ← Bits.width (n - 1) in Uniform.random.loop n w r

⊦ ∀f h t. map f (h :: t) = f h :: map f t

⊦ ∀p h t. all p (h :: t) ⇔ p h ∧ all p t

⊦ ∀p. p 0 ∧ (∀n. p n ⇒ p (suc n)) ⇒ ∀n. p n

⊦ ∀n m. ¬(n = 0) ⇒ m mod n mod n = m mod n

⊦ ∀m n. ¬(n = 0) ⇒ (m div n = 0 ⇔ m < n)

⊦ ∀m n. m ↑ n = 0 ⇔ m = 0 ∧ ¬(n = 0)

⊦ ∀q m n. Bits.compare q m n ⇔ if q then m ≤ n else m < n

⊦ ∀m n i. i < n ⇒ nth (interval m n) i = m + i

⊦ ∀m n p. m < min n p ⇔ m < n ∧ m < p

⊦ ∀m n p. m ≤ min n p ⇔ m ≤ n ∧ m ≤ p

⊦ ∀m n p. max n p ≤ m ⇔ n ≤ m ∧ p ≤ m

⊦ ∀m n p. m * (n + p) = m * n + m * p

⊦ ∀m n p. (m + n) * p = m * p + n * p

⊦ ∀n. Bits.width n = if n = 0 then 0 else log 2 n + 1

⊦ ∀f m n. f ↑ (m + n) = f ↑ m ∘ f ↑ n

⊦ ∀m n. ¬(n = 0) ⇒ (m div n) * n + m mod n = m

⊦ ∀p. p [] ∧ (∀h t. p t ⇒ p (h :: t)) ⇒ ∀l. p l

⊦ ∀f b h t. foldr f b (h :: t) = f h (foldr f b t)

⊦ ∀h t n. n < length t ⇒ nth (h :: t) (suc n) = nth t n

⊦ ∀n h t. n ≤ length t ⇒ drop (suc n) (h :: t) = drop n t