Package natural-fibonacci: Fibonacci numbers

Information

Files

• Package tarball natural-fibonacci-1.74.tgz
• Theory source file natural-fibonacci.thy (included in the package tarball)

Defined Constants

• Data
  • List
    • Fibonacci
      • Fibonacci.random
• Number
  • Natural
    • fibonacci
    • Fibonacci
      • all
      • decode
        • decode.dest
      • encode
        • encode.find
        • encode.mk
      • random
        • random.dest
      • zeckendorf

Theorems

⊦ zeckendorf []

⊦ all = fromFunction fibonacci

⊦ fibonacci 0 = 0

⊦ decode [] = 0

⊦ encode 0 = []

⊦ ∀n. zeckendorf (encode n)

⊦ decode = decode.dest 1 0

⊦ fibonacci 1 = 1

⊦ ∀n. decode (encode n) = n

⊦ ∀n. ∃k. n ≤ fibonacci k

⊦ fibonacci 2 = 1

⊦ ∀n. nth all n = fibonacci n

⊦ encode = λn. encode.find n 1 0

⊦ ∀n. null (encode n) ⇔ n = 0

⊦ ∀f p. decode.dest f p [] = 0

⊦ ∀n. encode n = encode.find n 1 0

⊦ ∀k. fibonacci k = 0 ⇔ k = 0

⊦ ∀l. zeckendorf l ⇔ encode (decode l) = l

⊦ ∀l. decode l = decode.dest 1 0 l

⊦ ∀h t. zeckendorf (h :: t) ⇒ zeckendorf t

⊦ ∀j k. j ≤ k ⇒ fibonacci j ≤ fibonacci k

⊦ ∀j k. fibonacci j < fibonacci k ⇒ j < k

⊦ ∀k. fibonacci (suc (suc k)) = fibonacci (suc k) + fibonacci k

⊦ ∀j. ¬(j = 1) ⇒ fibonacci j < fibonacci (suc j)

⊦ ∀r. random r = random.dest ⊥ 0 1 0 r - 1

⊦ ∀n. ∃k. fibonacci k ≤ n ∧ n < fibonacci (k + 1)

⊦ ∀n. fibonacci (n + 2) = fibonacci (n + 1) + fibonacci n

⊦ ∀l. ¬null l ∧ zeckendorf l ⇒ fibonacci (length l + 1) ≤ decode l

⊦ ∀l₁ l₂. zeckendorf (l₁ @ l₂) ⇒ decode l₁ < fibonacci (length l₁ + 2)

⊦ ∀l₁ l₂. zeckendorf l₁ ∧ zeckendorf l₂ ∧ decode l₁ = decode l₂ ⇒ l₁ = l₂

⊦ ∀h t.
    zeckendorf (h :: t) ⇔
    if null t then h else ¬(h ∧ head t) ∧ zeckendorf t

⊦ ∀l₁ l₂.
    zeckendorf l₁ ∧ zeckendorf l₂ ∧ length l₁ < length l₂ ⇒
    decode l₁ < decode l₂

⊦ ∀f r.
    Fibonacci.random f r =
    let (r₁, r₂) ← split r in random f (random r₁) r₂

⊦ all = unfold (λ(p, f). (p, f, p + f)) (0, 1)

⊦ ∀j k. ¬(j = 1 ∧ k = 2) ∧ j < k ⇒ fibonacci j < fibonacci k

⊦ ∀j k. ¬(j = 2 ∧ k = 1) ∧ fibonacci j ≤ fibonacci k ⇒ j ≤ k

⊦ (zeckendorf [] ⇔ ⊤) ∧
  ∀h t.
    zeckendorf (h :: t) ⇔
    if null t then h else ¬(h ∧ head t) ∧ zeckendorf t

⊦ ∀n f p.
    encode.find n f p =
    let s ← f + p in
    if n < s then encode.mk [] n f p else encode.find n s f

