~/bend-docscommunity

nat.bend checks

raw source on the hub · import bend-mathlib@0.3.0.0/nat.bend as MNat

bend-mathlib/nat.bend: Nat arithmetic (add, mul, sub, min, max, pow) and order (le, lt, ge, gt).

1 import
import Base

Laws

law add_zero provedsource · line 5 · raw

@x:Nat -> {Nat.add(x, 0n) == x : Nat}

Zero is a right identity for addition: x + 0 = x.

law zero_add provedsource · line 18 · raw

@-x:Nat -> {Nat.add(0n, x) == x : Nat}

Zero is a left identity for addition: 0 + x = x.

law add_succ provedsource · line 26 · 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 40 · 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 49 · 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 71 · 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 86 · 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 103 · 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 118 · 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 141 · 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 156 · raw

@-n:Nat -> @_:{0n == 1n+n : Nat} -> Empty

Zero is not a successor.

law succ_ne_zero provedsource · line 168 · raw

@-n:Nat -> @_:{1n+n == 0n : Nat} -> Empty

A successor is not zero.

law add_left_cancel provedsource · line 176 · 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 191 · 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 203 · raw

@x:Nat -> {Nat.mul(x, 0n) == 0n : Nat}

Zero absorbs multiplication on the right: x * 0 = 0.

law zero_mul provedsource · line 215 · raw

@-x:Nat -> {Nat.mul(0n, x) == 0n : Nat}

Zero absorbs multiplication on the left: 0 * x = 0.

law mul_one provedsource · line 223 · raw

@x:Nat -> {Nat.mul(x, 1n) == x : Nat}

One is a right identity for multiplication: x * 1 = x.

law one_mul provedsource · line 236 · raw

@x:Nat -> {Nat.mul(1n, x) == x : Nat}

One is a left identity for multiplication: 1 * x = x.

law mul_succ provedsource · line 244 · 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 261 · 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 271 · 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 288 · 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 305 · 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 322 · 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 359 · raw

@a:Nat -> le(a, a)

Every natural is at most itself: a <= a.

law zero_le provedsource · line 371 · raw

@b:Nat -> le(0n, b)

Zero is at most every natural: 0 <= b.

law le_succ provedsource · line 383 · raw

@n:Nat -> le(n, 1n+n)

Every natural is at most its successor: n <= n + 1.

law le_add_right provedsource · line 395 · 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 408 · 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 430 · 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 450 · 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 467 · 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 484 · raw

@a:Nat -> @_:lt(a, a) -> Empty

No natural is less than itself.

law lt_trans provedsource · line 496 · 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 520 · 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 538 · raw

@a:Nat -> @b:Nat -> @h:ge(a, b) -> le(b, a)

Flipping a >= b gives b <= a.

law ge_of_le provedsource · line 556 · raw

@a:Nat -> @b:Nat -> @h:le(b, a) -> ge(a, b)

Flipping b <= a gives a >= b.

law lt_of_gt provedsource · line 574 · raw

@a:Nat -> @b:Nat -> @h:gt(a, b) -> lt(b, a)

Flipping a > b gives b < a.

law gt_of_lt provedsource · line 592 · raw

@a:Nat -> @b:Nat -> @h:lt(b, a) -> gt(a, b)

Flipping b < a gives a > b.

law sub_zero provedsource · line 610 · raw

@n:Nat -> {Nat.sub(n, 0n) == n : Nat}

Subtracting zero changes nothing: n - 0 = n.

law zero_sub provedsource · line 622 · raw

@n:Nat -> {Nat.sub(0n, n) == 0n : Nat}

Truncated subtraction from zero is zero: 0 - n = 0.

law sub_self provedsource · line 634 · raw

@n:Nat -> {Nat.sub(n, n) == 0n : Nat}

A natural minus itself is zero: n - n = 0.

law succ_sub_succ provedsource · line 646 · raw

@-n:Nat -> @-m:Nat -> {Nat.sub(1n+n, 1n+m) == Nat.sub(n, m) : Nat}

Subtracting successors: (n + 1) - (m + 1) = n - m.

law add_sub_cancel provedsource · line 655 · raw

@n:Nat -> @m:Nat -> {Nat.sub(Nat.add(n, m), m) == n : Nat}

Adding then subtracting m cancels: (n + m) - m = n.

law add_sub_cancel_left provedsource · line 672 · raw

