Package natural-fibonacci: Fibonacci numbers

Information

Files

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

Defined Constants

• Number
  • Natural
    • fibonacci
    • Fibonacci
      • decode
        • decode.dest
      • encode
        • encode.find
        • encode.mk
      • fromRandom
        • fromRandom.dest
      • zeckendorf

Theorems

⊦ zeckendorf []

⊦ fibonacci 0 = 0

⊦ decode [] = 0

⊦ encode 0 = []

⊦ ∀n. zeckendorf (encode n)

⊦ fibonacci 1 = 1

⊦ ∀n. decode (encode n) = n

⊦ ∀n. ∃k. n ≤ fibonacci k

⊦ fibonacci 2 = 1

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

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

⊦ ∀n s₁ r₂.
    fromRandom
      (fromStream (interleave (encode (n + 1) @ ⊤ :: s₁) (toStream r₂))) =
    (n, r₂)

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

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

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

⊦ ∀r.
    fromRandom r =
    let (r₁, r₂) ← split r in (fromRandom.dest ⊥ 0 1 0 r₁ - 1, r₂)

⊦ ∀p. p 0 ∧ p 1 ∧ (∀n. p n ∧ p (n + 1) ⇒ p (n + 2)) ⇒ ∀n. p 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)

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

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

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
  • Pair
    • ,
  • Stream
    • ::
    • @
    • head
    • interleave
    • split
    • tail
• Function
  • id
• Number
  • Natural
    • *
    • +
    • -
    • <
    • ≤
    • bit0
    • bit1
    • even
    • minimal
    • suc
    • zero
• Probability
  • Random
    • bit
    • fromStream
    • split
    • toStream
• Relation
  • subrelation
  • wellFounded

Assumptions

⊦ ⊤

⊦ null []

⊦ wellFounded (<)

⊦ ¬⊥ ⇔ ⊤

⊦ ¬⊤ ⇔ ⊥

⊦ length [] = 0

⊦ bit0 0 = 0

⊦ ∀t. t ⇒ t

⊦ ∀n. 0 ≤ n

⊦ ∀n. n ≤ n

⊦ ⊥ ⇔ ∀p. p

⊦ ∀x. id x = x

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

⊦ ∀r. fromStream (toStream r) = r

⊦ ∀l. [] @ l = l

⊦ ∀l. l @ [] = l

⊦ ∀s. [] @ s = s

⊦ ∀s. toStream (fromStream s) = s

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

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

⊦ ∀t. t ⇒ ⊥ ⇔ ¬t

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

⊦ ∀m. 1 * m = m

⊦ ∀l. null l ⇔ l = []

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

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

⊦ ∀m. m ≤ 0 ⇔ m = 0

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

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

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

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

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

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

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

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

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

⊦ ∀n. 2 * n = n + n

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

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

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

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

⊦ ∀s₁ s₂. split (interleave s₁ s₂) = (s₁, s₂)

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

⊦ (∧) = λ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₂

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

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

⊦ ∀r. bit r = (head (toStream r), fromStream (tail (toStream r)))

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

⊦ ∀m n. even (m * n) ⇔ even m ∨ even n

⊦ ∀m n. even (m + n) ⇔ even m ⇔ even n

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

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

⊦ ∀l. l = [] ∨ ∃h t. l = h :: t

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

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

⊦ ∀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. (∀x. p ∨ q x) ⇔ p ∨ ∀x. q x

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

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

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

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

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

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

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

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

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

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

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

⊦ (∃!) = λp. (∃) p ∧ ∀x y. p x ∧ p y ⇒ x = y

⊦ ∀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 ⇒ q x) ⇒ (∀x. p x) ⇒ ∀x. q 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

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

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

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

⊦ ∀m n p. m * n < m * p ⇔ ¬(m = 0) ∧ n < p

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

⊦ ∀a b a' b'. (a, b) = (a', b') ⇔ a = a' ∧ b = b'

⊦ ∀p₁ p₂ q₁ q₂. (p₁ ⇒ p₂) ∧ (q₁ ⇒ q₂) ⇒ p₁ ∧ q₁ ⇒ p₂ ∧ q₂

⊦ ∀p₁ p₂ q₁ q₂. (p₂ ⇒ p₁) ∧ (q₁ ⇒ q₂) ⇒ (p₁ ⇒ q₁) ⇒ p₂ ⇒ q₂

⊦ ∀r.
    split r =
    let (s₁, s₂) ← split (toStream r) in (fromStream s₁, fromStream s₂)

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

⊦ ∀r. wellFounded r ⇔ ∀p. (∀x. (∀y. r y x ⇒ p y) ⇒ p x) ⇒ ∀x. p x

OpenTheory package summary generated by opentheory 1.2 (release 20131210)