nat.bend checks
raw source on the hub · import bend-mathlib@0.1.0.0/nat.bend as MNat
1 import
import Base
Laws
law add_zero provedsource · line 4 · raw
@x:Nat -> {Nat.add(x, 0n) == x : Nat}Zero is a right identity for addition: x + 0 = x.
law zero_add provedsource · line 17 · raw
@-x:Nat -> {Nat.add(0n, x) == x : Nat}Zero is a left identity for addition: 0 + x = x.
law add_succ provedsource · line 25 · raw
@n:Nat -> @-m:Nat -> {Nat.add(n, 1n+m) == 1n+Nat.add(n, m) : Nat}Adding a successor on the right: n + (m + 1) = (n + m) + 1.
law succ_add provedsource · line 39 · raw
@-n:Nat -> @-m:Nat -> {Nat.add(1n+n, m) == 1n+Nat.add(n, m) : Nat}Adding a successor on the left: (n + 1) + m = (n + m) + 1.
law add_comm provedsource · line 48 · raw
@n:Nat -> @m:Nat -> {Nat.add(n, m) == Nat.add(m, n) : Nat}Addition is commutative: n + m = m + n.
law add_assoc provedsource · line 70 · raw
@a:Nat -> @-b:Nat -> @-c:Nat -> {Nat.add(Nat.add(a, b), c) == Nat.add(a, Nat.add(b, c)) : Nat}Addition is associative: (a + b) + c = a + (b + c).
law add_left_comm provedsource · line 85 · raw
@a:Nat -> @b:Nat -> @-c:Nat -> {Nat.add(a, Nat.add(b, c)) == Nat.add(b, Nat.add(a, c)) : Nat}Left commutativity of addition: a + (b + c) = b + (a + c).
law add_right_comm provedsource · line 102 · raw
@a:Nat -> @b:Nat -> @c:Nat -> {Nat.add(Nat.add(a, b), c) == Nat.add(Nat.add(a, c), b) : Nat}Right commutativity of addition: (a + b) + c = (a + c) + b.
law add_add_add_comm provedsource · line 117 · raw
@a:Nat -> @b:Nat -> @c:Nat -> @-d:Nat -> {Nat.add(Nat.add(a, b), Nat.add(c, d)) == Nat.add(Nat.add(a, c), Nat.add(b, d)) : Nat}Four-way regrouping of a sum: (a + b) + (c + d) = (a + c) + (b + d).
law succ_inj provedsource · line 140 · raw
@-a:Nat -> @-b:Nat -> @e:{1n+a == 1n+b : Nat} -> {a == b : Nat}The successor function is injective: a + 1 = b + 1 implies a = b.
law zero_ne_succ provedsource · line 155 · raw
@-n:Nat -> @_:{0n == 1n+n : Nat} -> EmptyZero is not a successor.
law succ_ne_zero provedsource · line 167 · raw
@-n:Nat -> @_:{1n+n == 0n : Nat} -> EmptyA successor is not zero.
law add_left_cancel provedsource · line 175 · raw
@a:Nat -> @-b:Nat -> @-c:Nat -> @e:{Nat.add(a, b) == Nat.add(a, c) : Nat} -> {b == c : Nat}Addition cancels on the left: a + b = a + c implies b = c.
law add_right_cancel provedsource · line 190 · raw
@a:Nat -> @b:Nat -> @c:Nat -> @e:{Nat.add(a, b) == Nat.add(c, b) : Nat} -> {a == c : Nat}Addition cancels on the right: a + b = c + b implies a = c.
law mul_zero provedsource · line 202 · raw
@x:Nat -> {Nat.mul(x, 0n) == 0n : Nat}Zero absorbs multiplication on the right: x * 0 = 0.
law zero_mul provedsource · line 214 · raw
@-x:Nat -> {Nat.mul(0n, x) == 0n : Nat}Zero absorbs multiplication on the left: 0 * x = 0.
law mul_one provedsource · line 222 · raw
@x:Nat -> {Nat.mul(x, 1n) == x : Nat}One is a right identity for multiplication: x * 1 = x.
law one_mul provedsource · line 235 · raw
@x:Nat -> {Nat.mul(1n, x) == x : Nat}One is a left identity for multiplication: 1 * x = x.
law mul_succ provedsource · line 243 · raw
@n:Nat -> @m:Nat -> {Nat.mul(n, 1n+m) == Nat.add(Nat.mul(n, m), n) : Nat}Multiplying by a successor on the right: n * (m + 1) = n * m + n.
law succ_mul provedsource · line 260 · raw
@n:Nat -> @m:Nat -> {Nat.mul(1n+n, m) == Nat.add(Nat.mul(n, m), m) : Nat}Multiplying by a successor on the left: (n + 1) * m = n * m + m.
law mul_comm provedsource · line 270 · raw
@n:Nat -> @m:Nat -> {Nat.mul(n, m) == Nat.mul(m, n) : Nat}Multiplication is commutative: n * m = m * n.
law add_mul provedsource · line 287 · raw
@a:Nat -> @-b:Nat -> @c:Nat -> {Nat.mul(Nat.add(a, b), c) == Nat.add(Nat.mul(a, c), Nat.mul(b, c)) : Nat}Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c.
law mul_add provedsource · line 304 · raw
@a:Nat -> @b:Nat -> @c:Nat -> {Nat.mul(a, Nat.add(b, c)) == Nat.add(Nat.mul(a, b), Nat.mul(a, c)) : Nat}Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
law mul_assoc provedsource · line 321 · raw
@a:Nat -> @b:Nat -> @c:Nat -> {Nat.mul(Nat.mul(a, b), c) == Nat.mul(a, Nat.mul(b, c)) : Nat}Multiplication is associative: (a * b) * c = a * (b * c).
law le_refl provedsource · line 358 · raw
@a:Nat -> le(a, a)
Every natural is at most itself: a <= a.
law zero_le provedsource · line 370 · raw
@b:Nat -> le(0n, b)
Zero is at most every natural: 0 <= b.
law le_succ provedsource · line 382 · raw
@n:Nat -> le(n, 1n+n)
Every natural is at most its successor: n <= n + 1.
law le_add_right provedsource · line 394 · raw
@n:Nat -> @k:Nat -> le(n, Nat.add(n, k))
Adding on the right never decreases a natural: n <= n + k.
law le_trans provedsource · line 407 · raw
@a:Nat -> @b:Nat -> @c:Nat -> @ab:le(a, b) -> @bc:le(b, c) -> le(a, c)
The order is transitive: a <= b and b <= c imply a <= c.
law le_antisymm provedsource · line 429 · raw
@a:Nat -> @b:Nat -> @ab:le(a, b) -> @ba:le(b, a) -> {a == b : Nat}The order is antisymmetric: a <= b and b <= a imply a = b.
law le_total provedsource · line 449 · raw
@a:Nat -> @b:Nat -> Or(le(a, b), le(b, a))
The order is total: a <= b or b <= a.
law le_total_d provedsource · line 466 · raw
@a:Nat -> @b:Nat -> Either<&2, &2, le(a, b), le(b, a)>
The order is total, as a reusable sum: a <= b or b <= a.
law lt_irrefl provedsource · line 483 · raw
@a:Nat -> @_:lt(a, a) -> Empty
No natural is less than itself.
law lt_trans provedsource · line 495 · raw
@a:Nat -> @b:Nat -> @c:Nat -> @ab:lt(a, b) -> @bc:lt(b, c) -> lt(a, c)
The strict order is transitive: a < b and b < c imply a < c.
law le_of_lt provedsource · line 519 · raw
@a:Nat -> @b:Nat -> @h:lt(a, b) -> le(a, b)
A strict inequality implies the weak one: a < b implies a <= b.
law le_of_ge provedsource · line 537 · raw
@a:Nat -> @b:Nat -> @h:ge(a, b) -> le(b, a)
Flipping a >= b gives b <= a.
law ge_of_le provedsource · line 555 · raw
@a:Nat -> @b:Nat -> @h:le(b, a) -> ge(a, b)
Flipping b <= a gives a >= b.
law lt_of_gt provedsource · line 573 · raw
@a:Nat -> @b:Nat -> @h:gt(a, b) -> lt(b, a)
Flipping a > b gives b < a.
law gt_of_lt provedsource · line 591 · raw
@a:Nat -> @b:Nat -> @h:lt(b, a) -> gt(a, b)
Flipping b < a gives a > b.
law add_zero_sym provedsource · line 611 · raw
@x:Nat -> {x == Nat.add(x, 0n) : Nat}Zero is a right identity for addition: x + 0 = x, reversed to rewrite toward the simple side.
law zero_add_sym provedsource · line 619 · raw
@-x:Nat -> {x == Nat.add(0n, x) : Nat}Zero is a left identity for addition: 0 + x = x, reversed to rewrite toward the simple side.
law add_succ_sym provedsource · line 627 · raw
@n:Nat -> @-m:Nat -> {1n+Nat.add(n, m) == Nat.add(n, 1n+m) : Nat}Adding a successor on the right: n + (m + 1) = (n + m) + 1, reversed to rewrite toward the simple side.
law succ_add_sym provedsource · line 636 · raw
@-n:Nat -> @-m:Nat -> {1n+Nat.add(n, m) == Nat.add(1n+n, m) : Nat}Adding a successor on the left: (n + 1) + m = (n + m) + 1, reversed to rewrite toward the simple side.
law add_comm_sym provedsource · line 645 · raw
@n:Nat -> @m:Nat -> {Nat.add(m, n) == Nat.add(n, m) : Nat}Addition is commutative: n + m = m + n, reversed to rewrite toward the simple side.
law add_assoc_sym provedsource · line 654 · raw
@a:Nat -> @-b:Nat -> @-c:Nat -> {Nat.add(a, Nat.add(b, c)) == Nat.add(Nat.add(a, b), c) : Nat}Addition is associative: (a + b) + c = a + (b + c), reversed to rewrite toward the simple side.
law add_left_comm_sym provedsource · line 664 · raw
@a:Nat -> @b:Nat -> @-c:Nat -> {Nat.add(b, Nat.add(a, c)) == Nat.add(a, Nat.add(b, c)) : Nat}Left commutativity of addition: a + (b + c) = b + (a + c), reversed to rewrite toward the simple side.
law add_right_comm_sym provedsource · line 674 · raw
@a:Nat -> @b:Nat -> @c:Nat -> {Nat.add(Nat.add(a, c), b) == Nat.add(Nat.add(a, b), c) : Nat}Right commutativity of addition: (a + b) + c = (a + c) + b, reversed to rewrite toward the simple side.
law add_add_add_comm_sym provedsource · line 684 · raw
@a:Nat -> @b:Nat -> @c:Nat -> @-d:Nat -> {Nat.add(Nat.add(a, c), Nat.add(b, d)) == Nat.add(Nat.add(a, b), Nat.add(c, d)) : Nat}Four-way regrouping of a sum: (a + b) + (c + d) = (a + c) + (b + d), reversed to rewrite toward the simple side.
law mul_zero_sym provedsource · line 695 · raw
@x:Nat -> {0n == Nat.mul(x, 0n) : Nat}Zero absorbs multiplication on the right: x * 0 = 0, reversed to rewrite toward the simple side.
law zero_mul_sym provedsource · line 703 · raw
@-x:Nat -> {0n == Nat.mul(0n, x) : Nat}Zero absorbs multiplication on the left: 0 * x = 0, reversed to rewrite toward the simple side.
law mul_one_sym provedsource · line 711 · raw
@x:Nat -> {x == Nat.mul(x, 1n) : Nat}One is a right identity for multiplication: x * 1 = x, reversed to rewrite toward the simple side.
law one_mul_sym provedsource · line 719 · raw
@x:Nat -> {x == Nat.mul(1n, x) : Nat}One is a left identity for multiplication: 1 * x = x, reversed to rewrite toward the simple side.
law mul_succ_sym provedsource · line 727 · raw
@n:Nat -> @m:Nat -> {Nat.add(Nat.mul(n, m), n) == Nat.mul(n, 1n+m) : Nat}Multiplying by a successor on the right: n * (m + 1) = n * m + n, reversed to rewrite toward the simple side.
law succ_mul_sym provedsource · line 736 · raw
@n:Nat -> @m:Nat -> {Nat.add(Nat.mul(n, m), m) == Nat.mul(1n+n, m) : Nat}Multiplying by a successor on the left: (n + 1) * m = n * m + m, reversed to rewrite toward the simple side.
law mul_comm_sym provedsource · line 745 · raw
@n:Nat -> @m:Nat -> {Nat.mul(m, n) == Nat.mul(n, m) : Nat}Multiplication is commutative: n * m = m * n, reversed to rewrite toward the simple side.
law add_mul_sym provedsource · line 754 · raw
@a:Nat -> @-b:Nat -> @c:Nat -> {Nat.add(Nat.mul(a, c), Nat.mul(b, c)) == Nat.mul(Nat.add(a, b), c) : Nat}Multiplication distributes over addition on the right: (a + b) * c = a * c + b * c, reversed to rewrite toward the simple side.
law mul_add_sym provedsource · line 764 · raw
@a:Nat -> @b:Nat -> @c:Nat -> {Nat.add(Nat.mul(a, b), Nat.mul(a, c)) == Nat.mul(a, Nat.add(b, c)) : Nat}Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c, reversed to rewrite toward the simple side.
law mul_assoc_sym provedsource · line 774 · raw
@a:Nat -> @b:Nat -> @c:Nat -> {Nat.mul(a, Nat.mul(b, c)) == Nat.mul(Nat.mul(a, b), c) : Nat}Multiplication is associative: (a * b) * c = a * (b * c), reversed to rewrite toward the simple side.
Definitions
def internal_pred source · line 132 · raw
@n:Nat -> Nat
def internal_zero_ne_succ source · line 150 · raw
@-n:Nat -> @e:{0n == 1n+n : Nat} -> Empty
def internal_succ_ne_zero source · line 162 · raw
@-n:Nat -> @e:{1n+n == 0n : Nat} -> Empty
def le source · line 338 · raw
@a:Nat -> @b:Nat -> Data
The order a <= b on naturals, as a reusable proposition.
def lt source · line 342 · raw
@a:Nat -> @b:Nat -> Data
The strict order a < b on naturals, as a reusable proposition.
def ge source · line 346 · raw
@a:Nat -> @b:Nat -> Data
The order a >= b on naturals, as a reusable proposition.
def gt source · line 350 · raw
@a:Nat -> @b:Nat -> Data
The strict order a > b on naturals, as a reusable proposition.
def internal_false_ne_true source · line 353 · raw
@e:{False{} == True{} : Bool} -> Empty