@n:Nat -> @m:Nat -> {Nat.sub(Nat.add(n, m), n) == m : Nat}

Adding then subtracting n cancels: (n + m) - n = m.

law sub_add_cancel provedsource · line 685 · raw

@n:Nat -> @m:Nat -> @h:le(m, n) -> {Nat.add(Nat.sub(n, m), m) == n : Nat}

If m <= n, subtracting and adding m back gives n: (n - m) + m = n.

law sub_sub provedsource · line 706 · raw

@n:Nat -> @m:Nat -> @k:Nat -> {Nat.sub(Nat.sub(n, m), k) == Nat.sub(n, Nat.add(m, k)) : Nat}

Subtracting twice is subtracting the sum: (n - m) - k = n - (m + k).

law sub_le provedsource · line 724 · raw

@n:Nat -> @m:Nat -> le(Nat.sub(n, m), n)

Truncated subtraction never increases: n - m <= n.

law min_comm provedsource · line 741 · raw

@a:Nat -> @b:Nat -> {Nat.min(a, b) == Nat.min(b, a) : Nat}

Minimum is commutative.

law max_comm provedsource · line 759 · raw

@a:Nat -> @b:Nat -> {Nat.max(a, b) == Nat.max(b, a) : Nat}

Maximum is commutative.

law min_self provedsource · line 777 · raw

@a:Nat -> {Nat.min(a, a) == a : Nat}

The minimum of a natural and itself is itself.

law max_self provedsource · line 790 · raw

@a:Nat -> {Nat.max(a, a) == a : Nat}

The maximum of a natural and itself is itself.

law min_zero provedsource · line 803 · raw

@a:Nat -> {Nat.min(a, 0n) == 0n : Nat}

The minimum with zero is zero: min(a, 0) = 0.

law zero_min provedsource · line 815 · raw

@a:Nat -> {Nat.min(0n, a) == 0n : Nat}

The minimum with zero is zero: min(0, a) = 0.

law max_zero provedsource · line 827 · raw

@a:Nat -> {Nat.max(a, 0n) == a : Nat}

Zero is an identity for maximum: max(a, 0) = a.

law zero_max provedsource · line 839 · raw

@a:Nat -> {Nat.max(0n, a) == a : Nat}

Zero is an identity for maximum: max(0, a) = a.

law min_assoc provedsource · line 851 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.min(Nat.min(a, b), c) == Nat.min(a, Nat.min(b, c)) : Nat}

Minimum is associative.

law max_assoc provedsource · line 870 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.max(Nat.max(a, b), c) == Nat.max(a, Nat.max(b, c)) : Nat}

Maximum is associative.

law min_add_max provedsource · line 889 · raw

@a:Nat -> @b:Nat -> {Nat.add(Nat.min(a, b), Nat.max(a, b)) == Nat.add(a, b) : Nat}

The minimum plus the maximum is the sum: min(a, b) + max(a, b) = a + b.

law min_le_left provedsource · line 910 · raw

@a:Nat -> @b:Nat -> le(Nat.min(a, b), a)

The minimum is at most its left argument.

law min_le_right provedsource · line 927 · raw

@a:Nat -> @b:Nat -> le(Nat.min(a, b), b)

The minimum is at most its right argument.

law le_max_left provedsource · line 944 · raw

@a:Nat -> @b:Nat -> le(a, Nat.max(a, b))

The left argument is at most the maximum.

law le_max_right provedsource · line 961 · raw

@a:Nat -> @b:Nat -> le(b, Nat.max(a, b))

The right argument is at most the maximum.

law pow_zero provedsource · line 978 · raw

@-a:Nat -> {Nat.pow(a, 0n) == 1n : Nat}

Any natural to the power zero is one.

law pow_succ provedsource · line 986 · raw

@-a:Nat -> @-n:Nat -> {Nat.pow(a, 1n+n) == Nat.mul(a, Nat.pow(a, n)) : Nat}

A power with a successor exponent: a^(n+1) = a * a^n.

law pow_one provedsource · line 995 · raw

@a:Nat -> {Nat.pow(a, 1n) == a : Nat}

Any natural to the power one is itself.

law one_pow provedsource · line 1003 · raw

@n:Nat -> {Nat.pow(1n, n) == 1n : Nat}

One to any power is one.

law pow_add provedsource · line 1016 · raw