⊦ ∀f p h t.
    decode.dest f p (h :: t) =
    let s ← f + p in let n ← decode.dest s f t in if h then s + n else n

⊦ ∀j k.
    fibonacci (j + (k + 1)) =
    fibonacci j * fibonacci k + fibonacci (j + 1) * fibonacci (k + 1)

⊦ ∀p. p 0 ∧ p 1 ∧ (∀n. p n ∧ p (n + 1) ⇒ p (n + 2)) ⇒ ∀n. p n

⊦ ∀j k.
    nth all (j + (k + 1)) =
    nth all j * nth all k + nth all (j + 1) * nth all (k + 1)

⊦ (∀f p. decode.dest f p [] = 0) ∧
  ∀f p h t.
    decode.dest f p (h :: t) =
    let s ← f + p in let n ← decode.dest s f t in if h then s + n else n

⊦ ∀l n f p.
    encode.mk l n f p =
    if p = 0 then l
    else if f ≤ n then encode.mk (⊤ :: l) (n - f) p (f - p)
    else encode.mk (⊥ :: l) n p (f - p)

⊦ ∀h.
    (∀f g n. (∀m. m + 1 = n ∨ m + 2 = n ⇒ f m = g m) ⇒ h f n = h g n) ⇒
    ∃f. ∀n. f n = h f n

⊦ ∀b n f p r.
    random.dest b n f p r =
    let (r₁, r₂) ← split r in
    let b' ← bit r₁ in
    if b' ∧ b then n
    else let s ← f + p in random.dest b' (if b' then s + n else n) s f r₂

External Type Operators

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

External Constants

• =
• select
• Data
  • Bool
    • ∀
    • ∧
    • ⇒
    • ∃
    • ∨
    • ¬
    • cond
    • ⊥
    • ⊤
  • List
    • ::
    • @
    • []
    • head
    • length
    • null
    • random
  • Pair
    • ,
    • fst
    • snd
  • Stream
    • fromFunction
    • head
    • nth
    • tail
    • unfold
• Function
  • ↑
  • ∘
• Number
  • Natural
    • *
    • +
    • -
    • <
    • ≤
    • bit0
    • bit1
    • minimal
    • suc
    • zero
• Probability
  • Random
    • bit
    • split
• Relation
  • subrelation
  • wellFounded

Assumptions

⊦ ⊤

⊦ null []

⊦ wellFounded (<)

⊦ ¬⊥ ⇔ ⊤

⊦ ¬⊤ ⇔ ⊥

⊦ length [] = 0

⊦ bit0 0 = 0

⊦ ∀t. t ⇒ t

⊦ ∀n. 0 ≤ n

⊦ ∀n. n ≤ n

⊦ ⊥ ⇔ ∀p. p

⊦ ∀t. t ∨ ¬t

⊦ ∀m. ¬(m < 0)

⊦ ∀n. n < suc n

⊦ ∀n. n ≤ suc n

⊦ (¬) = λp. p ⇒ ⊥

⊦ (∃) = λp. p ((select) p)

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

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

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

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

⊦ ∀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. 0 * n = 0

⊦ ∀n. 0 + n = n

⊦ ∀m. m + 0 = m

⊦ ∀l. [] @ l = l

⊦ ∀l. l @ [] = l

⊦ ∀f. nth (fromFunction f) = f

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

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

⊦ ∀t. t ⇒ ⊥ ⇔ ¬t

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

⊦ ∀m. 1 * m = m

⊦ ∀l. null l ⇔ l = []

⊦ ∀s. head s = nth s 0

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

⊦ ∀m n. m ≤ m + n

⊦ ∀m n. n ≤ m + n

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

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

⊦ ∀m. suc m = m + 1

⊦ ∀m. m ≤ 0 ⇔ m = 0

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

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

⊦ ∀a b. fst (a, b) = a

⊦ ∀a b. snd (a, b) = b

⊦ ∀h t. head (h :: t) = h

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

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

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

⊦ ∀s. nth s 1 = head (tail s)

