Package natural-distance: Natural number distance function

Information

Files

• Package tarball natural-distance-1.5.tgz
• Theory file natural-distance.thy (included in the package tarball)

Defined Constant

• Number
  • Natural
    • distance

Theorems

⊦ ∀n. distance 0 n = n

⊦ ∀n. distance n 0 = n

⊦ ∀n. distance n n = 0

⊦ ∀m n. distance m n = distance n m

⊦ ∀m n. distance m n ≤ m + n

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

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

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

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

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

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

⊦ ∀m n. distance m n = if m ≤ n then n - m else m - n

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

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

⊦ ∀m n p q. distance m p ≤ distance (m + n) (p + q) + distance n q

⊦ ∀m n p q. distance (m + n) (p + q) ≤ distance m p + distance n q

⊦ ∀m n p q. distance m n + distance n p ≤ q ⇒ distance m p ≤ q

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

⊦ ∀P x y. P (distance x y) ⇔ ∀d. (x = y + d ⇒ P d) ∧ (y = x + d ⇒ P d)

⊦ ∀m n p q r s.
    distance m n ≤ r ∧ distance p q ≤ s ⇒
    distance m p ≤ distance n q + (r + s)

Input Type Operators

• →
• bool
• Number
  • Natural
    • natural

Input Constants

• =
• Data
  • Bool
    • ∀
    • ∧
    • ⇒
    • ∃
    • ∨
    • ~
    • cond
    • F
    • T
• Number
  • Natural
    • *
    • +
    • -
    • <
    • ≤
    • suc
    • zero

Assumptions

⊦ T

⊦ ∀n. 0 ≤ n

⊦ ∀n. n ≤ n

⊦ F ⇔ ∀p. p

⊦ ∀t. t ∨ ¬t

⊦ (~) = λp. p ⇒ F

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

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

⊦ ∀x. x = x ⇔ T

⊦ ∀n. ¬(suc n = 0)

⊦ ∀m. m - 0 = m

⊦ ∀n. n - n = 0

⊦ ∀m n. m ≤ m + n

⊦ ∀m n. n ≤ m + n

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

⊦ (¬T ⇔ F) ∧ (¬F ⇔ T)

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

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

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

⊦ ∀m n. m ≤ n ∨ n ≤ m

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

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

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

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

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

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

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

⊦ ∀P a. (∀x. x = a ⇒ P x) ⇔ P a

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

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

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

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

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

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

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

⊦ ∀t1 t2. (if T then t1 else t2) = t1 ∧ (if F then t1 else t2) = t2

⊦ ∀m n. n ≤ m ⇒ (m - n = 0 ⇔ m = n)

⊦ ∀m n p. p ≤ n ⇒ m + n - (m + p) = n - p

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

⊦ (∀n. 0 * n = 0) ∧ ∀m n. suc m * n = m * n + n

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

⊦ ∀m n p. p ≤ n ⇒ m * (n - p) = m * n - m * p

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

⊦ ∀t. ((T ⇔ t) ⇔ t) ∧ ((t ⇔ T) ⇔ t) ∧ ((F ⇔ t) ⇔ ¬t) ∧ ((t ⇔ F) ⇔ ¬t)

⊦ ∀t. (T ∧ t ⇔ t) ∧ (t ∧ T ⇔ t) ∧ (F ∧ t ⇔ F) ∧ (t ∧ F ⇔ F) ∧ (t ∧ t ⇔ t)

⊦ ∀t. (T ∨ t ⇔ T) ∧ (t ∨ T ⇔ T) ∧ (F ∨ t ⇔ t) ∧ (t ∨ F ⇔ t) ∧ (t ∨ t ⇔ t)

⊦ ∀t. (T ⇒ t ⇔ t) ∧ (t ⇒ T ⇔ T) ∧ (F ⇒ t ⇔ T) ∧ (t ⇒ t ⇔ T) ∧ (t ⇒ F ⇔ ¬t)

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

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