@a:Nat -> @m:Nat -> @n:Nat -> {Nat.pow(a, Nat.add(m, n)) == Nat.mul(Nat.pow(a, m), Nat.pow(a, n)) : Nat}

Exponents add under multiplication: a^(m+n) = a^m * a^n.

law double_eq_add provedsource · line 1036 · raw

@n:Nat -> {Nat.double(n) == Nat.add(n, n) : Nat}

Doubling is adding a natural to itself.

law is_eq_refl provedsource · line 1050 · raw

@n:Nat -> {Nat.is_eq(n, n) == True{} : Bool}

Every natural tests equal to itself.

law is_eq_comm provedsource · line 1062 · raw

@a:Nat -> @b:Nat -> {Nat.is_eq(a, b) == Nat.is_eq(b, a) : Bool}

The equality test is symmetric.

law eq_of_is_eq provedsource · line 1080 · raw

@a:Nat -> @b:Nat -> @h:{Nat.is_eq(a, b) == True{} : Bool} -> {a == b : Nat}

If the equality test says true, the naturals are equal.

law is_ge_eq_is_le provedsource · line 1099 · raw

@a:Nat -> @b:Nat -> {Nat.is_ge(a, b) == Nat.is_le(b, a) : Bool}

A >= b tests the same as b <= a.

law is_gt_eq_is_lt provedsource · line 1117 · raw

@a:Nat -> @b:Nat -> {Nat.is_gt(a, b) == Nat.is_lt(b, a) : Bool}

A > b tests the same as b < a.

law is_lt_eq_succ_le provedsource · line 1135 · raw

@a:Nat -> @b:Nat -> {Nat.is_lt(a, b) == Nat.is_le(1n+a, b) : Bool}

A < b tests the same as a + 1 <= b.

law not_is_le provedsource · line 1156 · raw

@a:Nat -> @b:Nat -> {Bool.not(Nat.is_le(a, b)) == Nat.is_lt(b, a) : Bool}

Not (a <= b) tests the same as b < a.

law not_is_lt provedsource · line 1173 · raw

@a:Nat -> @b:Nat -> {Bool.not(Nat.is_lt(a, b)) == Nat.is_le(b, a) : Bool}

Not (a < b) tests the same as b <= a.

law lt_succ_self provedsource · line 1190 · raw

@n:Nat -> lt(n, 1n+n)

Every natural is less than its successor: n < n + 1.

law succ_le_succ provedsource · line 1202 · raw

@-a:Nat -> @-b:Nat -> @h:le(a, b) -> le(1n+a, 1n+b)

The successor preserves the order: a <= b implies a + 1 <= b + 1.

law le_of_succ_le_succ provedsource · line 1212 · raw

@-a:Nat -> @-b:Nat -> @h:le(1n+a, 1n+b) -> le(a, b)

The order of successors is the order of the naturals: a + 1 <= b + 1 implies a <= b.

law lt_of_lt_of_le provedsource · line 1222 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @ab:lt(a, b) -> @bc:le(b, c) -> lt(a, c)

A < b and b <= c imply a < c.

law lt_of_le_of_lt provedsource · line 1246 · raw

@a:Nat -> @b:Nat -> @c:Nat -> @ab:le(a, b) -> @bc:lt(b, c) -> lt(a, c)

A <= b and b < c imply a < c.

law add_le_add_left provedsource · line 1270 · raw

@-a:Nat -> @-b:Nat -> @k:Nat -> @h:le(a, b) -> le(Nat.add(k, a), Nat.add(k, b))

Adding on the left preserves the order: a <= b implies k + a <= k + b.

law le_zero_eq provedsource · line 1285 · raw

@n:Nat -> @h:le(n, 0n) -> {n == 0n : Nat}

The only natural at most zero is zero.

law lt_zero provedsource · line 1298 · raw

@n:Nat -> @_:lt(n, 0n) -> Empty

No natural is less than zero.

law add_zero_sym provedsource · line 1312 · 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 1320 · 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 1328 · 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 1337 · 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 1346 · 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 1355 · 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 1365 · 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 1375 · 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 1385 · 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 1396 · 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 1404 · 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 1412 · 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 1420 · 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 1428 · 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 1437 · 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 1446 · 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 1455 · 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 1465 · 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 1475 · 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.

law sub_zero_sym provedsource · line 1485 · raw

@n:Nat -> {n == Nat.sub(n, 0n) : Nat}