⊦ ∀f y. (let x ← y in f x) = f y

⊦ ∀x. ∃a b. x = (a, b)

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

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

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

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

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

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

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

⊦ ∀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

⊦ ∀p. (∀b. p b) ⇔ p ⊤ ∧ p ⊥

⊦ ∀f b. head (unfold f b) = fst (f b)

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

⊦ ∀p. ¬(∀x. p x) ⇔ ∃x. ¬p x

⊦ ∀p. ¬(∃x. p x) ⇔ ∀x. ¬p x

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

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

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

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

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

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

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

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

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

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

⊦ ∀s n. nth s (suc n) = nth (tail s) n

⊦ ∀r s. subrelation r s ∧ wellFounded s ⇒ wellFounded r

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

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

⊦ ∀f b. tail (unfold f b) = unfold f (snd (f b))

⊦ ∀p. (∀x. p x) ⇔ ∀a b. p (a, b)

⊦ ∀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. n ≤ m ⇒ m - n + n = m

⊦ ∀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

⊦ ∀p q. p ∧ (∃x. q x) ⇔ ∃x. p ∧ q x

⊦ ∀p q. p ∨ (∀x. q x) ⇔ ∀x. p ∨ q x

⊦ ∀p q. p ∨ (∃x. q x) ⇔ ∃x. p ∨ q x

⊦ ∀p q. (∃x. p x) ∧ q ⇔ ∃x. p x ∧ q

⊦ ∀p q. (∃x. p x) ∨ q ⇔ ∃x. p x ∨ q

⊦ ∀p q r. p ⇒ q ⇒ r ⇔ p ∧ q ⇒ r

⊦ ∀t₁ t₂ t₃. (t₁ ∨ t₂) ∨ t₃ ⇔ t₁ ∨ t₂ ∨ t₃

⊦ ∀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. m + n < m + p ⇔ n < p

⊦ ∀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

⊦ ∀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

⊦ ∀l₁ l₂ l₃. l₁ @ l₂ @ l₃ = (l₁ @ l₂) @ l₃

⊦ ∀s₁ s₂. (∀n. nth s₁ n = nth s₂ n) ⇒ s₁ = s₂

⊦ ∀r. (∀x. ∃y. r x y) ⇔ ∃f. ∀x. r x (f x)

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

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

⊦ ∀r s. subrelation r s ⇔ ∀x y. r x y ⇒ s x y

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

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

⊦ ∀b f x y. f (if b then x else y) = if b then f x else f y

⊦ ∀p. (∀n. (∀m. m < n ⇒ p m) ⇒ p n) ⇒ ∀n. p n

⊦ ∀p g h. ∃f. ∀x. f x = if p x then f (g x) else h x

⊦ ∀p q. (∀x. p x ∧ q x) ⇔ (∀x. p x) ∧ ∀x. q x

⊦ ∀p q. (∃x. p x) ∨ (∃x. q x) ⇔ ∃x. p x ∨ q x

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

⊦ ∀p. (∃n. p n) ⇔ p ((minimal) p) ∧ ∀m. m < (minimal) p ⇒ ¬p m

⊦ ∀h₁ h₂ t₁ t₂. h₁ :: t₁ = h₂ :: t₂ ⇔ h₁ = h₂ ∧ t₁ = t₂

⊦ ∀p c x y. p (if c then x else y) ⇔ (c ⇒ p x) ∧ (¬c ⇒ p y)

⊦ ∀b f. ∃fn. fn [] = b ∧ ∀h t. fn (h :: t) = f h t (fn t)

⊦ ∀f b n k. nth (unfold f b) (n + k) = nth (unfold f (((snd ∘ f) ↑ n) b)) k

⊦ ∀r.
    wellFounded r ⇒
    ∀h.
      (∀f g x. (∀z. r z x ⇒ f z = g z) ⇒ h f x = h g x) ⇒
      ∃f. ∀x. f x = h f x

OpenTheory package document generated by opentheory 1.3 (release 20160501)