Subtracting zero changes nothing: n - 0 = n, reversed to rewrite toward the simple side.

law zero_sub_sym provedsource · line 1493 · raw

@n:Nat -> {0n == Nat.sub(0n, n) : Nat}

Truncated subtraction from zero is zero: 0 - n = 0, reversed to rewrite toward the simple side.

law sub_self_sym provedsource · line 1501 · raw

@n:Nat -> {0n == Nat.sub(n, n) : Nat}

A natural minus itself is zero: n - n = 0, reversed to rewrite toward the simple side.

law succ_sub_succ_sym provedsource · line 1509 · raw

@-n:Nat -> @-m:Nat -> {Nat.sub(n, m) == Nat.sub(1n+n, 1n+m) : Nat}

Subtracting successors: (n + 1) - (m + 1) = n - m, reversed to rewrite toward the simple side.

law add_sub_cancel_sym provedsource · line 1518 · raw

@n:Nat -> @m:Nat -> {n == Nat.sub(Nat.add(n, m), m) : Nat}

Adding then subtracting m cancels: (n + m) - m = n, reversed to rewrite toward the simple side.

law add_sub_cancel_left_sym provedsource · line 1527 · raw

@n:Nat -> @m:Nat -> {m == Nat.sub(Nat.add(n, m), n) : Nat}

Adding then subtracting n cancels: (n + m) - n = m, reversed to rewrite toward the simple side.

law sub_sub_sym provedsource · line 1536 · raw

@n:Nat -> @m:Nat -> @k:Nat -> {Nat.sub(n, Nat.add(m, k)) == Nat.sub(Nat.sub(n, m), k) : Nat}

Subtracting twice is subtracting the sum: (n - m) - k = n - (m + k), reversed to rewrite toward the simple side.

law min_comm_sym provedsource · line 1546 · raw

@a:Nat -> @b:Nat -> {Nat.min(b, a) == Nat.min(a, b) : Nat}

Minimum is commutative, reversed to rewrite toward the simple side.

law max_comm_sym provedsource · line 1555 · raw

@a:Nat -> @b:Nat -> {Nat.max(b, a) == Nat.max(a, b) : Nat}

Maximum is commutative, reversed to rewrite toward the simple side.

law min_self_sym provedsource · line 1564 · raw

@a:Nat -> {a == Nat.min(a, a) : Nat}

The minimum of a natural and itself is itself, reversed to rewrite toward the simple side.

law max_self_sym provedsource · line 1572 · raw

@a:Nat -> {a == Nat.max(a, a) : Nat}

The maximum of a natural and itself is itself, reversed to rewrite toward the simple side.

law min_zero_sym provedsource · line 1580 · raw

@a:Nat -> {0n == Nat.min(a, 0n) : Nat}

The minimum with zero is zero: min(a, 0) = 0, reversed to rewrite toward the simple side.

law zero_min_sym provedsource · line 1588 · raw

@a:Nat -> {0n == Nat.min(0n, a) : Nat}

The minimum with zero is zero: min(0, a) = 0, reversed to rewrite toward the simple side.

law max_zero_sym provedsource · line 1596 · raw

@a:Nat -> {a == Nat.max(a, 0n) : Nat}

Zero is an identity for maximum: max(a, 0) = a, reversed to rewrite toward the simple side.

law zero_max_sym provedsource · line 1604 · raw

@a:Nat -> {a == Nat.max(0n, a) : Nat}

Zero is an identity for maximum: max(0, a) = a, reversed to rewrite toward the simple side.

law min_assoc_sym provedsource · line 1612 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.min(a, Nat.min(b, c)) == Nat.min(Nat.min(a, b), c) : Nat}

Minimum is associative, reversed to rewrite toward the simple side.

law max_assoc_sym provedsource · line 1622 · raw

@a:Nat -> @b:Nat -> @c:Nat -> {Nat.max(a, Nat.max(b, c)) == Nat.max(Nat.max(a, b), c) : Nat}

Maximum is associative, reversed to rewrite toward the simple side.

law min_add_max_sym provedsource · line 1632 · raw

@a:Nat -> @b:Nat -> {Nat.add(a, b) == Nat.add(Nat.min(a, b), Nat.max(a, b)) : Nat}

The minimum plus the maximum is the sum: min(a, b) + max(a, b) = a + b, reversed to rewrite toward the simple side.

law pow_zero_sym provedsource · line 1641 · raw

@-a:Nat -> {1n == Nat.pow(a, 0n) : Nat}

Any natural to the power zero is one, reversed to rewrite toward the simple side.

law pow_succ_sym provedsource · line 1649 · raw

@-a:Nat -> @-n:Nat -> {Nat.mul(a, Nat.pow(a, n)) == Nat.pow(a, 1n+n) : Nat}

A power with a successor exponent: a^(n+1) = a * a^n, reversed to rewrite toward the simple side.

law pow_one_sym provedsource · line 1658 · raw

@a:Nat -> {a == Nat.pow(a, 1n) : Nat}

Any natural to the power one is itself, reversed to rewrite toward the simple side.

law one_pow_sym provedsource · line 1666 · raw

@n:Nat -> {1n == Nat.pow(1n, n) : Nat}

One to any power is one, reversed to rewrite toward the simple side.

law pow_add_sym provedsource · line 1674 · raw

@a:Nat -> @m:Nat -> @n:Nat -> {Nat.mul(Nat.pow(a, m), Nat.pow(a, n)) == Nat.pow(a, Nat.add(m, n)) : Nat}

Exponents add under multiplication: a^(m+n) = a^m * a^n, reversed to rewrite toward the simple side.

law double_eq_add_sym provedsource · line 1684 · raw

@n:Nat -> {Nat.add(n, n) == Nat.double(n) : Nat}

Doubling is adding a natural to itself, reversed to rewrite toward the simple side.

law is_eq_refl_sym provedsource · line 1692 · raw

@n:Nat -> {True{} == Nat.is_eq(n, n) : Bool}

Every natural tests equal to itself, reversed to rewrite toward the simple side.

law is_eq_comm_sym provedsource · line 1700 · raw

@a:Nat -> @b:Nat -> {Nat.is_eq(b, a) == Nat.is_eq(a, b) : Bool}

The equality test is symmetric, reversed to rewrite toward the simple side.

law is_ge_eq_is_le_sym provedsource · line 1709 · raw

@a:Nat -> @b:Nat -> {Nat.is_le(b, a) == Nat.is_ge(a, b) : Bool}

A >= b tests the same as b <= a, reversed to rewrite toward the simple side.

law is_gt_eq_is_lt_sym provedsource · line 1718 · raw

@a:Nat -> @b:Nat -> {Nat.is_lt(b, a) == Nat.is_gt(a, b) : Bool}

A > b tests the same as b < a, reversed to rewrite toward the simple side.

law is_lt_eq_succ_le_sym provedsource · line 1727 · raw

@a:Nat -> @b:Nat -> {Nat.is_le(1n+a, b) == Nat.is_lt(a, b) : Bool}

A < b tests the same as a + 1 <= b, reversed to rewrite toward the simple side.

law not_is_le_sym provedsource · line 1736 · raw

@a:Nat -> @b:Nat -> {Nat.is_lt(b, a) == Bool.not(Nat.is_le(a, b)) : Bool}

Not (a <= b) tests the same as b < a, reversed to rewrite toward the simple side.

law not_is_lt_sym provedsource · line 1745 · raw

@a:Nat -> @b:Nat -> {Nat.is_le(b, a) == Bool.not(Nat.is_lt(a, b)) : Bool}

Not (a < b) tests the same as b <= a, reversed to rewrite toward the simple side.

Definitions

def internal_pred source · line 133 · raw

@n:Nat -> Nat

def internal_zero_ne_succ source · line 151 · raw

@-n:Nat -> @e:{0n == 1n+n : Nat} -> Empty

def internal_succ_ne_zero source · line 163 · raw

@-n:Nat -> @e:{1n+n == 0n : Nat} -> Empty

def le source · line 339 · raw

@a:Nat -> @b:Nat -> Data

The order a <= b on naturals, as a reusable proposition.

def lt source · line 343 · raw

@a:Nat -> @b:Nat -> Data

The strict order a < b on naturals, as a reusable proposition.

def ge source · line 347 · raw

@a:Nat -> @b:Nat -> Data

The order a >= b on naturals, as a reusable proposition.

def gt source · line 351 · raw

@a:Nat -> @b:Nat -> Data

The strict order a > b on naturals, as a reusable proposition.

def internal_false_ne_true source · line 354 · raw

@e:{False{} == True{} : Bool} -> Empty